How to Plan Your Best Route Using GraphHopper API?

02 / Mar / 2017 by Mahima Agrawal 0 comments

Software engineers and organizations lookout for effective ways to create new applications that save time and money. We can easily do this by using third-party software tools and SDKs.

This blog is to spread awareness about a useful routing API GraphHopper, a third party SDK. I am working on a project which is based on routing and delivery mechanisms playing two roles: Buyer and Carrier.

A buyer is a person who delivers their load from location A to B while whereas carrier is the one who carries out and processes the created delivery. In this blog, our motive is to find out the best ways for delivery in terms of time and distance which is readily available on Google API.

An overview and importance of GraphHopper 

GraphHopper works on the theory ‘Deliver more in less time’. It provides you with a Route Optimization API including real world constraints such as capacity restrictions, skill checks, time windows and more.

There is a scenario in my node.js application that Buyer can upload a file with multiple deliveries (up to 1000) for a week. They need to perform multiple deliveries between time t1 and time t2 in a given day and we need to find out the routes with multiple vehicles so that all deliveries can be completed in a certain period.

For an instance, find route optimization for existing week, for each day one at a time. For example, on Monday, given all deliveries that need to happen before a certain time of the day, x routes will not help us to achieve it. We’ll find x+1 routes and use that planning.

How To Start?

For using a GraphHopper API you need an API key. This is a paid service but for the development phase, you can create a key which is valid for 2 weeks.

API Parts: We can divide Graphhopper API into following categories:

  • Routing API
  • Route Optimization API
  • Geocoding API
  • Map Matching API
  • Isochron API
  • Matrix API

I will cover two APIs in this blog: Routing API and Route Optimization API. For more details, please visit their site.

Routing API:

Endpoint: 
cURL: curl “https://graphhopper.com/api/1/route?point=51.131%2C12.414&point=48.224%2C3.867&vehicle=car&locale=de&key=[YOUR_KEY]”

Specification of Used Parameters:

  • point: You can specify multiple points to get the route. Points should be in order. At least two points are required to get the route between them.
  • locale:  Returned instruction in specified locale
  • vehicle: Specify the vehicle for which the route should be calculated. Vehicles can be a car, bike, small truck, bus. See here for details.

Output Json:

Paths: An array of possible path

Path[0].distance: Total distance of route(in meter)

Path[0].time: total time taken by route(in milliseconds)

Path[0].instructions: Information about the instructions of route.

Example Output:

{
 "paths": [
 {
 "instructions": [
 {
 "distance": 1051.612,
 "sign": 0,
 "interval": [
 0,
 24
 ],
 "text": "Continue",
 "time": 179565
 },
 {
 "distance": 132.064,
 "sign": -2,
 "interval": [
 24,
 29
 ],
 "text": "Turn left onto K 7931",
 "time": 7923
 },
 {
 "distance": 841.423,
 "sign": -2,
 "interval": [
 29,
 36
 ],
 "text": "Turn left onto B 176",
 "time": 45895
 },
 {
 "distance": 758.765,
 "sign": 0,
 "interval": [
 36,
 48
 ],
 "text": "Continue onto Bornaer Straße, B 176",
 "time": 41385
 },
 {
 "distance": 783.714,
 "sign": 0,
 "interval": [
 48,
 63
 ],
 "text": "Continue onto B 176",
 "time": 42747
 },
 {
 "distance": 0,
 "sign": 4,
 "interval": [
 5521,
 5521
 ],
 "text": "Finish!",
 "time": 0
 }
 ],
 "descend": 9829.136100769043,
 "ascend": 9843.335098266602,
 "distance": 899950.595,
 "weight": 27239.575076,
 "time": 27239361
 }
 ]
}

Routing Optimization API: Route Optimization determines the most cost-efficient route thereby reducing the cost and enhancing the overall experience. It automatically assigns efficient service orders to the best driver and plans the best stop sequences.

We can easily solve Travelling salesman or Vehicle routing problems by using Route Optimization API.

Endpoint: 
The Route Optimization API works in two steps

  • Post your problem json:
  1. Method: Post
  2. Header: “Content-Type: application/json”
  3. Problem json in body: your-vrp-problem.json. You can use one of these examples
  4. API URL: “https://graphhopper.com/api/1/vrp/optimize?key=[YOUR_KEY]”
  5. cURL: curl -X POST -H “Content-Type: application/json” “https://graphhopper.com/api/1/vrp/optimize?key=[YOUR_KEY]” –data @your-vrp-problem.json

We will get a job id in this step which will be used in next step.

  • Poll every 500ms until a solution is available: 
  1. Method: Get
  2. API URL: https://graphhopper.com/api/1/vrp/solution/[RETURNED_JOB_ID]?key=[YOUR_KEY]
  3. cURL: curl -X GET “https://graphhopper.com/api/1/vrp/solution/[RETURNED_JOB_ID]?key=[YOUR_KEY]”

