我想解决一个看起来像具有容量的车辆路径问题 (CVRP) 的问题,但可以多次拜访客户以满足他们的需求。
我有:
- 包含供应商和押金的完整图表 G(V,A)
- cost_matrix M
- 4 辆车,载客量为 Q
- V 上的正函数 f,表示必须为每个客户供应的数量。
我的目标是为所有客户提供 4 辆车。可以用两辆车拜访客户。
总路由距离必须最小化。
我想用python解决这个问题。
我查阅了一些文档(流量问题、TSP、VRP、CVRP 装箱...)。但没有成功。
你知道这个问题有名字吗?如果有记录的话?否则,我应该如何表述这个问题? 我应该使用哪个 Python 库?
谢谢!
最佳答案
这是一个分割交付车辆路由问题 (SDVRP)。
这是经典 VRP 的变体,可以多次拜访客户。 该问题可以表述为整数线性规划(ILP),但它仍然是一个 np 难题。
更多详情,您可以引用https://www.sciencedirect.com/science/article/pii/0166218X9200172I .
希望这有帮助。
关于python - 可以多次拜访客户的 CVRP,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59522296/