E-Commerce Middle-Mile Network Design with Delivery Speed Choices and Service Level Constraints

The increasing demand for expedited e-commerce deliveries, with delivery times of one to three days, highlights the importance of optimizing the middle-mile network. Most retailers store a considerable portion of their inventory at the regional distribution centers (RDCs) outside urban areas, from where it is moved to the customer zones equipped with last-mile distribution facilities as required. Thus, RDC locations become critical in middle-mile operations, directly impacting the transit times to customer zones and, ultimately, the delivery times in the last mile. This paper presents a middle-mile network design problem arising in the context of e-commerce companies in the presence of customers with different delivery time preferences. Specifically, it allows RDCs to satisfy demands from customer zones using delivery times longer than requested, albeit with penalties, if that helps reduce cost without violating the service level requirements of fulfilling at least a given threshold of the demands within the requested delivery times. The problem is formulated as a mixed-integer linear program, for which an exact Lagrangian relaxation-based branch-and-bound algorithm is proposed. Several enhancements to the algorithm are provided, including an efficient Lagrangian heuristic for the primal-bound, a Benders decomposition framework to solve one of the Lagrangian subproblems efficiently, an analytical approach for obtaining Benders optimality cuts, and a partial analytical characterization of Pareto-optimal Benders cuts. With these enhancements, our final algorithm substantially outperforms the state-of-the-art commercial solver, as highlighted by our computational experiments on an extensive set of 220 instances with up to 80 potential RDC locations and 1,000 customer zones. Our best algorithm solves 204 of the 220 instances to 0.50% duality gap compared with only 108 that CPLEX could solve to the same gap within an allowed 10-hour CPU time limit. Furthermore, it achieves an average time savings of 63.24% compared with CPLEX across all the instances. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0930 .