An Exact Approach to the Star Hub Location-Routing Problem with Time Windows for Intra-City Express System Design

With the rapid growth of e-commerce, intra-city express delivery has expanded rapidly, leading to various social issues, such as traffic congestion and air pollution. To address these problems, we focus on designing a multimodal intra-city express system in which parcels are collected from clients via local tours operated by a fleet of identical trucks, temporarily stored in satellite hubs, and then sent to the center hub via underground railway for further sorting and distribution. The problem involves capacitated hub location, client-to-hub allocation, and vehicle routing. Several practical constraints are considered in the routing aspect, including vehicle capacity, time windows, and maximum path length. With these practical considerations, we first formulate a star hub location-routing problem with time windows (SHLRPTW). Second, we use a branch-and-price-and-Benders-cut (BPBC) algorithm to solve it, which combines the Benders decomposition framework and branch-and-price-and-cut (BPC) framework. The BPBC algorithm is tailored, and several acceleration techniques are applied. Third, numerical experiments show that the proposed BPBC algorithm solves more instances and achieves smaller optimality gaps (0.75%) than CPLEX (19.55%) and the pure BPC algorithm (0.83%). The computational times are also critically reduced, with average speed-ups of 74.01 and 5.97, respectively. Furthermore, sensitivity analysis indicates that the BPBC algorithm performs much better than the BPC algorithm when the unit backbone transportation cost is high. Finally, case studies show the usefulness of the proposed model and algorithm.