Changes

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 open source route planners based on the [https://www.openstreetmap.org/ OpenStreetMap] a crowdsourced road network to determine travel. 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.

Routing multiple addresses is quite a puzzle. With 20 destinations the from-to travel times matrix has roughly 20 x 20 = 400 elements. The number of possible 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 even bigger, approximately 20 x 19 x 18 x ... x 3 x 2 x 1 = 2432902008176640000much more time consuming than simple A-to-B routing!

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 there are approximately 20 x 19 x 18 x ... x 3 x 2 x 1 = 2,432,902,008,176,640,000 combination. Mathematicians call it 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 can't solve in math there is no ultimate answer to this problem.

Operations Research researchers however have found some very good 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. === Method Runtime ===

RouteXL optimizes routes with an iterative search The maximum runtime for the optimization algorithmis 15 minutes. That means that itineraries may not always be optimalIf you have a large route, but they're close enoughwith many stops and a complex distribution (e.g. RouteXL uses scattered in a hybrid method large/urban area), the calculations may take the full 15 minutes. During this you can not optimize another route due to minimize total travel time:the [[Fair Use Policy]].

* Initial: several insertion methods to build When the algorithm is running on the website or webapp, a good initial route* Improvement: several of improvement methods inspired by [https://enprogress indicator is shown.wikipediaThe expected runtime may however not be enough for the algorithm.org/wiki/Lin%E2%If the algorithm needs more time, the progress indicator will pause at approximately 80%93Kernighan_heuristic Lin Kernighan] optimization* Checking: if until the quality check fails, algorithm finishes and the improvement phase route is repeatedshown on the map.