Vehicle routing with cargo bikes and small trucks

This article shows how to solve a time-dependent vehicle routing problem with cargo bikes and small trucks with GraphHopper’s Optimizaton API.

Lets assume that you want to solve a vehicle routing problem with a mixed fleet. The fleet consists of cargo bikes and small trucks, and you want to employ the fleet such that products are delivered as fast as possible. The problem sounds simple, but solving it is a challenge. Why? Because this involves a decent least cost path calculator that provides an optimizer – that actually solves the vehicle routing problem – with transport times and distances. Furthermore, you need to take into account that cargo bikes and small trucks move on different road networks. To make the problem even more complicated, travel times of small trucks are affected by traffic and congestion that vary widely by time of day.

Let me illustrate how we encapsulated the entire complexity of this problem with our Route Optimization API. Modelling the problem is as easy as executing three steps: (1) define objective, (2) specify vehicles and vehicle types and (3) specify deliveries.

(1) Define objective

Choose the appropriate objective function from a set of available objectives described here. In our example, we need to use

 "objectives": [
    {
      "type": "min-max";,
      "value": "completion_time";
    }
  ] 

(2) Specify vehicles and vehicle types

You require two types “cargo bike” and “small truck”. Each type gets a “profile” indicating the particular network. Since we want to consider traffic for small truck, we need to specify the network data provider. The default is OpenStreetMap which does not have traffic data. We partner with TomTom to provide traffic data. Therefore, considering traffic is as easy as specifying “tomtom” as “network_data_provider” and “consider_traffic” as shown here:

 "vehicle_types": [
    {
      "type_id": "3.5t",
      "profile": "small_truck",
      "network_data_provider": "tomtom",
      "consider_traffic": true
    },
    {
      "type_id": "cargo-bike",
      "profile": "bike"
    }
  ] 

If “consider_traffic” is set to false, free flow data from TomTom are used, i.e. as though as there were no traffic. To complete (2), we only need to specify vehicles referring to the above types. To keep it simple and clear, we just define 2 vehicles (you can actually specify up to 200 vehicles), one cargo bike and one small truck starting at 01/30/2019 @ 8:21am (UTC) translated in unix timestamp.

 "vehicles": [
    {
      "vehicle_id": "3.5t",
      "type_id": "3.5t",
      "start_address": {
        "location_id": "berlin",
        "lon": 13.406,
        "lat": 52.537
      },
      "return_to_depot": true,
      "earliest_start": 1548836494
    },
    {
      "vehicle_id": "cargo-bike",
      "type_id": "cargo-bike",
      "start_address": {
        "location_id": "berlin",
        "lon": 13.406,
        "lat": 52.537
      },
      "return_to_depot": true,
      "earliest_start": 1548836494
    }
  ] 

(3) Specify deliveries

Specify deliveries as shown below. The minimum requirement is an “id” and an “address”. However, there are a number of attributes like time windows, size or required driver skills that can be added to model your business constraints.

 "services": [
    {
      "id": "prenzlau-1",
      "address": {
        "location_id": "13.425465_52.537014",
        "lon": 13.425465,
        "lat": 52.537014
      },
      "duration": 600
    }, ... 
  ]

Et Voilá! The following image shows the above problem and solution with 8 random deliveries in Berlin. The green route refers to the cargo bike.

• 

Happy Routing!