algorithm - 多站车辆调度

Question

我一直在研究针对单站点车辆调度问题 (SDVSP) 的算法和 ILP，现在我想将我的知识扩展到多站点车辆调度问题 (MDVSP)，因为我想将这些知识用于我的项目。

至于这个问题，我已经找到并实现了几种用于 MDSVP 的算法。然而，我非常好奇的一个问题是如何确定所需仓库的数量(以及扩展的位置)。可悲的是，我还没有真正找到任何不假设/要求设置仓库的资源。因此，我的问题是:我如何能够接近 MDVSP，在其中我可以确定仓库的数量和位置？

(编辑)澄清:假设我们有一组行程 T₁、T₂...T_n，就像通常在 SDVSP 或 MDVSP 中一样。在返回站点之前可以连续进行多次行程。离开和返回仓库通常只发生在一天的开始和结束时。但作为对正常问题的扩展，我们现在可以确定仓库的数量和位置，而不是设置仓库。

我们的目标是找到一种解决方案，以最低的成本驱动所有行程。成本包括空载量(汽车在行程之间以及往返站点的距离)、每辆车的固定成本 K 和每个站点的固定成本 C。

我希望这能稍微解决这个问题。

Answer 1

标准方法包括添加 |V| ILP 中的二进制变量，每个节点一个，如果 v_i 是一个仓库，则 x_i = 1，否则为 0。

但是，按照目前表述问题的方式，所有 x_i 值都将变为零，因为将节点设为仓库并没有“优势”，总成本 =(其他成本因素)+ sum_i(x_i ) * FIXED_COST_PER_DEPOT。

也许这个问题需要用一些关于汽车范围的其他限制来更新。例如，汽车在返回仓库之前只能行驶某某英里。