Optimizing Medical Logistics Networks: A Hybrid Bat-ALNS Approach for Multi-Depot VRPTW and Simultaneous Pickup-Delivery

Anass Taha; Said  Elatar; Salim El Bazzi Mohamed; Abdelouahed  Ait Ider; Lotfi  Najdi

doi:10.35882/jeeemi.v7i4.1054

Anass Taha Laboratory of System Computer Engineering, Mathematics and Applications, Ibn Zohr university, Agadir, Morocco
Said Elatar Laboratory of Research in Optimization, Emerging Systems, Networks, and Imaging, Chouaib Doukkali university, Faculty of Science, El Jadida, Morocco https://orcid.org/0009-0009-3505-3384
Salim El Bazzi Mohamed
Abdelouahed Ait Ider Laboratory of Image and Pattern Recognition, Intelligent and Communicating Systems, Ibn Zohr university, Agadir, Morocco https://orcid.org/0000-0003-0201-9672
Lotfi Najdi Laboratory of System Computer Engineering, Mathematics and Applications, Ibn Zohr university, Agadir, Morocco https://orcid.org/0009-0000-5407-5612

DOI: https://doi.org/10.35882/jeeemi.v7i4.1054

Keywords: Pharmaceutical Distribution, Vehicle Routing Problem, Hybrid Metaheuristic, Bat Algorithm, Adaptive Large Neighborhood Search

Abstract

This paper tackles the multi-depot heterogeneous-fleet vehicle-routing problem with time windows and simultaneous pickup and delivery (MDHF-VRPTW-SPD), a variant that mirrors he growing complexity of modern healthcare logistics. The primary purpose of this study is to model this complex routing problem as a mixed-integer linear program and to develop and validate a novel hybrid metaheuristic, B-ALNS, capable of delivering robust, high-quality solutions. The proposed B-ALNS combines a discrete Bat Algorithm with Adaptive Large Neighborhood Search, where the bat component supplies frequency-guided diversification, while ALNS adaptively selects destroy and repair operators and exploits elite memory for focused intensification. Extensive experiments were conducted on twenty new benchmark instances (ranging from 48 to 288 customers), derived from Cordeau’s data and enriched with pickups and a four-class fleet. Results show that B-ALNS attains a mean cost 1.15 % lower than a standalone discrete BA and 2.78 % lower than a simple LNS, achieving the best average cost on 17/20 instances and the global best solution in 85% of test instances. Statistical tests further confirm the superiority of the hybrid B-ALNS, a Friedman test and Wilcoxon signed-rank comparisons give p-value of 0.0013 versus BA and p-value of 0.0002 versus LNS, respectively. Although B-ALNS trades speed for quality (182.65 seconds average runtime versus 54.04 seconds for BA and 11.61 seconds for LNS), it produces markedly more robust solutions, with the lowest cost standard deviation and consistently balanced routes. These results demonstrate that the hybrid B-ALNS delivers statistically significant, high-quality solutions within tactical planning times, offering a practical decision-support tool for secure, cold-chain-compliant healthcare logistics

Downloads

Download data is not yet available.

References

G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Manage Sci, vol. 6, no. 1, pp. 80–91, 1959.

A. Taha, M. Hachimi, and A. Moudden, “Adapted bat algorithm for capacitated vehicle routing problem,” International Review on Computers and Software, vol. 10, no. 6, pp. 610–619, 2015.

B. Kallehauge, J. Larsen, O. B. G. Madsen, and M. M. Solomon, “Vehicle Routing Problem with Time Windows,” Column Generation, pp. 67–98, 2005.

J. Jiang, K. M. Ng, K. L. Poh, and K. M. Teo, “Vehicle routing problem with a heterogeneous fleet and time windows,” Expert Syst Appl, vol. 41, no. 8, pp. 3748–3760, Jun. 2014.

S. N. Parragh, K. F. Doerner, and R. F. Hartl, “A survey on pickup and delivery problems,” Journal fur Betriebswirtschaft, vol. 58, no. 1, pp. 21–51, 2008.

M. Polacek, R. F. Hartl, K. Doerner, and M. Reimann, “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows,” Journal of Heuristics, vol. 10, no. 6, pp. 613–627, Dec. 2004.

X. Yang, “A New Metaheuristic Bat-Inspired Algorithm,” Nicso 2010, pp. 65–74, 2010.

