I just got a job doing deliveries around my area. Basically, I’m given a list of 100-200 addresses, and I then drive around and deliver the appropriate stuff to each address.
Now, in the interest of doing this in the most efficient way, I’m trying to figure out a good way to find “the best route” for a list of stops. That got me thinking about Mapquest.
Mapquest, for those who don’t know, allows you to enter a starting address and a destination address, and it then delivers the (arguably) most direct route. This is a great tool, and I use it all the time.
What I’m wondering, though, is if there’s a way to use this or a similar tool to aid me in my job. What I’d like to do is punch in a list of either addresses, or simply streets, and my starting point, and get back a route that hits all the addresses in question, and doesn’t involve lots of doubling-back or retracing of steps.
Has anyone ever seen/used/heard-of something like this? It could be a website such as Mapquest or maps.yahoo.com, or possibly one of those “street atlases” that people purchase on CD-ROM?
Microsoft has a product called MapPoint which does exactly what you want, but it’s not free. You can put in as many points as you like, and it will create a route from point a to point b, point b to point c etc. It doesn’t do any optimization (as far as I know). You can check out the MS site for more details. I have used it and it works well in most places in the US. It’s probably too expensive for your purposes.
Yes and no. On one hand, it is the travelling salesmen problem. But that’s not THAT bad for small numbers of stops. The number of routes to check with 5 stops isn’t going to kill a modern computer, for instance.
And if there are, say, 1,000,000 possible routes, and it picks one that’s about 2,000 down from the absolute best one… it won’t be that much longer than it should be. BTW, I have no idea if 1,000,000 is even close, I’m just making an example.
I did the one-week trial, and this is actually excellent – with one caveat. It can only support 18 locations when designing the ultimate route; my job generally involves 100-150 stops. Is there anywhere that does essentially the same thing as NavPro, but supports more stops?
I’m still unclear on whether Streets&Trips and Rand McNally’s offering can do this; descriptions of their features, even on the websites, are kinda vague. Can you enter a list of stops and have them spit out the best way to hit all of them in the least amount of time?