College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China; College of Computer & Information Science, Southwest University, Chongqing 400715, China; School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand
School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand
Evol Comput. 2020 Summer;28(2):289-316. doi: 10.1162/evco_a_00256. Epub 2019 Apr 23.
The uncertain capacitated arc routing problem is of great significance for its wide applications in the real world. In the uncertain capacitated arc routing problem, variables such as task demands and travel costs are realised in real time. This may cause the predefined solution to become ineffective and/or infeasible. There are two main challenges in solving this problem. One is to obtain a high-quality and robust , and the other is to design an effective to adjust the baseline task sequence when it becomes infeasible and/or ineffective during the execution. Existing studies typically only tackle one challenge (the other being addressed using a naive strategy). No existing work optimises the baseline task sequence and recourse policy simultaneously. To fill this gap, we propose a novel proactive-reactive approach, which represents a solution as a baseline task sequence and a recourse policy. The two components are optimised under a cooperative coevolution framework, in which the baseline task sequence is evolved by an estimation of distribution algorithm, and the recourse policy is evolved by genetic programming. The experimental results show that the proposed algorithm, called Solution-Policy Coevolver, significantly outperforms the state-of-the-art algorithms to the uncertain capacitated arc routing problem for the and benchmark instances. Through further analysis, we discovered that route failure is not always detrimental. Instead, in certain cases (e.g., when the vehicle is on the way back to the depot) allowing route failure can lead to better solutions.
不确定容量弧路由问题具有重要意义，因为它在现实世界中有广泛的应用。在不确定容量弧路由问题中，任务需求和旅行成本等变量是实时实现的。这可能导致预定义的解决方案变得无效和/或不可行。解决这个问题有两个主要挑战。一个是获得高质量和鲁棒的解决方案，另一个是设计有效的方法来调整基线任务序列，当它在执行过程中变得不可行和/或无效时。现有研究通常只解决一个挑战（另一个挑战则采用简单的策略）。没有现有的工作同时优化基线任务序列和应对策略。为了填补这一空白，我们提出了一种新的主动-反应方法，将解决方案表示为基线任务序列和应对策略。这两个组件在合作协同进化框架下进行优化，其中基线任务序列由分布估计算法进化，应对策略由遗传编程进化。实验结果表明，称为解决方案-策略协同进化器的算法在不确定容量弧路由问题的基准实例上明显优于最先进的算法。通过进一步分析，我们发现路由失败并不总是不利的。相反，在某些情况下（例如，当车辆在返回仓库的路上时），允许路由失败可以带来更好的解决方案。
