在Timefold中实现可调节权重的软约束方案咨询

核心概念明确 #

你要实现的是加权软约束组合优化，不属于帕累托评分（帕累托是保留多个非支配解，不做权重取舍），也不是简单评分（简单评分无权重区分）。仅对软约束部分做归一化，同时保留硬约束的架构完全可行——硬约束负责保证解的合法性，归一化后的软约束负责按权重优化目标。

归一化到Long范围的可行性 #

归一化到Long.MIN_VALUE到Long.MAX_VALUE是可行的，但需注意两个关键点：

• 舍入误差：若原始约束分数的动态范围极大，归一化时的精度损失可能降低求解器对解的区分度。建议先预计算每个约束的最大可能分数范围，再做线性映射。
• 性能损耗：每次约束评分都要执行归一化运算，确实会增加计算开销，但如果问题规模在数千访问点/车辆以内，这种损耗在可接受范围内，符合你“以性能换功能”的需求。

Timefold中归一化的正确实现步骤 #

1. 预计算约束分数极值 #

求解开始前，先估算每个软约束的最大可能值：

• 最小化距离约束：计算所有访问点间最长路径总和（极端场景：车辆绕遍所有点的最长驾驶时间）作为maxDistancePenalty
• 最大化访问时长约束：计算所有访问点的最长访问时长总和作为maxVisitReward

2. 实现归一化映射函数 #

将原始分数线性映射到[-1, 1]区间，再缩放至Long范围：

// 距离约束归一化（惩罚项：原始值越大，归一化后越接近Long.MIN_VALUE）
private long normalizeDistancePenalty(long rawPenalty, long maxDistancePenalty) {
    if (maxDistancePenalty == 0) return 0;
    double normalizedRatio = (double) rawPenalty / maxDistancePenalty;
    // 惩罚项映射到Long负数区间，值越大惩罚权重越高
    return (long) (normalizedRatio * Long.MIN_VALUE);
}

// 访问时长约束归一化（奖励项：原始值越大，归一化后越接近Long.MAX_VALUE）
private long normalizeVisitReward(long rawReward, long maxVisitReward) {
    if (maxVisitReward == 0) return 0;
    double normalizedRatio = (double) rawReward / maxVisitReward;
    // 奖励项映射到Long正数区间，值越大奖励权重越高
    return (long) (normalizedRatio * Long.MAX_VALUE);
}

3. 应用权重并组合约束分数 #

在约束流中，先归一化每个约束的分数，再乘以配置的权重后组合：

@Override
public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
    return new Constraint[] {
        minimizeDistance(constraintFactory),
        maximizeVisitDuration(constraintFactory)
    };
}

private Constraint minimizeDistance(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Delivery.class)
            .join(Vehicle.class, Joiners.equal(Delivery::getVehicle))
            .groupBy(Vehicle.class, sum(Delivery::getDrivingTime))
            .penalizeLong("Minimize Distance",
                    HardSoftScore.ONE_SOFT,
                    (vehicle, totalDrivingTime) -> {
                        long normalizedPenalty = normalizeDistancePenalty(totalDrivingTime, precomputedMaxDistancePenalty);
                        // 应用90%权重：惩罚项权重越高，对解的负面影响越大
                        return (long) (normalizedPenalty * 0.9);
                    });
}

private Constraint maximizeVisitDuration(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Delivery.class)
            .groupBy(sum(Delivery::getVisitDuration))
            .rewardLong("Maximize Visit Duration",
                    HardSoftScore.ONE_SOFT,
                    (totalVisitTime) -> {
                        long normalizedReward = normalizeVisitReward(totalVisitTime, precomputedMaxVisitReward);
                        // 应用10%权重：奖励项权重越高，对解的正面影响越大
                        return (long) (normalizedReward * 0.1);
                    });
}

之前实现失败的可能原因 #

1. 极值估算错误：如果预计算的maxDistancePenalty或maxVisitReward远小于实际可能的分数，会导致归一化后分数溢出或权重失效，比如实际驾驶时间远超估算最大值，所有解的分数都接近Long.MIN_VALUE，求解器无法区分优劣。
2. 权重方向错误：距离约束是惩罚项（原始值越大越差），需映射到负数区间；访问时长是奖励项（原始值越大越好），需映射到正数区间。方向搞反会导致求解器朝着错误方向优化。
3. 硬约束冲突：若存在未正确定义的硬约束，求解器会优先满足硬约束，导致软约束优化结果看起来不合理，需检查硬约束是否遗漏或逻辑错误。
4. 归一化精度损失：如果原始分数是小范围数值，归一化到Long范围时的舍入会导致分数区分度丢失，建议先将原始分数放大（比如把秒转为毫秒）再做归一化。

内容的提问来源于stack exchange，提问作者Clément Chataignon