引言
我们今天要聊一下来Optaplanner里的Tennis club scheduling例子。这个例子非常重要，因为它演示了如何使用Optaplanner来解决资源和工作量公平分配的问题，并且还要考虑到“公平约束”的设计。需要注意的是，设计约束时有一些独特的要求，我们将在这篇文章中详细讨论。
问题描述
Tennis club scheduling的实际问题
Tennis Club Scheduling问题是一个经典的排班问题，它模拟了一个网球俱乐部的赛程安排。这个问题涉及到多个要素，包括场地、队伍、赛程以及约束条件。
限制和目标
每周网球俱乐部有四个团队进行单循环赛。公平地分配这四个位置给这些团队。
硬性约束：
• 冲突：每个团队每天只能参加一场比赛。
• 不可用性：有些团队在某些日期不可用。
中等约束：
• 公平分组：所有团队应该进行（几乎）相等次数的比赛。
软性约束：
• 均匀对抗：每个团队应该与其他团队平等次数地对抗。
问题规模
让我们来看一下官网上给出的案例中，不同数据规模所对应的搜索空间大小情况：
munich-7teams has 7 teams, 18 days, 12 unavailabilityPenalties and 72 teamAssignments
with a search space of 10^60.
如何被建模
让我们来看一下官方提供的类图设计。这个类图描述了Tennis club scheduling中的核心类，包括解决方案、规划变量、规划实体以及规划问题：
ProblemFact
在这个类图中，Day、Team和UnavailabilityPenalty三个类被标示为白色部分，它们代表了整个解决方案中的ProblemFact（问题事实）部分。具体而言，Day类代表了日期，Team类代表了球队，而UnavailabilityPenalty类则代表了不可参赛日期的团队。
public class Team extends AbstractPersistable implements Labeled {
private String name;
}
public class Day extends AbstractPersistable implements Labeled {
private int dateIndex;
}
public class UnavailabilityPenalty extends AbstractPersistable {
private Team team;
private Day day;
}
PlanningEntity
TeamAssignment，表示赛程中某一天的某一个时间段中的一场比赛的安排，它是PlanningEntity。
@PlanningEntity
public class TeamAssignment extends AbstractPersistable {
private Day day;
private int indexInDay;
private boolean pinned;
// planning variable
private Team team;
public TeamAssignment() {
}
@PlanningPin
public boolean isPinned() {
return pinned;
}
@PlanningVariable
public Team getTeam() {
return team;
}
}
@PlanningVariable: 这个注解标记了一个方法，表示这个方法返回的属性（即 team）是OptaPlanner中的Planning Variable（规划变量），即需要OptaPlanner进行计算的可变属性。
我们来讲一下一个新的注解：@PlanningPin。这个注解标记了一个方法，表示这个方法返回的属性（即 pinned）是“不可变”的，也就是说，在整个调度过程中，OptaPlanner不会修改这个属性。例如，Angelika球队必须在13号进行比赛，这个条件在求解过程中不会被修改。之前，作者使用Hard约束来实现这个约束，但实际上这样做会浪费性能，而且还会复杂化分数的计算，不利于求解。
Solution
package org.optaplanner.examples.tennis.domain;
import java.util.List;
import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
import org.optaplanner.core.api.domain.solution.PlanningScore;
import org.optaplanner.core.api.domain.solution.PlanningSolution;
import org.optaplanner.core.api.domain.solution.ProblemFactCollectionProperty;
import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;
import org.optaplanner.core.api.score.buildin.hardmediumsoft.HardMediumSoftScore;
import org.optaplanner.examples.common.domain.AbstractPersistable;
@PlanningSolution
public class TennisSolution extends AbstractPersistable {
private List<Team> teamList;
private List<Day> dayList;
private List<UnavailabilityPenalty> unavailabilityPenaltyList;
private List<TeamAssignment> teamAssignmentList;
private HardMediumSoftScore score;
public TennisSolution() {
}
public TennisSolution(long id) {
super(id);
}
@ValueRangeProvider
@ProblemFactCollectionProperty
public List<Team> getTeamList() {
return teamList;
}
@ProblemFactCollectionProperty
public List<Day> getDayList() {
return dayList;
}
@ProblemFactCollectionProperty
public List<UnavailabilityPenalty> getUnavailabilityPenaltyList() {
return unavailabilityPenaltyList;
}
@PlanningEntityCollectionProperty
public List<TeamAssignment> getTeamAssignmentList() {
return teamAssignmentList;
}
@PlanningScore
public HardMediumSoftScore getScore() {
return score;
}
}
在这段代码中，TennisSolution类是一个OptaPlanner的Planning Solution类，它表示OptaPlanner问题的解决方案。这个类包含了多个成员变量，例如teamList、dayList、unavailabilityPenaltyList和teamAssignmentList，它们分别表示在比赛中参与的所有队伍、比赛的所有天数等。此外，还有score成员变量，表示OptaPlanner评估解决方案的得分。
约束分析
从问题“限制和目标”上可以得出，此问题有4个约束，而且对应的约束等级不同。下面我们来学习下每个约束的设计，TennisConstraintProvider是约束提供类。
public final class TennisConstraintProvider implements ConstraintProvider {
@Override
public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
return new Constraint[] {
oneAssignmentPerDatePerTeam(constraintFactory),
unavailabilityPenalty(constraintFactory),
fairAssignmentCountPerTeam(constraintFactory),
evenlyConfrontationCount(constraintFactory)
};
}
}
每个团队每天只能参加一场比赛
Constraint oneAssignmentPerDatePerTeam(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(TeamAssignment.class)
.join(TeamAssignment.class,
equal(TeamAssignment::getTeam),
equal(TeamAssignment::getDay),
lessThan(TeamAssignment::getId))
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("oneAssignmentPerDatePerTeam");
}
首先，该方法接受一个ConstraintFactory类型的参数constraintFactory，它是OptaPlanner中用于创建规划限制条件的工厂类。
然后，该方法通过调用constraintFactory的forEach方法来获取一个表示TeamAssignment实体的Stream，并将其与另一个TeamAssignment实体进行关联。这个关联使用join方法实现，它表示两个TeamAssignment对象必须满足以下条件：
- 它们的Team对象相同；
- 它们的Day对象相同；
- 它们的Id属性不同，即第一个TeamAssignment对象的Id属性小于第二个TeamAssignment对象的Id属性。
这个限制条件的意思是，对于同一个队伍和同一个比赛日期，不能有两个或多个TeamAssignment对象被分配。
有些团队在某些日期不可用
Constraint unavailabilityPenalty(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(UnavailabilityPenalty.class)
.ifExists(TeamAssignment.class,
equal(UnavailabilityPenalty::getTeam, TeamAssignment::getTeam),
equal(UnavailabilityPenalty::getDay, TeamAssignment::getDay))
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("unavailabilityPenalty");
}
这个约束比较容易理解。我们使用forEach方法来获取UnavailabilityPenalty的Stream，然后与TeamAssignment进行匹配，条件是team和day相同。如果存在匹配，就会执行硬约束惩罚。
公平性约束设计
接下来，我们来学习fairAssignmentCountPerTeam和evenlyConfrontationCount约束的设计。这里有一个核心的知识点，关于“公平”约束的设计。要实现这样的约束条件，看起来很简单，但通常最理想的实现方式是平方级别的工作量。
Constraint fairAssignmentCountPerTeam(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(TeamAssignment.class)
.groupBy(loadBalance(TeamAssignment::getTeam))
.penalize(HardMediumSoftScore.ONE_MEDIUM,
result -> (int) result.getZeroDeviationSquaredSumRootMillis())
.asConstraint("fairAssignmentCountPerTeam");
}
loadBalance是使用了一个自定义的约束收集器UniConstraintCollector来实现的，LoadBalanceData是groupBy所汇总的最终数据对象。
private static <A> UniConstraintCollector<A, ?, LoadBalanceData> loadBalance(
Function<A, Object> groupKey) {
return new UniConstraintCollector<A, LoadBalanceData, LoadBalanceData>() {
@Override
public Supplier<LoadBalanceData> supplier() {
return LoadBalanceData::new;
}
@Override
public BiFunction<LoadBalanceData, A, Runnable> accumulator() {
return (resultContainer, a) -> {
Object mapped = groupKey.apply(a);
return resultContainer.apply(mapped);
};
}
@Override
public Function<LoadBalanceData, LoadBalanceData> finisher() {
return Function.identity();
}
};
}
在LoadBalanceData类的apply方法中，我们实现了每个Team进行比赛分配的时候，会计算增量来计算整个比赛的负载。核心公式是squaredZeroDeviation = squaredZeroDeviation – (count – 1)² + count²，以及增量计算公式squaredSum += (2 * count – 1)。这个算式与之前提到的算式是等价的。
private static final class LoadBalanceData {
private final Map<Object, Long> groupCountMap = new LinkedHashMap<>(0);
// the sum of squared deviation from zero
private long squaredSum = 0L;
private Runnable apply(Object mapped) {
long count = groupCountMap.compute(mapped,
(key, value) -> (value == null) ? 1L : value + 1L);
// squaredZeroDeviation = squaredZeroDeviation - (count - 1)² + count²
// <=> squaredZeroDeviation = squaredZeroDeviation + (2 * count - 1)
squaredSum += (2 * count - 1);
return () -> {
Long computed = groupCountMap.compute(mapped,
(key, value) -> (value == 1L) ? null : value - 1L);
squaredSum -= (computed == null) ? 1L : (2 * computed + 1);
};
}
public long getZeroDeviationSquaredSumRootMillis() {
return (long) (Math.sqrt(squaredSum) * 1_000);
}
}
重要
这个地方是整个公平约束实现方式的核心。也许你看不懂，因为它涉及到平方和的计算以及增量算式的转换。如果你没有钻研精神，那么就不要看了，直接使用即可。因为即使我写了，也没有人会花时间认真研究它。如果需要的话，可以私信联系我进行讨论。
求解
最后贴一张效果图如下：
如果需要转载文章，必须注明原出处和作者，感谢您的理解和支持。
