OptaPlanner EOL notice - Timefold offers support
By

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.

Vehicle rounting problem data model

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.

Vehicle rounting problem data model

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.

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:

  1. Create an initial solution that reflects the optimization performed overnight.

  2. Generate a new visit to reproduce the phone call event.

  3. Call the RecommendedFit API to fetch recommendations and provide quick feedback to the client with available recommendations.

  4. 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.

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:

List of recommendations

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.

Continue reading

  • Red Hat: OptaPlanner End Of Life Notice (EOL)

    Timefold, led by former core OptaPlanner engineers, offers a seamless transition with extended support and accelerated innovation.

  • Newsletter 4: A big Speed Upgrade for Timefold - Our First Customer Story and AMA!

    Unlock unprecedented speed with Timefold's latest update! Essential for OptaPlanner and pre-1.8.0 users – upgrade now for instant gains

  • How fast is Java 22?

    Explore the performance of Java 22 against Java 21, this time also with GraalVM.

  • Continuous Planning Optimization with Pinning

    Discover how to make non-disruptive, feasible adjustments to your already in-progress plans with Timefold, ensuring real-time adaptability to unexpected changes.

  • Newsletter 3: Explainable AI for Planning Optimization

    Discover how Timefold's ScoreAnalysis API builds trust in automated planning. And don't forget to join Timefold's first AMA on Youtube Live on March 19th!

  • Use Multiple Solvers in the Same Application

    Learn how to configure and inject multiple SolverManager instances in one application using Timefold Solver, tackling distinct planning problems seamlessly.

Sign up for our newsletter

And stay up to date with announcements, the latest news, events, roadmap progress & product updates from Timefold!

We care about the protection of your data. Read our Privacy Policy.