1

我想解决一个看起来像载客车辆路线问题 (CVRP) 的问题,但可以多次访问客户以便满足他们的需求。

我有:

  • 包含供应商和存款的完整图 G(V,A)
  • 成本矩阵 M
  • 4辆容量Q的车辆
  • V 上的正函数 f,表示必须为每个客户提供的数量。

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

总路由距离必须最小化。

我想用python解决这个问题。

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

你知道这个问题是否有名字吗?如果记录在案?否则,我应该如何制定问题?我应该使用哪个 Python 库?

谢谢 !

4

1 回答 1

1

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

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

更多详情,您可以参考https://www.sciencedirect.com/science/article/pii/0166218X9200172I

希望这可以帮助。

于 2020-01-14T14:04:10.650 回答