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
