Solve the vehicle routing problem with time windows

The vehicle routing problem (VRP) is a popular academic optimization problem with numerous variants.

While you can map the vehicle routing problem to real-world tasks like planning deliveries or optimizing itineraries for field service technicians, very often you have to deal with at least one additional constraint: customers' availabilities.

This post will show you how to solve the vehicle routing problem using Timefold Solver.

# VRP with time windows

Let’s start by defining the problem. Same as the vanilla VRP, the task is to plan routes of N vehicles to visit M customers to minimize the driving time. The additional complexity comes from customers' availability in limited time windows. If the vehicle arrives at the destination too early, it has to wait, which is suboptimal. If it arrives too late, it’s even worse as the planned visit has to be rescheduled to some other day and all the mileage driven comes in vain.

# Domain model

The domain model takes advantage of the @PlanningListVariable: the Vehicle is the @PlanningEntity with a list of Customer instances to visit. The @PlanningListVariable enables the use of a few build-in shadow variables:

• @InverseRelationShadowVariable that points from the Customer to the assigned Vehicle.
• @PreviousElementShadowVariable and @NextElementShadowVariable that point to the previous and the next customer in the list respectively.

To calculate the arrival time at each customer, the model relies on the arrivalTimeshadow variable that is updated by the ArrivalTimeUpdatingVariableListener every time the previousCustomer or the vehicle changes.

# Constraints

The constraints are implemented using the Constraint Streams API and you can see them in the VehicleRoutingConstraintProvider.java.

# Service must be finished in time

Providing the service to the customer also takes time, expressed by the serviceDuration. Of course, the service duration counts towards the customer’s availability. This is a hard constraint.

protected Constraint serviceFinishedAfterDueTime(ConstraintFactory factory) {
    return factory.forEach(Customer.class)
            .filter(Customer::isServiceFinishedAfterDueTime)
            .penalizeLong(HardSoftLongScore.ONE_HARD,
                    Customer::getServiceFinishedDelayInMinutes)
            .asConstraint("serviceFinishedAfterDueTime");
}

# Minimize travel time

This is a soft constraint that penalizes the time spent driving per every vehicle, knowing the distances between individual locations.

protected Constraint minimizeTravelTime(ConstraintFactory factory) {
    return factory.forEach(Vehicle.class)
            .penalizeLong(HardSoftLongScore.ONE_SOFT,
                    Vehicle::getTotalDrivingTimeSeconds)
            .asConstraint("minimizeTravelTime");
}

Wait a second, where do we make sure we don’t arrive too early? The serviceFinishedAfterDueTime constraint does it for us, just indirectly. The more time vehicles spend waiting, the fewer customers they can visit without arriving too late.

# Try for yourself

1. git clone [email protected]:timefoldai/timefold-quickstarts.git
2. cd timefold-quickstarts/use-cases/vehicle-routing
3. mvn quarkus:dev
4. Open a browser and navigate to http://localhost:8080
5. Click on the solve button

If you want to try your own dataset, use the REST API. Click the Guide in the top-level menu to learn how to get started.

# Conclusion

The vehicle routing with time windows is a more practical variation of VRP, which we might translate to domains like field service technician or last mile delivery. You can solve all these using Timefold Solver.