OptaPlanner高级调度：处理无可行解的规划变量与过约束规划

本文深入探讨了optaplanner在调度问题中，当没有可行解时仍强制分配规划实体的问题。我们将介绍如何通过引入“过约束规划”概念和配置“可空规划变量”，来确保只有当存在有效方案时才进行分配。教程将通过详细的示例代码和约束定义，指导读者实现更智能、更符合业务需求的资源调度，避免生成不切实际的解决方案。

引言：OptaPlanner强制分配的挑战

在使用OptaPlanner解决资源调度问题时，一个常见且令人困扰的场景是：即使在没有销售代表可以被分配给某个预约的情况下，OptaPlanner仍然会尝试强制分配一个销售代表。这种“随机”或“不合理”的分配会导致最终解决方案无法使用，因为它违反了实际业务逻辑——如果一个任务无法被任何人执行，它就不应该被分配。默认情况下，OptaPlanner倾向于为所有规划实体找到一个分配，即使这意味着违反某些约束或生成一个次优解。

理解传统硬约束的局限性

为了防止销售代表在同一时间处理多个预约，我们通常会定义一个硬约束。例如，以下是一个常见的冲突约束：

Constraint repConflict(ConstraintFactory constraintFactory) {
    // 确保销售代表在任何给定时间只能处理一个预约
    return constraintFactory
            // 选择每个销售代表的预约对
            .forEachUniquePair(Appointment.class,
                    Joiners.equal(Appointment::getRepUuid)) // 根据销售代表UUID分组
            .filter((appt1, appt2) -> {
                // 检查两个预约是否有时间重叠
                // 如果 appt1 的开始时间在 appt2 结束时间之前，并且 appt2 的开始时间在 appt1 结束时间之前，则存在重叠
                return appt1.getStartTime().isBefore(appt2.getEndTime())
                        && appt2.getStartTime().isBefore(appt1.getEndTime());
            })
            // 如果存在重叠，施加一个硬性惩罚
            .penalize(HardSoftScore.ONE_HARD)
            .asConstraint("SalesRep conflict");
}

这个repConflict约束旨在确保销售代表的时间表不会重叠。当一个销售代表被分配了两个时间重叠的预约时，这个约束会施加一个硬性惩罚，从而指导求解器避免此类分配。然而，它的局限性在于：它只在已经存在分配时才发挥作用。它无法阻止OptaPlanner为那些根本找不到合适销售代表的预约“凭空”分配一个。

尝试通过SolverConfig中的withBestScoreFeasible(true)来配置求解器，虽然能确保最终解决方案不包含任何硬约束冲突，但这并不意味着未分配的实体会被自动置空。它仅仅是告诉求解器，如果无法找到一个完全没有硬约束的解决方案，它就不应该停止，而是继续寻找一个最佳的“可行”解决方案。对于那些无法满足任何硬约束的实体，它仍然会尝试找到一个“最佳”的、但可能不合理的分配。

核心解决方案：过约束规划与可空规划变量

要解决OptaPlanner在无可行解时强制分配的问题，我们需要引入“过约束规划”的概念，并利用“可空规划变量”来实现。

什么是过约束规划 (Overconstrained Planning)?

过约束规划是指在某些调度问题中，由于资源限制或任务冲突，可能无法为所有规划实体找到一个完美的、满足所有约束的解决方案。在这种情况下，我们允许一些实体不被分配，并对这些未分配的实体施加软性惩罚，而不是硬性惩罚。这使得求解器能够在无法满足所有需求时，找到一个“次优”但可接受的解决方案，而不是一个“完美”但实际上不可能实现的方案。

引入可空规划变量 (Nullable Planning Variable)

实现过约束规划的关键在于允许规划变量为null。这意味着一个规划实体（例如，一个预约）可以不被分配给任何一个规划值（例如，一个销售代表）。

在您的规划实体类（例如Appointment）中，您可以将代表分配的字段声明为可空规划变量：

甲骨文AI协同平台

专门用于甲骨文研究的革命性平台

下载

import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.variable.PlanningVariable;
// ... 其他导入

@PlanningEntity
public class Appointment {

    private String uuid; // 预约唯一标识
    private Date startTime;
    private Date endTime;

