Abstract: In view of wider application background，heterogeneous vehicle capacitated arc routing problem (HVCARP) and approach for it are investigated in this paper. First, the cost of any route in HVCARP is divided into two parts, i.e., 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.

Key words: capacitated arc routing problem(CARP), heterogeneous vehicle, memetic algorithm, exchanging vehicles among same group routes