JSON Input

The general input structure is as follows:

{
  "configuration": {..},
  "objectives": [..],
  "cost_matrices": [..],
  "vehicles": [..],
  "vehicle_types": [..],
  "services": [..],
  "shipments": [..],
  "relations": [..]
}

Most used input parameters are objectives, vehicles, vehicle_typesservices and shipments.

Objectives:
It requires two things namely, the type and the value to be optimized.

  • Type: min, min-max
  • Value: vehicles, transport_time, completion_time

Vehicles: It can only be used with min and minimizes vehicles.
Transport_time: It considers the time that drivers spend on the road.

"objectives" : [
   {
      "type": "min",
      "value": "transport_time"
   }
]   

Completion_time: It is the time from starting to end of the route i.e. the route’s transport time, the summation of total waiting time and total activity duration.

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

If you want to minimize vehicles first followed by completion_time, you can also combine different objectives as shown below:

"objectives" : [
   {
      "type": "min",
      "value": "vehicles"
   },
   {
      "type": "min",
      "value": "completion_time"
   }
]  

 

Vehicles:
If you want your vehicle to come back, specify it like this:

{
    "vehicle_id": "your-vehicle-id",
    "start_address": {
        "location_id": "your-location-id",
        "lon": 11.028771,
        "lat": 50.977723
    },
    "type_id": "your-vehicle-type-id"
}

If you want your vehicle to end at a specified end-location which is not equal to the start-location, specify it as shown below:

{
    "vehicle_id": "your-vehicle-id",
    "start_address": {
        "location_id": "your-start-location-id",
        "lon": 11.028771,
        "lat": 50.977723
    },
    "end_address": {
         "location_id": "your-end-location-id",
         "lon": 12.028771,
         "lat": 54.977723
    },
    "type_id": "your-vehicle-type-id"
}

If you want to let GraphHopper decide at which customer location the vehicle should end, specify it as shown below (then the vehicle will end at one of your customer locations):

{
    "vehicle_id": "your-vehicle-id",
    "start_address": {
        "location_id": "your-start-location-id",
        "lon": 11.028771,
        "lat": 50.977723
    },
    "return_to_depot": false,
    "type_id": "your-vehicle-type-id"
}

Here lat and lon refer to latitude and longitude of a given location.

Vehicle Types:
The default vehicle type is mentioned below.

{
    "type_id": "default_type",
    "profile": "car",
    "capacity": [ 0 ],//optional
    "speed_factor": 1.0,//optional
    "service_time_factor": 1.0//optional
}

Services or Shipments

The basic difference between a Service and a Shipment is that while the Service involves only one location Shipment involves two locations, i.e. a pickup and a delivery location. A service can be specified as:

{
     "id": "service-id",
     "type": "pickup",
     "name": "meaningful-name", 
     "address": {
       "location_id": "service-location-id",
       "name": "Goethe Street 1",
       "lon": 9.999,
       "lat": 53.552
     }, 
     "time_windows": [ 
        {
            "earliest": 0,
            "latest": 3600
        },
        {
            "earliest": 7200,
            "latest": 10800
        }
     ],
     "allowed_vehicles": ["vehicle_1", "vehicle_2"]
}

Similarly, a shipment can be specified as:

{
    "id": "shipment-id",
    "name": "meaningful-name", 
    "pickup": {
        "address": {
            "location_id": "your-pickup-location-id",
            "name": "Johann Sebastian Bach Avenue 5",
            "lon": 12.1333333,
            "lat": 54.0833333
        },
        "time_windows": [ 
            {
                "earliest": 0.0,
                "latest": 1000.0
            } 
        ]
    },
    "delivery": {
        "address": {
            "location_id": "your-delivery-location-id",
            "name": "Thomas Mann Street 1",
            "lon": 8.3858333,
            "lat": 49.0047222
        },
        "time_windows": [ 
            {
                "earliest": 10000.0,
                "latest": 20000.0
            }
        ]
    },
    "allowed_vehicles": ["vehicle_1", "vehicle_2"] }

A Full specification of some important fields of service object:

type: It is a string and a default service. type can be specified as service, pickup or delivery. When the type is service or pickup, items are loaded and stay in the vehicle for the rest of route. If it is, delivery items are implicitly loaded at the beginning of the route and will stay on the route until delivery

time_windows: It is an array. If a delivery needs to be carried out between a specific period of time, for example, between 7 am and 9 am then specify the array as follows: [ { “earliest”: 25200, “latest”: 32400 } ]. If the delivery facility has a lunch break and is open from 9am to 12am and 2pm to 6pm, just define the time windows as follows: [ { “earliest”: 32400, “latest” : 43200 }, { “earliest”: 50400, “latest” : 64800 } ]. If you need a time for the next day, add 24 hours, e.g. 7 am on the second day is 60*60*(7+24)=111600.

