Indexed by:Conference Paper

Date of Publication:2019-01-01

Included Journals:CPCI-S、EI

Page Number:37-44

Key Words:Vehicle Routing Problem; Elementary Shortest Path Problem; Column Generation; Vehicle Routing Problem With Time Windows

Abstract:In this article, we describe an algorithm to solve elementary shortest path problem (ESPPRC) that improves the method proposed in [Lozano et al., Transportation Science, 2015]. ESPPRC has been the backbone of solving vehicle routing problem (VRP) using the branch-and-price procedure, especially vehicle routing problem with time windows (VRPTW). The main idea of our contribution is splicing two partial paths to get a complete path in order to reduce the search space. We embed our algorithm into a column generation procedure to solve the linear relaxation of VRPTW. Experiment results show that the algorithm proposed in this paper can significantly reduce the search space and the running time. Our algorithm has a shorter average running time in 51 of the 56 instances. All experiment data sets are from Solomon benchmark [Solomon, Operations Research, 1987].