Research on Multi-trip Vehicle Routing Optimization Problem Considering Multiple Time Windows
In recent years,the rapid development of online retail has greatly increased the demand for"last mile"order delivery.However,large freight vehicles are usually kept off of city central roads by urban trans-portation authorities,so much so that carriers have to rely on vans to complete the"last mile"delivery.Hence,reasonable vehicle route planning can efficiently complete the delivery tasks,which is crucial to im-proving delivery efficiency and user experience.Therefore,the vehicle routing problem(VRP)has always been a hot topic in academia.Traditional VRPs assume that in each cycle,a vehicle can only perform one trip.Due to their limited capacity,vans could not accomplish much in a single trip,which,combined with limited fleet size,in order to improve vehicle utilization and reduce operating costs,necessitates us to allow the vans to"multi-trip"a distribution center.As a result,the VRP is extended into the multi-trip vehicle routing problem(MTVRP),which has higher practical value in the"last mile"delivery scenario.As a result,MTVRP and its variants have gradually attracted the attention of scholars in recent years.In order to meet the demand for large-scale distribution and increase the flexibility of vehicle route plan-ning,and avoid the excessive concentration of customer order within a single time window,we proposed a multi-trip vehicle routing problem with multiple time windows(MTVRPMTW),which is an extension of the multi-trip vehicle routing problem with time windows.It not only determines the order in which each vehicle serves the customers,but also determines the time window for providing such services.At the same time,it requires that the specific time windows for the delivery services be met,and also that the sum of the customer demand on each single trip not exceed the maximum load of the vehicle.Then we constructed a mixed integer programming model with the goal of minimizing the total driving time.In view of the com-plexity of the problem and the weakness of the optimization software CPLEX in solving large-scale exam-ples,we designed an iterative local search algorithm to solve the problem.Under the framework of said algo-rithm,we designed an improved Solomon greedy insertion algorithm suitable for multi-time windows and multi-trip scenarios to generate the initial solution.We then designed the Or-opt and Relocate local search operators and the random exchange perturbation operations as well.Based on the initial solution or the cur-rent best solution,the two operators were used alternately for iterative search so as to obtain the updated best solution.The example results show the effectiveness of the proposed model and algorithm,in that,compared with the MTVRPTW model,when considering multiple time windows,it allows the carrier to flexibly plan the vehicle routes and select service time windows,thereby reducing the number of vehicles used and the to-tal travel time.Future researches can expand this problem to consider multiple customer delivery addresses and more complex and realistic vehicle routing problems.
multiple time windowsmulti-tripvehicle routing problemmixed integer programmingit-erative local search
万方数据
维普
