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

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

S&T 2010 will do that.

S&T 2010 will do that.

S&T 2010 will do that.

S&T 2010 will cope with that.

S&T 2010 will NOT do that. But in my earlier experience, Street Atlas was not very specific about locations derived from telephone numbers.

S&T 2010 has that.

S&T 2010 will do that so long as you have internet access.

S&T 2010 will NOT do that.

I don't know what that is but S&T 2010 probably will NOT do that.

I hope this has been quick enough for you.

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.

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.

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!

Yes, there are some databases that provide that information which can be imported into S&T2010. See www.poifactory.com.

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.

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.

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.

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

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

East Rest Stops.est (954.0 KB)

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.

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

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?

I don't know - I would expect it has been speeded up over time.

I do remember a few years back, MapPoint had trouble with small numbers (say half a dozen) when one of them was a long distance from the others - eg. points split between Canada and Florida. I bet it was recalculating the route segments needlessly (you would have expected those results to have been cached).

2mins is very good going, and gives you an idea of why few apps don't do this type of optimization as it is hard to do. I dabbled with something similar a few years back. Route segments were precalculated (actually pre-seeded) and I didn't have any other constraints (ie. as per S&T) and I chose a genetic algorithm. The practical limit (=a few mins calc) was about 14 or 15 stops iirc on a slow PC. A modern PC and multi-threading might have pushed that to 16-17. My algorithm clearly wasn't up to what was required. I also very much doubt S&T uses a genetic algorithm.


Richard

I am impressed, Richard, by your mathematical knowledge. While I tend to TRUST IN MICROSOFT perhaps a little too much, I do subscribe to the notion that what the computer spits out as a route is just a starting point that probably needs some human wisdom before actually embarking on the journey as I suggested towards the top of the thread.

But LouInAL isn't going to complete his sweep of all his destinations in a day and I am sure that S&T will be able to optimize a route on his computer (even if it is not mathematically perfect) to the point that it will get him pointed in the right direction.

Yes it is "good enough" and I think the coders have done a good job coding it, especially with that 2min figure you quote (I know they get a lot of criticism - much of it unnecessary, especially considering their limited resources).

I guess the past few months my head has been in the optimization world whilst I've been working on MPCluster (cluster analysis for MapPoint). The underlying maths/algorithms have something in common, and I'm wondering if a route optimizer could be built along similar lines...


Richard

At the end of the day, I do not think Lou, or anyone, should be dissuaded from attempting a route optimization from a large population of stops because S&T/AR have the capability of undertaking the task in a manageably short period of time. On the other hand and as you point out, they need not take as gospel that the computational work product is that best that computer/mathematical science or human intelligence can devise.

Wow, this is more intriguing that I would have ever imagined. I guess what Richard is saying is that the only to find THE one best route is to compute all possible routes between the 1,024 points (a perfectly coincidental number, by the way), sropping the less efficient of two each time a new one is computed. I can see where that would probably be impossible in this day and time. There are some obvious shortcuts that the programmers clearly have to take, as when there are a cluster of points in a "group" to compute the route for that area separately.

Now I can't wait to get the software, load the data, and play with it!

Thank you all so much. I'll let you know how I make out.

Lou

We used to get this question a lot "how may waypoints can be included in my route?" For the vast majority 1000 is plenty enough but there is no hard limit.



I created a route with over 65,000 waypoints as a test. Yes it did take overnight to calculate and afterwards the resulting map was a beast to manuver. I would second the recommendation to break up your large trips into smaller legs. If you create a gps trail for each one as you go it is easy to combine the trails into 1 file to show the summary of your overall travels.

related post: What is the Max Number of Waypoints for a Route? - Windows Live

Now, that's stress-testing!

Optimization Far From Optimal in Streets & Trips.

OK, I imported my trip information and a little more than 700 stops matched map information, leaving about 290 that I had to correct or add additional information to. It took approximately 36 hours to optimize, but when I looked at the result the criss-crossing route just did not look right.

I decided to break the trip into "regions" and optimize smaller areas by visually selecting start and end points (the end point of one is the start point for the next). The second region I created is still rather large at about 600 stops, but it takes only 20-30 minutes to optimize.

Here is the problem - the route is clearly flawed. The attached file illustrated the problem. You will see that from stop 29, circled in red in the upper right to stop 30, also circled in red at the lower left, the route passes right by stop 156, circled in yellow with several other stops. Later on, the route goes from stop 155 down to stop 156, then right back up through stop 155 on the way to 157. There is no way that it would not have been more efficient to go from 29 to 156 then to 30, eliminating the loop down from 155 to 156 and back.

This completely blows my confidence in the programs ability to optimize a route. Any thoughts?

Thank you,
Louis

Attached Images

Optimization Question 01.jpg (211.7 KB)

Oh, something else: Since Streets & Trips can only handle one route in a file, I am not sure how to combine a number of "segments" (smaller routes created individually) into a single route. No big deal if that is not possible, but it would be nice to see the entire route with distance, time, etc. for the entire trip.

Louis

Lou, I have tried to replicate your mini-route and get a substantially different result, see the screenshot attached. Obviously, something different is going on with your database compared to this simple extraction I have made and it is difficult to conclude exactly what that is. There is no question that S&T's optimization process involves some compromises and has limitations as a result.

