kotlinoptimizationmodelingoptaplannertimefold

Can a ProblemFact have a reference to a PlanningEntity?


I currently have the following setup for solving a VRP with pickup and returns:

A Vehicle is a PlanningEntity and contains a PlanningListVariable of LoadJob instances (either PICKUP or DROPOFF):

@PlanningEntity
class Vehicle {
    @PlanningId lateinit var planningId: String

    @PlanningListVariable lateinit var tour: MutableList<LoadJob>
    
    // ...
} 

A LoadJob is another PlanningEntity:

@PlanningEntity
class LoadJob {
    @PlanningId lateinit var id: String

    @InverseRelationShadowVariable(sourceVariableName = "tour") //
    var vehicle: Vehicle? = null

    lateinit var location: Location
        private set

    lateinit var load: Load
        private set

    // ... more shadow variables and variable listener setup for arrival time follows
}

With our current setup, we are already able to handle multiple (sub-)tours on a single vehicle (we detect loops in the PlanningListVariable). Now, we would also like to be able to allow users to pin sub-tours on a vehicle. I know that optaplanner/timefold currently does not support variable pinning together with PlanningListVariable. I also know that refactoring the Model to use a chained planning variable could be an option. However, I suppose this could be more work than the approach I'm currently thinking of:

I could make the vehicle a planning fact by moving the @PlanningListVariable to a new Tour class:

@PlanningEntity
class Tour {
    @PlanningId lateinit var planningId: String

    @PlanningListVariable lateinit var tour: MutableList<LoadJob>

    lateinit var earliestStart: OffsetDateTime

    lateinit var latestEnd: OffsetDateTime

    lateinit var vehicle: Vehicle
    
    // ...
} 

and simply reference the Vehicle from the Tour class.

I then could have constraints on Tour so earliestStart and latestEnd are respected when planning. This way, it should be possible to leave time slots for locked tours unassigned (and remove/add these tours in my transformation/persistence layer).

So my first and foremost question is: Is this a valid approach? Can optaplanner/timefold handle a model like this?

Followup questions:

  1. If the answer to the first question is no, what would be a better approach?
  2. If the answer to the first question is yes, is there an "ergonomic" way of grouping all tours on the same vehicle? I know I can use groupBy on a constraint stream - would this be the way to go?

Solution

  • I'm afraid that you're stretching the model to places where it hasn't been before - I can not give definitive answers to your question without trying it first; and I can not really try it without completely replicating this setup.

    My recommendation would be to try your approach and report back what issues (if any) you ran into. We can then discuss if those issues are something we can/want to address.

    The most generic answer to your original question is yes, though - technically, entities can be referenced from facts, just double-check that the cloners work properly. It may require sprinkling the code with @DeepPlanningClone here and there. (FULL_ASSERT environment mode for a few minutes should be enough to prove or disprove that.)