First off I think the largest amount of time would be to calculate the distance between each possible combination of points, and I think most people wouldn't really have that many points anyway. Now if UPS decides to offload their routing onto the cell phones of their drivers it would take forever, but most people don't really go that many places.
Also if you set up the software to solve the TSP problem as an IP, then used the LP relaxation as your actual problem you would greatly reduce computation time, and get a list of possible next stops ordered based on their weight, most of the time it would give you a near optimal solution. On 7/18/07, Jeff Andros <[EMAIL PROTECTED]> wrote:
On 7/18/07, Tim Newsom <[EMAIL PROTECTED]> wrote: > > <snip> > You could expand this a little and possibly select items from multiple > location lists and then select > "Find the shortest route to complete all tasks" > > <snip> > --Tim > > _______________________________________________ > OpenMoko community mailing list > [email protected] > http://lists.openmoko.org/mailman/listinfo/community > just don't expect it to do so very fast... and make sure it runs as a REALLY low priority http://en.wikipedia.org/wiki/Traveling_salesman_problem http://en.wikipedia.org/wiki/NP-hard -- Jeff O|||||||O _______________________________________________ OpenMoko community mailing list [email protected] http://lists.openmoko.org/mailman/listinfo/community
_______________________________________________ OpenMoko community mailing list [email protected] http://lists.openmoko.org/mailman/listinfo/community