D. Pisinger and S. Ropke, “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science, vol. 40, no. August, pp. 455–472, 2006.

J. Wang, Y. Zhou, Y. Wang, J. Zhang, C. L. P. Chen, and Z. Zheng, “Multiobjective Vehicle Routing Problems with Simultaneous Delivery and Pickup and Time Windows: Formulation, Instances, and Algorithms,” IEEE Trans Cybern, vol. 46, no. 3, pp. 582–594, 2016.

E. Köse, A. Kokmazer, D. Danı¸sment Vural, G. Gül, G. Glu, and P. P. Pınar¸savlı, “Simultaneous pickup and delivery model suggestion for personnel transportation in COVID-19 pandemic conditions,” vol. 33, no. 4, 2023.

A. Kantasa-Ard, T. Chargui, A. Bekrar, A. Aitelcadi, and Y. Sallez, “Dynamic sustainable multiple-depot vehicle routing problem with simultaneous pickup and delivery in the context of the physical internet,” Journal of International Logistics and Trade, vol. 21, no. 3, pp. 110–134, 2023.

V. F. Yu, H. Susanto, Y. H. Yeh, S. W. Lin, and Y. T. Huang, “The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Parcel Lockers,” Mathematics 2022, Vol. 10, Page 920, vol. 10, no. 6, p. 920, Mar. 2022.

J. Ruiz-Meza, A. Torregroza Espinoza, D. Mejía-Ayala, and G. Mendoza Ortega, “Vehicle routing problem with simultaneous pickup and delivery for milk collection in Galeras, Sucre”, Sept 2020.

G. Liu, J. Hu, Y. Yang, S. Xia, and M. K. Lim, “Vehicle routing problem in cold Chain logistics: A joint distribution model with carbon trading mechanisms,” Resour Conserv Recycl, vol. 156, p. 104715, May 2020.

X. Xu et al., “Optimization of reliable vehicle routing problem for medical waste collection with time windows in stochastic transportation networks,” Engineering Optimization, Aug. 2024.

F. Ghiasvand Ghiasi, M. Yazdani, B. Vahdani, and A. Kazemi, “Multi-depot home health care routing and scheduling problem with multimodal transportation: Mathematical model and solution methods,” Scientia Iranica, vol. 31, no. 11, pp. 825–846, Jun. 2024.

R. Liu, X. Xie, V. Augusto, and C. Rodriguez, “Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care,” Eur J Oper Res, vol. 230, no. 3, pp. 475–486, Nov. 2013.

N. Ouertani, H. Ben-Romdhane, I. Nouaouri, H. Allaoui, and S. Krichen, “A multi-compartment VRP model for the health care waste transportation problem,” J Comput Sci, vol. 72, p. 102104, Sep. 2023.

Z. Lin, X. Xu, E. Demir, and G. Laporte, “Optimizing task assignment and routing operations with a heterogeneous fleet of unmanned aerial vehicles for emergency healthcare services,” Comput Oper Res, vol. 174, p. 106890, Feb. 2025.

C. P. Tomazella and M. S. Nagano, “A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem,” Expert Syst Appl, vol. 158, p. 113556, Nov. 2020.

A. Bettinelli, A. Ceselli, and G. Righini, “A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows,” Math Program Comput, vol. 6, no. 2, pp. 171–197, 2014.

E. A. G. de Souza, M. S. Nagano, and G. A. Rolim, “Dynamic Programming algorithms and their applications in machine scheduling: A review,” Expert Syst Appl, vol. 190, p. 116180, Mar. 2022.

D. Management, H. E. C. Montréal, Q. Ht, and G. Laporte, “Fifty Years of Vehicle Routing,” vol. 43, no. 4, pp. 408–416, 2009.

B. Herdianto and Komarudin, “Guided Clarke and Wright Algorithm to Solve Large Scale of Capacitated Vehicle Routing Problem,” 2021 IEEE 8th International Conference on Industrial Engineering and Applications, ICIEA 2021, pp. 449–453, Apr. 2021.

C. Hertrich, P. Hungerländer, and C. Truden, “Sweep Algorithms for the Capacitated Vehicle Routing Problem with Structured Time Windows,” pp. 127–133, 2019.

S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimed Tools Appl, vol. 80, no. 5, pp. 8091–8126, Feb. 2021.