allowed_vehicles: It is an array of vehicle Id’s (it is vehicle_id created in vehicles array mentioned above). if a service can only be processed EITHER by vehicle_1 OR vehicle_2 specify this as follows: [“vehicle_1”, “vehicle_2”].

JSON Output

If you post a problem, you either get back a job_id or an error. The job id looks as shown below:

{ “job_id“: “7ac65787-fb99-4e02-a832-2c3010c70097” }

With the job_id you can fetch your solution via https://graphhopper.com/api/1/vrp/solution/[job_id]?key=[YOUR_KEY]

Response

Your job can be in three states. (a.) if your problem is still waiting (b.) if your job is being processed but not yet finished. In both cases you will get this:

{
  "job_id" : "7ac65787-fb99-4e02-a832-2c3010c70097",
  "status" : "waiting",
  "waiting_time_in_queue" : 1061,
  "processing_time" : 0,
  "solution" : "pending"
}

Lastly (c.) if your job is complete and a solution is available. You will consequently get this:

{
  "job_id" : "64963b20-d358-4f26-bf79-82decae50a2d",
  "status" : "finished",
  "waiting_time_in_queue" : 0,
  "processing_time" : 267,
  "solution" : {
     "costs": 58835,
     "distance": 1898748,
     "time": 58835,
     "transport_time": 58835,
     "completion_time": 58835,
     "max_operation_time": 58835,
     "waiting_time": 0,
     "no_vehicles": 1,
     "no_unassigned": 0,
     "routes": [
       {
         "vehicle_id": "my_vehicle",
         "distance": 1898748,
         "transport_time": 58835,
         "completion_time": 58835,
         "waiting_time": 0,
         "activities": [
           {
             "type": "start",
             "location_id": "berlin",
             "address": {
               "location_id": "berlin",
               "lat": 52.537,
               "lon": 13.406
             },
             "end_time": 0,
             "distance": 0,
             "driving_time": 0,
             "load_after": [
               0
             ]
           },
           {
             "type": "service",
             "id": "munich",
             "location_id": "munich",
             "address": {
               "location_id": "munich",
               "name": "Meindlstraße 11c",
               "lat": 48.145,
               "lon": 11.57
             },
             "arr_time": 17985,
             "end_time": 17985,
             "waiting_time": 0,
             "distance": 587746,
             "driving_time": 17985,
             "load_before": [
               0
             ],
             "load_after": [
               0
             ]
           },
           {
             "type": "service",
             "id": "frankfurt",
             "location_id": "frankfurt",
             "address": {
               "location_id": "frankfurt",
               "name": "Thomas Mann Straße 24",
               "lat": 50.109,
               "lon": 8.67
             },
             "arr_time": 30991,
             "end_time": 30991,
             "waiting_time": 0,
             "distance": 1001605,
             "driving_time": 30991,
             "load_before": [
               0
             ],
             "load_after": [
               0
             ]
           },
           {
             "type": "service",
             "id": "cologne",
             "location_id": "cologne",
             "address": {
               "location_id": "cologne",
               "name": "Friedrichstraße 10",
               "lat": 50.936,
               "lon": 6.957
             },
             "arr_time": 37004,
             "end_time": 37004,
             "waiting_time": 0,
             "distance": 1189526,
             "driving_time": 37004,
             "load_before": [
               0
             ],
             "load_after": [
               0
             ]
           },
           {
             "type": "service",
             "id": "hamburg",
             "location_id": "hamburg",
             "address": {
               "location_id": "hamburg",
               "name": "Goethestraße 1",
               "lat": 53.552,
               "lon": 9.999
             },
             "arr_time": 49575,
             "end_time": 49575,
             "waiting_time": 0,
             "distance": 1612006,
             "driving_time": 49575,
             "load_before": [
               0
             ],
             "load_after": [
               0
             ]
           },
           {
             "type": "end",
             "location_id": "berlin",
             "address": {
               "location_id": "berlin",
               "lat": 52.537,
               "lon": 13.406
             },
             "arr_time": 58835,
             "distance": 1898748,
             "driving_time": 58835,
             "load_before": [
               0
             ]
           }
         ]
       }
     ],
     "unassigned": {
       "services": [],
       "shipments": [],
       "breaks": []
     }
   }
  }

To explore more, please visit here

In this way, you can easily get router data within a specified time-frame and efficient vehicles. Hope this blog was helpful to you. Keep watching this space for more blogs on technology and API updates.

FOUND THIS USEFUL? SHARE IT

Leave a Reply

Your email address will not be published. Required fields are marked *