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

Document Type : Research Paper

Author

Assistant prof., Department of Industrial Management, Faculty of Administrative Sciences and Economics, Arak University, Arak, Iran.

10.22059/imj.2025.402989.1008266

Abstract

Objective: This study introduces a location-routing model tailored for parcel delivery in large, sparsely populated regions with limited infrastructure. It aims to minimize system costs by optimizing hub placement, city-to-hub assignments, routing paths, and fleet composition. The model accounts for real-world complexities such as diverse vehicle types, flexible delivery time windows, and multiple pickup/delivery paths, offering a strategic planning tool for logistics operations in challenging environments. 
Methodology: To solve this NP-hard problem, the researchers reformulated a mixed-integer nonlinear program (MINLP) into a more computationally efficient mixed-integer programming (MIP) model. For larger instances, they developed a two-stage hybrid metaheuristic: the first stage uses an Artificial Bee Colony (ABC) algorithm to explore hub locations and initial allocations, while the second stage applies Simulated Annealing (SA) with local search to optimize routing and assignments. Validation was performed using CPLEX for small instances and benchmarked against a published SA-based method across 75 test scenarios and two real-world case studies from an Iranian parcel delivery company.
Results: The hybrid method achieved optimal or near-optimal solutions faster than CPLEX for minor problems and outperformed the SA benchmark for larger ones, improving solution quality by 4% and reducing routes by 11%. The model also increased 24-hour deliveries by 4% without raising costs. The SA phase alone contributed a 1.6% cost reduction by restructuring the network. Case studies confirmed the model’s practical value, consistently identifying robust hub configurations across diverse network scales and operational strategies.
Conclusion: This study presents a strategic planning tool for parcel delivery in challenging geographic and infrastructural conditions. It enables logistics managers to minimize operational costs while maintaining stable hub configurations during network expansion. A case study in Iran highlights its long-term value: a four-hub network with a 680 km line-haul limit offers superior nationwide coverage compared to a three-hub setup with a 510 km limit focused on major cities.

Keywords

References

