Research Of Meta-heuristic On Split-delivery Capacitated Arc Routing Problem

Arc Routing Problem is a combinatorial optimization problem and noticed by the most scholars in operations research due to the widely application on transportation. In this paper,we mainly study the capacitated arc routing problem and the split-delivery capacitated arc routing problem. The two problems are usually applied on postal deliveries, urban waste collection, and winter gritting.In the research of the capacitated arc routing problem, This paper proposes a parallel algorithm called Parallel Evolutionary Algorithm which applies parallel computing on memetic algorithm for the CARP. The computational results on the instances of standard benchmarks show that the proposed algorithm is feasible and effective and also can save time.In the research of the split-delivery capacitated arc routing problem, this paper presents a intermediate model to transfer CARP to SDCARP and then solve the problem by an new algorithm which combines the iterated local search and the crossover procedure. The computational results on 63 instances of standard benchmarks of CARP show that the proposed algorithm outperforms most of the existing best-known solutions obtained by other heuristics within a reasonable computing time. Furthermore, compared with the CARP solutions,our algorithm finds three optimums for the SDCARP.