Hybrid Simulated Annealing for Multi–Objective Capacitated Vehicle Routing in School Milk Distribution

Peerapong Pakawanich

doi:10.55003/ETH.430101

Authors

Peerapong Pakawanich Faculty of Engineering and Industrial Technology, Silpakorn University Sanam Chandra Palace Campus, Thailand

DOI:

https://doi.org/10.55003/ETH.430101

Keywords:

Capacitated vehicle routing problem, Hybrid simulated annealing, workload balance, Multi–objective

Abstract

This study develops a Hybrid Multi–Objective Simulated Annealing (HMOSA) framework for solving the Multi–Objective Capacitated Vehicle Routing Problem in Thailand’s School Milk Program, where balancing efficiency and fairness is essential due to the manual unloading tasks performed by each delivery team. The model minimizes total travel distance and workload imbalance, quantified by the standard deviation of vehicle loads to better capture physical handling effort. The proposed HMOSA introduces two novel mechanisms: i) warm–start initialization using extreme seed solutions generated from Single–Objective SA (SOSA) and Weighted–Sum SA (WSSA), and ii) a guided neighborhood mechanism that selects promising neighbors using weighted scores to enhance search efficiency and diversity. These contributions improve convergence stability without relying on complex parameter tuning. Computational experiments on 10, 30, and 51–customer instances demonstrate that HMOSA consistently outperforms conventional MOSA and SA, and provides superior Pareto–front quality compared with Non-dominated Sorting Genetic Algorithm II NSGA–II. Performance was assessed using two widely adopted indicators: hypervolume (HV) for solution diversity and inverted generational distance (IGD) for convergence reliability. In the real–world 51–school case, small increases in total distance resulted in substantial improvements in workload equity, offering actionable compromise solutions between distance and fairness. Overall, HMOSA embeds fairness into routing decisions while maintaining scalability and robustness, serving as a practical decision–support tool for real routing applications where routing efficiency and equitable workload distribution are both essential.

References

Z. H. Ahmed, N. Al-Otaibi, A. Al-Tameem and A. K. J. Saudagar, “Genetic Crossover Operators for the Capacitated Vehicle Routing Problem,” Computers, Materials & Continua, vol. 74, no. 1, pp. 1575–1605, 2023, doi: 10.32604/cmc.2023.031325.

C. Wang, B. Ma and J. Sun, “A co-evolutionary genetic algorithm with knowledge transfer for multi-objective capacitated vehicle routing problems,” Applied Soft Computing, vol. 148, 2023, Art. no. 110913, doi: 10.1016/j.asoc.2023.110913.

M. Kumari, P. K. De, K. Chaudhuri and P. Narang, “Utilizing a hybrid metaheuristic algorithm to solve capacitated vehicle routing problem,” Results in Control and Optimization, vol. 13, 2023, Art. no. 100292, doi: 10.1016/j.rico.2023.100292.

J. Li, R. Liu and R. Wang, “Handling dynamic capacitated vehicle routing problems based on adaptive genetic algorithm with elastic strategy,” Swarm and Evolutionary Computation, vol. 86, 2024, Art. no. 101529, doi: 10.1016/j.swevo.2024.101529.

X. Zhang, Y. Hao, L. Zhang and X. Yuan, “Application of improved genetic algorithm to vehicle routing problem considering the environmental self-regulation of the freight companies,” Expert Systems with Applications, vol. 274, 2025, Art. no. 127010, doi: 10.1016/j.eswa.2025.127010.

R. Kuo, M. Luthfiansyah, N. Masruroh and F. E. Zulvia, “Application of improved multi-objective particle swarm optimization algorithm to solve disruption for the two-stage vehicle routing problem with time windows,” Expert Systems with Applications, vol. 225, 2023, Art. no. 120009, doi: 10.1016/j.eswa.2023.120009.

A. Thammano and P. Rungwachira, “Hybrid modified ant system with sweep algorithm and path relinking for the capacitated vehicle routing problem,” Heliyon, vol. 7, no. 9, 2021, Art. no. e08029, doi: 10.1016/j.heliyon.2021.e08029.

A. Motaghedi-Larijani, “Solving the number of cross-dock open doors optimization problem by combination of NSGA-II and multi-objective simulated annealing,” Applied Soft Computing, vol. 128, 2022, Art. no. 109448, doi: 10.1016/j.asoc.2022.109448.

V. F. Yu, S.-W. Lin, L. Zhou and R. Baldacci, “A fast simulated annealing heuristic for the multi-depot two-echelon vehicle routing problem with delivery options,” Transportation Letters, vol. 16, no. 8, pp. 921–932, 2023, doi: 10.1080/19427867.2023.2257923.

