HomeSoftware


Need PC Software & GPS for Seriously Long Trip
LouInAL
Hello. I am plannig a bit of an unusual business trip and I am in desperate need of advice. What is unusual is that I will be visiting 1,024 specific destinations in 16 northeastern states in a single trip. I need trip planning software with the following capabilities:

Input waypoint/destination data from an Excel spreadsheet or text file.

Calculate the most efficient route that will take me to all 1,024 locations in a single trip.

Link to a GPS to transfer the trip data, with waypoints in the correct order.

If Microsoft Streets & Trips with GPS Locator (2010) is up to the task described above that would be great, and I will still buy a GPS to use as a backup or for when more mobility is required. The database of locations that I have to visit has street address, city, county, state, and phone number but, oddly enough, not ZIP codes. I know that you can enter a phone number into Street Atlas USA 2009 Plus and it will find the location but I don't know if Streest & Trips has that capability.

The GPS should have the following features:

Text-to-speech with spoken street names.

Construction alerts and updates.

Traffic advisories.

Hot spot locator (is that available?).

I have very little time to plan this and much to do so I need to decide what to get and go buy it ASAP. Any advice would be greatly appreciated.

LouInAL
winwaed
Streets & Trips should, although 1024 locations is a lot, and the "Optimize" setting might take a very long time or not work at all: You may need to split it up (I've heard of people using 100 or so points on the same route successfully).

Note that to actually calculate the best order of 1024 points would take longer than the expected life of the universe! So internally, Streets & Trips is going to take some short cuts and may not produce the true optimum route - assuming it can handle this amount in one go, that is.


Richard
SpadesFlush
Quote:
Input waypoint/destination data from an Excel spreadsheet or text file.
S&T 2010 will do that.

Quote:
Calculate the most efficient route that will take me to all 1,024 locations in a single trip.
S&T 2010 will do that.

Quote:
Link to a GPS to transfer the trip data, with waypoints in the correct order.
S&T 2010 will do that.

Quote:
The database of locations that I have to visit has street address, city, county, state, and phone number but, oddly enough, not ZIP codes.
S&T 2010 will cope with that.

Quote:
I know that you can enter a phone number into Street Atlas USA 2009 Plus and it will find the location but I don't know if Streest & Trips has that capability.
S&T 2010 will NOT do that. But in my earlier experience, Street Atlas was not very specific about locations derived from telephone numbers.

Quote:
The GPS should have the following features:

Text-to-speech with spoken street names.
S&T 2010 has that.

Quote:
Construction alerts and updates.
S&T 2010 will do that so long as you have internet access.

Quote:
Traffic advisories.
S&T 2010 will NOT do that.

Quote:
Hot spot locator (is that available?).
I don't know what that is but S&T 2010 probably will NOT do that.

Quote:
I have very little time to plan this and much to do so I need to decide what to get and go buy it ASAP.
I hope this has been quick enough for you.
SpadesFlush
Quote:
Originally Posted by winwaed
...
Note that to actually calculate the best order of 1024 points would take longer than the expected life of the universe! ...
This might be something of an exageration but it does seem like a good idea, as Richard suggests, to sub-divide your data base into more manageable bites, for instance State-by-State.
SpadesFlush
If you go the Streets and Trips route (as I think would be best), you should also download a data base of points of interest. Once you have S&T installed, come back here and we can help you with that. If you meant speed cameras by your term "hotspots", then you can get data bases on the internet that have that information although you may have to pay for it.
LouInAL
Wow, thank you both for your replies. Very helpful! I am planning to buy a Garmin GPS (considering the Nuvi 1350T for $180 or Nuvi 1490T for $280) in addition to Streets & Trips as a backup and for if/when I need to leave the vehicle with it to do some foot work. What I was asking about hot spots is if there is POI data available that will help me find the closest WiFi hot spot in order to get my laptop online.

Thanks again!
SpadesFlush
Yes, there are some databases that provide that information which can be imported into S&T2010. See www.poifactory.com.
LouInAL
P.S. After looking at the distribution of locations I may pick a "narrow" point or two to divide the overall area into two or three sections and map them separately if it takes more than running my PC overnight to compute a route for the entire trip.
LouInAL
I just saw your last post, SpadesFlush, I didn't realize you had replied again so soon. That is a great site to bookmark! Thank you very much again.
SpadesFlush
It's a pleasure to be able to help.

I do not think the problem with a lot of waypoints/stops/POIs is calculating the optimum route; I think that can be done relatively quickly, not as long as overnight. However, you might find that having all of that data in one file makes on-the-fly adjustments and re-calculations a bit slow.

My suggestion would be to aim towards having a separate file for each day. This would break things down into manageably-sized files. But to get to that, you could do a one-shot route optimization for the overall picture with all data points and then refine that down to single day files from that.

It always makes sense to apply a bit of human intelligence to refine your route after the computer has had a run at the data. With Streets & Trips 2010, you can actually be running various maps in separate windows simultaneously so you can always flip back and forth between the general and the more specific.
winwaed
SpadesFlush: Actually it isn't an exaggeration. It could probably be said for 100 waypoints as well. The problem is NP complete (computationally 'difficult' in a mathematical sense) - to show a result is optimum would require the calculation of all possibilities. There are 1024! (factorial) possibilities - that is also significantly more than there are sub atomic particles in the Universe (current estimates are significantly less than 10^100).




Richard
SpadesFlush
Well, Rich, I respectfully beg to differ.

I just did a little experiment on 1,141 rest stops in the eastern half of the United States and it took less than two minutes to calculate an optimum route of all the stops. See attached.
Attached Files
File Type: est East Rest Stops.est (954.0 KB)
Marvin Hlavac
Wow, I'm personally very surprised. I would have bet $100 w/out any hesitation that Richard was correct. Perhaps it is because I haven't experimented with so may waypoints in several years. Microsoft might have improved the program, and computers have gotten faster since, too.

Thanks for taking the time to do the experiment for all of us, SpadesFlush. Your .est file, a trip of over 60,000 kilometers long(!), 80 days worth of driving(!), opened in about 2 minutes and 20 seconds.
winwaed
Exactly - Streets & Trips is making a lot of computational short-cuts (heuristics - ie. usually-intelligent guesses and assumptions). You have no guarantee that that is the best route, and it probably isn't the best route, but it is probably a pretty good one. The perfect solution would require all possibilities to check. The problem is known as the "Travelling Salesman Problem" - there's lots of literature on the subject!

BTW, if you can truly solve the Travelling Salesman Problem in polynomial time (rather than exponential time) without any approximations, then you have effectively shown a case where P=NP - there's a $1 million prize available for showing that (or showing that it is impossible)... Alas the maths is beyond me!

Theoretically proving P=NP for one situation means a huge swath of problems are viable in much less processing time. If you were so inclined, paying a good patent lawyer and you'd probably make a lot more than the $1 million prize from licensing.


Richard
Marvin Hlavac
Richard, undoubtedly you are correct. But it is impressive that the software can actually calculate a route with over 1,000 stops. Do you remember if this was at all possible in earlier years?
laptopgpsworld.com About