IEEE Trans Syst Man Cybern B Cybern. 2011 Dec;41(6):1654-67. doi: 10.1109/TSMCB.2011.2158307. Epub 2011 Jul 14.
This paper investigates the Periodic Capacitated Arc Routing Problem (PCARP), which is often encountered in the waste collection application. PCARP is an extension of the well-known Capacitated Arc Routing Problem (CARP) from a single period to a multi-period horizon. PCARP is a hierarchical optimization problem which has a primary objective (minimizing the number of vehicles ) and a secondary objective (minimizing the total cost ). An important factor that makes PCARP challenging is that its primary objective is little affected by existing operators and thus difficult to improve. We propose a new Memetic Algorithm (MA) for solving PCARP. The MA adopts a new solution representation scheme and a novel crossover operator. Most importantly, a Route-Merging (RM) procedure is devised and embedded in the algorithm to tackle the insensitive objective . The MA with RM (MARM) has been compared with existing meta-heuristic approaches on two PCARP benchmark sets and a real-world data set. The experimental results show that MARM obtained better solutions than the compared algorithms in much less time, and even updated the best known solutions of all the benchmark instances. Further study reveals that the RM procedure plays a key role in the superior performance of MARM.
本文研究了周期性容量弧路由问题（PCARP），该问题在垃圾收集应用中经常遇到。PCARP是著名的容量弧路由问题（CARP）从单周期到多周期的扩展。PCARP是一个分层优化问题，有一个主要目标（最小化车辆数量）和一个次要目标（最小化总成本）。使PCARP具有挑战性的一个重要因素是其主要目标受现有算子影响很小，因此难以改进。我们提出了一种新的用于求解PCARP的混合算法（MA）。该混合算法采用了一种新的解表示方案和一种新颖的交叉算子。最重要的是，设计了一种路由合并（RM）过程并将其嵌入算法中以处理不敏感目标。将带有RM的混合算法（MARM）与现有的元启发式方法在两个PCARP基准集和一个真实数据集上进行了比较。实验结果表明，MARM在更短的时间内获得了比比较算法更好的解，甚至更新了所有基准实例的已知最优解。进一步的研究表明，RM过程在MARM的优越性能中起着关键作用。
