Allow @ShadowSources path to traverse through non-planning variables

Aperta
  • Qualcosa non va?
#2,331 3 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 2 giorni

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
48/100
Tipo di issue
Funzionalità
Chiarezza
Abbastanza chiara
Stato di attività
Tranquilla
Stack tecnologico
java
Ambito
ai

Direzione di ricerca

Start with the @ShadowSources annotation and the Vehicle, Tour, and Stop model shown in the issue, tracing how shadow-source paths are resolved. Verify how the plain Stop.tour reference and Tour.vehicle or Tour.previousTour are represented, then define completion as allowing the supplier path to traverse those non-planning references without breaking existing shadow-variable behavior.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

process/needs triage

Is your feature request related to a problem? Please describe.
Our domain is basically a vehicle routing problem. In contrast to the "basic" setup each stop is not just a single stop but effectively a fixed tour of multiple stops which we are planning on the vehicles. We had a pretty complicated setup with variable listeners and chained entities and are currently migrating to Timefold v2.1.

As of now the vehicle has a planning list variable of tours and each tour has a fixed list of stops. Each stop has a parent reference to the tour it belongs to and it has a shadow variable drivingTime that is calculated by a supplier. For all stops except the first one the driving time just depends on the vehicle (during solving), because the previous stop is fixed and for the first stop in a tour it also depends on the (last stop of the) previous tour.

The problem we are running into is that to access the vehicle and the previous tour we need to traverse through the parent reference to the tour within the shadow source which is not possible, because it's just a plain reference and not part of the entity meta model.

@PlanningEntity
public class Vehicle {
    @PlanningListVariable
    private List<Tour> tours = new ArrayList<>();
}

@PlanningEntity
public class Tour {
    @PreviousElementShadowVariable(sourceVariableName = "tours")
    private Tour previousTour;
    
    @InverseRelationShadowVariable(sourceVariableName = "tours")
    private Vehicle vehicle;
    
    private List<Stop> stops = new ArrayList<>();
}

@PlanningEntity
public class Stop {
    @ShadowVariable(supplierName = "calculateDrivingTime")
    private Duration drivingTime;

    private Tour tour;

    @ShadowSources({"tour.vehicle", "tour.previousTour"})
    public Duration calculateDrivingTime() {
        //...
    }
}

Describe the solution you'd like
I'm not sure whether this would be the best solution but considering the alternatives I can think of this seems like the best solution to me right now: Allow the @ShadowSources path to traverse through non-planning variables, possibly by marking them somehow as a problem fact?

Describe alternatives you've considered
Alternatives I could think of, which I haven't tested yet as it seems rather hacky to me.

  1. Make the tour-stop relation a planning variable and make sure that their values are never actually changed. This would add them to the meta model but it would be really hacky in my opinion, because it would misuse planning variables that should never be planned.
  2. Effectively get rid of the tour class and directly plan stops. However, this would need to make sure that all stops of a tour are only moved together. With hard constraints this would introduce a huge amount of useless moves. Therefore this would probably require custom moves to always move all stops together. This might work but from a modeling perspective it doesn't feel great because it's not actually representing the problem and also from a complexity and maintainability perspective it wouldn't be ideal.
  3. Have the shadow variable(s) and supplier(s) in the tour instead of the stops and update everything at once. While this probably works for the minimal example above it would probably run into problems with our more complicated actual setup. There each stop can have dependencies to other stops of other tours on other vehicles and it could also happen that two tours reference each other multiple times in a non-cyclic way that requires bouncing back and forth between the two tours when calculating their times. If the listeners would be on the tours it would probably require a lot of redundant calculations, because we have to calculate the whole tour, instead of only the necessary times and I'm not sure whether the built-in cycle detection of Timefold wouldn't abort this back-and-forth.

Additional context

Lingua principale
Java
Stelle
1.8k
Fork
242
Merge medio
2g 14h
PR unite (30g)
43

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di TimefoldAI/timefold-solver

Tutte le issue di TimefoldAI/timefold-solver

Issue simili

Altre issue su Java

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.