Research On Algorithms For Dynamic Vehicle Logistics Routing Problem With Time Windows

In recent years,enterprises have higher and higher requirements for the company's supply chain capacity with the rapid development of manufacturing industry.Through the management and optimization of supply chain,enterprises can greatly improve customer satisfaction and reduce the manufacturing cost of enterprises,and then realize the maximization of profits.The vehicle route planning for goods transportation is a key element,which can effectively improve the logistics efficiency and reduce the transportation cost of enterprises.Dynamic Vehicle Routing Problem with Time Windows(DVRPTW)is a problem which includes the time window reqiurements for the delivery time of goods for each customer.In addition,the problem further considers the situation that customer orders appear dynamically and randomly.This aspect requires the vehicle routes to be updated in an ongoing manner.This problem is more close to the actual application scenarios of logistics manufacturing enterprises,so the research on DVRPTW has a strong practical significance.Firstly,this thesis studies the VRPTW problem and adopts the improved Ant Colony Optimization(ACO)to optimize the vehicle routes.The nearest neighbour heuristic is used to construct the initial solution,which can make the initial solution more stable.In the iterative process of ACO,pareto optimal strategy is used for the global pheromone update.Meanwhile,we resort to local research procedure to further improve the solutions built by ants.Experiments are conducted on the Solomon's dataset and Gehring & Homberger dataset.The results show that our algorithm has a better performance compared to Column Generation Algorithm(CG),Simulated Annealing Algorithm(SA),Genetic Algorithm(GA)and Adaptive Large Neighborhood Search(ALNS)with respect to the result quality and computing time.The second part is the algorithm research on DVRPTW.This project adopts rolling time method and dynamic algorithm framework with two threads,which can maximize the optimization time.Meanwhile,we adopt the ACO described in the first section during each time slice.Based on ACO,we adjust the pheromone update strategy and the parameters of ACO adaptively.The algorithm is tested on the standard DVRPTW dataset and compared with the existing algorithms.The experimental results show that the algorithm designed in this project has better performance in the optimization of vehicle distance,and the advantage becomes apparent as the dynamic level of instances increases,especially on almost all instances of 50% and 100% dynamic degree.In terms of the stability of getting optimal solutions,our algorithm is better than the other existing algorithms.