Difference between revisions of "Algorithm"
(Add traffic info) |
(Adding runtime) |
||
| Line 28: | Line 28: | ||
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. | 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. | ||
| + | |||
| + | === Runtime === | ||
| + | |||
| + | The maximum runtime for the optimization 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]]. | ||
Revision as of 14:14, 7 November 2019
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/
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.
- You can change the speed parameter, which makes travel times shorter or longer.
- 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. 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 (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
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.
Runtime
The maximum runtime for the optimization 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.
