Matching Vehicles and Drivers with Skills and Time Windows in VRP API

Directions API Route Optimization API
1

Hello GraphHopper community,

I’m using the VRP API (https://graphhopper.com/api/1/vrp?key=<your_key> ) to optimize routes for my delivery operations. I’m passing my delivery locations (services ) and available vehicles (vehicles ) in the JSON request.

In my system, vehicles have specific “skills” (constraints) that match the requirements of certain deliveries, similar to how drivers have skills. However, the time windows (availability) are associated with the drivers, not the vehicles themselves.

Is there a way to effectively match vehicles and drivers through the GraphHopper engine, considering both their skills and the drivers’ time windows? I’m looking for a solution that allows me to:

  1. Assign deliveries to vehicles based on matching skills.
  2. Assign drivers to vehicles based on their time start and time limits.

Any suggestions or insights on how to achieve this would be greatly appreciated.

Thank you!

2

Hello Alessandro,

There is no difference between vehicles and drivers and you’ll have to do the assignment of the drivers to the vehicles before solving the vehicle routing problem.

Can you describe the problem in more detail? Maybe it is still possible with our API.

Regards
Peter

3

Thanks Peter,

Let me give you an example: I have 5 vans, two of which have special skills that match the skills required by some of the services I need to optimize. Then I have drivers, each with different working hours. How can I find the right match between the driver to use based on the unloading windows of the various services, using the correct vehicle with the skills required by the services?

I know it’s a bit complicated. But the company I’m automating doesn’t have vehicles and drivers associated. A driver can take any vehicle based on the optimization. The only thing is that the skills (permits) are associated with the vehicles, and the start times and maximum route duration are associated with the drivers.

4

So you have 2 different kinds of vehicles? Like 2 vans with a forklift (A) and 3 without (B)?

This is indeed tricky, but as the numbers are low you could try a “brute force” solution. Assume the order is associated with the specific driver then, if I did no mistake, there would be 10 problems to solve:
AABBB, (drivers 1 and 2 get a van of type A, the others get B),
ABABB, ABBAB, ABBBA, BAABB, …

To solve this without brute force we would need the possibility to say either vehicle A or vehicle B should be in the solution (then you would create two vehicles A and B for every driver, and only one would be picked in the solution). But currently this is not possible.

5

Actually, the volumes are not low. We are talking about 40 vehicles and about 30 deliveries for each vehicle.

Let me explain the scenario:

Each location requires special permits to access (such as ZTL zones). The permits required for access are passed as skills required for the various services (deliveries).
Each vehicle has different certificates to access different areas. So some vehicles have skills (permits) and others don’t.
To complicate matters, customers want deliveries in specific time windows and also the drivers who should be associated with the vehicles work different hours. This is why I cannot assign drivers to vehicles before optimization. Because, otherwise, I risk not respecting the triplet (REQUIRED PERMITS / DRIVERS’ WORKING HOURS / DELIVERY TIME WINDOWS).