Over the past year, we’ve been investigating time-dependent routing, in particular time-dependent access restrictions and time-dependent turn restrictions. We’ve been working with the University of Heidelberg, and the work has been supported by a grant from the Federal Ministry of Transport and Digital Infrastructure.

The recommended route from the northern part of the city of Hamburg to the southern part is usually through the Elbe tunnel, which is part of the federal freeway route (Autobahn) A7. However, for hazardous goods vehicles, this route is closed for parts of the day. If the desired departure time is known to the routing engine, this route should not be recommended. The next best alternative should be recommended.

Note that whether or not the tunnel can be part of a recommended route cannot simply be decided by looking at the intended departure time. What matters is the time the driver will, or would, arrive at the restricted road segment. Typical planned trips for heavy-goods vehicles can be long, so this does make a practical difference.

Next, we wanted to look into time-dependent turn restrictions. Those are far less common. The difference they make to optimal routes is much more local: A driver who encounters an unexpected turn restriction will typically know where to drive instead, and the detour will be short. Still, we can now give correct instructions right away.

Time-dependent routing requires a routing profile prepared for flexible mode, which means query times will be longer than what you are used to from speed mode. The code we wrote for this project will be merged into our open-source codebase. We are considering ways to offer this functionality on our hosted API. We’ll keep you posted.

Ending support for TLS 1.0/1.1

From March 4th, 2020, all requests to the GraphHopper Directions API must use HTTP over TLS (HTTPS), with support for TLS 1.2. We’ve decided to make this change in the best interest of our customers. This way we can ensure the security of data in transit and stay up to date with modern encryption, security protocols, and practices.

This means that TLS 1.0 and 1.1 will no longer be supported for requests to the GraphHopper Directions API. We announced this deprecation for September 2019 and it is finally being implemented.

Update: This update was shifted and done on 22th April.

Releasing the Cluster API

In February, we released our Cluster API. It can be used in many practical applications. For example, it can help to design territories for field workers or to solve large vehicle routing problems. Read our announcement for more information.

New synchronous POST endpoints

The new POST endpoint for the Routing API is useful to handle tens and hundreds of locations without URL restrictions and with the possibility to compress even the request and not just the response.

The new synchronous POST endpoint for the Route Optimization API allows customers to retrieve their solution more quickly and easier without the need of polling queries. Read more in our documentation.

Happy Routing!

We’re happy to announce our new product: the Cluster API! It solves the “capacity clustering problem” by assigning a set of customers to a given number of distinct groups (called clusters). The API “clusters” by minimizing the total distance from each individual customer to its designated group median. It can also consider minimum and maximum capacity restrictions for each group.

Clustering can be used in many practical applications. For example, it can help to design territories for field workers or to solve large vehicle routing problems (VRP). Our experiences with vehicle routing in particular motivated us to implement this API. It helps with some types of problems we cannot solve yet, like the VRP with a minimum number of stops. It even improves the visual attractiveness of the VRP solutions we provide with our Route Optimization API*!

For a visual representation of Cluster API, let’s take a look at this example. There are 490 customers in Munich. Each customer is assigned a demand of 1, represented by the blue dots on the map below.

Assume that we can deploy 17 vehicles, thus, we want to assign 490 customers to 17 clusters. The minimum number of customers in a cluster should be 15, however, the cluster size should not exceed 35 customers.

If you post that clustering problem to our API, you will be provided with the following solution:

There are two steps to solving the problem. First, the API calculates a travel time and distance matrix between all customers, resulting in a 490 x 490 matrix. Travel times and distances depend on the travel profile selected. You may specify any profile that GraphHopper Maps provides, like “car”, “foot”, “bike”, “small_truck” etc…Second, the API solves the clustering problem based on this generated matrix.

Do you want to solve your own clustering problem? You can learn how to do it with a slightly more technical article and our comprehensive documentation – find out more at graphhopper.com.

Happy clustering!

Note: You can find the entire example here and with a valid API key see and analyze the solution directly on the map.

*If you think visual attractiveness doesn’t matter, let me quote Rossit et al. (2019): “Enhancing visual attractiveness in a routing plan has proven to be an effective way to facilitate practical implementation and positive collaboration among planning and operational levels in transportation.” I recommend their comprehensive review, here Visual attractiveness in routing problems: A review.