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 with time windows 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:
-
@InverseRelationShadowVariablethat points from theCustomerto the assignedVehicle. -
@PreviousElementShadowVariableand@NextElementShadowVariablethat 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 arrivalTime shadow 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.
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.
