algorithm - 多车多落差的路径算法

Question

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

这是我要寻找的内容的粗略说明..

• 应该以快速有效的方式计算路线
• 一次性处理 100 多辆货车/1000 多个包裹/1000 多个下车点
• 每辆面包车的尺寸和重量限制可能不同
• 每个包裹的尺寸和重量可能不同
• 应以公平和经济的方式将包裹组织到货车上，同时考虑路线、重量和尺寸限制
• 面包车应该走的路线应该是经济的并且尽可能短(或者两者之间的可配置平衡)
• 货车可能仅限于某些道路(低桥、宽度、高度和重量限制)
• 有些包裹可能会指定送货时间段

有没有人以前见过这种事情，如果有，关于可以使用什么算法来做这件事的任何想法，或者如何做的例子？我看过一些大学论文，但它们已经很老了(现在可能效率很低)并且不处理包裹管理 - 他们只是假设所有货车和包裹的尺寸都相同。

如有任何想法，我们将不胜感激!

丰富

Answer 1

我的印象是这种问题经常出现在运筹学中，标准方法是使用混合整数规划求解器。这是 an example使用 MIP 对 cargo 调度问题进行编码

显然最近 15 年的 MIP 研究造就了现代求解器 30,000比原来快 1 倍。

如果您想从头开始制定解决方案，您可以先弄清楚您的目标和约束是什么，然后使用整数规划中的一些想法，例如近似分支定界搜索。