With regard to segmentation of your database, I wonder if it might make sense to figure out how many locations you can visit in a day and then visually select clumps of pushpins that approximate that target, optimize, calculate, and then use that for single-day route files. It seems a population of 600 data points is not much better than 1,024 for optimization purposes based upon your experiences.

No, you cannot directly merge multiple shorter routes files into a single file route file. This is a wishlist request elsewhere on the forum. However, you can copy the route waypoints of each single segment file as exported GPX data files and then import these multiple GPX files into a single route file and possibly build a single route from those waypoints. It might be a bit tricky, though.

Attached Images

06-06-10.jpg (71.4 KB)

Any individual error is not significant. In particular, the errors that you can detect by eye are probably outnumbered by the errors that you cannot detect.

What matters in the end is the total trip length. The best way to realistically assess S&T's overall performance is to throw the same set of points into several different route optimization software packages, and compare the trip lengths that come out.

The real question is: how much are you willing to pay to save an extra hundred miles? How much does it cost you to spend each extra day on the road? There are plenty of route optimization packages -- problem is, most of them are marketed to service/delivery businesses that can save hundreds of thousands of dollars from doing route optimization properly.

Streets & Trips costs under $30. I wouldn't expect it to do as well as a $500 route optimizer or a $5000 route optimizer. There are a lot of tricks that a software company can throw in if they're willing to spend engineering time on it.

Thank you SpadesFlush. Due to the exponential nature of the computational difficulty in optimizing a route as the number of stops increases fropping the number from 1,000+ to 600 makes a huge difference in the time to compute. Apparently, though, it doesn't help much with the compromises and shortcuts that the algorithm takes. I plan to do basically what you suggest, i.e. break the trip up into segments, but on a trip expected to last 3 1/2 months or so I will make chunks larger than one day's worth of driving.

Thanks again.

taoyue, I didn't see your response earlier. Thank you for the input. Maybe I was expecting too much, but I CERTAINLY wouldn't expect it to compute a route that runs right by a stop then makes a specal loop later on to catch it. Oh well. I called Microsoft technical support in the hopes that they would tell me something specific, like 'don't optimize more than 100 stops at a time' or 'that's a known problem - here's an easy workaround.' No such luck. At one point the guy actually told me that optimization does not re-order the stops, it just finds the best route from stop 1 to stop 2, then the best route from stop 2 to stop 3, etc. What a joke. I replied that simply clicking "Get Directions" does that and he just mumbled 'oh yeah' or something. Anyway, I'm going to try it with trip segments of no more than 100 or so and see what happens.
Louis

No, it is not at all surprising that errors like path duplication will pop up. It all depends on which heuristic they chose to use. Every heuristic has a worst-case failure mode. And humans are *very* good at detecting patterns that look out-of-place. That makes us very merciless critics of computer programs. So, for example, we might complain that a program makes an obvious path-duplication error that costs us 60 miles in one place, without realizing that it saved us 200 miles somewhere else.

Essentially, what seems to be happening is that S&T does a global heuristic optimization and just throws the results at you -- without cleaning up the inevitable errors that make it look bad. But you can't use this one error to extrapolate overall performance. The only way to really evaluate S&T's route optimization is to compare total trip length against other programs.

I have no doubt that S&T performs worse than a more expensive route optimizer. But I do think you're expecting too much from a $30 program for which route optimization is not the primary function. Unfortunately, not that many people are actually traveling salespeople.

Fortunately, I am not a traveling salesman either. Not knocking those who are, it just wouldn't suit me.

Thanks again.

When I was a travelling salesman a long time ago, I would have loved to have had Streets and Trips 2010, even though oil companies gave out free maps...

I am working on my route in smaller segments now, not much more than a hundred stops each, and Streets & Trips is working great! The drawing tools come in real handy for marking off segments (I have a lot of stops in specific areas, in some cases dozens of stops within a single city or well defined area). Using the drawing tools really helps to visualize the "flow" of my travels and also to help ensure that I don't miss adding any stops to my route (I have over 1,000 pushpins in a pushpin set that I imported from an Excel sheet).

Along with the address data on the Excel sheet I imported several columns of other data. I am supposed to be able to edit it, but I cannot. When I try to select text in a balloon to type over it or delete it, it will not allow it. Any idea as to why this would be?

Thanks!

Lou, it sounds like you are making great progress with your route planning. I am sure you will find Streets and Trips to be an invaluable tool for this expedition.

With respect to your pushpin balloon text issue, I was hoping someone would have answered it for you by now because I have had the same experience occasionally. I have found this to occur sporadically and I cannot figure out what the common thread is or how to solve it, so I would like a solution, too. I cannot replicate this performance and now I cannot find any pushpins where that has caused me problems in the past so maybe it solved itself in my case. You might try saving the map file and re-opening it to see if the problem persists. Otherwise, I don't have much constructive advice to give you but perhaps someone else will.

Lou, if you manually create pushpins you can change the balloon text all you want. However, if the source of the data comes from a spreadsheet it is "read-only" in the balloons. Edit the details in the spreadsheet and then re-import it.

....or.....

copy the contents of a single pushpin balloon [high-light, copy] and then create a new pushpin (taking care to place it in the 'right' place), and paste that copied content into the balloon of the new pushpin and edit as it pleases you without going back to the spreadsheet. Delete the imported pushpin.

These new pushpins will not initially be in the set of the imported pushpins but they can be moved to the other set if that is an issue.