一种求解多车型CARP问题的高效进化算法

High efficient evolutionary computing method for solving multi-vehicle CARP

对传统遗传算法的染色体编码机制和种群结构进行了改进,并借鉴单亲遗传算法和Memetic Algorithm(MA)算法的优秀思想,设计了一种解决CARP(Capacitated ArcRouting Problem)问题的高效算法HEGA。新算法不但有效解决了使用现有算法无力解决的多车型CARP问题,并且应用于一般的单车型CARP问题在求解效率和求解精度上也比现有MA算法效果更好。结合洒水车路径优化问题,通过一组真实的数据集合对文中算法在该问题上的求解能力做出评测。

This paper produces a new algorithm called HEGA for solving the CARP（Capacitated Arc Routing Problem）.The new algorithm improves the method of coding chromosomes and structure of population in traditional genetic algorithm,and some of its ideas derive from Partheno-Genetic Algorithm（PGA） and memetic algorithm.HEGA can solve the multi-vehicle CARP which is hardly to be solved by existing algorithms,in solving general CARP,its efficiency and accuracy are more excellent as well.Related with a typical case of optimizing the routings of sprinkler cars,the new method is evaluated with a real set of data.