Last Truck Scheduling for Middle-mile Next-day Delivery Coverage

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 last truck schedule. We formulate a novel optimization problem which decides the departure of the last truck at each (potential) network connection in order to maximize the number of customer orders that are served with next-day promise. We show that the respective next-day delivery optimization is a combinatorial problem that is NP-hard to approximate within $(1-1/e)opt\approx 0.632opt$, 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 worst-case optimality gap guarantees, and evaluated in realistic datasets and network scenarios were found to achieve even near-optimal results.