Greedy Randomized Adaptive Large Neighborhood Search For Multi-trip Vehicle Routing Problem With Time Windows

With the rapid development of the economy,the demand for logistics and distribution has also increased sharply and the distribution scene has exhibited diversified characteristics.For the multi-trip vehicle routing problem with time windows which is common in logistics,This paper studies the MTVRPTW that is common in logistics.This problem studied has three objectives,and the first objective is to reduce time swap and overtime,and the second objective is to minimize the number of vehicles,and the last objective is to minimize the total travel time or total working duration.This paper provides mathematical models to solve the MTVRPTW under different objectives,so as to better serve the scheduling decisions of logistics enterprises,reduce logistics costs,and improve competitiveness.The detailed research work is as follows.(1)This paper reviews the existing literature on MTVRPTW,analyzes the problems in the research results and classifies the algorithms.By analyzing the problem,this paper studies the MTVRPTW problem of which the first objective is to reduce time swap and overtime,and the second objective is to minimize the number of vehicles,and the last objective is to separately consider minimizing the total travel time or total working duration.(2)Based on the mathematical model of MTVRPTW with different objectives,the paper designs the greedy randomized adaptive large neighborhood search algorithm(GRALNS)to solve the MTVRPTW.Firstly,we use the construction stage of Greedy Randomized Adaptive Search Procedure to generate the initial high-quality solution.Then in the neighborhood exploring stage,we design the removal heuristics,insertion heuristics and the vehicle reduction strategy,to reduce the time swap and overtime,the number of vehicle,and the duration time or travel time.(3)Simulation experiments were performed on 9 data instances of the public data set to verify the effectiveness of the solution.Compared with the basic large neighborhood search,GRALNS proposed in this paper could get the satisfactory solution more stably.And the experimental results showed that GRALNS have better search ability in the most instances.Finally,we compared and analyzed the cost of solutions.