Published in Blog
Simplify the Shadow Variable Listener Implementation
Learn how to simplify creating listeners for planning list variables with the new shadow variable @CascadingUpdateShadowVariable.
Imagine reducing your code by 90% while making your optimization models more efficient and easier to maintain.
Sounds impossible? Not anymore.
With Timefold’s new @CascadingUpdateShadowVariable,
you can streamline complex planning tasks—like updating the arrival times in a vehicle route—into just a few lines of code.
In this article,
I’ll show you how this powerful new feature can simplify your codebase,
enhance performance,
and free you from the tedious task of writing custom listeners.
We will demonstrate how to simplify the Vehicle Route Problem (VRP),
turning 60 lines of code into 5.
The challenge: Managing Tail Chain updates in VRP
Timefold Solver has a useful feature called shadow variables.
A shadow variable is a planning variable that can be deduced from the state of genuine planning variables,
such as the arrival time of a given visit
or the following visit of a vehicle route.
The shadow variable @ShadowVariable provides an approach that allows implementing a custom listener to update the variable values.
Before Timefold Solver 1.13.0,
you would update a chain of connected elements using the @ShadowVariable listener.
This robust solution can be applied to any related use case. However,
at Timefold, we aim to simplify your life by offering solutions that enhance your models' understandability
and improve their performance.
And now we’ve made it so that creating a separate listener to update source variables is sometimes unnecessary.
The upcoming sections will initially discuss the requirements for updating the tail chains. Following that, the different approaches for configuring a listener that updates a specified source shadow variable and triggers changes to the subsequent elements of a planning list variable will be explained.
Tail chains need updating
Let’s consider the VRP problem definition. Given a set of vehicles and a list of locations to visit, each visit carries the expected arrival time to the destination. We estimate the arrival time based on the arrival time to the previous location and the travel time between locations.
In the previous image, the vehicle arrives at Location A at 08:00. After that, it travels to Location B, arriving at 09:00, and then travels to Location C. We have a series of related locations that need to be updated sequentially. That means if there are any changes in the arrival time at Location A, all subsequent locations must update their arrival times. In other words, a tail chain update is needed.
To illustrate the use case,
let’s take a look at the Visit model class:
public class Visit {
...
@InverseRelationShadowVariable(sourceVariableName = "visits")
private Vehicle vehicle;
@PreviousElementShadowVariable(sourceVariableName = "visits")
private Visit previousVisit;
@NextElementShadowVariable(sourceVariableName = "visits")
private Visit nextVisit;
...
private LocalDateTime arrivalTime;
}The arrivalTime field contains the vehicle’s arrival time,
which the constraint can utilize to impose penalties for missing deadlines.
The next two sections explain how to use the @ShadowVariable
and @CascadingUpdateShadowVariable listeners, respectively.
The old way: implementing shadow variable listeners
The @ShadowVariable triggers a listener when one or more source shadow variables change.
Let’s update the model Visit:
public class Visit {
...
@InverseRelationShadowVariable(sourceVariableName = "visits")
private Vehicle vehicle;
@PreviousElementShadowVariable(sourceVariableName = "visits")
private Visit previousVisit;
@NextElementShadowVariable(sourceVariableName = "visits")
private Visit nextVisit;
@ShadowVariable(variableListenerClass = ArrivalTimeUpdatingVariableListener.class, sourceVariableName = "vehicle")
@ShadowVariable(variableListenerClass = ArrivalTimeUpdatingVariableListener.class, sourceVariableName = "previousVisit")
private LocalDateTime arrivalTime;
}Next,
let’s implement the ArrivalTimeUpdatingVariableListener:
public class ArrivalTimeUpdatingVariableListener
implements VariableListener<VehicleRoutePlan, Visit> {
...
@Override
public void afterVariableChanged(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit visit) {
if (visit.getVehicle() == null) {
if (visit.getArrivalTime() != null) {
scoreDirector.beforeVariableChanged(visit, ARRIVAL_TIME_FIELD);
visit.setArrivalTime(null);
scoreDirector.afterVariableChanged(visit, ARRIVAL_TIME_FIELD);
}
return;
}
Visit previousVisit = visit.getPreviousVisit();
LocalDateTime departureTime =
previousVisit == null ? visit.getVehicle().getDepartureTime() : previousVisit.getDepartureTime();
Visit nextVisit = visit;
LocalDateTime arrivalTime = calculateArrivalTime(nextVisit, departureTime);
while (nextVisit != null && !Objects.equals(nextVisit.getArrivalTime(), arrivalTime)) {
scoreDirector.beforeVariableChanged(nextVisit, ARRIVAL_TIME_FIELD);
nextVisit.setArrivalTime(arrivalTime);
scoreDirector.afterVariableChanged(nextVisit, ARRIVAL_TIME_FIELD);
departureTime = nextVisit.getDepartureTime();
nextVisit = nextVisit.getNextVisit();
arrivalTime = calculateArrivalTime(nextVisit, departureTime);
}
}
...
}Whenever the vehicle or previousVisit changes, the listener automatically updates the subsequent visits.
The new way: simplifying with Cascading Updates
As of Timefold Solver 1.13.0,
the @CascadingUpdateShadowVariable does not require a separate listener class.
Instead,
we add a new method to the domain class that updates the related shadow variables.
Let’s update the Visit class with the cascading shadow variable annotation:
public class Visit {
...
@InverseRelationShadowVariable(sourceVariableName = "visits")
private Vehicle vehicle;
@PreviousElementShadowVariable(sourceVariableName = "visits")
private Visit previousVisit;
@NextElementShadowVariable(sourceVariableName = "visits")
private Visit nextVisit;
@CascadingUpdateShadowVariable(targetMethodName = "updateArrivalTime")
private LocalDateTime arrivalTime;
}After that,
we need to add a method called updateArrivalTime with the logic to update arrivalTime:
private void updateArrivalTime() {
if (previousVisit == null && vehicle == null) {
arrivalTime = null;
return;
}
LocalDateTime departureTime = previousVisit == null ? vehicle.getDepartureTime() : previousVisit.getDepartureTime();
arrivalTime = departureTime != null ? departureTime.plusSeconds(getDrivingTimeSecondsFromPreviousStandstill()) : null;
}The method must not be static
and must not accept any parameters.
Timefold Solver triggers updateArrivalTime after all events are processed.
Therefore,
the listener will be the last one executed during the event lifecycle.
Additionally,
it automatically propagates changes to the subsequent visits
and stops when the arrivalTime value does not change
or when it reaches the end.
Conclusion
Updating a set of interconnected elements in a specific order is a common scenario when defining your optimization model. Timefold Solver provides different solutions for defining listeners that update shadow variable sources in a specific sequence. The new Cascading Update Shadow Variable simplifies creating listeners for planning list variables, resulting in code that is easier to write, read, and maintain.
