Enhanced Ant Colony Optimization Algorithm For Multi-depot Vehicle Routing Problem

Logistics is an important industry related to the national economy and people’s livelihood,and it is also an important embodiment of a country’s comprehensive national strength.China’s logistics industry has developed rapidly in recent years,but compared with the developed countries,there are still problems of high cost and low efficiency.Research on Vehicle Routing Problem(VRP)is one of the most effective ways to solve this problem.Multi-depot Vehicle Routing Problem(MDVRP)is an important extension of VRP with a wide application scenario.Because of its high fitting with the operation modes of modern logistics’ distributed warehousing and multi-point distribution,MDVRP has attracted much attention of relevant enterprises,and because of its largescale,multi-constrained,non-linear,Non-deterministic Polynomial hard(NP-hard)and other attributes,MDVRP has been a hot and difficult problem for scholars for many years.In this paper,the modeling and solving methods of MDVRP are researched.Firstly,the local search performance of the improved Ant Colony Optimization(IACO)algorithm which based on Ant Colony Optimization,(ACO)is improved by constructing a local search strategy mixed with a variety of neighborhood operations and local search operators,and the IACO is used to solve the shortest path MDVRP.Secondly,the vehicle speed calculation model considering the traffic congestion information is designed,and the vehicle travel distance,load,and speed factors are integrated to establish a model for the green multi-depot vehicle routing problem with the criterion of minimizing the total fuel-consumption costs(TFC-GMDVRP).Then,a learning ant colony optimization algorithm(LACO)combining with related knowledge model and IACO is proposed for solving the TFC-GMDVRP.Thirdly,considering the balance of each vehicle’s driving task,a multi-objective MDVRP model is established with simultaneously minimizing the total driving distance of all vehicles and minimizing the maximum mileage difference between different vehicles based on the shortest path MDVRP model.and the multiobjective LACO(MLACO)is designed to solve it.Finally,the effectiveness of the proposed algorithms are verified by simulation experiments on different scale problems and algorithm comparison results.