Abbasi, M., Mokhtari, N., Shahvar, H., & Mahmoudi, A. (2019). Application of variable neighborhood search for solving large-scale many-to-many hub location routing problems. Journal of Advances in Management Research, 16(5), 683–697.
Aloullal, A., Saldanha-da-Gama, F., & Todosijević, R. (2023). Multi-period single-allocation hub location-routing: Models and heuristic solutions. European Journal of Operational Research, 310(1), 53–70.
Andaryan, A. Z., Mousighichi, K., & Ghaffarinasab, N. (2024). A heuristic approach to the stochastic capacitated single allocation hub location problem with Bernoulli demands. European Journal of Operational Research, 312(3), 954–968.
Athamneh, R. A., Tanash, M., Hani, D. B., Rawshdeh, M., Alawin, A., & Albataineh, Z. (2023). Variable Neighborhood Search Algorithm for the Single Assignment Incomplete Hub Location Problem with Modular Capacities and Direct Connections. Operations Research Perspectives, 11, 100286.
Bahrami, F., Safari, H., Tavakkoli-Moghaddam, R., & Modarres Yazdi, M. (2016). On modeling door-to-door parcel delivery services in Iran. Interdisciplinary Journal of Management Studies, 9(4), 883–906.
Bahrami, F., Safari, H., Tavakkoli-Moghaddam, R., & Modarres Yazdi, M. (2017). Road hub location-routing issue in a sparse and distant area. Industrial Management Journal, 9(1), 59–78.
Basirati, M., Akbari Jokar, M. R., & Hassannayebi, E. (2020). Bi-objective optimization approaches to many-to-many hub location routing with distance balancing and hard time window. Neural Computing and Applications, 32(17), 13267–13288.
Bement, T. R. (1989). Taguchi techniques for quality engineering. In: Taylor & Francis.
Brimberg, J., Todosijević, R., Urošević, D., & Mladenović, N. (2021). Efficient flow models for the uncapacitated multiple allocation p-hub median problem on non-triangular networks. Computers & Industrial Engineering, 162, 107723.
Bütün, C., Petrovic, S., & Muyldermans, L. (2021). The capacitated directed cycle hub location and routing problem under congestion. European Journal of Operational Research, 292(2), 714-734.
Černý, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of optimization theory and applications, 45(1), 41-51.
Čupić, A., & Teodorović, D. (2014). A multi‐objective approach to the parcel express service delivery problem. Journal of Advanced Transportation, 48(7), 701-720.
Davari, S., Zarandi, M. F., & Turksen, I. (2013). The incomplete hub-covering location problem considering imprecise location of demands. Scientia Iranica, 20(3), 983-991.
De Camargo, R. S., de Miranda Jr, G., O’Kelly, M. E., & Campbell, J. F. (2017). Formulations and decomposition methods for the incomplete hub location network design problem with and without hop-constraints. Applied Mathematical Modelling, 51, 274–301.
De Sá, E. M., Morabito, R., & de Camargo, R. S. (2018). Benders decomposition applied to a robust multiple allocation incomplete hub location problem. Computers & Operations Research, 89, 31–50.
Estrada-Romeu, M., & Robusté, F. (2015). Stopover and hub-and-spoke shipment strategies in less-than-truckload carriers. Transportation Research Part E: Logistics and Transportation Review, 76, 108–121.
Fallah-Tafti, M., Honarvar, M., Tavakkoli-Moghaddam, R., & Sadegheih, A. (2022). Mathematical modeling of a bi-objective hub location-routing problem for rapid transit networks. RAIRO-Operations Research, 56(5), 3733–3763.
Ghodratnama, A., Tavakkoli-Moghaddam, R., & Azaron, A. (2013). A fuzzy possibilistic bi-objective hub covering problem considering production facilities, time horizons, and transporter vehicles. The International Journal of Advanced Manufacturing Technology, 66(1), 187-206.
Gianpaolo, G., Gilbert, L., & Roberto, M. (2013). Introduction to Logistics Systems Management. In: Wiley.
Gu, W., Archetti, C., Cattaruzza, D., Ogier, M., Semet, F., & Speranza, M. G. (2024). Vehicle routing problems with multiple commodities: A survey. European Journal of Operational Research, 317(1), 1–15.
Guo, F., Wang, Z., Huang, Z., & Ma, X. (2024). Robust optimization of microhub network and mixed service strategy for a multidepot location-routing problem. Computers & Industrial Engineering, 190, 110070.
Kabadurmus, O., & Erdogan, M. S. (2023). A green vehicle routing problem with multi-depot, multi-tour, heterogeneous fleet and split deliveries: a mathematical model and heuristic approach. Journal of Combinatorial Optimization, 45(3), 89.
Karaboga, D., & Akay, B. (2009). A comparative study of artificial bee colony algorithm. Applied mathematics and computation, 214(1), 108–132.
Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477.
Kartal, Z., Hasgul, S., & Ernst, A. T. (2017). Single allocation p-hub median location and routing problem with simultaneous pick-up and delivery. Transportation Research Part E: Logistics and Transportation Review, 108, 141–159.
Khoshgehbari, F., & Al-e, S. M. J. M. (2023). Ambulance location routing problem considering all sources of uncertainty: Progressive estimating algorithm. Computers & Operations Research, 160, 106400.
Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Lüer-Villagra, A., Eiselt, H. A., & Marianov, V. (2019). A single allocation p-hub median problem with general piecewise-linear costs in arcs. Computers & Industrial Engineering, 128, 477–491.
Nagy, G., & Salhi, S. (1998). The many-to-many location-routing problem. Top, 6(2), 261-275.
Nielsen, P., Dahanayaka, M., Perera, H. N., Thibbotuwawa, A., & Kilic, D. K. (2024). A systematic review of vehicle routing problems and models in multi-echelon distribution networks. Supply Chain Analytics, 7, 100072.
O'Kelly, M. E. (1986). The location of interacting hub facilities. Transportation science, 20(2), 92–106.
O'Kelly, M. E., Campbell, J. F., de Camargo, R. S., & de Miranda Jr, G. (2015). Multiple allocation hub location model with fixed arc costs. Geographical Analysis, 47(1), 73–96.
O’Kelly, M., Sun, X., & Wandelt, S. (2025). Hub location problems: A meta review and ten disruptive research challenges. Journal of the Air Transport Research Society, 100073.
Oudani, M., Aouam, T., & Ghogho, M. (2023). The p-hub centre routing problem with emissions budget: Formulation and solution procedure. Computers & Operations Research, 154, 106211.
Öztürk, C., Tuzkaya, G., & Bulkan, S. (2021). Centrality based solution approaches for median-type incomplete hub location problems. Computers & Industrial Engineering, 156, 107275.
Pourmohammadi, P., Tavakkoli-Moghaddam, R., Rahimi, Y., & Triki, C. (2023). Solving a hub location-routing problem with a queue system under social responsibility by a fuzzy meta-heuristic algorithm. Annals of Operations Research, 324(1), 1099–1128.
Ratli, M., Urošević, D., El Cadi, A. A., Brimberg, J., Mladenović, N., & Todosijević, R. (2022). An efficient heuristic for a hub location routing problem. Optimization Letters, 16(1), 281-300.
Rieck, J., Ehrenberg, C., & Zimmermann, J. (2014). Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery. European Journal of Operational Research, 236(3), 863–878.
Shang, C., Ma, L., & Liu, Y. (2023). Green location routing problem with flexible multi-compartment for source-separated waste: A Q-learning and multi-strategy-based hyper-heuristic algorithm. Engineering Applications of Artificial Intelligence, 121, 105954.
Sharma, A., Jakhar, S. K., Vlachos, I., & Kumar, S. (2025). Advances in hub location problems: a literature review and research agenda. International Journal of Productivity and Performance Management, 74(1), 24–55.
Shi, Y., Lin, Y., Wang, S., Wen, H., Lim, M. K., & Li, Y. (2023). A simultaneous facility location and vehicle routing problem with recyclable express packaging consideration for sustainable city logistics. Sustainable Cities and Society, 98, 104857.
Vahdani, B., Tavakkoli-Moghaddam, R., Zandieh, M., & Razmi, J. (2012). Vehicle routing scheduling using an enhanced hybrid optimization approach. Journal of Intelligent Manufacturing, 23(3), 759-774.
Wandelt, S., Wang, S., & Sun, X. (2025). A literature review on hub location-routing models and their solution techniques. Computers & Operations Research, 173, 106861.
Wang, C., Liu, Y., & Yang, G. (2023). Adaptive distributionally robust hub location and routing problem with a third-party logistics strategy. Socio-Economic Planning Sciences, 87, 101563.
Wang, S., Sun, W., Baldacci, R., & Elomri, A. (2025). Exact solution of location–routing problems with heterogeneous fleet and weight-based carbon emissions. Transportation Research Part E: Logistics and Transportation Review, 193, 103862.
Wang, X., & Li, X. (2017). Carbon reduction in the location routing problem with heterogeneous fleet, simultaneous pickup-delivery, and time windows. Procedia Computer Science, 112, 1131-1140.
Wasner, M., & Zäpfel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90(3), 403–419.
Wu, Y., Qureshi, A. G., & Yamada, T. (2022). Adaptive large neighborhood decomposition search algorithm for multi-allocation hub location routing problem. European Journal of Operational Research, 302(3), 1113–1127.
Yaman, H., Kara, B. Y., & Tansel, B. Ç. (2007). The latest arrival hub location problem for cargo delivery systems with stopovers. Transportation Research Part B: Methodological, 41(8), 906-919.
Zhao, Q., Wang, W., & De Souza, R. (2018). A heterogeneous fleet two-echelon capacitated location-routing model for joint delivery arising in city logistics. International Journal of Production Research, 56(15), 5062–5080.
Zhao, Z., Lee, C. K., Tsang, Y. P., & Xu, X. (2025). A heuristic-attention method for location-routing problems with shared pick-up stations in green last-mile delivery. Transportation Research Part C: Emerging Technologies, 172, 105031.
 
 
Industrial Management Journal
Volume 17, Issue 4
2025
Pages 100-139

Files

Share

How to cite

Statistics