Continuous Planning Optimization with Pinning

How does your business adapt when unexpected changes disrupt your carefully planned schedules after a part of the plan has already been executed? Can you quickly adjust a vehicle routing plan when an additional urgent customer request comes in or an employee unexpectedly takes the afternoon off?

Perhaps you have read Fast Planning Optimization with the Recommended Fit API blog post by Frederico and you are wondering how to handle the cases where a new visit comes in after the route plan has started?

With Timefold, you can mark the historical part of the plan, telling the solver not to change it anymore. In addition, you can prevent changes to future parts of the plan which are to be executed "soon enough", such as redirecting a technician who had already started travelling to another customer.

In models such as Employee scheduling, marking the historical part of the plan is straightforward by using Timefold Solver’s Pinned planning entities feature. This article is focused on a more advanced pinning application for the Vehicle Routing Problem.

# The Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is a commonly encountered real-world scenario with numerous variants.

Let’s recall Frederico’s VRP definition from his blog post:

• The available vehicles must visit a list of locations within their capacity and before a deadline.
• The goal is to minimize the total driving time of the vehicles.

You can check the VRP quickstart and its documentation to get an idea how this scenario is implemented with Timefold.

# Continuous planning example

Imagine an initial plan for the day has been created and optimized before the vehicles start to work. The yellow blocks with "T" or "Travel" illustrate travelling time to the customer’s location, the green ones represent a technician’s visit at a particular customer):

The vehicles are on their way to customers and the shift goes on as expected until noon, when a new customer calls in and needs to schedule an urgent visit for today:

The plan needs to be adjusted by including a new customer visit, but we need to let the solver know that some of the visits must not be changed (we call them pinned), either because they are already done, or a change in their planning would be disruptive. See a possible plan incorporating the change at 12:00:

By the time of re-planning (12:00), the blue customer visits are pinned: either they have already been finished, or a vehicle has already started travelling to their location (see Beth’s last visit). Not changing their plan is the first requirement (R1) for pinning. We will discuss its implementation for VRP models shortly.

Notice the time the newly requested customer visit is planned to: travelling to the customer starts at 12:00, even though this visit has been assigned to Carl whose last visit finished around 10:00. This is the second requirement (R2) for pinning: any visit cannot be planned for a time interval already in the past. Again, we will discuss its implementation for VRP models in the next section.

The adjusted plan conforms with the above requirements and the execution continues until another customer calls in at 16:00, requesting a visit for that day:

Let’s check how an updated solution at 16:00 could look like:

We can see that a few other visits have been finished by 16:00, therefore they were marked as pinned. The newly requested visit is planned after the time of re-planning (16:00).

In addition, you can see that the last visit originally assigned to Ann has been re-assigned to Beth. Such a re-assignment is possible, because the last visit was not pinned, and desired, because it allows the solver to find a more optimal solution: for instance by optimizing the travel distance for all vehicles as Beth’s last two visits locations are very close to each other.

# Implementation

How to implement the two aforementioned requirements in a VRP model?

# Requirement R1: do not change the plan for visits in history

In a VRP model, the list of visits assigned to a vehicle shift can be implemented by a Planning list variable, such as in the VRP quickstart. The requirement not to change the plan for visits that already finished can be implemented using PlanningPinToIndex, for example:

public class VehicleShift {
  // omitted other class members

  @PlanningListVariable
  private List<Visit> visits = new ArrayList<>();

  @PlanningPinToIndex
  private int firstUnpinnedIndex = 0;
}

However, we need an easy way how to specify the time instant defining which visits are to be considered pinned. For this purpose, we introduce a new attribute into the Vehicle Route Plan model, named, for instance, freezeDeparturesBeforeTime (corresponding to the blue line in the diagrams above). The model uses the attribute value to set VehicleShift.firstUnpinnedIndex (for all vehicle shifts) to the index of the first unpinned visit in the list of visits assigned to that vehicle shift.

Before submitting the plan to the solver, the model calculates the firstUnpinnedIndexvalues automatically by determining the pinned and unpinned visits using the following criteria:

