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 Например, позаботиться о максимально возможном количестве входных функций (что привело к некоторым интересным шаблонам с ООП).
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]
Я не хочу, чтобы они перекрывались. Я хочу, чтобы за один раз назначался только один водитель, и я хочу, чтобы весь рабочий день был покрыт. Как я могу выразить двоичное состояние уже занятого времени?
1 ответ
Похоже, я запустил это и запустил, благодаря помощи Эрвина в разделе "Математика". Ключ был бинарным переключателем.
Вот результат. Водитель 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]