洒水车作业路线规划的复杂CARP问题求解  

Solution for complicated CARP of route planning of sprinklers

作　　者：朱征宇[1] 谢志华[1] 杨永[1] 夏梦霜[1] 李小花[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机应用》2008年第3期768-772,共5页journal of Computer Applications

基　　金：高等学校博士学科点专项科研基金资助项目(20030611016);重庆大学骨干教师资助计划项目(2003A33)

摘　　要：作为容量限制弦路径车辆行驶问题(CARP)的一种实际应用,洒水车路线规划涉及多车型、多路型、转弯限制等因素,属于复杂的CARP问题。对此,提出了一种高性能遗传算法(HEGA),以传统遗传算法为基础,对种群机制和染色体结构及交叉操作进行改进,并引入局部搜索(LS)操作增强算法的寻优能力。根据真实数据进行实验,获得了比人工更优的解决方案。最后的对比实验验证了算法具有较高的求解精度。As a kind of Capacitated Arc Routing Problem （CARP） application, route planning of sprinklers involves many factors such as multi-type vehicle, multi-type road, turn prohibition, and so on, and it is a complicated CARP. A algorithm called High Efficient Genetic Algorithm （HEGA） was presented, which was based on traditional genetic algorithm. HEGA improved the population mechanism, structure of chromosome and crossover operation, and then introduced a kind of operation called Local Search （LS） to enhance the ability of searching optimal value. An experiment adopting real data shows that HEGA gains a better plan than manual assignment originally. At last, another comparison experiment between two algorithms proves that HEGA can get quite high accuracy of solution.

关 键 词：复杂容量限制弦路径车辆行驶问题 多车型 高性能遗传算法 重优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]