Many-to-many location-routing problem with multiple paths, heterogeneous vehicles and time windows

Objective: This research introduces a new many-to-many location-routing problem (MMLRP) for designing parcel delivery networks in large, sparse countries with incomplete road infrastructure. This study aims to minimizes total system costs—including hub establishment, vehicle operation, and delivery penalties—by simultaneously optimizing hub locations, city-to-hub allocations, multi-path routes, and the number of heterogeneous vehicles. This work addresses a gap in logistics literature by integrating real-world complexities like distinct vehicle types, service time windows (24-72 hours), and multiple, non-touring collection and delivery paths originating from each hub. The goal is to provide a robust strategic planning tool for delivery companies facing the challenges of restricted road networks and vast distances between cities.

Methods: To address this NP-hard problem, a mixed-integer programming (MIP) model was formulated, which was linearized from an initial mixed-integer non-linear program (MINLP) to ensure computational tractability. For large-scale instances where exact methods are infeasible, a new two-stage hybrid metaheuristic was designed. Stage one uses an Artificial Bee Colony (ABC) algorithm to effectively explore the solution space, determining promising hub locations and initial node allocations. Stage two employs a Simulated Annealing (SA) algorithm, enhanced with local search methods, to exploit the solutions from the first stage and intensively refine the routing and allocation details. The methodology was validated against the CPLEX solver for optimality on small instances and a published SA-based method for performance on larger ones, using 75 generated test instances and two real-world Iranian case studies with data from a parcel delivery company.

Results: The proposed hybrid method proved highly efficient, finding optimal or near-optimal solutions on small instances significantly faster than the CPLEX solver. On larger problems, it consistently outperformed a standard SA-based method, improving solution quality by an average of 4% for 50-node instances while reducing computation time. The two-stage structure was critical to its success; the second (SA) stage improved the final solution cost by an average of 1.6% across all tests. This cost saving was achieved by intelligently restructuring the network, which included reducing the number of routes by an average of 11% and increasing the share of 24-hour transportations by 4%, thereby enhancing service levels without raising costs. The Iranian case studies confirmed the model's practical applicability by identifying stable and optimal hub configurations for different network sizes and operational policies.

Conclusion: This research successfully developed a realistic MMLRP variant and a robust hybrid algorithm to solve it, offering a valuable tool for strategic, long-term investment decisions in the parcel delivery industry. The model provides managers with a method for making integrated decisions that minimize costs in large, sparse regions. A key finding is that strategic hub locations can remain stable during network expansion if the line-haul distance policy is maintained. This allows growth to focus on tactical routing adjustments rather than disruptive and costly new infrastructure investments. In the Iranian case study, the model suggests a four-hub network with a 680 km line-haul limit is a more robust long-term strategy to accommodate future nationwide coverage, compared to a three-hub network with a 510 km limit optimized only for current major cities.