  We consider an e-commerce retailer operating a supply chain that consists of
middle- and last-mile transportation, and study its ability to deliver products
stored in warehouses within a day from customer's order time. Successful
next-day delivery requires inventory availability and timely truck schedules in
the middle-mile and in this paper we assume a fixed inventory position and
focus on optimizing the middle-mile. We formulate a novel optimization problem
which decides the departure of the last middle-mile truck at each (potential)
network connection in order to maximize the number of next-day deliveries. We
show that the respective \emph{next-day delivery optimization} is a
combinatorial problem that is $NP$-hard to approximate within
$(1-1/e)\cdot\texttt{opt}\approx 0.632\cdot\texttt{opt}$, hence every retailer
that offers one-day deliveries has to deal with this complexity barrier. We
study three variants of the problem motivated by operational constraints that
different retailers encounter, and propose solutions schemes tailored to each
problem's properties. To that end, we rely on greedy submodular maximization,
pipage rounding techniques, and Lagrangian heuristics. The algorithms are
scalable, offer optimality gap guarantees, and evaluated in realistic datasets
and network scenarios were found to achieve near-optimal results.
