Branch And Cut And Price Algorithm For Vehicle Routing Problem With Time Windows

Vehicle routing problem with time windows(VRPTW)is one of the most common combinatorial optimization problems in logistics industry.Its model structure and algorithms are universal and extensible.VRPTW's model and algorithms can also be applied to other combinatorial optimization scenarios by specific transformation and deformation.The resource allocation problems such as bus route planning and coordinated port equipment scheduling have similar mathematical structures with VRPTW.Therefore,this paper argues that the research on vehicle routing problem is also helpful to promote the development of other related fields.How to effectively improve the efficiency of solving this problem has a direct and significant impact on the development of the logistics industry.This paper will take exact algorithm as the research direction,and make a more comprehensive theoretical research on VRPTW.At present,the research of exact algorithm is mainly divided into two directions: integer programming and dynamic programming.Since VRPTW is NP-hard in the strong sense,most scholars prefer to choose dynamic programming that can be solved in pseudo-polynomial time.However,the theoretical lower bound's quality of the optimal solution obtained by dynamic programming is poor.Moreover,under the condition of wide time window constraints,its property of calculating is not superior to integer programming.In contrast,integer programming is more flexible.It can solve this problem quickly by merging branch decisions or adding effective inequalities.Therefore,this paper will take the integer programming as the theoretical basis to optimize the algorithm of VRPTW.The main innovations and research results are as follows:(1)The algorithm's framework of branch and cut and price combined with column generation and cutting plane is built.And this paper improved the subtour constraints in the original two-index vehicle flow model to make it suitable for VRPTW.In the later stage of the algorithm,the improved two-index vehicle flow model is introduced to replace the original branching process.On this basis,the upper bound of the minimum number K of vehicles is guessed,and all the experiments completed in this paper confirm the conjecture.(2)The two-point and three-point generalized cutset inequalities are proposed innovatively and proved to be inequalities satisfying facet-defining.VRPTW,as a classic combinatorial optimization problem,has a long history of research.However,its sub-problem: Elementary Shortest Path Problem with Resource Constraints(ESPPRC)is rarely explored.The only theoretical research based on integer linear programming is to apply the classic inequalities of the traveling salesman problem to ESPPRC.This paper explored the polymorphic structure of ESPPRC and proposed two set of effective inequalities for ESPPRC.(3)Aiming at the strategy of adding effective inequalities,this paper tried to do all the combinatorial experiments of two-point and three-point generalized cutset inequalities in the form of permutation and combination.Finally,three-point generalized cutset inequalities are added to the root node of the branch-and-bound tree of the subproblem in the form of cutting plane callback.The experiments of ESPPRC and VRPTW are completed,and the validity of generalized cutset inequalities is verified.The model's performance is significantly improved.