ojAlgo Optimisation linéaire - Prévention des chevauchements de travail?

Question

Je suis un peu nouveau dans l'optimisation linéaire, et je veux l'appliquer aux problèmes d'ordonnancement classiques. En ce qui concerne les problèmes de dotation, je ne vois pas très bien comment déclarer les fonctions qui capturent le concept de «changement». J'utilise ojAlgo qui a été plutôt génial jusqu'à maintenant. Voici mon petit problème artificiel je suis venu avec:

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 

Voici le code de Kotlin que j'ai mis ensemble. J'ai trouvé plus facile pour chaque instance Driver de prendre en charge autant de ses entrées de fonction que possible (ce qui a donné quelques motifs intéressants avec 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) 
    } 

} 

Mais je reçois cette sortie indiquant que les trois pilotes ont été assignés à 06h00 et de travailler simultanément. Le chauffeur 1 de 6h00 à 11h00, le chauffeur 2 de 6h00 à 12h00 et le chauffeur 3 de 6h00 à 11h00.

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

Je ne veux pas qu'ils se chevauchent. Je ne veux qu'un seul conducteur à la fois, et je veux que toute la journée de travail soit couverte. Comment exprimer l'état binaire du temps déjà occupé?

Answer 1

Il semble que je me suis mis en route, grâce à Erwin's help in the Math section. La clé était un commutateur binaire.

Voici le résultat. Le conducteur 1 était prévu entre 16h00 et 22h00, le conducteur 2 entre 6h00 et 10h00 et le chauffeur 3 entre 10h00 et 16h00.

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) 
       } 
    } 
} 

SORTIE:

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]