VE Team
01-18-2008, 04:01 PM
<p>I saw this <a href="http://technology.slashgeo.org/technology/08/01/17/2258255.shtml" target="_blank">post on SlashGeo</a> 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. <p>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) <p>But for the rest of us, there's <a href="http://www.microsoft.com/streets/default.mspx" target="_blank">Streets and Trips</a> :-) 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. <strong></strong> <p><strong>DEVELOPER NOTE:</strong> 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. <p><strong><font color="#0000ff">Here's a look at how to solve the traveling salesman problem with Streets and Trips or MapPoint 200X:</font></strong> <p><strong>1. Add Your stops.</strong> 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. <p><a href="http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ0ymzbGG0rdtJlSVCJffz5jNSX7mccaQdiNoFb 0vRMfGHswre6ehzgiHQ_hq93qRW3hYOKOAW6aKg?PARTNER=WR ITER">
http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ2UiNBVd9eVdbZFj4Omug8hoYg385933oI_m_k VlZ4lx2xpmI-t_yirT9iMmUyKhp4EvMct_Hh_ng?PARTNER=WRITER</a> <p><strong>2. Optionally Set Restrictions on stops</strong>. 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. <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA-_TPJv-nQd3XrDu6MUKEXLoT7funseekEKiBTEmE7r08R6kOBC3xAnEtj Ej__72o8?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA_58o1AMlc77aD73xKwAdhNtwME4MUyMikDMuC _ahNXA61ieraC-5Yf6v8Zhd9YNQ0?PARTNER=WRITER</a> <p><strong>3. Optionally set other global options.</strong> The optimizer can consider many factors that you can control such as rest stops and your personal tolerance for being late. <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA-LQGhm5p7PZVNrjKEyPucOYAQ9tr2_hnKc8pkj-QTB-7NOnsNxBzArS9uX4HHc8iM?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA_Iuj0wEXSIGf-xpnxMtc50WEKktXS2gOA_3VBsrpd0PAVq8-hUPVKVEdlfzzf7PWs?PARTNER=WRITER</a> <p><strong>4. Hit the optimize Stops Button.</strong> For this trip consisting of 8 stops in the same city, it took about 8 seconds on my modest laptop. <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA_a3hwKaOLmFIDMOphOFJZ3sNy2W45qypGt0fA blNJvVfTSUAb75uOvd1EwsVooL-s?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA8LlLWyIL84jlxnVDZGfm8mGtV4m7yfUdSXDIt WTkFRHrIMRCHSsodhxBytJvoZsUg?PARTNER=WRITER</a> <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA9Lyg67Ke2k5WV6KUt1Kfrvqv_tbDqfnLQrwzx qmNYEEx-dzeZyjTWMhOAwz87MqJw?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA9ss2x2qLHM4x3zWFZkTTZM5VyGcOUNDoQBoVg weNxLYMOZ4MkBMU3XNXx7phIhyl8?PARTNER=WRITER</a> <p><strong>Here are the re-ordered stops:</strong><br><a href="http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ1BAmMlsC7gMcQ6KOZarIJuBwTTFcmGCKxgfaT 2BFCU0qt-R29VQhlPLHuaSJ2R6t-KFltubFuvUw?PARTNER=WRITER">
http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ3cHZJLoU5zznYXpIsA0NOMl2Hj3qcdL6rnSTS esRVIXEbexUobC4hIzn8vMutjM7kaHPnPpsVSBg?PARTNER=WR ITER</a> <p><strong>5. Calculate directions.</strong> 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. <p><a href="http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ1tP41rFqYd8eYDmUkYNiddJzpeya_-LfRQXgIPTGyoexFDiIr5rgiMZ9Qy85zEQUU5W2S1jkewNg?PAR TNER=WRITER">
http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ2YNEeu_mSIQO2Hi8YP1aQQSzbP49gHGQgo3rZ 9c-9UnswJnrkuRMXTIOd_QAsXMoUYGDv6O3l0eQ?PARTNER=WRITE R</a> <p>If you have a GPS device connected to your laptop, S&T will also give you voice assisted navigation instructions as you drive. <div style="padding-right:0px;display:inline;padding-left:0px;padding-bottom:0px;margin:0px;padding-top:0px">Technorati tags: <a href="http://technorati.com/tags/Streets and Trips" rel=tag>Streets and Trips</a>, <a href="http://technorati.com/tags/Autoroute" rel=tag>Autoroute</a>, <a href="http://technorati.com/tags/route optimization" rel=tag>route optimization</a>, <a href="http://technorati.com/tags/traveling salesman" rel=tag>traveling salesman</a></div><img src="http://c.services.spaces.live.com/CollectionWebService/c.gif?cid=3151506992847969176&page=RSS%3a+Traveling+Salesman+problem+in+Streets+ and+Trips&referrer=" width="1px" height="1px" border="0" alt=""><img style="position:absolute" alt="" width="0px" height="0px" src="http://c.live.com/c.gif?NC=31263&NA=1149&PI=73329&RF=&DI=3919&PS=85545&TP=virtualearth.spaces.live.com>1=virtualearth">
Click here to view the full post. (http://virtualearth.spaces.live.com/Blog/cns!2BBC66E99FDCDB98!10973.entry)
http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ2UiNBVd9eVdbZFj4Omug8hoYg385933oI_m_k VlZ4lx2xpmI-t_yirT9iMmUyKhp4EvMct_Hh_ng?PARTNER=WRITER</a> <p><strong>2. Optionally Set Restrictions on stops</strong>. 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. <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA-_TPJv-nQd3XrDu6MUKEXLoT7funseekEKiBTEmE7r08R6kOBC3xAnEtj Ej__72o8?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA_58o1AMlc77aD73xKwAdhNtwME4MUyMikDMuC _ahNXA61ieraC-5Yf6v8Zhd9YNQ0?PARTNER=WRITER</a> <p><strong>3. Optionally set other global options.</strong> The optimizer can consider many factors that you can control such as rest stops and your personal tolerance for being late. <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA-LQGhm5p7PZVNrjKEyPucOYAQ9tr2_hnKc8pkj-QTB-7NOnsNxBzArS9uX4HHc8iM?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA_Iuj0wEXSIGf-xpnxMtc50WEKktXS2gOA_3VBsrpd0PAVq8-hUPVKVEdlfzzf7PWs?PARTNER=WRITER</a> <p><strong>4. Hit the optimize Stops Button.</strong> For this trip consisting of 8 stops in the same city, it took about 8 seconds on my modest laptop. <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA_a3hwKaOLmFIDMOphOFJZ3sNy2W45qypGt0fA blNJvVfTSUAb75uOvd1EwsVooL-s?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA8LlLWyIL84jlxnVDZGfm8mGtV4m7yfUdSXDIt WTkFRHrIMRCHSsodhxBytJvoZsUg?PARTNER=WRITER</a> <p><a href="http://byfiles.storage.msn.com/y1pTcqBXnZTBA9Lyg67Ke2k5WV6KUt1Kfrvqv_tbDqfnLQrwzx qmNYEEx-dzeZyjTWMhOAwz87MqJw?PARTNER=WRITER">
http://byfiles.storage.msn.com/y1pTcqBXnZTBA9ss2x2qLHM4x3zWFZkTTZM5VyGcOUNDoQBoVg weNxLYMOZ4MkBMU3XNXx7phIhyl8?PARTNER=WRITER</a> <p><strong>Here are the re-ordered stops:</strong><br><a href="http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ1BAmMlsC7gMcQ6KOZarIJuBwTTFcmGCKxgfaT 2BFCU0qt-R29VQhlPLHuaSJ2R6t-KFltubFuvUw?PARTNER=WRITER">
http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ3cHZJLoU5zznYXpIsA0NOMl2Hj3qcdL6rnSTS esRVIXEbexUobC4hIzn8vMutjM7kaHPnPpsVSBg?PARTNER=WR ITER</a> <p><strong>5. Calculate directions.</strong> 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. <p><a href="http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ1tP41rFqYd8eYDmUkYNiddJzpeya_-LfRQXgIPTGyoexFDiIr5rgiMZ9Qy85zEQUU5W2S1jkewNg?PAR TNER=WRITER">
http://xax3ia.bay.livefilestore.com/y1p511BmElsGQ2YNEeu_mSIQO2Hi8YP1aQQSzbP49gHGQgo3rZ 9c-9UnswJnrkuRMXTIOd_QAsXMoUYGDv6O3l0eQ?PARTNER=WRITE R</a> <p>If you have a GPS device connected to your laptop, S&T will also give you voice assisted navigation instructions as you drive. <div style="padding-right:0px;display:inline;padding-left:0px;padding-bottom:0px;margin:0px;padding-top:0px">Technorati tags: <a href="http://technorati.com/tags/Streets and Trips" rel=tag>Streets and Trips</a>, <a href="http://technorati.com/tags/Autoroute" rel=tag>Autoroute</a>, <a href="http://technorati.com/tags/route optimization" rel=tag>route optimization</a>, <a href="http://technorati.com/tags/traveling salesman" rel=tag>traveling salesman</a></div><img src="http://c.services.spaces.live.com/CollectionWebService/c.gif?cid=3151506992847969176&page=RSS%3a+Traveling+Salesman+problem+in+Streets+ and+Trips&referrer=" width="1px" height="1px" border="0" alt=""><img style="position:absolute" alt="" width="0px" height="0px" src="http://c.live.com/c.gif?NC=31263&NA=1149&PI=73329&RF=&DI=3919&PS=85545&TP=virtualearth.spaces.live.com>1=virtualearth">
Click here to view the full post. (http://virtualearth.spaces.live.com/Blog/cns!2BBC66E99FDCDB98!10973.entry)