多滴多车辆的路由算法

Question

我正在寻找/创建一种路由算法,该算法可用于管理执行交付的多辆货车以及每辆货车的负载.

这是我正在寻找的粗略规范..

• 应以快速有效的方式计算路线
• 可以一次处理100多个货车/ 1000+包/ 1000+下降点
• 每辆货车可能有不同的尺寸,并有不同的重量限制
• 每个包装可以是不同的尺寸和重量
• 考虑到路线,重量和尺寸限制,应以公平和经济的方式将包裹整理到货车上
• 货车应采取的路线应该是经济的并且尽可能短(或两者之间的可配置平衡)
• 货车可能仅限于某些道路(低桥,宽度,高度和重量限制)
• 一些包裹可能会被给予时间段以便递送

有没有人见过这种事情,如果有的话,有什么算法可以用来做这个,还是一个如何做的例子？我已经看过一些大学论文,但它们已经很老了(现在可能效率很低)并且没有处理包管理 - 他们只是假设所有的面包车和包装都是相同的尺寸.

任何想法将不胜感激!

丰富

Answer 1

我的印象是这种问题通常出现在Operations Research中,标准方法是使用混合整数编程求解器.这是使用MIP编码货运计划问题的示例

显然,最近在MIP进行的15年研究使得现代求解器比原始求解器快30,000倍.

如果你想从头开始制作解决方案,你可以先弄清楚你的目标和约束是什么,然后使用整数编程中的一些想法,比如近似的分支定界搜索.