Vehicle Routing (VRP)

A Vehicle Routing Problem (VRP) is a optimization problem for which each customer is visited exactly once by one of the vehicles. A solution decides for each vehicle which customers to visit and in which order, while minimizing the driving time and adhering to constraints.

Building effective Vehicle Routing management software is complex. There are various constraints to keep into account to ensure operational efficiency. For instance: vehicle capacity, driver skill, traffic, …At Timefold we support software builders with the right toolbox to tackle these hard mathematical problems. Our VRP model helps companies to manage their fleet of vehicles efficiently and reduces wasteful planning.

Constraints

Like other Optimization problems, the Vehicle Routing Problem has Constraints. Constraints define the rules and objectives of the VRP solution. We distinguish between hard and soft constraints

Hard constraints

Hard constraints represent limitations or requirements that cannot be violated.

They are often essential for ensuring the feasibility, practicality or following business rules and SLAs of the optimized solution. Failure to satisfy a hard constraint would render the solution infeasible, impractical, in contradiction to legislation for implementation.

Hard constraint examples in VRP:

• Vehicle capacity: a vehicle can’t carry more items than its capacity.
• Skill: Driver skill, for instance Hazardous Materials Handling, which represents the driver’s ability to handle and transport hazardous materials safely and in compliance with regulation.
• Time windows: Restricts arrival time per customer. For example: arrive between 8 AM and 10 AM.
• Travel time: Traveling from one location to another takes time.
• Customer service duration: a vehicle must stay at the customer for the length of the service duration.

Soft constraints

Soft constraints represent a cost reduction, preferences, service quality, employee wishes, …Meeting them is desirable but not mandatory for a feasible planning solution.

Optimizing VRP for the desired business goals

Optimizing for the real world

Whilst optimizing a VRP, goals can be to minimize costs, driving time, or distance. It’s key to be able to differentiate and combine these or other business goals for the best outcome.

Driving time optimization, a vital VRP aspect, seeks to reduce the total time vehicles spend on the road considering traffic conditions, speed limits, and more.

Another crucial aspect is driving distance optimization. Shorter distances lead to less fuel usage and vehicle wear, reducing costs. Using elements like the shortest path, road conditions, and vehicle characteristics to determine optimal routes.

Total cost optimization in VRP extends to maintenance costs, driver wages, vehicle depreciation, and opportunity costs from inefficient routing.

Integration with maps

To precalculate road costs Timefold can be integrated with other technologies. Typical solutions precalculate road costs include GraphHopper (embeddable, offline Java engine), Open MapQuest (web service) and Google Maps Client API (web service).

Why solving a Vehicle Routing Problem is complex

As the number of customers and vehicles increases, the possible combinations grow exponentially, making exhaustive search infeasible. Additionally, incorporating constraints like time windows and capacity limits further escalates the complexity.

In Computer Science, VRP is classified as an NP-Hard problem. That means it’s notoriously hard to scale out. A mathematical planning optimization solver like Timefold has a proven track record of dealing with this complex matter.

Operational fit

When handling day-to-day planning for vehicle routing you need your planning software to offer you:

• Continuous planning: Dynamically adapting and updating the optimized routes and schedules as new information becomes available.
• Pinning: Fixing or locking specific elements of the problem to their current state or desired values. For instance: customer preference to be serviced by a specific driver.
• Overconstrained planning: Making visits optional. When there are too few resources to cover all the work, help find a solution.
• Real-time planning: React on real-time disruptions of the plan within milliseconds.

Variations of VRP

Whilst there are various variations of the Vehicle Routing Problem they are mainly the basic Vehicle Routing Problem with specific constraints added to it.

A non-exhaustive list:

• Capacitated Vehicle Routing Problem (CVRP): Accounts for limited vehicle capacities, ensuring that the total demand served by each vehicle does not exceed its capacity.
• Vehicle Routing Problem with Time Windows (VRPTW): Incorporates time constraints for customer visits, ensuring that deliveries or services occur within specific time intervals.
• Split Delivery Vehicle Routing Problem (SDVRP): Allows splitting customer demands across multiple vehicles, providing more flexibility in route planning.
• Vehicle Routing Problem with Heterogeneous Fleets (VRPHF): Addresses scenarios where the fleet consists of vehicles with different capacities, characteristics, or capabilities.
• Dynamic Vehicle Routing Problem (DVRP): Deals with real-time changes in demand and traffic conditions, requiring adaptive route planning to optimize resource utilization.