车辆路径算法？

Question

我有过

• 仓库
• 一支运输队，每个运输队最多可载重10吨
• 几个顾客。

我怎样才能最大限度地增加运输机的载重量，并尽量减少旅行？

到目前为止，我使用一个一维垃圾箱包装，以分组运输和蚁群优化，以缩短旅游，但它感觉不对。我读过背包算法吗？我能做得更好吗？

Answer 1

它是经典的车辆路径问题(VRP)。对于中小型实例，您可以通过构造一个(混合)整数问题并使用MIP-求解器(如Gurobi )来找到最优解。

应用启发式方法是很常见的。然而，它们不一定能产生最佳解决方案。这一领域中最重要的启发式算法是禁忌搜索、模拟退火和各种受生物学启发的算法。事实证明，这些启发式方法产生了相当好的解决方案，当涉及到具有多个边约束的大规模问题时，它们是无可替代的。对于许多问题，它们甚至产生了最优解，但这往往是很难证明的。

然而，理解和实现这些算法并不是一天的事情。

我实现了一个名为jsprit的项目。jsprit是一个轻量级的java工具包，可以解决您的问题，并允许您分析生成的解决方案，例如可视化它们。该算法采用了模拟退火和阈值接受相结合的大邻域搜索方法(参考了应用的算法原理)。您将发现一些帮助您实现问题的示例。

对于你来说，一个简单的方法是尽量减少可变成本(不管你的成本是多少，比如距离、时间、燃料或一种综合措施)，同时考虑你的车辆的固定成本。我相信你最终会找到一个“尽量减少旅游”的解决方案，并以赞成的方式利用你的运输工具。如果你在设置你的问题上有问题，不要犹豫直接联系我。

Answer 2

您的问题可以通过此免费软件解决，用于解决https://jsprit.github.io中的VRP https://jsprit.github.io或Lisp中的https://github.com/mck-/Open-VRP。

Answer 3

如本文所述，将A*搜索(修改为最大成本路径)与最短路径算法相结合可能值得研究：http://research.microsoft.com/pubs/154937/soda05.pdf