Changes

Jump to: navigation, search

Algorithm

No change in size, 7 March
m
Optimization
Routing multiple addresses is quite a puzzle. First, you'll need a distance matrix for all destinations. Or better: travel times matrix, as the algorithm minimizes total travel time.
With 20 destinations the travel times matrix has roughly 20 x 20 = 400 elements. Each element represents one route between two points. To sort 20 destinations the algorithm first needs to calculate 400 individual routes. No wonder route optimization is much more time consuming than simple A-to-B routing!.
Secondly, the number of possible routes to visit 20 destinations is even larger than that. The first pick can be any of the 20 destinations, so there are 20 possible choices for the first stop. For the second there are 19 choices left. That means there are 20 x 19 = 380 combinations for the first two stops. There are 18 choices for the third stop after that, making 20 x 19 x 18 combinations. And so on.
For the full route with 20 stops there are approximately 20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 2,432,902,008,176,640,000 combinations!
Mathematicians call route optimization a "hard" problem and there is no final one-size-fits-all solution available. They even have a name for it: the ''The Travelling Salesman Problem'' (TSP). Indeed, humans can fly to the moon, but in math there is no ultimate solution to this routing problem.
Learn more: https://en.wikipedia.org/wiki/Travelling_salesman_problem

Navigation menu