A Hybrid Adaptive Simulated Annealing and Tempering Algorithm for Solving the Half-Open Multi-Depot Vehicle Routing Problem
Open Access
- 22 March 2024
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 12 (7) , 947
Abstract
The half-open multi-depot vehicle routing problem (HOMDVRP) is a typical decision optimization problem in the field of collaborative logistics that considers resource sharing. This study aims to develop an effective meta-heuristic algorithm for solving the HOMDVRP. Firstly, a mixed-integer programming model of HOMDVRP is established to minimize the total travel distance of the vehicles. After that, a novel hybrid adaptive simulated annealing and tempering algorithm (HASATA) is proposed based on the features of HOMDVRP. The proposed algorithm combines the strengths of the simulated annealing algorithm and the large-neighborhood search algorithm to balance the algorithm’s searching capabilities in both breadth and depth. Meanwhile, an adaptive Markov chain length mechanism and a tempering mechanism are designed to improve the algorithm’s computational efficiency and convergence ability. Finally, simulation experiments are conducted to verify the effectiveness of the proposed model and the computational performance of the proposed algorithm. Four comparison algorithms are selected and analyzed using 24 groups of problem instances. The comparison results show that the proposed HASATA can solve the HOMDVRP more efficiently and obtain a solution with better optimization performance and satisfactory stability.Keywords
Funding Information
- National Natural Science Foundation of China (72371155, 20692193300, 23692121400)
- Shanghai Municipal Commission of Science and technology (72371155, 20692193300, 23692121400)
This publication has 28 references indexed in Scilit:
- An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problemsComputers & Operations Research, 2021
- Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distanceComputers & Operations Research, 2021
- Collaborative vehicle routing: A surveyEuropean Journal of Operational Research, 2018
- A simulating annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardinessApplied Soft Computing, 2015
- Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickupsExpert Systems with Applications, 2015
- A literature review on the vehicle routing problem with multiple depotsComputers & Industrial Engineering, 2015
- Multi-depot vehicle routing problem with time windows under shared depot resourcesJournal of Combinatorial Optimization, 2014
- Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problemComputers & Industrial Engineering, 2010
- A hybrid genetic algorithm for the multi-depot vehicle routing problemEngineering Applications of Artificial Intelligence, 2008
- A unified heuristic for a large class of Vehicle Routing Problems with BackhaulsEuropean Journal of Operational Research, 2006