基于多可选地点的OptaPlanner车辆路径规划优化问题咨询

1. 核心模型调整：区分必访与可选节点 #

• 把配送包裹（必访）和可选空地点统一抽象为Location实体，通过标记区分类型：

  public class Location {
      private boolean mandatory; // true=必须配送的包裹点，false=可选空地点
      private int demand; // 包裹点有载重需求，可选地点需求为0
      // 坐标、唯一ID等其他属性
  }
  

• 不要提前将订单分配到可选地点，让OptaPlanner自主决定哪些可选地点纳入路径，以及所有节点的顺序。

2. 变量与约束的正确配置 #

• 规划变量定义：在Vehicle类中用@PlanningListVariable直接关联Location列表，覆盖所有必选和可选地点：

  public class Vehicle {
      private int capacity;
      @PlanningListVariable(valueRangeProviderRefs = {"allLocations"})
      private List<Location> route;
      // getter/setter及其他属性
  }
  

  这里的allLocations是包含所有必选包裹点和可选空地点的数据源。
• 约束实现：
  • 硬约束1：确保所有必选节点被访问

    private Constraint mandatoryNodesMustBeVisited(ConstraintFactory factory) {
        return factory.forEach(Location.class)
                .filter(Location::isMandatory)
                .filter(location -> !isInAnyVehicleRoute(location))
                .penalize("Mandatory node missing", HardScore.ONE);
    }
    

  • 硬约束2：控制车辆载重不超限

    private Constraint vehicleCapacityLimit(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .filter(vehicle -> calculateTotalDemand(vehicle.getRoute()) > vehicle.getCapacity())
                .penalize("Over capacity", HardScore.ONE,
                        vehicle -> calculateTotalDemand(vehicle.getRoute()) - vehicle.getCapacity());
    }
    

  • 软约束：最小化路径总距离

    private Constraint minimizeTotalDistance(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .penalize("Total route distance", SoftScore.ONE,
                        vehicle -> calculateRouteTotalDistance(vehicle.getRoute()));
    }
    

3. 解决列表变量无优化效果的问题 #

• 检查算法配置：列表变量需要适配CHANGING_LIST类型的启发式算法，示例配置：

  <solver>
      <constructionHeuristic>
          <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
      </constructionHeuristic>
      <localSearch>
          <localSearchType>TABU_SEARCH</localSearchType>
          <acceptor>
              <tabuSize>8</tabuSize>
          </acceptor>
      </localSearch>
  </solver>
  

• 排查约束逻辑：如果约束未触发，检查过滤条件（如isInAnyVehicleRoute的实现）、需求/距离计算是否存在错误。
• 移除提前绑定：不要预先固定订单到可选地点，否则会限制算法的优化自由度。

4. 关于getRoute()的误区 #

getRoute()只是Vehicle类中存储规划后路径的属性，OptaPlanner的优化逻辑不依赖这个方法的命名或初始内容。你完全可以让它只包含最终选中的必选+可选节点，而非所有待访问地点，完全适配你的场景需求。

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