In the last decades, the classical Vehicle Routing Problem (VRP), i.e., assigning a set of orders to vehicles and planning their routes has been intensively researched. As only the assignment of order to vehicles and their routes is already an NP-complete problem, the application of these algorithms in practice often fails to take into account the constraints and restrictions that apply in real-world applications, the so called rich VRP (rVRP) and are limited to single aspects. In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times, and apply a Genetic Algorithm (GA) and Ant Colony Optimization (ACO) individually to the problem to find optimal solutions. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.


翻译:在过去几十年中,对古典车辆运行问题(VRP)进行了深入的研究,即向车辆分配一系列订单和规划其路线,因为仅仅向车辆及其路线分配订单已经是一个NP问题,这些算法的实际应用往往没有考虑到现实应用中适用的制约和限制,即所谓的富富的VRP(rVRP),并局限于单一方面。在这项工作中,我们纳入了与现实世界相关的主要制约和要求。我们提出了一个两阶段战略和时间窗口和暂停时间的时线算法,并单独对问题采用遗传阿尔戈利特姆(GA)和Ant Colony Opptimical(ACO)来寻找最佳解决办法。我们对四种最先进的算法的八个不同问题案例的评估表明,我们的方法在合理的时间里处理所有设定的限制。

0
下载
关闭预览

相关内容

强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
计算机类 | SIGMETRICS 2019等国际会议信息7条
Call4Papers
9+阅读 · 2018年10月23日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
人工智能 | 国际会议/SCI期刊约稿信息9条
Call4Papers
3+阅读 · 2018年1月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2022年1月19日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
计算机类 | SIGMETRICS 2019等国际会议信息7条
Call4Papers
9+阅读 · 2018年10月23日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
人工智能 | 国际会议/SCI期刊约稿信息9条
Call4Papers
3+阅读 · 2018年1月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员