• every visit ending before freezeDeparturesBeforeTime is pinned,
• every visit that a vehicle already started travelling to before freezeDeparturesBeforeTime is pinned as well,
• all other visits are unpinned.

# Requirement R2: any visit cannot be scheduled for a time period in the past

By having set the VehicleShift.firstUnpinnedIndex value, we ensure that the solver can schedule any unassigned visit only after all pinned visits. However, this does not guarantee that the last pinned visit did not end several hours before freezeDeparturesBeforeTime - see Carl’s second visit in Continuous planning example.

In order to fulfil this requirement, we need to set a lower bound when a vehicle shift can start travelling to a visit and apply it during visit’s arrival time calculation in a VariableListener, based on this one from the VRP quickstart:

LocalDateTime calculateArrivalTime(Visit visit, LocalDateTime previousDepartureTime, LocalDateTime freezeDeparturesBeforeTime) {
    if (visit == null || previousDepartureTime == null) {
        return null;
    }

    LocalDateTime adjustedDepartureTime = adjustByFreezeTime(previousDepartureTime, freezeDeparturesBeforeTime);
    return adjustedDepartureTime.plusSeconds(visit.getDrivingTimeSecondsFromPreviousStandstill());
}

Let’s think about the time adjustment method implementation:

LocalDateTime adjustByFreezeTime(LocalDateTime timeToAdjust, LocalDateTime freezeDeparturesBeforeTime) {
    return freezeDeparturesBeforeTime != null && timeToAdjust.isBefore(freezeDeparturesBeforeTime) ? freezeDeparturesBeforeTime : timeToAdjust;
}

However, this approach does not work correctly when re-planning happens multiple times with different freezeDeparturesBeforeTime values - in our example scenario above, the adjustByFreezeTime(…​) method would delay the travel start of Carl’s second visit not to 12:00 but to 16:00.

To remedy the situation, we need to remember the minimum time when a vehicle is allowed to start travelling to each visit:

public class Visit {
  // other class members omitted

  private LocalDateTime minimumStartTravelTime;
}

Every unpinned visit gets the minimumStartTravelTime field set to the current value of freezeDeparturesBeforeTime, the model can do it before submitting the plan to the solver. Every pinned visit already has the value set either from the previous pinning, or, in the case of no previous pinning, the planning window start (or another sensible default):

void updateVisitsMinimumStartTravelTime(VehicleRoutePlan plan) {
    LocalDateTime effectiveMinimumStartTravelTime =
            plan.getFreezeDeparturesBeforeTime() != null ? plan.getFreezeDeparturesBeforeTime()
                    : plan.getPlanningWindow().getStartDate();

    plan.getAllVisits().forEach(visit -> {
        if (!visit.isPinned()) {
            visit.setMinimumStartTravelTime(effectiveMinimumStartTravelTime);
        } else if (visit.getMinimumStartTravelTime() == null) {
            // the edge case of freezeDeparturesBeforeTime set for the initial solving,
            // some visits may already be pinned
            visit.setMinimumStartTravelTime(plan.getPlanningWindow().getStartDate());
        }
    });
}

The adjustByFreezeTime(…​) method is adjusted to take it into account, handling multiple pinnings correctly:

LocalDateTime adjustByFreezeTime(LocalDateTime timeToAdjust, Visit visit) {
    LocalDateTime travelStartsFrom = visit.getMinimumStartTravelTime();
    return travelStartsFrom != null && timeToAdjust.isBefore(travelStartsFrom) ? travelStartsFrom : timeToAdjust;
}

Then, the arrival time calculation can look as follows:

LocalDateTime calculateArrivalTime(Visit visit, LocalDateTime previousDepartureTime) {
    if (visit == null || previousDepartureTime == null) {
        return null;
    }

    LocalDateTime adjustedDepartureTime = adjustByFreezeTime(previousDepartureTime, visit);
    return adjustedDepartureTime.plusSeconds(visit.getDrivingTimeSecondsFromPreviousStandstill());
}

# Conclusion

We have shown the importance of being able to adjust a plan which already started to be executed and one possible approach to it using Pinned planning entities.

With Timefold, it is possible to handle this use-case for most models, including VRP, allowing the customer to react on unexpected requirements in time.