Research On Multi-objective Multi-depot Capacitated Arc Routing Problem

The capacitated arc routing problem(CARP)is a special vehicle routing problem(VRP).It has wide real-world applications,such as urban waste collection,street sprinkling and winter gritting.The acceleration of new urbanization construction as well as the rapid increase of the urban road area add the environmental pressure.Therefore,the model of CARP,which is one depot or single objective,has come short of the actual needs.It is urgent to be solved for the multi-objective multi-depot CARP in road services.Firstly,this paper analyzes several models of CARP and describes the issue of vehicle transportation considering carbon emissions.We introduce the concept and characteristics of low carbon logistics as well as the method of vehicle carbon emissions calculation.Controlling carbon emissions when solving the path planning problems can alleviate the energy crisis,reduce environmental pollution and save social costs.It can also contribute to the construction of resource-saving and environment friendly type of society.It also studies the multi-objective optimization problems and summarizes three algorithms for solving CARP.Secondly,based on the closed multi-depot capacitated arc routing problem,a multi-objective and multi-depot CARP optimization model with three objectives of economic cost,makespan,and carbon emission cost is proposed considering the carbon emission cost during the driving and service process.Due to the characteristics of proposed model,multi-objective and multi-depot,a novel two-dimensional array solution structure is constructed to improve performance of the multi-objective evolutionary algorithm.Each line represents the route of the vehicle in a depot,which more conveniently shows the relationship between the depot and the route.For the problem of path planning between multiple depots,the boundary arc determination operator considering distance and demand,and the dynamic adjustment strategy of boundary arc are proposed to improve the search ability of algorithms.The local search of the memetic algorithm exhibits poor performance.Therefore,an extended ant colony local search strategy is constructed by combining the ant colony algorithm with the local search algorithm.Based on the above study,we construct a memetic algorithm with multi-depot and improved local search based on decomposition(MDILSMA/D).Finally,we use a certain day’s waste collection instance of the Chicago to test the model and the algorithm.The MDILSMA/D is compared with the other three advanced optimization algorithms of IACO,MD-MAENS and MD-NSGA-III.The experimental results show that MDILSMA/D is significantly better than the other three optimization algorithms when solving the problem of the three depots.Additionally,we conduct experiments on different number of depots instances.It’s demonstrated that MDILSMA/D performs better.This paper can provide some insights for the up-coming road service problems.