The capacitated arc routing problem (CARP) is a challenging combinatorial optimisation problem abstracted from typical real-world applications, like waste collection and mail delivery. However, few studies considered dynamic changes during the vehicles' service, which can make the original schedule infeasible or obsolete. The few existing studies are limited by dynamic scenarios that can suffer single types of dynamic events, and by algorithms that rely on special operators or representations, being unable to benefit from the wealth of contributions provided by the static CARP literature. Here, we provide the first mathematical formulation for dynamic CARP (DCARP) and design a simulation system to execute the CARP solutions and generate DCARP instances with several common dynamic events. We then propose a novel framework able to generalise all existing static CARP optimisation algorithms so that they can cope with DCARP instances. The framework has the option to enhance optimisation performance for DCARP instances based on a restart strategy that makes no use of past history, and a sequence transfer strategy that benefits from past optimisation experience. Empirical studies are conducted on a wide range of DCARP instances. The results highlight the need for tackling dynamic changes and show that the proposed framework significantly improves over existing algorithms.
翻译:电动电弧路由问题(CARP)是一个具有挑战性的组合式优化问题,它来自典型的现实应用,如废物收集和邮件发送等,它是一个具有挑战性的组合式优化问题。然而,很少有研究考虑到车辆服务期间的动态变化,这会使原来的时间表变得不可行或过时。现有的少数研究受到以下因素的限制:可能遭受单一类型动态事件的动态假设,以及依赖特殊操作者或代表的算法,无法从静态的CARP文献所提供的大量贡献中受益。这里,我们为动态的CARP(DCARP)提供了第一个数学配方,并设计了一个模拟系统,以实施CARP(DCARP)解决方案,并用一些共同的动态事件生成DCARP(DCARP)实例。我们随后提出了一个新的框架,能够概括现有的所有静态CARP优化算法,以便它们能够应对DCARP实例。这个框架可以选择在不使用过去历史的重新启用战略的基础上提高DCARP(DCARP)的优化绩效,以及从过去的优化经验中受益的顺序转移战略。正在对广泛的DCARP(C)框架进行全局式研究,并展示了现有的动态框架。