2

我对线性优化有点陌生，我想把它应用到经典的调度问题上。对于人员配备问题，我不太清楚如何声明捕获正在采取的“转变”概念的功能。

我正在使用到目前为止非常棒的 ojAlgo。这是我想出的人为的小问题：

SCENARIO:
You have three drivers to make deliveries.

Driver 1 costs $10 / hr
Driver 2 costs $12 / hr
Driver 3 costs $14 / hr


Each driver can only work 3-6 hours a day.
Only one shift can be worked by a worker a day.
Operating day is 6:00 to 22:00, which must be fully covered.

Driver 2 cannot work after 11:00.

Create a schedule that minimizes the cost. 





Solve Variables:
Tsx = shift start for Driver X
Tex = shift end for Driver X

Minimize:
10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
10Te1 - 10Te2 + 12Te2 - 12Ts2 + 14Te3 - 14Ts3

Constraints:
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11

这是我整理的 Kotlin 代码。我发现每个Driver实例都更容易处理尽可能多的函数输入（这产生了一些有趣的 OOP 模式）。

import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable


fun main(args: Array<String>) {


    val model = ExpressionsBasedModel()

    val drivers = sequenceOf(
            Driver(1, 10.0, model),
            Driver(2, 12.0, model),
            Driver(3, 14.0, model)
    ).map { it.driverNumber to it }
     .toMap()


    model.addExpression("EnsureCoverage")
            .level(16.0)
            .apply {
                drivers.values.forEach {
                    set(it.shiftEnd, 1)
                    set(it.shiftStart, -1)
                }
            }

    model.addExpression("Driver2OffAt11")
            .upper(11)
            .set(drivers[1]!!.shiftEnd, 1)

    val result = model.minimise()

    println(result)
}

data class Driver(val driverNumber: Int,
                  val rate: Double,
                  val model: ExpressionsBasedModel) {

    val shiftStart = Variable.make("${driverNumber}shiftStart").weight(rate).lower(6).upper(22).apply(model::addVariable)
    val shiftEnd = Variable.make("${driverNumber}shiftEnd").weight(rate).lower(6).upper(22).apply(model::addVariable)

    init {
        model.addExpression("${driverNumber}shiftLength")
                .lower(4.0)
                .upper(6.0)
                .set(shiftEnd, 1)
                .set(shiftStart, -1)
    }

}

但是我得到的输出表明所有三个驱动程序都在早上 6:00 分配并同时工作。司机 1 从 6:00-11:00，司机 2 从 6:00-12:00，司机 3 从 6:00-11:00。

OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]

我不希望它们重叠。我希望一次只分配一个司机，并且我希望整个工作日都被分配。如何表达已经占用时间的二进制状态？

4

1 回答 1

3

多亏了Erwin 在数学部分的帮助，我似乎已经启动并运行了它。关键是一个二进制开关。

这是结果。司机 1 安排在 16:00-22:00，司机 2 安排在 6:00-10:00，司机 3 安排在 10:00-16:00。

import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable

// declare model
val model = ExpressionsBasedModel()

// parameters
val operatingDay = 6..22
val operatingDayLength = operatingDay.endInclusive - operatingDay.start
val allowableShiftSize = 4..6

// Map drivers by their ID for ad hoc retrieval
val drivers = sequenceOf(
        Driver(driverNumber = 1, rate =  10.0),
        Driver(driverNumber = 2, rate = 12.0, availability = 6..11),
        Driver(driverNumber = 3, rate =  14.0)
    ).map { it.driverNumber to it }
     .toMap()


fun main(args: Array<String>) {

    drivers.values.forEach { it.addToModel() }

    val result = model.minimise()

    println(result)
}

// Driver class will put itself into the Model
data class Driver(val driverNumber: Int,
                  val rate: Double,
                  val availability: IntRange? = null) {

    val shiftStart = Variable.make("${driverNumber}shiftStart").weight(rate).lower(6).upper(22).apply(model::addVariable)
    val shiftEnd = Variable.make("${driverNumber}shiftEnd").weight(rate).lower(6).upper(22).apply(model::addVariable)

    fun addToModel() {

        //constrain shift length
        model.addExpression("${driverNumber}shiftLength")
                .lower(allowableShiftSize.start)
                .upper(allowableShiftSize.endInclusive)
                .set(shiftEnd, 1)
                .set(shiftStart, -1)

        //ensure coverage of entire day
        model.addExpression("EnsureCoverage")
                .level(operatingDayLength)
                .apply {
                    drivers.values.forEach {
                        set(it.shiftEnd, 1)
                        set(it.shiftStart, -1)
                    }
                }

        //add specific driver availability
        availability?.let {
            model.addExpression("${driverNumber}StartAvailability")
                    .lower(it.start)
                    .upper(it.endInclusive)
                    .set(shiftStart, 1)

            model.addExpression("${driverNumber}EndAvailability")
                    .lower(it.start)
                    .upper(it.endInclusive)
                    .set(shiftEnd, 1)
        }

        //prevent shift overlap
        drivers.values.asSequence()
                .filter { it != this }
                .forEach { otherDriver ->

                    val occupied = Variable.make("${driverNumber}occupyStatus").lower(0).upper(1).integer(true).apply(model::addVariable)

                    model.addExpression("${driverNumber}to${otherDriver.driverNumber}Binary1")
                            .upper(0)
                            .set(otherDriver.shiftEnd, 1)
                            .set(occupied, operatingDayLength * - 1)
                            .set(shiftStart, -1)

                    model.addExpression("${driverNumber}to${otherDriver.driverNumber}Binary2")
                            .upper(operatingDayLength)
                            .set(shiftEnd, 1)
                            .set(occupied, operatingDayLength)
                            .set(otherDriver.shiftStart, -1)
                }
    }
}

输出：

OPTIMAL 936.0 @ [16.0, 22.0, 6.0, 10.0, 10.0, 16.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0]
于 2017-10-20T15:34:42.417 回答