A Kernel Route Tabu Search Algorithm for Large-Scale Integrated Vehicle Routing Problem

Based on the principle of kernel route, a tabu search algorithm is designed for large-scale integrated vehicle routing problem (LSIVRP) with constraints of capacity and delivery distance. The algorithm has two phases: initial optimization and post-optimization. In initial optimization, the kernel routes in route library are updated constantly to form the framework of optimal routes. In the first phase of post-optimization, the algorithm uses the kernel routes produced in initial optimization to get better solution. The kernel routes are disconnected in the second phase to prevent the vertex links of worse route from influencing the formation of good solution. Many representative results and analysis are given in this paper. This proposed algorithm was also applied to illustrate its validity in comparison with the best results in other literatures. The results and analysis demonstrate the effectiveness of this algorithm to the LSIVRP in the condition mentioned above.