如何构建带容量约束的VRP模型以实现月度计划与客户多次拜访？

一、核心模型调整要点 #

• 拆分拜访任务：将原VRP中的Customer实体拆分为Customer（存储客户基础信息、拜访次数需求、单拜访销售额）和Visit（规划实体，每个实例代表一次具体拜访）。每个Visit关联对应客户，并标记可安排的日期范围（1个月窗口），示例代码：

  @PlanningEntity
  public class Visit {
      @PlanningId
      private Long id;
      private Customer customer;
      private LocalDate earliestDate;
      private LocalDate latestDate;
      @PlanningVariable(valueRangeProviderRefs = {"vehicleRange"})
      private Vehicle vehicle;
      @PlanningVariable(valueRangeProviderRefs = {"dateRange"})
      private LocalDate plannedDate; // 若需自动分配日期则设为规划变量
      private int expectedSales;
      // getter/setter
  }
  

• 每日容量重置约束：通过约束流按车辆+日期分组，检查当日总负载不超过车辆容量：

  @Constraint
  public Constraint dailyVehicleCapacity(ConstraintFactory factory) {
      return factory.forEach(Visit.class)
              .filter(visit -> visit.getVehicle() != null)
              .groupBy(Visit::getVehicle, Visit::getPlannedDate, Collectors.summingInt(Visit::getLoad))
              .filter((vehicle, date, totalLoad) -> totalLoad > vehicle.getCapacity())
              .penalize("Daily Vehicle Capacity Exceeded", HardSoftScore.ONE_HARD,
                      (vehicle, date, totalLoad) -> totalLoad - vehicle.getCapacity());
  }
  

二、均匀分布与销售额最大化的约束实现 #

• 销售额最大化：将单拜访销售额作为软约束奖励，优先安排高价值拜访：

  @Constraint
  public Constraint maximizeTotalSales(ConstraintFactory factory) {
      return factory.forEach(Visit.class)
              .filter(visit -> visit.getVehicle() != null)
              .reward("Maximize Sales", HardSoftScore.ONE_SOFT, Visit::getExpectedSales);
  }
  

• 拜访均匀分布：针对每个客户，计算已安排拜访的日期间隔方差，惩罚间隔差异过大的情况：

  @Constraint
  public Constraint evenlyDistributeCustomerVisits(ConstraintFactory factory) {
      return factory.forEach(Customer.class)
              .join(Visit.class, Joiners.equal(Customer::getId, Visit::getCustomerId))
              .groupBy((customer, visit) -> customer, Collectors.mapping(Visit::getPlannedDate, Collectors.toList()))
              .filter((customer, dateList) -> dateList.size() == customer.getRequiredVisitCount())
              .penalize("Uneven Visit Distribution", HardSoftScore.ONE_SOFT,
                      (customer, dateList) -> calculateDateIntervalVariance(dateList));
  }
  
  private int calculateDateIntervalVariance(List<LocalDate> dateList) {
      Collections.sort(dateList);
      List<Integer> intervals = new ArrayList<>();
      for (int i = 1; i < dateList.size(); i++) {
          intervals.add((int) ChronoUnit.DAYS.between(dateList.get(i-1), dateList.get(i)));
      }
      double mean = intervals.stream().mapToInt(Integer::intValue).average().orElse(0);
      return (int) intervals.stream().mapToDouble(d -> Math.pow(d - mean, 2)).sum();
  }
  

三、参考模型与入门项目迁移方向 #

无需寻找完全匹配的现成项目，可基于Timefold官方示例组合改造：

• 多次拜访逻辑：参考Employee Rostering示例中员工重复排班的思路，将“重复班次”替换为“客户重复拜访”，通过批量生成Visit实例满足客户的拜访次数需求。
• 日期分组约束：参考Maintenance Scheduling示例中按日期分组的资源负载检查逻辑，迁移到车辆每日容量重置的约束实现上。
• 基础框架复用：直接复用官方VRP示例中的Vehicle、Location、路径距离计算等模块，减少重复开发。

四、关键优化注意事项 #

• 规划变量配置：若需自动分配拜访日期，将Visit的plannedDate设为规划变量，值范围设为1个月内的工作日集合。
• 得分权重调整：根据业务优先级设置权重，比如将每日容量约束设为硬约束，销售额奖励权重高于均匀分布惩罚权重。
• 求解器性能优化：针对1个月窗口的大规模问题，调整求解器终止条件（如设置termination.spentLimit=PT30M），或启用constructionHeuristic快速生成初始解。

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