On 13. July, Wednesday, from 16:00 to 17:30 we’ll hold the first GraphHopper meeting at Beuth University, Haus Bauwesen, room D 451.

We’ll have the following topics:

• Introductory talk about the GraphHopper routing and current development
• You are invited to show us your projects based on GraphHopper.
• Hands on workshop, where one of the topics will be indoor navigation

All talks should be 20 slides and 20s max for every slide, currently all in German language. See PechaKucha at Wikipedia for more details. To make planning a bit simpler please send a short email to info@graphhopper.com

Also please note our workshop (4th July) and talk (5th July) at FOSSGIS in Salzburg.

About

It was a great success having 5 talks of GraphHopper usages and all in all over 4 hours of discussion about the different topics like indoor routing, offline routing, map matching and traffic data integration.

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):

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

Figure 2: Minimize completion time

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

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.

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:

• 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

Today we are happy to announce the new release of our open source road routing engine GraphHopper 0.7. It includes many improvements as well as a new round trip calculation for the flexibility mode.

A big thanks for this release goes to all of our contributors and translators! To become a contributor see our contributing guidelines and e.g. the good first issues. Read here to see how to become a sponsor and how to benefit from our expertise or donate us.

Thanks a lot to all contributors and translators!

Here are the highlights for GraphHopper 0.7:

• moving from Java 5 to Java 7 for the core and Java 8 for the web modules.
• a new Croatian translation contributed from Ivan, this is language number 37!
• round trip calculation from boldtrn
  
• speed up mode (Contraction Hierarchies) can be disabled per request making several flexibility mode features available like alternative routes, round trips, weighting changes, heading settings or even turn restrictions which required a bit of refactoring
• adaptions for the GraphHopper iOS port from clns
• conditional restrictions can now be used for numbers like for weight not only for dates
• a new ‘hike’ profile which differs from ‘foot’
• bike improvements by ratrun
• SRTM data now fetched from kurviger.de to avoid timeout problems – thanks again boldtrn!
• We use underscore notation for all properties and file names now instead of the camelCase notation which was sometimes mixed with underscore
• Other contributions came from ammagamma, IsNull, devemux86 and fbonzon. See more bug fixes and pull requests and the changelog

The next release 0.8 will focus on more flexibility. Furthermore we would like to use the chance and point to the new work of our map matching component, which is now based on a more precise algorithm and often results in better matchings. It includes work from Michael (MATSim) and Stefan Holder (BMW Car IT). Please try it out here and give us feedback so we can include safely it in the next release or even replace the current algorithm.

As always our GraphHopper Directions API consumes these changes and makes it possible to use alternative routes, round trip calculations, heading indication, shortest path calculation and turn restrictions for the Routing API – read here for more details.

Have a nice route and discuss here.

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:

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!