How to model multiple delivery routes with a single vehicle?

Introduction

In this tutorial we are going to show you how to model a vehicle routing problem with vehicles that can have multiple return trips to the depot or hub.
For example, let us assume you have 2 drivers that have a car much like the one on the figure below. It has an electric motor so it is basically a Tesla for people with a passion for antique cars. It can load 5 parcels. The drivers can be employed for 5 hours. A typical delivery route of 5 parcels takes far less than 5 hours so each driver still has time to return to the depot to pickup and deliver more parcels. How can this problem be solved with the GraphHopper Directions API?

Instructional Content

1. Specify vehicle type

First, let us specify the vehicles. We assume that the two vehicles are ordinary electro antique cars with a capacity to load 5 parcels. Specifying this is as simple as the following json snippet:

"vehicle_types":[
   {
      "type_id": "e_antique_car",
      "profile": "car",
      "capacity": [ 5 ]
   }
]

2. Specify vehicles

This type can be referred to in the vehicle specification. Additionally, we assume that the vehicles start at 19:00 and can be employed for 5 hours, i.e. they finally need to be back at 24:00 at latest.

"vehicles": [
    {
        "vehicle_id": "vehicle1",
        "start_address": {
            "location_id" : "depot",
            "lon" : 13.388572,
            "lat" : 52.516874
        },
        "type_id": "e_antique_car",
        "earliest_start": 68400,
        "latest_end": 86400
    },
    {
        "vehicle_id": "vehicle2",
        "start_address": {
            "location_id" : "depot",
            "lon" : 13.388572,
            "lat" : 52.516874
        },
        "type_id": "e_antique_car",
        "earliest_start": 68400,
        "latest_end": 86400
    }
]

3. Specify shipments

Our problem can only be solved reasonably with shipments. Therefore, you just need to model this with shipments from the depot to your customers. Let’s assume that there are 20 shipments. They can be modeled as follows:

"shipments" : [
        {
            "id": "peter",
            "name": "ship_parcel_from_depot_to_customer_peter",
            "pickup": {
                "address": {
                    "location_id" : "depot",
                    "lon" : 13.388572,
                    "lat" : 52.516874
                }
                "duration": 300
            },
            "delivery": {
                "address": {
                    "location_id": "peters_location",
                    "lon": 8.3858333,
                    "lat": 49.0047222
                }
                "duration": 600,
                "time_windows": [
                   {
                       "earliest": 68400,
                       "latest": 75600
                   }
                ]
            },
            "size": [1]

        }
       ...
]

The pickup address always corresponds to the depot location. In turn, the delivery address corresponds to the customer location. Here, we also assume that loading takes 5 minutes and delivering a parcel takes 10 min. Additionally, customer Peter is quite demanding when it comes to his delivery time window; he wants to have his parcel before 21:00 (and not in the middle of the night).

4. Putting it all together

Modelling the entire problem with random addresses in Berlin yield this json file. Post it to our servers and you get back the following solution:

As you can see, the delivery plan of your two drivers yield four nice round trips starting at the depot.

Closing remark

Congratulations! You should now be able to solve a vehicle routing problem with vehicles that can have multiple return trips. If you want to learn more, visit our documentation, search for other tutorials or just asks questions in our forum.

Happy routing!