Allow @ShadowSources path to traverse through non-planning variables
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 48/100
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
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.
- 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.
- 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.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from TimefoldAI/timefold-solver
-
component/docs
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
TimefoldAI/timefold-solver#2671 ·
-
process/needs triage
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
TimefoldAI/timefold-solver#2652 ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
TimefoldAI/timefold-solver#2647 · 1 reaction ·
-
component/service
Difficulty 3/5 1-2 days Newbie friendliness 66/100
TimefoldAI/timefold-solver#2629 ·
-
component/docs
TimefoldAI/timefold-solver#2626 · 1 assignee ·
All issues in TimefoldAI/timefold-solver
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
bug needs triage
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
Difficulty 1/5 Under an hour Newbie friendliness 94/100
objectionary/hone-maven-plugin#1061 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
spring-projects/spring-modulith#1895 ·