MapForums

I saw this post on SlashGeo yesterday asking about solving the traveling salesman problem in online maps, and more specifically why no one has done it. I think there are a few reasons starting with the fact that route optimization isn't something most of us need to do very often. but probably more importantly, when done correctly route optimization is pretty cpu intensive and most web users of online mapping software wouldn't want to wait for the results. For in-city trips, not so bad, but spread your stops over a larger area and it can be costly. You can cut corners by eliminating a number of possibilities with fast crow-flies estimates, but that's cheating and will yield crappy results. Any online mapping site could provide this functionality, but i'm not sure anyone would be happy with the results or perf.

As for solving via a Web API, this is also possible but would take a lot of real-time. if your optimization code sits close to the routing engine you can solve much more quickly, but for the number of remote calls needed latency kills. Most applications that call for this type of functionality (logistics, delivery, etc...) have their own optimization code that needs to consider more than just time and distance (its cheaper to run a truck with a full take of gas downhill for instance)

But for the rest of us, there's Streets and Trips S&T solves the traveling salesman problem quite well and is a popular and easy to use feature especially among business travelers. To use it, just add your stops to a route, hit the 'optimize stops' button on the directions panel, then wait while S&T crunches away. When its done your stops are presented in optimal order. You can even specify stop restrictions such as the time of day you need to be at a particular location! Below are screen shots of the process.

DEVELOPER NOTE: MapPoint 200X has the same functionality built in and is exposed via our API making MapPoint a popular choice in logistics and fleet management applications. Check it out if you need to add this type of calculation to your apps.

Here's a look at how to solve the traveling salesman problem with Streets and Trips or MapPoint 200X:

1. Add Your stops. Here I am traveling around Portland. The trip starts at my hotel and ends at the airport. In between I have 6 stops to make.

2. Optionally Set Restrictions on stops. I want to leave my Hotel at 9am and be at 148th Ave at noon for lunch. the other stops are flexible. Oh, and I need to finish at the airport.

3. Optionally set other global options. The optimizer can consider many factors that you can control such as rest stops and your personal tolerance for being late.

4. Hit the optimize Stops Button. For this trip consisting of 8 stops in the same city, it took about 8 seconds on my modest laptop.

Here are the re-ordered stops:

5. Calculate directions. Now that your stops are optimized, you probably want Streets and Trips to give you directions between all of them. Hit the 'Get Directions' button.

If you have a GPS device connected to your laptop, S&T will also give you voice assisted navigation instructions as you drive.