摘要
传统方法无法有效求解交通道路维护运作中的有补给点及多装载的容量约束弧路径(CARP-RP-ML)问题。为此,提出改进的启发式算法和遗传算法。启发式算法将不同的分割算法用于由所有需求弧随机排序得到的个体上,构造问题的可行解;遗传算法利用分割算法计算其个体适应值,确定对应的可行车辆路径及补给位置,并用局部搜索作为变异算子,进一步扩大搜索空间。数值实验结果表明,与启发式算法相比,遗传算法能更有效地求解CARP-RP-ML问题。
Capacitated Arc Routing Problem with Refill Points and Multiple Loads（CARP-RP-ML）,stems from road network maintenance,is the CARP with refill vehicles which can refill several times because of multiple loads.A heuristic and genetic algorithm is proposed to solve CARP-RP-ML.The Heuristic Algorithm（HA） adapts a split algorithm,designed based on two types of vehicle,on each random permutated individual to construct the feasible solution of the problem.The Genetic Algorithm（GA） uses the split algorithm described in heuristic algorithm to calculate the fitness of individuals and to determine feasible vehicle routes and replenishment locations,and adopts local search as the mutation to expand search space.Experimental results show that GA outperforms HA,which demonstrates that GA can more efficiently solve CARP-RP-ML.
出处
《计算机工程》
CAS
CSCD
2012年第7期168-170,共3页
Computer Engineering
基金
教育部留学回国人员基金资助项目
关键词
容量约束弧路径问题
组合优化
启发式算法
遗传算法
适应值
局部搜索
Capacitated Arc Routing Problem（CARP）
combinated optimization
Heuristic Algorithm（HA）
Genetic Algorithm（GA）
fitness value
local search
