假设您是一家在 Map 上具有固定起始位置的包裹递送公司 . 您必须提供40个包裹，但拥有无限的司机，无限制的汽油，唯一的限制是您希望在车辆总数上放置最少的里程数，每辆车可以容纳16个包裹 . 卡车可以达到18英里/小时，从早上8点开始
在交付计划的某个时刻，将为一个包重新分配一个地址 .
我知道Dijkstra的算法允许我们找到两点之间的最短路径，但我不能想到一种有效的方法，我可以将算法应用于3条独立的路径，这些路径能够在路线上改变并仍然保持最低的里程 .
我可能会过度思考但是有人能指出我正确的方向吗？
1 回答
遗憾的是，这个问题是NP难的，这意味着到目前为止，我们还没有任何算法，这些算法已知是最坏情况有效，确定性且始终正确的 . 也就是说，我们没有类似Dijkstra算法或A *的东西，我们可以从架子上取下并保证从中获得快速的最佳结果 .
话虽如此，这是我们实际上想要定期解决的问题（例如，参见this article about UPS） . 您可能需要考虑使用整数编程求解器，这不能保证有效运行，但实际上通常会这样做 .