当前位置:首页> AI教程> Optaplanner Tennis Club Scheduling案例分析

Optaplanner Tennis Club Scheduling案例分析

释放双眼,带上耳机,听听看~!
本文分析了Optaplanner中的Tennis club scheduling例子,讨论了资源和工作量公平分配的问题,以及设计约束时的独特要求。

引言

我们今天要聊一下来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中的核心类,包括解决方案、规划变量、规划实体以及规划问题:
Optaplanner Tennis Club Scheduling案例分析

ProblemFact

在这个类图中,DayTeamUnavailabilityPenalty三个类被标示为白色部分,它们代表了整个解决方案中的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);
        }

    }

重要

这个地方是整个公平约束实现方式的核心。也许你看不懂,因为它涉及到平方和的计算以及增量算式的转换。如果你没有钻研精神,那么就不要看了,直接使用即可。因为即使我写了,也没有人会花时间认真研究它。如果需要的话,可以私信联系我进行讨论。

求解

最后贴一张效果图如下:
Optaplanner Tennis Club Scheduling案例分析

如果需要转载文章,必须注明原出处和作者,感谢您的理解和支持。

本网站的内容主要来自互联网上的各种资源,仅供参考和信息分享之用,不代表本网站拥有相关版权或知识产权。如您认为内容侵犯您的权益,请联系我们,我们将尽快采取行动,包括删除或更正。
AI教程

清华大学与美团合作论文获ACM嵌入式网络感知系统大会最佳论文奖

2023-12-9 11:13:14

AI教程

Anthropic推出的AI助手Claude:安全、有用、无害

2023-12-9 11:20:14

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索