摘要： 传统方法无法有效求解交通道路维护运作中的有补给点及多装载的容量约束弧路径(CARP-RP-ML)问题。为此，提出改进的启发式算法和遗传算法。启发式算法将不同的分割算法用于由所有需求弧随机排序得到的个体上，构造问题的可行解；遗传算法利用分割算法计算其个体适应值，确定对应的可行车辆路径及补给位置，并用局部搜索作为变异算子，进一步扩大搜索空间。数值实验结果表明，与启发式算法相比，遗传算法能更有效地求解CARP-RP-ML问题。

关键词: 容量约束弧路径问题, 组合优化, 启发式算法, 遗传算法, 适应值, 局部搜索

Abstract: 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.

Key words: Capacitated Arc Routing Problem(CARP), combinated optimization, Heuristic Algorithm(HA), Genetic Algorithm(GA), fitness value, local search

中图分类号: 

• TP312