ojAlgo线性优化 – 防止工作班次重叠？
我对线性优化很陌生，我想将其应用于经典的调度问题。 对于人员配置问题，我不太清楚如何声明捕捉正在采取的“转变”概念的功能。
我正在使用迄今为止非常棒的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]
我不希望他们重叠。 我一次只需要一名司机，而且我希望整个工作日都能被覆盖。 我如何表达时间已经占用的二进制状态？
看起来我得到了这个运行，感谢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) } } }
OUTPUT：
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]