如何用OptaPlanner约束实现同CityID地址的排序分配？

模型定义 #

Employee 模型 #

@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
@Builder
@PlanningEntity
public class Employee {

  @PlanningId
  private Long id;

  @InverseRelationShadowVariable(sourceVariableName = "employee")
  private List<Address> addresses = new ArrayList<>();

}

Address 模型 #

@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
@Builder
@PlanningEntity
public class Address {

    @PlanningId
    private Long id;

    private Long cityId;

    @PlanningVariable(valueRangeProviderRefs = "employeeRange")
    private Employee employee;
}

需求说明 #

同一cityId的地址必须分配给同一员工，且每个员工分配的地址需按cityId连续排列，示例结果如下：

+----------------------+-----------------------+
|      Employee 1      |      Employee 2       |
+----------------------+-----------------------+
| Address 1 (cityId 4) | Address 4 (cityId 1)  |
| Address 2 (cityId 4) | Address 5 (cityId 1)  |
| Address 3 (cityId 4) | Address 6 (cityId 2)  |
| Address 7 (cityId 5) | Address 8 (cityId 2)  |
| Address 9 (cityId 5) | Address 10 (cityId 2) |
+----------------------+-----------------------+

尝试过的无效约束 #

约束1 #

public static Constraint cityConflict(ConstraintFactory constraintFactory) {
  return constraintFactory.forEach(Address.class)
          .groupBy(Address::getEmployee)
          .filter(employee -> employee.getAddresses().stream()
                  .anyMatch(address ->
                          !Objects.equals(address.getCityId(), address.getAddresses().get(0).getCityId())
                  )
          ).penalize(CITY_CONFLICT, HardMediumSoftLongScore.ONE_MEDIUM);
}

约束2 #

public static Constraint addressesInSameCity(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Address.class)
            .groupBy(Address::getEmployee, Address::getCityId)
            .filter(((employee, cityId) -> {
                Long previousCityId = Long.MIN_VALUE;
                for (Address address : inspector.getAddresses()) {
                    Long currentVillageId = address.getCityId();
                    if (currentCityId < previousCityId) {
                        return true; 
                    }
                    previousCityId = currentCityId;
                }
                return false; 
            }))
            .penalize(CITY_CONFLICT, HardMediumSoftLongScore.ONE_MEDIUM);
}

正确的约束实现方案 #

需拆分两个核心约束：同城市地址必须归属同一员工（硬约束，确保合规），员工地址按城市连续排列（中等约束，优化排序）。

1. 硬约束：同一城市地址必须分配给同一员工 #

该约束确保同一cityId的地址不会被拆分给不同员工，违反则判定为不可行解：

public static Constraint sameCityMustShareEmployee(ConstraintFactory constraintFactory) {
    return constraintFactory.forEachUniquePair(Address.class,
            Joiners.equal(Address::getCityId),
            Joiners.notEqual(Address::getEmployee))
            .penalize("Same city assigned to different employees", 
                    HardMediumSoftLongScore.ONE_HARD);
}

2. 中等约束：员工地址需按城市连续排列 #

该约束惩罚员工地址列表中出现城市“断裂”的情况（相同城市地址被其他城市地址分隔），示例以地址id作为排序基准（可根据业务替换为时间、地理位置等）：

public static Constraint cityAddressesMustBeConsecutive(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Employee.class)
            .filter(employee -> {
                // 统计每个城市在有序地址列表中的区块数
                Map<Long, Integer> cityBlockCount = new HashMap<>();
                Long previousCity = null;
                // 按地址id排序，确保顺序稳定
                List<Address> sortedAddresses = employee.getAddresses().stream()
                        .sorted(Comparator.comparingLong(Address::getId))
                        .collect(Collectors.toList());
                
                for (Address address : sortedAddresses) {
                    Long currentCity = address.getCityId();
                    if (!Objects.equals(currentCity, previousCity)) {
                        cityBlockCount.put(currentCity, cityBlockCount.getOrDefault(currentCity, 0) + 1);
                        previousCity = currentCity;
                    }
                }
                // 区块数大于1说明该城市地址被分隔
                return cityBlockCount.values().stream().anyMatch(count -> count > 1);
            })
            .penalize("Non-consecutive city blocks", 
                    HardMediumSoftLongScore.ONE_MEDIUM,
                    employee -> {
                        // 按断裂次数加权惩罚，断裂越多惩罚越重
                        Map<Long, Integer> cityBlockCount = new HashMap<>();
                        Long previousCity = null;
                        List<Address> sortedAddresses = employee.getAddresses().stream()
                                .sorted(Comparator.comparingLong(Address::getId))
                                .collect(Collectors.toList());
                        
                        for (Address address : sortedAddresses) {
                            Long currentCity = address.getCityId();
                            if (!Objects.equals(currentCity, previousCity)) {
                                cityBlockCount.put(currentCity, cityBlockCount.getOrDefault(currentCity, 0) + 1);
                                previousCity = currentCity;
                            }
                        }
                        return cityBlockCount.values().stream()
                                .mapToLong(count -> count - 1)
                                .sum();
                    });
}

说明 #

• 硬约束保障业务规则的强制性，中等约束优化排列的合理性；
• 地址排序基准需根据实际业务场景确定，确保排序逻辑稳定可预期。

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