python - 可以多次拜访客户的 CVRP

Question

我想解决一个看起来像具有容量的车辆路径问题 (CVRP) 的问题，但可以多次拜访客户以满足他们的需求。

我有:

• 包含供应商和押金的完整图表 G(V,A)
• cost_matrix M
• 4 辆车，载客量为 Q
• V 上的正函数 f，表示必须为每个客户供应的数量。

我的目标是为所有客户提供 4 辆车。可以用两辆车拜访客户。

总路由距离必须最小化。

我想用python解决这个问题。

我查阅了一些文档(流量问题、TSP、VRP、CVRP 装箱...)。但没有成功。

你知道这个问题有名字吗？如果有记录的话？否则，我应该如何表述这个问题？我应该使用哪个 Python 库？

谢谢!

Answer 1

这是一个分割交付车辆路由问题 (SDVRP)。

这是经典 VRP 的变体，可以多次拜访客户。该问题可以表述为整数线性规划(ILP)，但它仍然是一个 np 难题。

更多详情，您可以引用https://www.sciencedirect.com/science/article/pii/0166218X9200172I .

希望这有帮助。