Releasing the Map Matching API

Today we are proud to release our Map Matching API as part of our Directions API. It is a web service based on one of our open source components. You can use it to snap measured GPS points to a digital road network to e.g. clean data or attach certain data to it like turn instructions for biking trials. Read more about map matching at Wikipedia. Our Map Matching API is powered by the Apache licensed hmm-lib from BMW Car IT. ‘hmm’ stands for hidden markov model and indicates the underlying algorithm.

In the following screenshot and in these live examples you can see the Map Matching API in action. The black line represents the original GPS track e.g. received from a smartphone’s GPS. The green line represents the matched result, i.e. the part of the digital network, the black line is matched to:

mmatching

matching-sim

The Map Matching API works through tunnels, bridges, complex junctions etc. and can utilize different available vehicle profiles. Even more off-the-road examples will snap correctly – depending on the chosen GPS accuracy:

crazy-match

We are confident that it is another helpful routing tool that can be used in production for your web or mobile application. If you find any example where our Map Matching does not work as expected, please let us know in the forum.

Use this link to sign up and try the API for 2 weeks and let us know about your GPS tracks and questions!

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.
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?

parcel_delivery
Figure 1: Electro antique car (Source: Pixabay)

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 7pm and can be employed for 5 hours, i.e. they finally need to be back at 12pm 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 21pm (and not in the middle of the night).
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:

multiple_depot_trips

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 site, search for other tutorials or just asks questions in our forum.

Happy routing!

What is the difference between the minimization of completion time and minimizing transport time?

Every optimization requires an objective ie. a goal to which the results should be optimize for. Here, we want to illustrate the differences between two objectives: min transport time and min completion time. Using the GraphHopper Directions API the specification of these goals is as simple and intuitive as the following json snippets:

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

or

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

Transport time is the time your driver spends on the road to transport items from one location to another. The total transport time of a route is the sum of each leg’s transport time. A leg is what happens between one activity location and another.
The completion time of a route is the total time your driver takes from the start to the end of his route.
Therefore, transport time is included in the completion time of the route. To be more precise:
The completion time of a route = the sum of route leg’s transport time + sum of route’s waiting time + sum of route’s activity duration.

Therefore, the difference between min transport time and min completion time is that in contrary to min transport time, min completion time takes waiting time and activity duration into account. Waiting time and activity duration become part of the objective function. Since activity duration is usually constant (it cannot contribute to improve the objective), the main difference between transport and completion time is waiting time.

Waiting time only occurs in scenarios with time windows. No time windows, no waiting. Therefore, min transport time and min completion time should yield the same results if no time windows are specified.
If you specified time windows, waiting time only occurs if your driver arrives too early at an activity location, i.e. before the earliest_start of an activity.

Let us give you an illustrative example. Assume there is a bicycle messenger that starts at 8am to deliver parcels to 3 locations: West, East and North. West and East have time windows and only allow you to deliver parcels from 9am to 11am. North, however, can be delivered anytime. Min transport time results in the following solution (Figure 1):

min_tpt
Figure 1: minimize transport time

This is the expected solution when solely looking at transport times. However, one might ask why the driver waits for almost an hour at West. Instead of just waiting, he should deliver location North first. This is exactly what min completion time takes into account. Waiting times become part of the objective function and thus it results in the following solution (Figure 2).

min_ct
Figure 2: Minimize completion time

To make this even more visible, lets compare the solutions in a table.

table_minTp

As you can see min transport time ignores the potential waiting time savings of 45 min and solely focuses on transport time. Thus, transport time and distance are lower than when minimizing completion time. However, waiting times and thus completion time can be reduced significantly by minimizing completion time which comes with slightly higher overall transport times.

GraphHopper Directions API News June

The GraphHopper Directions API is continually improved and we’ll keep you up to date with the newsletter, today the first time publicly available as blog post.

We added more features to the Route Optimization API

  • Often there are more customers than the available vehicle fleet can serve. In this case, you can now assign priorities to customers that must be served to differentiate them from those that can be served later or omitted at all.
  • You can integrate load dependent transport costs, i.e. we consider that it is usually more expensive in terms of energy consumption to drive a full truck load, i.e. unnecessary kilometers with full truck loads can be avoided
  • Many auto generated clients for the different programming languages like C#, php, ruby and python are now available

The Geocoding API now allows you to specify an external provider like Nominatim or OpenCageData using the same API and no need for additional contracts. We’ll add more soon, if you need one which is not yet there, please ask for addition here.

The Matrix API has a more memory efficient Java client.

A more flexible routing is now available in the Routing API:

Alternative Paths

  • You can now create round trips with the Routing API using ch.disable=true and algorithm=round_trip, plus some more optional parameters
  • An often requested feature is the turn restriction support, which is now possible (example) and
  • additionally alternative routes can be used to provide users a nice choice
  • When navigating with motor vehicles it can be important to avoid to turn at destination or via points, this is now possible with the heading parameters
  • A snapped_waypoints field in the JSON allows you to calculate the distances from road to the provided destination or via points e.g. to consider more time when planning a delivery route
  • You can now calculate the shortest not only the fastest path too, via weighting=shortest (and ch.disable=true), but keep in mind that only very few use cases require the shortest path.

