Route Optimization and Routing Explained

There are many terms when it comes to route optimization and route planning. In this blog post we describe the ones we use.

Routing

Routing is the process of finding the best path between two or more locations with a fixed order in a road or rail network. The criterion according to which a path is the best can vary. You may be looking for the shortest path (by distance), the fastest (by travel time), but also the most scenic or the safest path. Anything is possible as long as it can be specified by assigning some quantity, a generalized cost, to each road segment, and looking for the least-cost path.

Such paths can be calculated with our Routing API which is powered by our open source routing engine.

Other terms like journey planning, trip planning or route planning are frequently used, sometimes also itinerary planning.

There are a number of algorithms to solve this problem. The most famous ones are Dijkstra’s algorithm, and its accelerated version, the A* algorithm. The following image illustrates how the A* algorithm finds the fastest path between two locations. It explores all roads marked in blue to find the fastest path marked in red:

Route Optimization

When we use the term route optimization, we mean solving vehicle routing problems (VRP) and travelling salesman problems (TSP).

These problems can be solved with our Route Optimization API. It can be used to solve various vehicle routing problems like the capacitated VRP with time windows or the VRP with multiple depots. It allows the user to specify a number of business-specific constraints like time windows, multiple capacity dimension, driver skills etc., and it can even be used to solve large scale problems (>1000 locations and >100 vehicles).

The optimization is based on a heuristic approach that cannot guarantee optimal solutions, but, if configured well, it can provide very good solutions fast. The following steps are done under the hood of our Route Optimization API:

1. Calculate transport times and distances between all involved locations, e.g. pickup and delivery locations, as well as vehicle start locations. This is done with our Matrix API, see below for more information.
2. Based on this matrix, assign deliveries to vehicles and then sort the deliveries for each vehicle such that the specified objective function is minimized. We use a large neighborhood search that combines elements of simulated annealing and threshold-accepting algorithms. Essentially, it works as follows: starting with an initial solution, it disintegrates parts of the solution leading to
   (i) a set of deliveries that are not served by a vehicle anymore and to
   (ii) a partial solution containing all other deliveries.
   This step is called the ruin step.
   Based on the partial solution (ii) all deliveries from (i) are re-integrated again, which is therefore referred to as recreation, yielding a new solution. If the new solution has a certain quality, it is accepted as the new best solution, whereupon a new ruin-and-recreate iteration starts. These steps are repeated over and over again until a certain termination criterion is met, e.g. computation time or number of iterations.

The following image shows a typical solution for a capacitated vehicle routing problem with 249 deliveries and 2 depots:

Our Route Optimization API is powered by our open source optimization engine jsprit.

 

Navigation

Navigation is

is a field of study that focuses on the process of monitoring and controlling the movement of a craft or vehicle from one place to another

according to Wikipedia. And for us this means that once you found a path in the network, then navigation is the process of guiding you to the destination. It is tightly coupled to an actual device that knows your location and an algorithm that guesses your direction and the road you are on. With the help of our Routing API and Map Matching API, such a process can be implemented. If, for example, you would like to implement an Android app for the driver of a delivery vehicle, you could start with our Java API client.

Distance Matrix

The distance matrix is a two-dimensional matrix containing distances for all locations to all the other locations. Suppose you have 5 locations A, B, C, D and E, then the distance matrix consists of all 20 distances (5*5-5): A to B, A to C, A to D, A to E, B to A, B to C, and so forth:

Note that the matrix is not necessarily symmetric as you can have one-way roads, and the diagonal is 0 because a location to itself has always the distance of 0. You can calculate this matrix (or, similarly, the travel time matrix) by calling the Routing API multiple times, or much faster, in a single request, with our Matrix API.

Learn More

Learn more on our website about the GraphHopper Directions API.