GraphHopper and jsprit join forces

We are happy to announce that Stefan from jsprit will join forces with GraphHopper and together we’ll not only create a flexible and fast routing engine with optimization features in our Directions API but also push forward the business with GraphHopper in general – stay tuned 🙂 !

Open Source Projects

What does this mean for the open source projects? jsprit and the GraphHopper core will stay separate, well supported open source projects, and nothing will change towards the community or our commitment.

GraphHopper Directions API

Since several months we have worked together to create a new and easy way to solve route optimization and traveling salesman problems which led to several improvements on both open source projects already.

Additionally, we jointly developed our new Route Optimization API and a simple way to solve traveling salesman problems via our Routing API. The latest work is a simple route editor which makes creating and debugging requests against the route optimization API a lot easier and intuitive, and thus it makes a whole lot of fun to play with our Optimization API. Read more about it here.

route-editor-overview

Graphhopper Directions API News October

A long silence for a young company can mean many different things. In our case it only means that we further concentrate on making our products better! We are very happy to improve the GraphHopper Directions API every week and keep you up to date with this newsletter.

We improved the Route Optimization API in various ways:

We released version 0.8 of our open source routing engine coming now with 39 translations, which are directly available in the Routing API.

A new Map Matching API was released which does an automated ‘snap to road’ useful to improve recorded GPS traces:

Map Matching API Demo
A lot more is happening in the GraphHopper space: we had our first, very own GraphHopper meeting, spoke at IAA, FOSSGIS, … and reached a new star record for our open source projects (sum is over 1400!).
You can now follow us not only on Twitter but also on LinkedIn and Facebook. Or visit us at WhereCamp Berlin or at Startup-DemoNight in Munich in real life.
Over the last months we were very happy to welcome dozens of new customers, bigger and smaller – hello again 🙂 !

If you have questions or problems, do not hesitate to contact us!

Happy Routing!
Your GraphHopper Team

GraphHopper Routing Engine 0.8 Released

We are proud to release version 0.8 of our open source GraphHopper routing engine! Here is the polished snap-to-road feature in two screenshots:

matching-sim

A big thanks 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.

Here are the highlights for GraphHopper 0.8:

  • the new map matching algorithm based on hidden markov chains is finally integrated and gives us a big quality improvement, thanks to @michaz (GraphHopper) and @stefanholder (BMW Car IT). This feature was already deployed 2 months ago in our GraphHopper Directions API. Some improvements were done by @kodonnell.
  • the osm import module is split from the core #450 making Android and iOS integration cleaner
  • there is a new overlay module #781 allowing you to specify GeoJSON at import time to change properties like access and speed of the routing graph
  • new ‘more standard’ code formatting for all repositories #770
  • many UI fixes like upgrading to leaflet 1.0, thanks to @fbonzon (Bikewithme)
  • updated the iOS port, thanks to Calin @clns
  • travis build enhancements like running against jdk9 and deploying snapshots #806, thanks to @mprins
  • a new ‘on-demand’ weighting with a new data encoder #730
  • elevation interpolation in tunnels&bridges #713, thanks to @highsource (DB Systel)
  • fixing time calculation for turn costs #393
  • a new short_fastest weighting #747
  • Several updates to Android build/sample from @devemux86 (talent)
  • several bug fixes (incl. three major)

The changelog is here – please read about the necessary changes to your config.properties and/or your Java code. Dowload the new version here. As the documentation has slightly improved we’d like your input here as well.

In the next release we expect bigger changes to come like one top secret 😉 and this exciting work from @devemux86 which continues the work from VTM (OpenScienceMap) and has OpenGL support, allows map rotation, iOS support and more, while keeping compatibility with the Mapsforge file format.

And if you like OpenStreetMap as we do, consider supporting them via money.

Happy routing!

The daily bug hunt

Yesterday we got a support request that a certain route request fails and just says ‘route not found’. We wanted to quickly reply that the open source routing engine has an option where you can reduce to a sufficient minimum, but as it turned out he meant the hosted GraphHopper Routing API where we already use a properly configured engine. So something was wrong with it. And in the geographical area we detected nothing strange with the OpenStreetMap data, (although for Google Maps we found one ;)) and so it had to be something in the routing engine.

Grabbing the area via the export button at openstreetmap.org was easily done, but we could not reproduce this on my local machine. And so we would need to somehow use the remote data, which is a bit too big to fit on my local computer (~50GB).

How do you remotely debug a Java application in a safe way?

fruit-bug

Let me explain this for NetBeans but it should work similar for any other Java IDE. Add the following options to your remote Java application:

java -agentlib:jdwp=transport=dt_socket,server=y,suspend=n,address=8888 ...

You can find out more about these settings via

java -agentlib:jdwp=help

As a side note: there is also an old settings “-Xdebug -Xrunjdwp:transport=dt_socket,server=y,address=8888,suspend=n” but for that we got an error: “OutOfMemoryError: Java heap space” which did not go away even when trippling the -Xmx setting (maximum RAM for the JVM). After switching to a different off-heap graph storage method (MMAP_STORE_SYNC) we got it working with the old method.

Now, how can you open the port 8888 without making it public to anyone? Instead just 8888 use localhost:8888, then the socket is not publicly accessible and so you can safely access it through a SSH tunnel:

ssh -L 8888:localhost:8888 user@server

Then click ‘Debug’ in the Netbeans menu, then ‘Attach Debugger’ and press ‘okay’. Keep localhost and 8888 or if you do not have a SSH tunnel use the remote server IP. It should then open a new output window telling you that you are connected. In our case we still had a problem:

Not able to submit breakpoint LineBreakpoint GraphHopper.java. Reason: Breakpoint's source file does not belong into the preferred source root '.../.m2/repository/com/graphhopper/graphhopper/0.7.0/graphhopper-0.7.0-sources.jar'

This is easy to fix. Go to Window->Debugging->Sources and deselect the entry for graphhopper 0.7.0 as the open project with 0.8-SNAPSHOT itself is sufficient in my case.

Finally er were able to remotely debug into the JVM

Nice! But we were still not able to figure out what went wrong ;(

The reason was that this bug was not related to runtime (i.e. finding the route) but it was related to how we post-process the OpenStreetMap network to make it less error-prone. Read more about the details here and if you liked this maybe you would like to contribute 🙂 ? Have a look into our quickstart and sign-up to our forum.

contribute

We hope you enjoyed reading this bug hunt and you can apply the findings to your own debug sessions!

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!