A. Singh and S. Kumar, “Differential evolution: An overview,” Advances in Intelligent Systems and Computing, vol. 436, pp. 209–217, 2016.

J. Gao, F. Gu, P. Hu, Y. Xie, and B. Yao, “Automobile chain maintenance parts delivery problem using an improved ant colony algorithm,” Advances in Mechanical Engineering, vol. 8, no. 9, pp. 1–13, Sep. 2016.

T. J. Ai and V. Kachitvichyanukul, “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,” Comput Oper Res, vol. 36, no. 5, pp. 1693–1702, 2009.

R. Yesodha and T. Amudha, “A bio-inspired approach: Firefly algorithm for Multi-Depot Vehicle Routing Problem with Time Windows,” Comput Commun, vol. 190, pp. 48–56, Jun. 2022.

W. C. Chiang and R. A. Russell, “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Ann Oper Res, vol. 63, no. 1, pp. 3–27, 1996.

E. Taillard, P. Badeau, M. Gendreau, F. Geurtin, and J. Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, vol. 31, no. December 2016, pp. 170–186, 1997.

D. Pisinger and S. Ropke, “Large neighborhood search,” Handbook of Metaheuristics, vol. 146, pp. 1–22, 2010.

C. Blum, “Hybrid metaheuristics in combinatorial optimization: A survey,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7505 LNCS, no. 6, pp. 1–10, 2012.

S. Naccache, J. F. Côté, and L. C. Coelho, “The multi-pickup and delivery problem with time windows,” Eur J Oper Res, vol. 269, no. 1, pp. 353–362, Aug. 2018.

D. Sacramento, D. Pisinger, and S. Ropke, “An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones,” Transp Res Part C Emerg Technol, vol. 102, pp. 289–315, May 2019.

E. Mofid-Nakhaee and F. Barzinpour, “A multi-compartment capacitated arc routing problem with intermediate facilities for solid waste collection using hybrid adaptive large neighborhood search and whale algorithm,” Waste Manag Res, vol. 37, no. 1, pp. 38–47, Jan. 2019.

C. Chen, E. Demir, and Y. Huang, “An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots,” Eur J Oper Res, vol. 294, no. 3, pp. 1164–1180, Nov. 2021.

E. Osaba, X. S. Yang, I. Fister, J. Del Ser, P. Lopez-Garcia, and A. J. Vazquez-Pardavila, “A Discrete and Improved Bat Algorithm for solving a medical goods distribution problem with pharmacological waste collection,” Swarm Evol Comput, vol. 44, pp. 273–286, Feb. 2019.

E. Osaba, R. Carballedo, X. S. Yang, I. Fister, P. Lopez-Garcia, and J. Del Ser, “On Efficiently Solving the Vehicle Routing Problem with Time Windows Using the Bat Algorithm with Random Reinsertion Operators,” Studies in Computational Intelligence, vol. 744, pp. 69–89, 2018.

A. Taha, M. Hachimi, and A. Moudden, “A discrete Bat Algorithm for the vehicle routing problem with time windows,” 2017 International Colloquium on Logistics and Supply Chain Management: Competitiveness and Innovation in Automobile and Aeronautics Industries, LOGISTIQUA 2017, pp. 65–70, Jun. 2017.

P. Shaw, “A new local search algorithm providing high quality solutions to vehicle routing problems,” APES Group, Dept of Computer Science, University of …, pp. 1–12, 1997.

E. Osaba, R. Carballedo, F. Diaz, E. Onieva, A. D. Masegosa, and A. Perallos, “Good practice proposal for the implementation, presentation, and comparison of metaheuristics for solving routing problems,” Neurocomputing, vol. 271, pp. 2–8, Jan. 2018.

J. F. Cordeau, G. Laporte, and A. Mercier, “A unified tabu search heuristic for vehicle routing problems with time windows,” Journal of the Operational Research Society, vol. 52, no. 8, pp. 928–936, 2001.

S. Wang, W. Sun, and M. Huang, “An adaptive large neighborhood search for the multi-depot dynamic vehicle routing problem with time windows,” Comput Ind Eng, vol. 191, p. 110122, May 2024.

C. E. Miller, R. A. Zemlin, and A. W. Tucker, “Integer Programming Formulation of Traveling Salesman Problems,” Journal of the ACM (JACM), vol. 7, no. 4, pp. 326–329, Oct. 1960.