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時に割り当てられていたと同時に動作するようにすべての3つのドライバーを示すこの出力を取得しています。ドライバ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人の運転手しか割り当てられないようにしたい、そして私は全営業日をカバーしたい。既に占有されている時間のバイナリ状態を表現するにはどうすればよいですか？

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]