如何用OptaPlanner选择适配员工数的最优运力车辆

使用OptaPlanner实现员工车辆分配：现有车辆运力为20、4、6、2，需分配6名员工到车辆中。当前算法会优先选择运力20的车辆（满足不超员的硬约束），但业务期望选择运力6的车辆（运力完全匹配，无浪费）。

现有约束仅包含硬约束（禁止车辆载人数超过运力），没有定义引导算法选择最优方案的软约束。OptaPlanner在满足硬约束的前提下，没有优化目标来区分“可行但不优”和“最优”的方案。

通过添加软约束定义优化目标，引导算法选择运力最匹配的车辆。具体步骤如下：

1. 添加运力浪费最小化的软约束 #

在约束提供类中新增软约束，对车辆的运力浪费（运力-实际载人数）进行惩罚，浪费越多惩罚越重，算法会倾向于选择浪费最少的车辆。

修改后的约束代码：

// 原有的硬约束：禁止超员
private Constraint transportCapacity(ConstraintFactory factory) {
    return factory.forEach(Transport.class)
                  .filter(transport -> transport.getEmployeeList().size() > transport.getCapacity())
                  .penalizeLong("capacity violation",
                        HardMediumSoftLongScore.ONE_HARD, 
                        transport -> transport.getEmployeeList().size() - transport.getCapacity());
}

// 新增的软约束：最小化运力浪费
private Constraint minimizeCapacityWaste(ConstraintFactory factory) {
    return factory.forEach(Transport.class)
                  .filter(transport -> !transport.getEmployeeList().isEmpty())
                  .penalizeLong("capacity waste", 
                        HardMediumSoftLongScore.ONE_SOFT,
                        transport -> transport.getCapacity() - transport.getEmployeeList().size());
}

2. 注册新约束 #

将软约束添加到约束数组中，确保求解器能识别并应用：

@Override
public Constraint[] defineConstraints(ConstraintFactory factory) {
    return new Constraint[]{
            transportCapacity(factory),
            minimizeCapacityWaste(factory)
    };
}

3. 可选：优化求解器配置（按需调整） #

如果算法未快速收敛到最优解，可调整求解器的终止条件或启发式算法，给算法足够的探索时间：

// Java代码配置示例
SolverFactory<Solution> solverFactory = SolverFactory.create(new SolverConfig()
        .withSolutionClass(Solution.class)
        .withEntityClasses(Transport.class)
        .withTerminationConfig(new TerminationConfig()
                .withSecondsSpentLimit(30L)) // 延长求解时间
        .withConstructionHeuristicConfig(new ConstructionHeuristicConfig()
                .withConstructionHeuristicType(ConstructionHeuristicType.FIRST_FIT_DECREASING))
        .withLocalSearchConfig(new LocalSearchConfig()
                .withLocalSearchType(LocalSearchType.HILL_CLIMBING)));

• 硬约束保证业务规则不被违反（绝对不能超员），软约束定义业务期望的优化方向（选最匹配的车辆），二者结合才能得到符合需求的最优解。
• 若业务有其他优先级（比如优先使用闲置车辆、最少使用车辆数量），可调整软约束的惩罚逻辑，比如改为惩罚使用的车辆数量，或优先选择运力较小的可用车辆。

内容的提问来源于stack exchange，提问作者Scott A. Levinson