Published in Blog
Fast Planning Optimization with the Recommended Fit API
Discover how Timefold's Recommended Fit API offers swift, feasible adjustments to your plans, ensuring real-time adaptability to unexpected changes.
How does your business adapt when unexpected changes disrupt your carefully planned schedules? Can you quickly adjust a vehicle routing plan when a last-minute customer request comes in or an employee unexpectedly takes a day off? Are your current planning solutions flexible enough to handle these curveballs efficiently without requiring hours of recalibration?
The ability to swiftly respond to unforeseen circumstances isn’t just an advantage; it’s a necessity.
Timefold’s answer to this: the Recommended Fit API, providing immediate, feasible adjustments to existing plans, enabling businesses to respond to changes in real time. Whether it’s incorporating a new delivery stop or reassigning tasks due to sudden changes, the Recommended Fit API delivers quick and efficient solutions.
With Timefold, you can fetch solution recommendations and incorporate them into the final solution.
The Vehicle Routing Problem
The Vehicle Routing Problem (VRP) is a commonly encountered real-world scenario, and this article aims to use it as an example to elucidate the Recommended Fit API. It is important to understand that the Recommended Fit API is not limited to VRP, and it will work in any situation where quick responses to unexpected events are necessary.
Let’s suppose a solution for the VRP runs overnight to provide a feasible route plan for the next day. That means the process requires hours to complete. The available vehicles must visit a list of locations within their capacity and before a deadline. The goal is to minimize the total drive time of the vehicles. This article will demonstrate the feature in focus using models and resources from the VRP quickstart.
An Unexpected Phone Call
After optimizing the problem last night, the produced route plan is ready for execution. However, we receive a phone call from a customer who wishes to schedule a visit to a new location. The customer must now promptly know which vehicle to use and when to visit the new location.
We cannot re-optimize the problem with the new visit due to time constraints, as the customer is waiting on the phone. Therefore, the answer must quickly provide a feasible solution, including the new visit.
Solving Unexpected Events with the Recommended Fit API
Timefold has the Recommended Fit API that provides quicker suggestions when the problem changes. To reproduce the scenario described, please follow the steps outlined below:
-
Create an initial solution that reflects the optimization performed overnight.
-
Generate a new visit to reproduce the phone call event.
-
Call the RecommendedFit API to fetch recommendations and provide quick feedback to the client with available recommendations.
-
Once the customer chooses a recommendation, include it in the solution.
Create an Initial Solution
The Recommended Fit API expects a feasible solution as input, with all entities initialized except the one we want to add.
Generate a new location to visit
It’s worth noting that the unscheduled visit is part of the current solution visits list. Recommended Fit API searches for an uninitialized entity to start the optimization process. The process can only succeed if there is a single uninitialized entity.
Fetching recommendations with Recommended Fit API
At this moment, the customer is waiting for an answer. We need to specify three arguments to call the Recommended Fit API: the current solution, the unscheduled visit, and a proposition function that extracts the necessary details. Let’s find the visit we want to schedule:
// Find the visit
Visit visit = request.solution().getVisits().stream()
.filter(c -> c.getId().equals(request.visitId()))
.findFirst()
.orElseThrow(() -> new IllegalStateException("Visit %s not found".formatted(request.visitId())));The SolutionManager::recommendFit() function returns a list of recommendation instances.
Let’s retrieve the recommendations and gather the details of the vehicles:
// Fetch the recommendations
List<RecommendedFit<VehicleRecommendation, HardSoftLongScore>> recommendedFitList =
solutionManager.recommendFit(request.solution(), visit, v -> new VehicleRecommendation(v.getVehicle().getId(), v.getVehicle().getVisits().indexOf(c)));The recommendation call includes the current solution, unscheduled visit, and a function to extract the vehicle ID and position of the visit. As the recommendation list can be extensive, we will only provide the top five recommendations:
// Return the best five recommendations
if (!recommendedFitList.isEmpty()) {
return recommendedFitList.subList(0, Math.min(MAX_RECOMMENDED_FIT_LIST_SIZE, recommendedFitList.size()));
}
return recommendedFitList;The recommendation process involves evaluating the feasibility of various elements, also known as placement. Each placement receives a score based on the entire solution. The proposition function extracts the necessary information from the current placement.
After testing the placement, the solution reverts to its original state, undoing all changes made by the fitting in the placement. Therefore, the proposition function must extract data that won’t change after resetting the placement. In our example, the function extracts two pieces of information - the vehicle ID and the recommended visit position. None of them is affected or lost during the placement evaluation.
The list of recommendations sorts its elements based on their score, with the most favorable score at the top. When executing the VRP quickstart, a list of recommendations is presented as options:
The response follows the structure of the JSON snippet provided below:
[
{
"proposition": {
"vehicleId": "4",
"index": 5
},
"scoreDiff": {
"score": "0hard/-4soft",
"constraints": [
...
]
}
},
{
"proposition": {
"vehicleId": "3",
"index": 6
},
"scoreDiff": {
"score": "0hard/-1751soft",
"constraints": [
...
]
}
}
...
]Applying a Selected Recommendation
Upon receiving our recommendations, the customer selects the best one, which is the first element of the list. In order to incorporate a recommendation into a solution, let’s find the vehicle and visit targets:
// Find the target vehicle
String vehicleId = request.vehicleId();
Vehicle vehicleTarget = updatedSolution.getVehicles().stream()
.filter(v -> v.getId().equals(vehicleId))
.findFirst()
.orElseThrow(() -> new IllegalStateException("Vehicle %s not found".formatted(vehicleId)));
// Find the target visit
Visit visit = request.solution().getVisits().stream()
.filter(c -> c.getId().equals(request.visitId()))
.findFirst()
.orElseThrow(() -> new IllegalStateException("Visit %s not found".formatted(request.visitId())));Next, we must insert the unscheduled visit into the designated vehicle at the specific position. Afterward, update the score of the updated solution.
// Add the visit to the target vehicle at the expected position
vehicleTarget.getVisits().add(request.index(), visit);
// Recalculate the score for the updated solution
solutionManager.update(updatedSolution);We now have a revised route plan ready to be executed again. So far, we assumed the route plan started after the phone call. In this way, we don’t have to keep track of the routes already visited.
In cases where a new visit comes in after the route plan has started, we need to apply continuous planning techniques to manage them.
Conclusion
We explained the importance of optimization tools being able to respond quickly to unexpected events in real-life situations. Additionally, we evaluated a unique feature of Timefold Solver called Recommended Fit API, which provides feasible solutions promptly when dealing with unforeseen problem changes.
