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.
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:
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:
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:
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.
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.
Continue reading
Blog
Is PlanningAI a blessing for Operations Research?
Operations Research is, and has always been, about solving one of the world’s toughest challenges: planning problems. Finding the best way to allocate resources, schedule shifts, or route deliveries under an abundance of real-world constraints. It is widely accepted that optimizing those problems will make the world a better place. The value has never been in question. But the road to real-world adoption? That’s been another story. With PlanningAI, we can alter the narrative.
Blog
Why PlanningAI encompasses scheduling, routing, and strategic decision-making
PlanningAI intentionally captures scheduling, routing, and strategy because businesses naturally function across multiple timeframes and complexities. Find out more about the etymology of PlanningAI in this blog post.
Blog
Different problems, different solutions: PlanningAI and GenAI compared
Generative AI might be grabbing the headlines, but on the opposite end of the AI spectrum there’s a complex subset that’s been driving solutions long before the buzz began: PlanningAI. In this blog post, we’ll explain how PlanningAI en GenAI are fundamentally different, despite being both AI.