Research On Multi Depot Multi Trip Vehicle Routing Problem With Time Windows

In this paper,we address a variant of vehicle routing problem under urban logistic distribution,containing three constraints:(i)In reality,there are several depots in many companies for combined distribution,choosing the right depot to delivery goods for a given customer can significantly cut delivery cost down,this is called multi depot constraint.(ii)When perishable goods,fresh foods,emergency goods are transported,there is a time limitation on each delivery trip;due to road conditions and law restrictions,vehicles with small capacity are usually chosen,as a consequence,only a few customers can get service on a trip;since vehicle quantity is generally fixed in reality,in above-mentioned situations,vehicles need to perform several trips during its workday in order to serve more customers as well as increase its utilization,this is referred to multi trip constraint.(iii)Delivery during the time period appointed by customers is referred to time windows constraint.Our study combines above three constraints,which is called Multi Depot Multi Trip Vehicle Routing Problem with Time Windows(MDMTVRPTW).We study this topic hoping a lower delivery cost,a raise on company competition could be achieved.Our research mainly focus on MDMTVRPTW with time limitation.We build its mixed integer programming model.With the restrictions of time limitation,time windows and vehicle quantity,it is difficult to serve all customers,therefore we need a tradeoff between the number of served customers and the total travel distance.Since it benefits the company when serving more customers,we consider the hierarchical objective,where the quantity of served customers is firstly maximized and the total travel distance is then minimized.Based on hierarchical objective,we design a two-phase heuristic algorithm to solve MDMTVRPTW.In the first phase,we use a cluster algorithm based on distance to assign customers,converting multi depot problem to several single depot problems,then for each depot,we construct initial solution through insert algorithm,after that,we apply a heuristic algorithm based on large neighborhood search to improve the initial solution and adjust the cluster result to expand the solution search space,the objective of this phase is to maximize the number of served customers.In the second phase,we improve the solution by using tabu search algorithm,aiming at reducing the total travel distance.To evaluate performance of the two-phase algorithm,we design instances for computational experiments.The results show that on small instances,our algorithm can get optimal solutions or solutions that better than Cplex's feasible solution quickly,also,for large scale instances,our algorithm is able to solve efficiently.One step further,we solve the relaxation problem: Multi Trip Vehicle Routing Problem with Time Windows,comparing with the results from existing papers,it shows that our algorithm can obtain quasi-optimal solution on small problems and high quality solution on large scale problems.At last,we solve MDMTVRPTW without time limitation and MTVRPTW without time limitation,by comparing with Cplex and exact algorithm's results respectively,it shows that our algorithm has good performance.