E. Rodríguez-Esparza, A. D. Masegosa, D. Oliva and E. Onieva, “A new Hyper-heuristic based on Adaptive Simulated Annealing and Reinforcement Learning for the Capacitated Electric Vehicle Routing Problem,” Expert Systems with Applications, vol. 252, 2024, Art. no. 124197, doi: 10.1016/j.eswa.2024.124197.

T. Leelertkij, J. Buddhakulsomsiri and V. -N. Huynh, “A multi-thread simulated annealing for multi-objective vehicle routing problem with time windows and demand priority,” Computers & Industrial Engineering, vol. 207, 2025, Art. no. 111253, doi: 10.1016/j.cie.2025.111253.

V. Praveen, P. Keerthika, G. Sivapriya, A. Sarankumar and B. Bhasker, “Vehicle Routing Optimization Problem: A Study on Capacitated Vehicle Routing Problem,” Materials Today: Proceedings, vol. 64, pp. 670–674, 2022, doi: 10.1016/j.matpr.2022.05.185.

Z. Nan, X. Yang, L. Ruiz-Garcia, J. Qiu, Y. Feng and J. Han, “Multi-objective optimization of cold chain distribution routes considering traffic congestion,” Agriculture Communications, vol. 3, no. 4, 2025, Art. no. 100104, doi: 10.1016/j.agrcom.2025.100104.

S. I. Nyako, D. Tayachi and F. Abdelaziz, “Machine learning multi-objective optimization for time-dependent green vehicle routing problem,” Energy Economics, vol. 148, 2025, Art. no. 108628, doi: 10.1016/j.eneco.2025.108628.

M. Vukićević, M. Ratli, A. Rivenq, R. Todosijević and B. Jarboui, “Energy minimizing capacitated covering vehicle routing problem,” Applied Soft Computing, vol. 183, 2025, Art. no. 113620, doi: 10.1016/j.asoc.2025.113620.

Z. Wu and H. Yaman, “Comparison of compact formulations for the electric vehicle routing problem,” Transportation Research Part B: Methodological, vol. 200, 2025, Art. no. 103314, doi: 10.1016/j.trb.2025.103314.

H. Yu and W. D. Solvang, “Incorporating flexible capacity in the planning of a multi-product multi-echelon sustainable reverse logistics network under uncertainty,” Journal of Cleaner Production, vol. 198, pp. 285–303, 2018, doi: 10.1016/j.jclepro.2018.07.019.

Z. Yanhu, Y. Lijuan, K. ShuMei and M. Decheng, “Research on multi-objective optimization of multi-endpoint VRP with time window for the distribution of seasonal products by multi-homing heterogeneous fleets,” Expert Systems with Applications, vol. 298, 2026, Art. no. 129595, doi: 10.1016/j.eswa.2025.129595.

P. Matl, R.F. Hartl and T. Vidal, “Workload equity in vehicle routing: The impact of alternative workload resources,” Computers and Operations Research, vol. 110, pp. 116–129, 2019. doi: 10.1016/j.cor.2019.05.016.

F. Lehuédé, O. Péton and F. Tricoire, “A lexicographic minimax approach to the vehicle routing problem with route balancing,” European Journal of Operational Research, vol. 282, no. 1, pp. 129–147, 2020, doi: 10.1016/j.ejor.2019.09.010.

S. Shahnejat-Bushehri, A. Kermani, O. Arslan, J.-F. Cordeau and R. Jans, “A Vehicle Routing Problem with Time Windows and Workload Balancing for COVID-19 Testers: A case study,” IFAC-PapersOnLine, vol. 55, no. 10, pp. 2920–2925, 2022, doi:10.1016/j.ifacol.2022.10.175.

J. Li, Y. Fang and N. Tang, “A cluster-based optimization framework for vehicle routing problem with workload balance,” Computers & Industrial Engineering, vol. 169, 2022, Art. no. 108221, doi: 10.1016/j.cie.2022.108221.

W. Zhao, Y. Yuan, C. Cheng and W. Liu, “Bi-objective sustainable urban logistics vehicle routing problem with workload balance,” Journal of Industrial Information Integration, vol. 48, 2025, Art. no. 100985. doi: 10.1016/j.jii.2025.100985.

X. Xu and H. Ouyang, “A branch-and-cut algorithm for the pallet-loading vehicle routing problem considering load balance of semi-trailer trucks,” Computers & Operations Research, vol. 185, 2025, Art. no. 107258, doi: 10.1016/j.cor.2025.107258.

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 Transactions on Cybernetics, vol. 46, no. 3, pp. 582–598, 2016, doi: 10.1109/TCYB.2015.2409837.

J. Wang, T. Weng and Q. Zhang, “A Two-Stage Multiobjective Evolutionary Algorithm for Multiobjective Multidepot Vehicle Routing Problem With Time Windows,” IEEE Transactions on Cybernetics, vol. 49, no. 7, pp. 2467–2478, 2019, doi: 10.1109/tcyb.2018.2821180.