Difference between revisions of "Algorithm"
(→Travel times) |
|||
| Line 3: | Line 3: | ||
== Travel times == | == 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 | + | 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/ | Learn more: https://www.openstreetmap.org/ | ||
Revision as of 20:11, 2 December 2015
The RouteXL planning algorithm uses travel times and a optimization method to minimize total travel time.
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/
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 routes is even bigger, approximately 20 x 19 x 18 x ... x 3 x 2 x 1 = 2,432,902,008,176,640,000.
Mathematicians call it 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. Indeed, humans can fly to the moon, but can't solve this problem.
Learn more: https://en.wikipedia.org/wiki/Travelling_salesman_problem
Method
RouteXL optimizes routes with an iterative search algorithm. That means that itineraries may not always be optimal, but they're close enough. RouteXL uses a hybrid method to minimize total travel time.
