ojAlgo線性優化 - 防止工作班次重疊？

Question

我對線性優化很陌生，我想將其應用於經典的調度問題。對於人員配置問題，我不太清楚如何聲明捕捉正在採取的「轉變」概念的功能。

我使用的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] 

我不希望它們重疊。我一次只需要分配一名司機，我希望整個工作日都能得到滿足。我如何表達已經佔用時間的二進制狀態？

Answer 1

它看起來像我得到了這個運行，感謝Erwin's help in the Math section。關鍵是一個二進制開關。

這是結果。司機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]