点击次数：

论文类型：会议论文

发表时间：2019-01-01

收录刊物：EI、CPCI-S

页面范围：37-44

关键字：Vehicle Routing Problem; Elementary Shortest Path Problem; Column Generation; Vehicle Routing Problem With Time Windows

摘要：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].