A Hybrid Algorithm for Single-Depot Integrated Vehicle Routing Problem

摘要

This paper designed a simulated annealing algorithm (SA) for the single depot integrated vehicle routing problem and introduced the principium of the algorithm. The SA is based on the delivery route expressed with natural numbers. Considering the differences between delivery distance and time windows limits, the penalty function and the properties of the limits are proposed into the simulated annealing algorithm for the depot insertion control. For the search space extension, three kinds of neighborhood are proposed and incorporated into the state generating function. In addition, the algorithm uses tabu rules to control the sampling process. We conducted a comparative analysis between discrepant scales and different algorithms. The results of computational experiments shows that the proposed algorithm is effective in solving the single depot integrated vehicle routing problem.