Study On The Heterogeneous Vehicle CARP Problem Optimization Based On Memetic Algorithm

Capacitated Arc Routing Problem(CARP)has a wide range of applications in real life,which is of great significance to alleviate the energy crisis,improve production efficiency and create a conservation-oriented society.However,many practical problems can't be solved by the basic CARP model.Therefore,the extended CARP model is more and more important for the increase of the constraint condition.There are many extended CARP models,such as multi-center CARP model,multi-vehicle CARP model,multi-period CARP model,uncertain CARP model and so on.Basic CARP model research has become more mature,but the extension of CARP model-related research resultsare not many.This dissertationmakes an in-depth study on the Heterogeneous Vehicle Capacitated Arc Routing Problem(HVCARP)in the common extended CARP model.We propose an effect memetic algorithm called MAEVSGR for HVCARP.First,the cost of any route in HVCARP is divided into two parts,variable cost and fixed cost,and penalty coefficients for vehicles keep the routes and their vehicles close.In view of the characteristic of HVCARP,we propose a local search operator,namely Exchanging Vehicles among Same Group Routes(EVSGR)for the vehicle,which adjusts the vehicles for routes based on the loads and vehicles of the routes so as to minimize the cost.Then,the EVSGR operator is integrated into memetic algorithm(MA),and the resultant algorithm is used to solve HVCARP.Finally,the proposed algorithm is run on the instances modified from the instances of the benchmark data sets for CARP,and a large number of experimental results show that the EVSGR operator based memetic algorithm is effective for HVCARP.For the uncertain CARP model,this dissertationdescribes the definition of the basic uncertain CARP model.And then it introduced several common uncertainty evaluation criteria.Finally,an uncertain heterogeneous vehicle CARP model is proposed based on the heterogeneous vehicle CARP model.