OptaPlanner解决线性规划问题-一一网

这是我参与更文挑战的第18天，活动详情查看：更文挑战

内容概要

上一篇章我们学习了如何使用OptaPlanner来求解最值的问题，今天我们继续通过一个例子来学习如何求解线性规划问题，话不多说直接开始。

问题描述

今天这个问题是从韩伯棠教授的《管理运筹学》书中的一个例题，我们来尝试使用OptaPlanner来解决这个线性规划维问题。

人力资源分配问题

例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如表 4-1 所示：

设：司机和乘务人员分别在各时间段开始时上班，并连续工作 8 h，问该公交线路应怎样安排司机和乘务人员，既能满足工作需要，又使配备司机和乘务人员的人数最少？

线性规划求解

我们来看下书中线性规划的求解答案，线性规划的求解重要三步骤，建模型，建约束，极值函数。

解：

解设x，表示第i班次时开始上班的司机和乘务人员人数，这样可以知道在第i班次工作的人数应包括第i-1班次时开始上班的人数和第i班次时开始上班的人数，如有x1+x2≥70.又要求这六个班次时开始上班的所有人员最少，即要求x1+x2+x3+x4+x5+x6。最小，这样建立如下的数学模型∶

约束条件

min z = x1 + x2 + x3 + x4 + x5 + x5

x1+x6≥60,

x1+x2≥70,

x2+x3≥60,

x3+x4≥50,

x4+x5≥20,

x5+x6≥30,

x1,x2,x3,x4,x5,x6≥0

用”管理运筹学”软件可以求得此问题的最优解∶x1=50，x2=20，x3=50，x4=0，x5=20，x6=10，一共需要司机和乘务人员 150 人.

OptaPlanner求解

OptaPlanner的三步骤就是，建模型、写约束评分。

模型如上图所示。

模型建立

BusDriverSolution.java

@PlanningSolution
public class BusDriverSolution extends AbstractPersistable {

    @PlanningEntityCollectionProperty
    private List<BusShift> busShifts;

    @ProblemFactCollectionProperty
    private List<HourShift> hourShifts;

    @ProblemFactCollectionProperty
    private List<HourPeoplePattern> hourPeoplePatterns;

    @PlanningScore
    private HardMediumSoftScore score;

    @ValueRangeProvider(id = "peopleNumRange")
    public CountableValueRange<Integer> getPeopleNumRange() {
        // Range: 0, 1, 2, 3, ..., 69, 70
        return ValueRangeFactory.createIntValueRange(0, 100, 1);
    }
    ......
}
复制代码

BusShift.java

@PlanningEntity(difficultyComparatorClass = BusShiftStrengthComparator.class)
public class BusShift extends AbstractPersistable implements Comparable<BusShift> {

    /**
     * assignment people
     */
    @PlanningVariable(valueRangeProviderRefs = "peopleNumRange")
    private Integer assignmentPeople;

    private HourShift hourShift;
}
复制代码

HourShift.java

public class HourShift extends AbstractPersistable {

    /**
     * need people
     */
    private Integer needPeople;

    /**
     * start hour
     */
    private Integer start;

    /**
     * end hour
     */
    private Integer end;
}
复制代码

HourPeoplePattern.java

public class HourPeoplePattern extends AbstractPersistable {

    private HourShift beforeHourShift;

    private HourShift afterHourShift;

    private Integer minxPeopleNum;
}
复制代码

HourPeoplePattern

HourPeoplePattern对象属性为，beforeHourShift，afterHourShift，minPeopleNum，这个Pattern代表着，每两个班次的人数最少为多少人的数据。在后面进行约束匹配时，是很关键的。

约束评分

busDriverConstraints.drl

package org.optaplanner.examples.busdriver.solver;
    dialect "java"

import org.optaplanner.core.api.score.buildin.hardmediumsoft.HardMediumSoftScoreHolder
import org.optaplanner.examples.bus.domain.BusDriverSolution;
import org.optaplanner.examples.bus.domain.BusShift;
import org.optaplanner.examples.bus.domain.HourShift;
import org.optaplanner.examples.bus.domain.HourPeoplePattern;
import org.optaplanner.examples.bus.StaticKit;
import java.lang.Math;
import org.optaplanner.examples.bus.StaticKit;

global HardMediumSoftScoreHolder scoreHolder;




rule "Meeting the Needs"
    when
        HourPeoplePattern(
            $beforeHourShift : beforeHourShift,
            $afterHourShift : afterHourShift,
            $minxPeopleNum : minxPeopleNum
        )
        $before : BusShift(hourShift == $beforeHourShift)
        $after : BusShift(hourShift == $afterHourShift)
    then
        scoreHolder.addMediumConstraintMatch(kcontext, -1 * StaticKit.calcMinScore($minxPeopleNum, $before, $after));
end

rule "Meeting the Needs lack"
    when
        HourPeoplePattern(
            $beforeHourShift : beforeHourShift,
            $afterHourShift : afterHourShift,
            $minxPeopleNum : minxPeopleNum
        )
        $before : BusShift(hourShift == $beforeHourShift)
        $after : BusShift(hourShift == $afterHourShift,
             StaticKit.lackMinScore($minxPeopleNum, $before, $after) == true)
    then
        scoreHolder.addHardConstraintMatch(kcontext, -1 * StaticKit.calcMinScore($minxPeopleNum, $before, $after));
end



rule "Min People"
    when
        accumulate (
            BusShift(assignmentPeople != null , $assignmentPeople : assignmentPeople);
            $busTotalSum : sum($assignmentPeople)
        )
    then
        scoreHolder.addSoftConstraintMatch(kcontext, - $busTotalSum.intValue());
end
复制代码

求解结果

10:21:23.927 [main        ] INFO  Local Search phase (1) ended: time spent (4087), best score (0hard/-10medium/-150soft), score calculation speed (25268/sec), step total (185).
10:21:23.927 [main        ] INFO  Solving ended: time spent (4087), best score (0hard/-10medium/-150soft), score calculation speed (20259/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (NONE).
bus - 1, people : 60
bus - 2, people : 10
bus - 3, people : 50
bus - 4, people : 0
bus - 5, people : 30
bus - 6, people : 0
复制代码

我们可以看到最后的求解结果是：

x1=60，x2=10，x3=50，x4=0，x5=30，x6=0，最少人数为150人。

我们再来看下例题的求解结果：

用”管理运筹学”软件可以求得此问题的最优解∶x1=50，x2=20，x3=50，x4=0，x5=20，x6=10，一共需要司机和乘务人员 150 人。

可以看出虽然各个变量不同，但是其结果都是为150人。因为我的变量都是x≥0，所以结果都不同的最优解。

当前结果的分数为best score (0hard/-10medium/-150soft)，我们来尝试下如果按照例子的结果，最终OptaPlanner的评分是多少呢：

---------------------do move-------------------
-- bus - 1, people : 50
-- bus - 2, people : 20
-- bus - 3, people : 50
-- bus - 4, people : 0
-- bus - 5, people : 20
-- bus - 6, people : 10
0hard/-10medium/-150soft
Explanation of score (0hard/-10medium/-150soft):
复制代码