A Shiny New Engine for OptiMap
OptiMap, the free TSP solver for Google Maps, used to guarantee the optimal solution for up to 9 locations only. That number has now been increased to 15. If you had more than that number of locations, you would get a solution close to the optimal (often the optimal).
The new OptiMap uses the dynamic programming solution to the TSP for problems of size 10 - 15. I tested various values for the cutoff in different browsers, and I could have set it differently. The main problem with the dynamic programming solution is its memory footprint. It uses O(n * 2^n) memory, which gets problematic around n = 15 in JavaScript (n being the number of locations, of course). This is especially true on smaller devices like smartphones. It would probably work well with n = 18 on most desktop computers and browsers, but I haven’t gotten around to making a dedicated smartphone version yet.
There is also a noticable difference between different browsers in JavaScript execution speed. Safari 4 is the fastest browser I tried so far. I haven’t tested Google Chrome yet, but I suspect it is also in the super-fast category. Once Opera comes with its Carakan JavaScript engine, I will run a speed test on OptiMap and publish the results here. Maybe I should set n automatically based on the user’s browser?