# Difference between revisions of "Algorithm"

Line 5: | Line 5: | ||

== Method == | == Method == | ||

− | RouteXL optimizes routes with an search algorithm. That means that | + | 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 | * Initial: several insertion methods to build a good initial route |

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