# Difference between revisions of "Algorithm"

Line 1: | Line 1: | ||

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

− | RouteXL optimizes routes with an search algorithm. That means that our routes may not always be optimal, but they're close enough. | + | == Method == |

+ | |||

+ | RouteXL optimizes routes with an search algorithm. That means that our routes may not always be optimal, but they're close enough. RouteXL uses a hybrid method: | ||

+ | |||

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

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

+ | * Quality check: 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:02, 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 search algorithm. That means that our routes may not always be optimal, but they're close enough. RouteXL uses a hybrid method:

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

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