Exact Algorithms For Vehicle Routing Problem With Time Windows

Vehicle Routing Problem with Time Windows(VRPTW)is a classic combinatorial optimization problem,is also one of the most widely used transport problems in the current application.Based on the theoretical principles,this paper is established in the exact algorithm,making a more comprehensive theoretical study on the integer linear programming of VRPTW.In the algorithm,this paper chooses to use the current mainstream of the column generation algorithm,which involves the sub problem of Elementary Shortest Path with Resource Constraints(ESPPRC).When using the column generation algorithm to solve VRPTW,we are usually beset by the problem that the sub problem is difficult to solve quickly,so we do an in-depth research focused on the sub problem,and we found that the research on it is mostly used the route of dynamic programming to solve this problem.In recent years,a few foreign scholars began to study the integer linear programming model of the ESPPRC,but the results were not significant.So we choose the integer linear programming of ESPPRC as the main research object,trying to make a breakthrough in this field.The main research results and innovations are as follows:(1)Do a research on the polytope structure of ESPPRC and prove a facet-defining inequality.In the field of combinatorial optimization,the research of polyhedral structure mainly focuses on the traveling salesman problem and the vehicle routing problem with capacity constraints,which was solved by the older generation of scholars at the end of last century.At home and abroad,there are few researches on the polyhedron structure of ESPPRC,and the scholars are more interested in solving the problem by using the dynamic programming method,or applying the classical inequality in traveling salesman problem to ESPPRC.In this paper,we have studied and proved the multi polytope structure of ESPPRC by using polyhedral theory,and found a facet-defining definition.(2)For the ESPPRC,we put forward three sets of valid inequalities.Drawing lessons from the related theory of dynamic programming and constraint programming,this paper puts forward the domination rule of ESPPRC which is applicable for integer linear programming.In this paper,we study the polyhedral structure of ESPPRC,and find a set of inequalities which accord with the facet-defining.Then,based on the above theory,three kinds of valid inequalities are proposed innovatively.Finally,the performance of these three models is tested by the modified version of the Solomon benchmark package,in which we got a significant effect.(3)The mathematical model of two-index vehicle flow is applied in VRPTW.We extend the two-index vehicle flow model of Capacitated Vehicle Routing problem to the VRPTW,and use it to replace the branch-and-cut process in the column generation algorithm,which provides a new way to solve VRPTW.At the same time,the theoretical upper bound of the minimum number of vehicles is conjectured,texting by the Solomon benchmark package,the experiment that carried out by this paper is also affirmed this conjecture.