Welcome to MapForums!

Register, sign in, or use Facebook Connect above to join in and participate in the forum.

When you are signed in, this message, the ads in this row, and the red-underlined link ads all go away.

Subscribe to receive our newsletter.
Subscribe Unsubscribe
Results 1 to 4 of 4

Traveling Salesman problem in Streets and Trips

This is a discussion on Traveling Salesman problem in Streets and Trips within the Bing Maps Blogs & Tweets forums, part of the Blogs category; I saw this post on SlashGeo yesterday asking about solving the traveling salesman problem in online maps, and more specifically ...

  1. #1
    VE Team is offline Senior Member Blue Belt
    Join Date
    Sep 2007
    Posts
    185

    Traveling Salesman problem in Streets and Trips

    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.



    Click here to view the full post.
    Last edited by Eric Frost; 01-18-2008 at 09:42 PM.

  2. #2
    WonderMonkey is offline Junior Member Yellow Belt
    Join Date
    Apr 2006
    Posts
    22

    Re: Traveling Salesman problem in Streets and Trips

    This is a nice feature. I assume it would take custom programming to say "I have three salesman and want to visit these 10 locations today, who should go where and in what order?". I'm currently combing the forums looking for discussion on this topic and this post (and link to article) is the first one that I came across that goes along that trail.

  3. #3
    Eric Frost's Avatar
    Eric Frost is offline Administrator Black Belt
    Join Date
    Jul 1992
    Posts
    5,094
    Blog Entries
    4

    Re: Traveling Salesman problem in Streets and Trips

    MapPoint adds another level of sophistication allowing you to automate things, I'd imagine for a small jobs like 3 ppl 10 stops, you could simply iterate over the possible solutions and choose the ideal one.

    For bigger tasks there are higher-end logistics/route optimization tools like TourSolver, I'm not sure what to recommend.

    Eric
    ~ Order MapPoint MapPoint 2013 Here and Get Free Access to the MapForums Downloads ~
    ~~
    ~ Upgrade to Get Access to the MapForums Downloads ~

  4. #4
    WonderMonkey is offline Junior Member Yellow Belt
    Join Date
    Apr 2006
    Posts
    22

    Re: Traveling Salesman problem in Streets and Trips

    The time it takes to solve is the issue of course. I can easily create a matrix of all combinations of people and stops with the parameters and run it through the optimizer but it takes considerable time.

    I'll look into the TourSolver you mentioned and look into others like it.

    Thanks.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. MapPoint, Pocket Streets, Streets and Trips
    By chpw in forum MapPoint Desktop Discussion
    Replies: 3
    Last Post: 01-04-2006, 09:54 AM
  2. Streets&Trips
    By Anonymous in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 01-19-2005, 09:41 AM
  3. Streets and Trips
    By Alex Chow in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 11-09-2004, 02:22 PM
  4. streets and trips
    By Anonymous in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 12-02-2003, 08:13 PM
  5. MS Streets And Trips and VB6
    By NickSP in forum MapPoint Desktop Discussion
    Replies: 2
    Last Post: 02-04-2003, 11:37 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91