Allow @ShadowSources path to traverse through non-planning variables

Open
#2,331 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
48/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Quiet
Tech stack
java
Domain
ai

Research direction

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.

Written by the indexing model from the issue text.

Description

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

Dominant language
Java
Stars
1.8k
Forks
228
Avg merge
1d 13h
Merged PRs (30d)
46

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from TimefoldAI/timefold-solver

All issues in TimefoldAI/timefold-solver

Similar issues

More Java issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.