如何用OR-Tools和Google距离矩阵构造固定起点任意终点的VRP

问题背景 #

多司机带取派件场景下，要求司机起点为当前实时位置，终点无需返回起点可在任意点位结束。原有实现输出为闭环路线，需通过构造特殊距离矩阵实现终点清零效果，但OR-Tools官方的虚拟节点方案会破坏原有索引到经纬度点位的映射逻辑。

实现方案 #

核心思路 #

仅在求解阶段临时扩展虚拟节点，不改动原有真实点位的索引规则，求解完成后过滤虚拟节点即可复用原有映射逻辑。

操作步骤 #

1. 距离矩阵扩展
   原有逻辑生成NN的真实点位距离矩阵后，在矩阵最后新增1行和1列，所有值设为0，得到(N+1)(N+1)的扩展矩阵，新增的第N位索引为虚拟终点。
2. 求解参数配置
   调用OR-Tools求解时，所有车辆的起点仍设置为司机位置对应的原有真实索引，所有车辆的终点统一设置为新增的虚拟节点索引N。
3. 映射逻辑适配
   求解得到路线后，先移除路线末尾的虚拟节点N，剩余索引完全匹配原有真实点位的索引规则，无需改动原有映射逻辑的主体部分。

代码示例 #

距离矩阵扩展代码

# 调用原有逻辑生成原始距离矩阵
original_distance_matrix = create_distance_matrix()
real_point_num = len(original_distance_matrix)
# 扩展每一行的最后一列设为0
for row in original_distance_matrix:
    row.append(0)
# 新增最后一行全为0
original_distance_matrix.append([0]*(real_point_num + 1))
# 扩展后的矩阵传入OR-Tools求解
final_distance_matrix = original_distance_matrix

映射代码适配

仅需在原有映射逻辑中新增过滤虚拟节点的步骤即可：

def get_deliverer_route(routes):
  # 原有地址列表保持不变
  addresses = [{'deliverer_12': '30.588306869629527%2C31.47918156839698'}, 
               {'13_pickup': '30.073040504782547%2C31.345765282277267'}, 
               {'13_dropoff': '30.068329781020058%2C31.323759091237868'}, 
               {'14_pickup': '30.073040504782547%2C31.345765282277267'}, 
               {'14_dropoff': '30.062493604295614%2C31.34477108388055'}, 
               {'15_pickup': '30.073040504782547%2C31.345765282277267'}, 
               {'15_dropoff': '30.09912973586751%2C31.315054495649424'}, 
               {'16_pickup': '30.584087371098757%2C31.50439621285545'}, 
               {'16_dropoff': '30.596311789481327%2C31.488618697512486'}, 
               {'17_pickup': '30.584087371098757%2C31.50439621285545'}, 
               {'17_dropoff': '30.548610813018943%2C31.834700566824836'}]
  real_point_num = len(addresses)
  route_table = []
  for idx in range(len(routes)):
    # 司机点位映射逻辑保持不变
    address = addresses[idx]
    for key, value in address.items():
      single_loc = {}
      k = key.split('_')
      single_loc['deliverer_id'] = k[1]
      single_loc['coordinates'] = value.replace('%2C', ',')
      route_table.append([single_loc])
    # 处理路线
    route = routes[idx]
    route.pop(0) # 移除重复的起点
    # 新增：过滤末尾的虚拟节点
    if route and route[-1] == real_point_num:
        route.pop(-1)
    # 原有订单点位映射逻辑保持不变
    for n in route:
      order_address = addresses[n]
      for key, value in order_address.items():
        single_loc = {}
        k = key.split("_")
        single_loc["order_id"] = k[0]
        single_loc["coordinates"] = value.replace('%2C', ',')
        single_loc["type"] = k[1]
        route_table[idx].append(single_loc)
  return route_table

内容的提问来源于stack exchange，提问作者Rawan G