Research And Application Of Two-stage Hybrid Heuristic Algorithms For Multi-trip Vehicle Routing Problem With Time Windows

With the continuous development of Chinese e-commerce,the number of e-commerce parcels is increasing rapidly,and logistics companies are facing increasingly fierce competition in the last-mile delivery scene.It is crucial to efficiently complete delivery tasks through reasonable path planning for improving delivery efficiency and user experience.In recent years,urban road traffic rules have started to restrict large vehicles from entering central city roads.Therefore,last-mile logistics delivery needs to use small trucks,which make multiple trips between the central warehouse and customer locations to complete deliveries.In this scenario,customers often have time window requirements.If we consider the Vehicle Routing Problem with Time Windows(VRPTW)with time window constraints,each vehicle can only execute one trip.Due to the small capacity of small trucks,the utilization rate of single-trip vehicles is low,and the cost can only be reduced by increasing the number of vehicles used to meet customer demand.Therefore,the Multi-trip Vehicle Routing Problem with Time Windows(MTVRPTW)has higher practical value in the lastmile delivery scene.Considering that MTVRPTW has been proven to be an NP-hard problem,and the existing exact solution algorithm for MTVRPTW can only solve small instances,it cannot obtain high-quality solutions in a short time,and cannot meet the demand of large-scale delivery scenarios in urban logistics.Therefore,designing a mixed heuristic solution algorithm for efficient solving MTVRPTW has significant implications.This thesis analyzes and summarizes the characteristics,types,and primary optimization issues of the multi-trip vehicle routing problem.It employs operations research,intelligent optimization algorithms,and other methods to address the main research work on the multi-trip vehicle routing problem with time windows(MTVRPTW).This work includes the following aspects:(1)Investigating the MTVRPTW problem with an undefined number of vehicles,a mixed integer programming model is developed to optimize the total cost.Two solving strategies are designed,including the Solomon initial solution construction strategy SILTS algorithm and the greedy initial solution construction strategy GRILS-VND algorithm.Using the Solomon benchmark,the optimization effects of these two strategies are analyzed and compared from two dimensions: customer distribution and time window density.(2)Investigating the MTVRPTW problem with a fixed number of vehicles,a mixed integer programming model is developed to minimize the distance traveled.A two-stage mixed heuristic algorithm HVNTS is designed using the variable neighborhood algorithm and taboo search method in combination with the problem features.By comparing the results with existing solutions,the effectiveness of the algorithm is validated.(3)Using J Company’s last mile delivery scenario as an example,actual road network data based on the Manhattan distance is generated.By using J Company’s actual road network data,the optimization effects of the SILTS algorithm and the GRILS-VND algorithm on total cost under actual scenarios are compared and analyzed.Additionally,the optimization methods for actual MTVRPTW mileage with a fixed number of vehicles are discussed.This study provides a decision-making basis for logistics transportation companies to implement logistics path planning and enriches the relevant optimization research of MTVRPTW in theory.