Research On Vehicle Route Planning With Time Windows Based On Pulse Algorithm

With the rapid development of e-commerce industry,China’s express business volume has ranked first in the world for six consecutive years.Facing such a huge customer group,enterprises need to invest more resources and costs to carry out logistics transportation and express delivery.It plays a key role to search an efficient and reasonable large-scale customer distribution scheme in increasing profits and reducing costs.This thesis studies the solution of Vehicle Routing Problem with Time Windows(VRPTW)and the Orienteering Problem with Time Windows(OPTW).Both VRPTW and OPTW are complex combinatorial optimization problems,traditional exact algorithms can only solve small and medium-scale problems,while heuristic algorithms sacrifice the accuracy of the optimal solution to obtain faster calculation speed.The current route planning problem often has hundreds of nodes,therefore,designing fast and efficient algorithms is the focus and difficulty around the world.The main work and results are as follows:(1)By analyzing and comparing the state-of-art algorithms of vehicle routing problem and orienteering problem,we choose the column generation algorithm as the main algorithm,which can solve large-scale problems.In the framework of column generation algorithm,the original problem is divided into Master Problem(MP)and Sub-Problem(SP),and the optimal solution is obtained by calculating between the MP and the SP iteratively.The breadth-first search algorithm is widely used in solving the sub-problem,but this thesis introduces a new pulse algorithm to solve it,which is a depth-first search algorithm proposed by Lozano et al,and different pulse pruning strategies are applied to different sub-problems.(2)In the framework of column generation,pulse algorithm is applied to solve the VRPTW sub-problem.According to the Dantzig-Wolfe decomposition principle,the established mixedinteger programming model is decomposed into a set partitioning master problem and an elementary shortest path problem with resource constraints,three pulse pruning strategies are applied to speed up the solution of sub-problem.The experimental results of Solomon and Gehring&Homberger benchmark test set show that the proposed algorithm can significantly improve the speed of VRPTW problems with different scales,it has a certain research potential and application value.(3)In the framework of column generation,pulse algorithm is applied to solve the OPTW sub-problem.The mixed-integer programming model is rewritten as the set-packing master problem and an elementary longest path problem with resource constraints.Two core pulse pruning strategies and two specific pulse pruning strategies are used in the sub-problem.The results of Solomon and Cordeau show that the proposed algorithm performs well in solution accuracy,besides,when solving large-scale problems,compared with other exact algorithms,it can effectively improve the calculation speed,which provides a theoretical basis and reference method for practical application.