JSprit中条件时间窗口的实现与扩展点咨询

核心思路 #

你对JSprit时间窗口机制的理解是准确的：时间窗口的可行性由插入算法+硬约束共同作用，条件时间窗口需要在插入阶段就动态匹配车辆类型对应的时段，而非仅靠硬约束事后拦截非法解。

方案1：通过扩展点注入自定义插入计算器（推荐） #

JSprit本身提供了替换插入计算器的扩展点，完全无需fork库。具体步骤如下：

• 自定义插入计算器：无需从零实现，直接继承默认的DefaultServiceInsertionCalculator和DefaultShipmentInsertionCalculator，在计算插入可行性前，根据当前车辆类型动态替换作业的时间窗口。
  示例代码（以Service为例）：

  public class ConditionalTWServiceInsertionCalculator extends DefaultServiceInsertionCalculator {
      // 存储作业ID+车型ID到对应时间窗口的映射
      private final Map<String, TimeWindow> conditionalTWMap;
  
      public ConditionalTWServiceInsertionCalculator(Map<String, TimeWindow> conditionalTWMap) {
          this.conditionalTWMap = conditionalTWMap;
      }
  
      @Override
      public InsertionData calculateInsertion(Job job, VehicleRoute route, Vehicle vehicle, double newDepTime, Driver driver, double cost, TransportCosts transportCosts, ActivityCosts activityCosts) {
          if (!(job instanceof Service)) return super.calculateInsertion(job, route, vehicle, newDepTime, driver, cost, transportCosts, activityCosts);
  
          Service originalService = (Service) job;
          String key = originalService.getId() + "_" + vehicle.getType().getId();
          TimeWindow conditionalTW = conditionalTWMap.get(key);
  
          // 如果有对应车型的时间窗口，临时修改作业的时间窗口再计算
          if (conditionalTW != null) {
              Service modifiedService = Service.Builder.copyOf(originalService)
                      .setTimeWindow(conditionalTW)
                      .build();
              return super.calculateInsertion(modifiedService, route, vehicle, newDepTime, driver, cost, transportCosts, activityCosts);
          }
  
          // 无规则时使用默认逻辑
          return super.calculateInsertion(job, route, vehicle, newDepTime, driver, cost, transportCosts, activityCosts);
      }
  }
  

• 注入自定义计算器：通过VehicleRoutingAlgorithmBuilder替换默认实现：

  // 构建条件时间窗口映射
  Map<String, TimeWindow> conditionalTWMap = new HashMap<>();
  conditionalTWMap.put("job1_light", TimeWindow.newInstance(0, 86400)); // 轻型车全天通行
  conditionalTWMap.put("job1_heavy", TimeWindow.newInstance(64800, 86400)); // 重型车夜间（18:00-24:00）通行
  
  // 注入自定义计算器到算法构建器
  VehicleRoutingAlgorithmBuilder builder = VehicleRoutingAlgorithmBuilder.newInstance(problem);
  builder.setServiceInsertionCalculator(new ConditionalTWServiceInsertionCalculator(conditionalTWMap));
  // 同理处理Shipment类型作业
  builder.setShipmentInsertionCalculator(new ConditionalTWShipmentInsertionCalculator(conditionalTWMap));
  VehicleRoutingAlgorithm algorithm = builder.build();
  

方案2：作业变体+硬约束（简便但有局限） #

如果不想修改插入逻辑，可以给同一作业创建多个变体，搭配硬约束实现需求：

• 为每个作业生成多份实例，比如job1_light（时间窗口全天）、job1_heavy（时间窗口夜间），并给每个实例添加车型标签（通过addAttribute("allowedVehicleType", "light")）。
• 编写硬约束VehicleTypeJobMatchingConstraint，检查车辆类型是否与作业的allowedVehicleType属性匹配，不匹配则禁止分配该作业。
• 设置作业的setRequired(true)，并添加分组约束，确保同一原始作业的变体中只有一个被选中执行。

这种方法无需触碰核心插入逻辑，但缺点是作业数量会随车型数量倍增，当规则复杂、作业量大时，会增加求解问题规模，影响运行效率。

关于fork库的问题 #

完全不需要fork。JSprit的设计预留了足够的扩展点，替换插入计算器是官方支持的扩展方式，所有修改都可以在业务代码中完成，无需改动库的源码。

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