Algorithm

When you hit the Find route button the route planning algorithm is launched. The algorithm minimizes total travel time to find the fastest route (less hours/minutes). It does not minimize total distance as such, so our routes may not be the shortest route (less miles/kilometers). The algorithm uses travel times and a optimization method to sort your locations in the optimal order.

Contents

Travel times

To find the best route, the travel times between all locations are required. While most other route optimization tools use geographic distances (as the crow flies), RouteXL uses a crowdsourced road network. OpenStreetMap is the free Wiki World Map, an openly licensed map of the world being created by volunteers using local knowledge, GPS tracks and donated sources.

Learn more: https://www.openstreetmap.org/

We update the data on our servers every 1-2 months, which means that updates to the streets made in OpenStreetMap takes some time to become visible in the routes of RouteXL.

Traffic

The travel times do not incorporate actual or forecasted traffic. There are some ways to adjust the routes for traffic:

• You can set time windows for your stops, which can be used to visited certain places during specific hours. E.g. you could set a ready time at 10AM to visit some address after morning rush hours.

• You can change the speed parameter, which makes travel times shorter or longer. E.g. maximum speeds during rush hours may be to optimistic, setting the speed to 60% may be more realistic.

• You can drag & drop stops in order manually after the route optimization.

• When driving, you can launch third-party navigation apps which have actual traffic, e.g. Google Maps or Waze.

Optimization

Routing multiple addresses is quite a puzzle. First, you'll need a distance matrix for all destinations. Or better: travel times matrix, as the algorithm minimizes total travel time.

With 20 destinations the travel times matrix has roughly 20 x 20 = 400 elements. Each element represents one route between two points. To sort 20 destinations the algorithm first needs to calculate 400 individual routes. No wonder route optimization is much more time consuming than simple A-to-B routing.

Secondly, the number of possible routes to visit 20 destinations is even larger than that. The first pick can be any of the 20 destinations, so there are 20 possible choices for the first stop. For the second there are 19 choices left. That means there are 20 x 19 = 380 combinations for the first two stops. There are 18 choices for the third stop after that, making 20 x 19 x 18 combinations. And so on.

For the full route with 20 stops there are approximately 20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 2,432,902,008,176,640,000 combinations!

Mathematicians call route optimization a "hard" problem and there is no final one-size-fits-all solution available. They even have a name for it: the Travelling Salesman Problem (TSP). Indeed, humans can fly to the moon, but in math there is no ultimate solution to this routing problem.

Learn more: https://en.wikipedia.org/wiki/Travelling_salesman_problem

However, Operations Research researchers have found some very good approximation methods. Our algorithm is an effective implementation that finds the optimal route in most cases. But it is an algorithm for matter of speed that does not guarantee optimality.

Runtime

The runtime of the algorithm varies and depends on the complexity of the route. The aim is to have 95% of all routes with 40 locations (normal car, single round, no restrictons) optimized within 10 seconds. If you use another vehicle type, multiple rounds or restrictions, the runtime will increase.

The maximum runtime for the algorithm is 15 minutes. If you have a large route, with many stops and a complex distribution (e.g. scattered in a large/urban area), the calculations may take the full 15 minutes. During this you can not optimize another route due to the Fair Use Policy.

When the algorithm is running on the website or webapp, a progress indicator is shown. The expected runtime may however not be enough for the algorithm. If the algorithm needs more time, the progress indicator will pause at approximately 80% until the algorithm finishes and the route is shown on the map.

Hint: if you need to speed up the algorithm drastically and you are willing to accept lesser quality, set the vehicle type to "drone". It will draw straight lines (as the crow flies) between locations and find a route much faster due to the lower complexity.