我有
- 一个仓库
- 一个运输车队，每辆最多可运载 10 吨
- 几个客户。
我怎样才能最大限度地增加运输车的负载并最大限度地减少旅行？
到目前为止，我使用 1d bin-packing对运输机进行分组，并使用蚁群优化来缩短行程，但感觉不对。我读过背包算法？我能做得更好吗？
问问题
4408 次
4 回答
4
这是经典的车辆路径问题（VRP）。对于中小型实例，您可以通过制定（混合）整数问题并使用 MIP 求解器（例如 Gurobi）找到最佳解决方案。
应用启发式是很常见的。但是，它们不一定会产生最佳解决方案。该领域最重要的启发式算法是禁忌搜索、模拟退火和受生物学启发的各种算法。事实证明，这些启发式方法产生了相当好的解决方案，当涉及具有许多侧面约束的大规模问题时，它们是无可替代的。对于许多问题，它们甚至会产生最佳解决方案，但通常很难证明。
然而，理解和实现这些算法并不是一天的事情。
我实现了一个名为jsprit的项目。jsprit 是一个轻量级的 java 工具包，可以解决您的问题，并让您分析生成的解决方案，例如通过可视化它们。它使用了一个大型邻域搜索，它结合了模拟退火和阈值接受（此处引用了应用的算法原理）。您将找到许多帮助您解决问题的示例。
一个简单的方法是在考虑车辆的固定成本的同时，尽量减少可变成本（无论您的成本衡量标准是什么，例如距离、时间、燃料或综合衡量标准）。我相信您最终会得到一个“最大限度地减少旅行”并适当利用您的运输工具的解决方案。如果您在设置问题时遇到问题，请随时直接与我联系。
于 2013-12-13T16:51:06.893 回答
3
你的问题可以用这个免费的软件来解决，用于解决 Java 中的 VRP https://jsprit.github.io或 Lisp 中的https://github.com/mck-/Open-VRP。
于 2014-02-12T00:08:17.360 回答
1
A* 搜索（修改为最大成本路径）与 Microsoft Research 论文中描述的最短路径算法的组合可能值得研究： http ://research.microsoft.com/pubs/154937/soda05.pdf
于 2012-12-07T21:10:58.463 回答
1
我认为您的问题没有完美的解决方案。如果我做对了，你的问题就是帕累托最优。您可以优化您的路线或负载或您需要的车队数量（侧面限制日常工作时间可能也是一个问题）。您必须重视自己更重要的事情，例如由于燃料成本而缩短的路线，更少的汽车等等。
在我看来，您应该对您的客户进行地理分区，每个分区的负载总和不大于 10 吨。之后，您可以在那个小问题上使用 TSP 来计算出完美的路线。主要的“魔法”是在分区步骤中完成的，如果你以一种好的方式解决了这个问题，你的问题可能会消失。
希望有帮助
于 2012-12-19T09:20:06.707 回答