基于Optaplanner实现带收益的车辆路径规划问题（VRPP）

1. 调整领域模型 #

• 给客户实体新增两个核心字段：profit（访问该客户可获得的收益），同时修改链式规划变量（比如previousVisit），设置nullable = true——未纳入路径的客户，其previousVisit和nextVisit都为null，不属于任何车辆的路径链，无需额外创建虚拟节点。

2. 重构分数计算逻辑 #

• 移除原VRP-TW中"所有客户必须被分配"的硬约束，改成可选逻辑。
• 软约束核心逻辑：总收益 = 所有已分配客户的收益总和 - 路径行驶成本（距离/时间等），目标是最大化这个值。
• 用Constraint Streams实现示例：

  // 奖励已分配客户的收益
  Constraint rewardCustomerProfit(ConstraintFactory factory) {
      return factory.from(Customer.class)
          .filter(customer -> customer.getPreviousVisit() != null) // 筛选已分配客户
          .reward("Customer Profit", HardSoftScore.ONE_SOFT, Customer::getProfit);
  }
  
  // 惩罚路径行驶成本
  Constraint penalizeTravelCost(ConstraintFactory factory) {
      return factory.from(Customer.class)
          .filter(customer -> customer.getPreviousVisit() != null && !(customer.getPreviousVisit() instanceof Vehicle))
          .join(Customer.class, Joiners.equal(Customer::getPreviousVisit))
          .penalize("Travel Cost", HardSoftScore.ONE_SOFT, (current, previous) -> calculateTravelCost(previous, current));
  }
  

  注：calculateTravelCost是自定义的路径成本计算方法。

3. 修改初始化策略 #

• 原VRP初始化会强制把所有客户塞进路径链，现在改成部分初始化：
  • 方法一：规划变量设置nullable = true后，OptaPlanner默认初始化器会自动将部分客户设为未分配状态，可通过配置调整比例。
  • 方法二：自定义SolutionInitializer，优先将高收益客户纳入路径，低收益客户留待后续移动调整，比如先筛选收益高于平均成本的客户初始化到链中。

4. 适配移动策略 #

• 启用支持"添加/移除客户"的移动类型：
  • ChangeMove：可将未分配客户分配到路径任意位置，或把已分配客户从路径中移除（设previousVisit为null）。
  • TailChainSwapMove：保留原链交换逻辑，优化已分配客户的路径顺序。
• 在Solver配置中添加对应移动工厂即可：

  <moveListFactory>
      <moveListFactoryClass>org.optaplanner.examples.vehiclerouting.domain.move.CustomerChangeMoveFactory</moveListFactoryClass>
  </moveListFactory>
  <moveListFactory>
      <moveListFactoryClass>org.optaplanner.examples.vehiclerouting.domain.move.TailChainSwapMoveFactory</moveListFactoryClass>
  </moveListFactory>
  

关于实现案例 #

不少开发者用OptaPlanner实现过VRPP，核心思路都是上述几点：放开客户分配的强制性，用收益-成本差值作为核心优化目标，通过调整规划变量和约束逻辑实现需求。你可以基于官方VRP示例直接改造，无需从零搭建。

内容的提问来源于stack exchange，提问作者elk-tamer