求助：如何在Timefold/OptaPlanner中实现开放式回路VRP？

场景1：配送任务（仓库出发，完成任务后不返回） #

• 修改VRP模型约束：直接移除传统闭合VRP中「车辆必须返回仓库」的约束，将车辆终点设为最后一个配送节点即可。
• 成本矩阵调整：无需计算最后一个配送节点返回仓库的成本，仅保留仓库到各配送点、配送点之间的路径成本。
• 算法适配：
  • 启发式算法（如遗传算法、蚁群算法）：终止条件改为车辆完成所有配送任务即结束，无需回到起点。
  • 精确算法（如分支定界）：删除「返回仓库」的变量约束，只保留完成所有配送任务的核心要求。
• 伪代码示例：

  # 配送路径：仓库→配送点1→配送点2→...→最后一个配送点（终点）
  def delivery_route(warehouse, delivery_nodes):
      # 生成包含仓库和配送点的成本矩阵
      cost_matrix = gen_cost_matrix([warehouse] + delivery_nodes)
      current = warehouse
      route = [current]
      unvisited = delivery_nodes.copy()
      
      while unvisited:
          # 每次选择当前点到未访问点的最小成本节点
          next_node = min(unvisited, key=lambda x: cost_matrix[current][x])
          route.append(next_node)
          unvisited.remove(next_node)
          current = next_node
      return route
  

场景2：次日揽收任务（从揽收点出发，最终抵达仓库） #

• 反向建模逻辑：将仓库固定为最终终点，把所有揽收点作为起点集合，路径规划目标变为「从任意揽收点出发，遍历所有揽收点后抵达仓库」。
• 成本矩阵调整：计算各揽收点之间、揽收点到仓库的路径成本，无需考虑仓库到揽收点的成本。
• 算法适配：
  • 启发式算法：将终点固定为仓库，路径生成时确保最后一步是从某揽收点到仓库；若要选最优起始点，可遍历所有揽收点作为起点，对比总路径成本后取最小值。
  • 工具库配置：若用OR-Tools这类工具，可将仓库设为唯一终点，把揽收任务配置为从各个节点出发的集合任务。
• 伪代码示例：

  def pickup_route(pickup_nodes, warehouse):
      min_total_cost = float('inf')
      best_route = []
      
      # 遍历每个揽收点作为起点，寻找最优路径
      for start in pickup_nodes:
          unvisited = [n for n in pickup_nodes if n != start]
          current = start
          route = [current]
          total_cost = 0
          
          # 遍历所有未访问的揽收点
          while unvisited:
              next_node = min(unvisited, key=lambda x: calc_cost(current, x))
              total_cost += calc_cost(current, next_node)
              route.append(next_node)
              unvisited.remove(next_node)
              current = next_node
          # 最后前往仓库
          total_cost += calc_cost(current, warehouse)
          route.append(warehouse)
          
          if total_cost < min_total_cost:
              min_total_cost = total_cost
              best_route = route
      return best_route
  

通用注意事项 #

• 保留车辆容量/载重约束，避免配送或揽收时超载；
• 若有时间窗要求，路径规划时需加入节点访问时间的检查逻辑；
• 第三方工具库适配：比如OR-Tools中可通过设置vehicle.return_to_depot = False关闭返回仓库要求，揽收任务则调整任务的起始/终点配置即可。

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