Simplify the Shadow Variable Listener Implementation

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.

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.