A Hybrid Adaptive Simulated Annealing and Tempering Algorithm for Solving the Half-Open Multi-Depot Vehicle Routing Problem

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

• collaborative logistics
• half-open multi-depot vehicle routing problem
• adaptive Markov chain length
• improved large-neighborhood search
• tempering mechanism