# Difference between revisions of "Algorithm"

(→Method) |
|||

Line 9: | Line 9: | ||

* Initial: several insertion methods to build a good initial route | * Initial: several insertion methods to build a good initial route | ||

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

For more information on algorithms: https://en.wikipedia.org/wiki/Travelling_salesman_problem | For more information on algorithms: https://en.wikipedia.org/wiki/Travelling_salesman_problem |

## Revision as of 16:04, 25 November 2015

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.

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

For more information on algorithms: https://en.wikipedia.org/wiki/Travelling_salesman_problem