使用Google Or-Tools求解移除Depot约束的VRP问题

这个问题是可解的，它属于多车场VRP（Multi-Depot VRP, MDVRP）的变体——每个车场（始发地）仅对应一辆车，且所有始发地不重复。虽然复杂度确实高于传统单depot VRP，但现有算法框架完全可以适配改造。

核心修正思路 #

你之前尝试的“将depot与各地点距离设为0”的方案之所以失效，是因为它混淆了“统一depot”和“多专属始发地”的逻辑，无法绑定每辆车的起止点为同一专属地点。正确的做法是直接为每辆车定义独立的起止约束，而非依赖虚拟depot。

具体实现方案 #

1. 小规模问题：整数规划建模

直接构建明确的约束模型，以Gurobi/CPLEX这类求解器为例：

• 决策变量：
  • x_ij^k：1表示车辆k从地点i行驶到j，0否则
  • y_ik：1表示任务点i分配给车辆k，0否则
• 约束条件：
  • 每个任务点仅被一辆车访问：Σ_k y_ik = 1 对所有任务点i
  • 车辆k的路径闭环：起点S_k的出度=1、入度=1；终点S_k的入度=1、出度=1；其他分配给k的节点入度=出度
  • 车辆仅访问分配给自己的节点：Σ_j x_ij^k = y_ik、Σ_j x_ji^k = y_ik 对所有任务点i和车辆k
• 目标函数：min(max_k (Σ_{i,j} x_ij^k * t_ij))，其中t_ij是i到j的行驶耗时

2. 大规模问题：启发式/元启发式算法

当任务点数量较多时，整数规划求解效率不足，优先用启发式方法：

• 初始解生成：
  1. 用聚类算法（如K-means，基于任务点到各始发地的距离）将任务点分配给对应车辆，保证每辆车的初始任务集离其始发地较近
  2. 对每辆车的子问题，用TSP求解器（如LKH、Concorde）生成从始发地出发、返回始发地的闭环路径
• 迭代优化：
  聚焦于缩短最长路径：每次找到当前耗时最长的车辆，尝试将其部分任务点转移给路径较短的车辆，再重新优化这两辆车的路径；或对最长路径内部进行节点重排、反转等邻域操作，逐步降低整体最大耗时

3. 工具适配技巧

用开源VRP工具时，无需虚拟depot，直接指定车辆专属起止点：

• 比如Google OR-Tools，为每辆车设置vehicle.start = S_k和vehicle.end = S_k，同时关闭默认的统一depot配置
• 用PyVRP这类库时，在问题初始化阶段为每个车辆单独定义起止位置，而非使用全局depot

内容的提问来源于stack exchange，提问作者Andrea Nucci