Research On Exact Algorithm For Complicated Multi-trip Vehicle Routing Problem

This dissertation focuses on the multi-trip vehicle routing problems,and studies the exact algorithms for seven types of variant problems: the multi-trip vehicle routing problem with time windows(CMTVRPTW),the multi-trip vehicle routing problem with time windows and loading times(CMTVRPTW-LT),the multi-trip vehicle routing problem with time windows and limited trip duration(CMTVRPTW-LD),the multi-trip vehicle routing problem with time windows and release dates(CMTVRPTW-R),the drone-routing problem(DRP),The multi-trip vehicle routing problem with time windows and unloading queue at depot(MTVRPTW-UQD),and time-dependent multi-trip vehicle routing problem with time windows(TD-MTVRPTW).The multi-trip vehicle routing problem is a variant of the classic vehicle routing problem,which is common in warehouse transportation,urban garbage transportation,drone transportation and other networks.Based on the high complexity of this problem and few people have studied exact algorithm at present,this paper deeply explores these problems from the perspective of buliding arc-flow models and set partition models,designing exact algorithms and experimental demonstration.The research results of this dissertation are as follows:(1)CMTVRPTW: We formulate this problem into an arc-flow model and a set partitioning model where variables represent feasible trips,respectively.And then,a branchand-price-and-cut algorithm(BPC)is proposed to solve the problem.Subsequently,we compare our algorithm with Paradiso et al.(2020)based on 135 instances,and experimental results verify the accuracy and efficiency of the proposed algorithm.(2)Four types of variant problems of multi-trip vehicle routing with time windows(CMTVRPTW-LT,CMTVRPTW-LD,CMTVRPTW-R and DRP): Based on the BPC for solving CMTVRPTW,considering the different characteristics of the four variant problems,the new BPCs for different problems are customized.Through a large number of experiments and comparisons,it can be found that our algorithms can find optimal solutions for 81 out of 135 instances in CMTVRPTW-LT,find optimal solutions for 219 out of 270 instances in CMTVRPTW-LD,find optimal solutions for 315 out of 405 instances in CMTVRPTW-R and 196 out of 220 instances in DRP.Compared with the current exact algorithms,the designed algorithms are far superior to the predecessors in solving scale.(3)CMTVRPTW-UQD:We formulate this problem into an arc-flow model and a set partitioning model where variables represent feasible trips,respectively.There are two sets of mutual exclusion constraints which aim at avoiding overlap of trips assigned to the same vehicle and avoiding overlap during the unloading process in the set partitioning model.Based on this set partitioning model,a new BPC is designed.And the accuracy of the BPC is verified by comparing with CPLEX on small scale instances with no more than 15 customers.Then,tested on instances with 25 or more customers,the algorithm can accurately solve 80 out of 108 instances within 3 hours.(4)TD-MTVRPTW:First,an arc-flow model and a set partitioning model where variables represent feasible trips are formulated,respectively.Then,a BPC of this problem is customized.In the label setting algorithm,a multi-dimensional label with curve characteristics is designed,and the set dominance rule is introduced to judge the validity of the labels.And the accuracy of the BPC is verified by comparing with CPLEX on small scale instances with no more than 15 customers.Then,tested on instances with 25 or more customers,the algorithm can accurately solve 70 out of 81 instances within 2 hours.To improve the lower bounds of different problems,valid inequalities are added to the set partitioning models.And methods such as decremental search space relaxation,heuristic label setting,label pruning and bounded bidirectional search strategy are used in the label setting algorithms to speed up the column generation process.At the same time,the surrogate relaxation is introduced to reduce the number of constraints in the linear master problem and the number of feasible routes searched in the label setting algorithm.