678
edits
Changes
m
→Runtime
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 ===
== Optimization ==
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 = 2,432,902,008,176,640,000.much 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 in math there is no ultimate answer to this problem.
Learn more: https://en.wikipedia.org/wiki/Travelling_salesman_problem
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.
''