    // salesRep 是一个规划变量，它会从 salesRepRange 中选择一个 SalesRep 对象
    // nullable = true 允许这个规划变量的值为 null，表示该预约未被分配
    @PlanningVariable(valueRangeProviderRefs = "salesRepRange", nullable = true)
    private SalesRep salesRep; // 被分配的销售代表

    // ... 构造函数, getter 和 setter

    // 确保 getRepUuid() 方法返回 salesRep 的 UUID，如果 salesRep 为 null，则返回 null
    public String getRepUuid() {
        return (salesRep != null) ? salesRep.getUuid() : null;
    }
}

在上述代码中，@PlanningVariable(valueRangeProviderRefs = "salesRepRange", nullable = true)是核心。nullable = true明确告诉OptaPlanner，salesRep这个规划变量可以被设置为null。当一个预约的salesRep为null时，就表示该预约没有被分配给任何销售代表。

处理未分配实体的软约束

仅仅允许nullable = true是不够的。如果一个预约被设置为null可以避免硬约束，OptaPlanner可能会倾向于将所有预约都置为null，因为这能得到一个“无硬约束冲突”的解决方案。为了确保在有可行解时优先进行分配，我们需要定义一个软约束来惩罚那些未被分配的预约。

import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
import org.optaplanner.core.api.score.stream.Constraint;
import org.optaplanner.core.api.score.stream.ConstraintFactory;
// ... 其他导入

public class RepSchedulerConstraintProvider implements ConstraintProvider {

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

    Constraint repConflict(ConstraintFactory constraintFactory) {
        // ... （与上面相同的 repConflict 约束）
        return constraintFactory
                .forEachUniquePair(Appointment.class,
                        // 注意：如果 getRepUuid() 返回 null，Joiners.equal 将不会匹配，
                        // 这意味着未分配的预约不会参与此冲突检查，这是期望的行为。
                        Joiners.equal(Appointment::getRepUuid))
                .filter((appt1, appt2) -> {
                    return appt1.getStartTime().isBefore(appt2.getEndTime())
                            && appt2.getStartTime().isBefore(appt1.getEndTime());
                })
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("SalesRep conflict");
    }

    Constraint penalizeUnassignedAppointment(ConstraintFactory constraintFactory) {
        // 惩罚所有未被分配销售代表的预约
        return constraintFactory.forEach(Appointment.class)
                .filter(appointment -> appointment.getSalesRep() == null)
                .penalize(HardSoftScore.ONE_SOFT) // 施加一个软性惩罚
                .asConstraint("Penalize unassigned appointment");
    }
}

通过penalizeUnassignedAppointment这个软约束，OptaPlanner在发现无法在不违反硬约束的情况下分配一个预约时，会将其salesRep设置为null，并因此承担一个软性惩罚。这使得求解器能够优先满足硬约束（不冲突），其次是尽量多地进行分配（避免软惩罚）。

至于您在问题中提到的repRewardForAppointment约束，它奖励的是销售代表之间没有时间冲突的预约对。虽然这可以作为一种优化策略来鼓励更紧凑或更合理的调度，但它并非解决“不分配”问题的核心机制。在引入nullable变量和penalizeUnassignedAppointment软约束后，这个奖励约束可以作为额外的优化目标（例如，使用HardMediumSoftScore.ONE_MEDIUM）来进一步引导解决方案，但它不是强制性的。

综合示例：销售代表预约调度

为了完整地展示这一解决方案，我们来看一下相关的规划模型和配置。

1. 规划域模型

SalesRep (规划值)

public class SalesRep {
    private String uuid;
    private String name;
    // ... 构造函数, getter 和 setter
}

Appointment (规划实体)

import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.variable.PlanningVariable;
import java.util.Date;

@PlanningEntity
public class Appointment {
    private String uuid;
    private Date startTime;
    private Date endTime;

    @PlanningVariable(valueRangeProviderRefs = "salesRepRange", nullable = true)
    private SalesRep salesRep;

    public Appointment() {} // OptaPlanner需要无参构造函数

    public Appointment(String uuid, Date startTime, Date endTime) {
        this.uuid = uuid;
        this.startTime = startTime;
        this.endTime = endTime;