Published in Blog
Optimizing Santa’s Travels with Timefold Solver
Discover how you can use Timefold Solver, our Open Source AI library, to optimize Santa's travel route. Leave no gift un-gifted!
Merry Christmas everyone!
We are getting extremely close to Christmas and Santa’s preparations are in full swing. Santa is running a very serious enterprise!
-
The gifts needs to be constructed and nicely packaged
-
Elves need a work schedule so they know when and where they should help
-
And then there is the big question of “how do I visit everyone as efficiently as possible?”
These planning problems are typically tricky to solve… but we can all do this using the power of Java and Timefold, an Open Source AI Solver. So put on your Christmas hats, open your laptops and let’s see how we can use these tools to optimize Santa’s road trip! (or is that a sky trip,… I don’t know).
Video walkthrough
This blogpost is also available as a step-by-step video.
Step 1: Model our domain
First, we model our domain, just like we’d do with any other application. With Timefold Solver you can model your domain in Plain Java Objects. Our class diagram will look something like this.
The class structure is pretty straightforward. We got the jolly big man on one side and we have the children Santa wants to visit on the other. They both have a link to the Location object, which is nothing more than a POJO containing the latitude and longitude.
Next we need to order the Visits so Santa can be home again as soon as possible. This is where Timefold Solver comes in. The solver will find a near-optimal order of those visits to keep Santa’s travel time to a minimum.
Timefold Solver needs a little bit more information than a plain POJO. Much like the Java Persistence API (JPA), we need to add a few annotations to our classes for the magic to work. In our case we need to add some annotations to our Santa class. The Visit and Location classes remain untouched.
@PlanningEntity
public class Santa {
private Location homeLocation;
@PlanningListVariable
private List<Visit> visits;
// excluded constructor getter/setter
}@PlanningEntity indicates the solver should make changes to instances of the annotated class. Anything which is changeable is typically called a planning variable. An entity can have multiple planning variables, but in this case we only want the solver to change the list of visits Santa will use. To indicate this, we annotate the visits with @PlanningListVariable.
The solver will first fill the list with visits using a greedy algorithm. Greed isn’t good, especially not during Christmas times, so this initial solution will be far from optimal. To improve the situation, Timefold Solver moves the items in the list, looking for a combination which results in a better solution.
Step 2: Add Constraints
We have however not defined what a “good” or “better” solution is. Next, we define a constraint.
A constraint is a business rule expressed in code which modifies the score for a given solution. In our example, the best solution minimizes total travel time. We model this in Timefold Solver using Constraint Streams.
public class SantaConstraintProvider implements ConstraintProvider {
// NOTE: Normally you'd want to calculate a Distance Matrix before starting the solver.
DrivingTimeCalculator drivingTimeCalculator = DrivingTimeCalculator.getInstance();
public static final String MINIMIZE_TRAVEL_TIME = "minimizeTravelTime";
@Override
public Constraint[] defineConstraints(ConstraintFactory factory) {
return new Constraint[]{
minimizeTravelTime(factory)
};
}
/**
* Creates a constraint which will reduce the SOFT score by 1 for each second driven by a Santa.
*/
Constraint minimizeTravelTime(ConstraintFactory factory) {
return factory.forEach(Santa.class)
.penalizeLong(HardSoftLongScore.ONE_SOFT,
santa -> drivingTimeCalculator.getTotalDrivingTimeSeconds(santa))
.asConstraint(MINIMIZE_TRAVEL_TIME);
}
}In this example for constraint minimizeTravelTime, we select all Santas (yes, in some situations there might be some helpers) and we calculate the total driving time for each Santa. Every second a Santa needs to drive to deliver the gifts will be penalized, decreasing the score of the solution. The solver uses an advanced algorithm to optimize this score.
Santa is a bit weird when it comes to calculating travel time. He doesn’t need roads, so we calculate the distance “as the crow flies”, using the Haversine formula. To convert the distance to total travel time, we’ll assume Santa’s average speed is half the speed of light. You can find the full implementation of this calculation in the DrivingTimeCalculator class on GitHub. In most cases, you should calculate a distance matrix before starting the solving process.
Step 3: Initialize the problem and run!
Now it’s time to bring it all together. The SantaPlan class is once again a POJO, this time collecting all the elements Timefold Solver can work with. It’s annotated with @PlanningSolution and holds all problem facts, planning entities, and a score.
@PlanningSolution
public class SantaPlan {
@PlanningEntityProperty
private Santa santa;
@ProblemFactCollectionProperty
@ValueRangeProvider
private List<Visit> visits;
@PlanningScore
private HardSoftLongScore score;
// excluded constructor getter/setter
}This class contains:
-
Our Santa as a @PlanningEntityProperty. This indicates that for this solution, Santa is a planning entity, aka an object which will be changed by the solver.
-
A list of Visits. These are the visits which will be assigned to Santa. It’s annotated both with @ProblemFactCollectionProperty to indicate it’s a collection of facts which don’t change while solving, and @ValueRangeProvider to indicate this field provides a range of values the solver can use to assign to Santa, specifically to his @PlanningListVariable field shown earlier.
-
A score field annotated with @PlanningScore, which the solver will update with the score of the solution after it has evaluated the constraints.
Next we need a Solver instance which will accept this @PlanningSolution and start working its magic (aka math) on it. While Timefold Solver works in any Java application, when using the Spring or Quarkus extensions, a SolverFactory is autoconfigured based on your configuration properties and classes found on the classpath, like the SantaConstraintProvider we showed before.
In this example I’ll use Quarkus, mainly because the logo looks like a star and has the most Christmas-y colors out of the 2 frameworks.
public class SantaResource {
private final SolverFactory<SantaPlan> solverFactory;
// CDI Injected solverFactory
public SantaResource(SolverFactory<SantaPlan> solverFactory) {
this.solverFactory = solverFactory;
}
/**
* Uses a solver to sort a list of visits
* @param visits the locations santa needs to visit
* @return an optimized plan
*/
public SantaPlan solve(List<Visit> visits) {
// This is the location of Santa's village in Rovaniemi, Finland
Santa santa = new Santa(new Location(66.5039, 25.7294));
SantaPlan santaPlan = new SantaPlan(santa, visits);
Solver<SantaPlan> solver = solverFactory.buildSolver();
return solver.solve(santaPlan);
}
}Without configuration the solver will keep searching for better solutions indefinitely. That’s not good, because Santa’s deadline is coming up. Luckily, we can determine how long the solver should run with some configuration.
quarkus.timefold.solver.termination.spent-limit=5s
Note: The call to Solver.solve() above is blocking. To execute asynchronously, we could inject and use a SolverManager instead.
Step 4: Visualize
We can run the code with the Solver, calculate a near-optimal route and then print it… but printing it just doesn’t work for Santa, he needs a map!
These kinds of problems just beg to be visualized. While Timefold doesn’t come with visualizations out of the box, we can expose the data through an API and then have some Javascript to visualize it. In this case, I’ll use the popular LeafletJS library together with the data from OpenStreetMap to visualize our route.
@Path("santa")
public class SantaResource {
// Fields and constructor excluded
@POST
@Path("plan")
@Consumes(MediaType.APPLICATION_JSON)
@Produces(MediaType.APPLICATION_JSON)
public SantaPlan solve(List<Visit> visits) {
Santa santa = new Santa(new Location(66.5039, 25.7294));
SantaPlan santaPlan = new SantaPlan(santa, visits);
Solver<SantaPlan> solver = solverFactory.buildSolver();
return solver.solve(santaPlan);
}
}The code above shows the necessary annotation to expose the objects through an API using Quarkus. Next is the Javascript code used to create a clickable map and render the results from the solver.
// Prepare a custom icon, since default one is not "Christmas" enough.
const treeIcon = L.icon({iconUrl: 'tree-marker.png', iconSize: [20, 20]})
const map = L.map('map', {doubleClickZoom: false}).setView([66.5039, 25.7294], 4);
L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
attribution: '© <a href="https://www.openstreetmap.org/">OpenStreetMap</a> contributors',
}).addTo(map);
// Create a layer group,
const linesGroup = L.layerGroup().addTo(map);
const visitsOnMap = [];
// Allow adding visits on click
map.on('click', function(e) {
const { lat, lng } = e.latlng;
addLocation(lat, lng);
});
// Add a location to the map and to the javascript array
function addLocation(lat, lng) {
visitsOnMap.push({
id: visitsOnMap.length,
location: {
lat: lat,
lng: lng
}
})
// Add a marker at the clicked location
L.marker([lat, lng], {icon: treeIcon}).addTo(map);
}
// The function which will call the solver and visualize the result
function solve() {
linesGroup.clearLayers();
fetch('http://localhost:8080/santa/plan', {
method: 'POST',
headers: {
'Content-Type': 'application/json',
},
body: JSON.stringify(visitsOnMap)
})
.then(response => response.json())
.then(data => {
const homeLocation = data.santa.home;
const locations = data.santa.visits.map(visit => visit.location);
L.polyline([homeLocation, ...locations, homeLocation]).addTo(linesGroup);
return data;
})
.catch(error => {
console.error('Fetch error:', error);
});
}The result is a backend and a UI, with a map which allows us to add locations and a "solve" button which will call the solver and eventually draws the result on the map.
The full implementation of this very basic UI can be found in the /src/main/resources/ folder of the GitHub repository.
Sending off Santa
In this post we helped Santa to find a near-optimal route. This is only a basic example of what is possible in Java using Timefold Solver. Finally, some inspiration for people who’d like to make changes:
-
Use a SolverManager instead of the SolverFactory and run the solver asynchronously while updating the UI with intermediate results
-
Add multiple helpers for Santa, splitting the visits among them
-
Add more constraints, for example forcing Santa to only visit kids when they are asleep
You can find this project on GitHub. Be sure to check it out and try the demo yourself! For more elaborate examples, check out the extensive Timefold Solver Quickstarts repository.
To all who celebrate I wish you a very merry Christmas and all the good things in the new year!
