# Difference between revisions of "Algorithm"

(→Method) |
|||

Line 1: | Line 1: | ||

+ | The route planning algorithm uses travel times and a optimization method. | ||

+ | |||

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

+ | |||

+ | == Optimization == | ||

+ | |||

Routing multiple addresses is quite a puzzle. With 20 destinations the from-to travel distance 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 = 2432902008176640000 | Routing multiple addresses is quite a puzzle. With 20 destinations the from-to travel distance 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 = 2432902008176640000 | ||

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. | 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. | ||

− | == Method == | + | More information: 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: | 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: | ||

Line 10: | Line 20: | ||

* Improvement: several of improvement methods inspired by k-opt optimization | * Improvement: several of improvement methods inspired by k-opt optimization | ||

* Checking: if the quality check fails, the improvement phase is repeated | * Checking: if the quality check fails, the improvement phase is repeated | ||

− | |||

− |

## Revision as of 07:14, 26 November 2015

The route planning algorithm uses travel times and a optimization method.

## 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 open source route planners based on the [OpenStreetMap] road network to determine travel.

## Optimization

Routing multiple addresses is quite a puzzle. With 20 destinations the from-to travel distance 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 = 2432902008176640000

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.

More information: 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:

- Initial: several insertion methods to build a good initial route
- Improvement: several of improvement methods inspired by k-opt optimization
- Checking: if the quality check fails, the improvement phase is repeated