We are getting extremely close to Christmas and Santa’s preparations are in full swing. You might not realize it but 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 an Open Source AI library, Timefold 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).
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 the 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 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 solution, 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.
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.
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.
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 the most 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.
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.
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 an 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.
Don’t hesitate to reach out if you want to learn more!
To all who celebrate I wish you a very merry Christmas and all the good things in the new year!
steinhauer.software