Last but not least a new ‘hike’ vehicle is available for all APIs, this profile is more suitable for tourism navigation e.g. prefers hiking tours. Instead the ‘foot’ profile prefers shorter routes which is more suiteable for inner city pedestrian navigation

How to schedule technicians with skills and multiple dependencies between tasks?

Introduction

In this tutorial we are going to show you how to model a vehicle routing problem where tasks do not only have multiple dependencies, but also require special skills. For example, let us assume we have two technicians called Peter and Stefan. Peter cannot only read the warm water meter, but he can also replace an old meter with a new one. Stefan can just read the meter. To get new warm water meters there is this water meter inventory. To open it one needs to pickup a key before (that needs to be returned). Furthermore, the replacement of a meter requires a special tool that needs to be picked up before as well. Both, Peter and Stefan, can only ride by bike since – much to the joy of everyone involved – their employer recently decided to replace all cars by bikes. Given a number of customers and these requirements, your task is to schedule Stefan and Peter such that the overall transportation costs are minimized. Peter’s and Stefan’s route could look for example like this:

technician-img

Instructional Content

In our documentation you find the general setup of the json request as well as how to post this request to our servers. What follows is a step-by-step approach to model the problem above, i.e. creating the necessary JSON request.

1. Specify your vehicle type

Both, Peter and Stefan, can only ride by bike. Let us assume that capacity does not play any role then your json snippet should look like this:

"vehicle_types":[ 
   { 
      "type_id": "bike_type", 
      "profile": "bike" 
   } 
] 

Thus you need a “type_id” that can be used to reference it in your vehicles. Additionally, you need to specify the profile “bike” (learn more about the profiles you can choose here). This way transport times and distances are calculated based on a bike network. The results correspond exactly to what you get when operating with our Routing API and GraphHopper Maps.

2. Specify your vehicles

Here, we require two bikes that basically represent Peter and Stefan. Both have skills, Peter can “read” and “replace” the meter. Stefan can just “read”. Furthermore, it is assumed that they can both work from 8am to 6pm (specified in seconds of that day).

"vehicles": [
    {
        "vehicle_id": "peter",
        "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
        },
        "type_id": "bike_type",
        "earliest_start": 28800,
        "latest_end": 64800,
        "skills": ["read","replace"]
    },
    {
        "vehicle_id": "stefan",
        "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
        },
        "type_id": "bike_type",
        "earliest_start": 28800,
        "latest_end": 64800,
        "skills": ["read"]
    }
]

3. Specify the tasks

Tasks can be specified as ordinary services. First, we need to specify tasks to pickup and delivery the inventory key much like this:

"services": [
   {
      "id": "pickup-key",
      "name": "pickup the key for this inventory",
      "address": {
         "location_id": "key-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 200
   },
   {
      "id": "deliver-key",
      "name": "deliver the key for this inventory",
      "address": {
         "location_id": "key-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 200
   }
...

]

Second, to replace the meter, one needs to pickup this special tool.

   {
      "id": "pickup-special-tool",
      "name": "pickup special tool to replace warm water meter",
      "address": {
         "location_id": "tool-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 200
   }
...

Third, there is this inventory with warm water meters that needs to be visited before serving customers with new meters. Here, it is assumed that the inventory has enough meters and that it always takes 1800sec to pick them up.

   {
      "id": "visit-inventory",
      "name": "pickup the required number of warm water meters",
      "address": {
         "location_id": "tool-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800
   }
...

Fourth, there are customers with meters to be read and with meters to be read and replaced.

   {
      "id": "serve-customer1",
      "name": "read warm water meter",
      "address": {
         "location_id": "customer1-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800,
      "required_skills": ["read"]
   },
   {
      "id": "serve-customer2",
      "name": "read and replace warm water meter",
      "address": {
         "location_id": "customer2-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800,
      "required_skills": ["read","replace"]
   }
...

Let us also assume that there is a customer that has a meter to be read and that wants to see Stefan. The specification of this customer would look like this:

   {
      "id": "serve-customer3",
      "name": "read warm water meter and wants to get this done by Stefan",
      "address": {
         "location_id": "customer1-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 1800,
      "required_skills": ["read"],
      "allowed_vehicles": ["stefan"]
   }
...

3. Specify the relations

There are few relations that need to be considered:

  • to open the warm water meter inventory one needs a key
  • to serve the customers with new meters, one needs to pickup new meters as well as this special tool first

This can be specified in the relation part of the JSON request:

"relations": [
   {
      "type": "in_direct_sequence",
      "ids": ["pickup-key","visit-inventory"]
   },   
   {
      "type": "in_sequence",
      "ids": ["visit-inventory","deliver-key"]
   },
   {
      "type": "in_sequence",
      "ids": ["pickup-special-tool","serve-customer2"] 
   },
   { 
      "type": "in_sequence",
      "ids": ["visit-inventory","serve-customer2"]
   }
   ...
]

This way you can define an arbitrary number of relations of type “in_same_route”, “in_sequence”
and “in_direct_sequence”.

Entire example

If you want to play around with relations etc. here you can find an entire example. Just copy the problem to our route editor, solve it and analyse the solution. You can either do it by looking at a map or at the raw json data.

Closing remark

Congratulations! You should now be able to add relations to your traveling salesman and vehicle routing problem. If you want to learn more about the conrete specification of relations, visit our documentation site or just asks questions in our forum.

Happy routing!