python - 带时间窗的车辆路线在 Python 中实现

Question

我正在研究一个用例，其中我有多个车辆作为仓库、送货员和来自不同地点的一组客户来提供新鲜食物。客户从应用程序下订单，然后送货员收到订单并从 Van 获取食物，然后在承诺的交货时间（15 分钟）内交付。我想优化这个问题，以便降低旅行的运营成本并最大限度地缩短交货时间。只是想知道 Python 中是否有任何实现来解决 VRPTW 问题？请帮忙

Answer 1

你可以在 python 中找到 Dijkstra 最短路径算法的实现。

一个示例实现是

http://code.activestate.com/recipes/577506-dijkstra-shortest-path-algorithm/

Answer 2

如果您想解决路线问题，首先要弄清楚您要解决的车辆路线问题的变体。我将假设货车是静止的（即您也没有尝试优化货车本身的定位）。首先，问题是动态的，因为它是实时发生的——即它是一个实时路线优化问题。如果送货人员被预先分配到一辆面包车上，那么这可能被认为是一个动态的多程车辆路线问题（显然有时间窗）。一般来说，虽然这是一个动态的取货和送货车辆路线问题，但据推测送货人员可以从不同的货车上取货（所以 DPDVRPTW）。您几乎肯定也需要软时间窗，使其成为具有软时间窗的 DPDVRP。软时间窗口是必不可少的，因为在实时环境中，您通常希望尽可能快地交付，因此希望尽量减少迟到的时间。像 VRPTW 中的正常“硬”时间窗口不允许您在特定时间后交付，但在此时间之前交付不会产生成本损失（即它们是二进制的）。因此，您不能使用它们来最大程度地减少延迟。

恐怕我不知道 Python 或任何其他语言中的任何开源求解器可以解决具有软时间窗的动态取货和送货车辆路线问题。

这篇调查文章很好地概述了该主题。我们还发布了关于开发实时路由优化器的白皮书，这可能比学术论文更容易阅读。（免责声明 - 我是本白皮书的作者）。

Answer 3

阅读一些关于车辆路径问题的研究论文。我已经看到一些论文提供了关于车辆路线的完整算法，并且它们通过考虑多个标准以不同的方式出现。因此，可以实现这些论文中提供的一种或多种算法，并进行测试以使用最佳解决方案。