projects of interest? - mebot

Mark Rossman marossma at oakland.edu
Wed Jul 18 20:35:38 CEST 2007


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 <jeff at bigredtj.com> wrote:
>
>
> On 7/18/07, Tim Newsom <cephdon at gmail.com> 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
> > community at lists.openmoko.org
> > 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
> community at lists.openmoko.org
> http://lists.openmoko.org/mailman/listinfo/community
>
>




More information about the community mailing list