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)框架进行全局式研究,并展示了现有的动态框架。

0
下载
关闭预览

相关内容

如何构建你的推荐系统?这份21页ppt教程为你讲解
专知会员服务
65+阅读 · 2021年2月12日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
80+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
250+阅读 · 2020年4月19日
【大规模数据系统,552页ppt】Large-scale Data Systems
专知会员服务
61+阅读 · 2019年12月21日
【新书】Python编程基础,669页pdf
专知会员服务
196+阅读 · 2019年10月10日
机器学习相关资源(框架、库、软件)大列表
专知会员服务
40+阅读 · 2019年10月9日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
机器人开发库软件大列表
专知
10+阅读 · 2018年3月18日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Learning Dynamic Routing for Semantic Segmentation
Arxiv
8+阅读 · 2020年3月23日
Arxiv
7+阅读 · 2018年3月21日
VIP会员
相关VIP内容
如何构建你的推荐系统?这份21页ppt教程为你讲解
专知会员服务
65+阅读 · 2021年2月12日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
80+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
250+阅读 · 2020年4月19日
【大规模数据系统,552页ppt】Large-scale Data Systems
专知会员服务
61+阅读 · 2019年12月21日
【新书】Python编程基础,669页pdf
专知会员服务
196+阅读 · 2019年10月10日
机器学习相关资源(框架、库、软件)大列表
专知会员服务
40+阅读 · 2019年10月9日
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
机器人开发库软件大列表
专知
10+阅读 · 2018年3月18日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Top
微信扫码咨询专知VIP会员