OpenStreetMap

Travelling Salesman Website

Posted by sdoerr on 18 May 2011 in English (English)

I've started using the website http://gebweb.net/optimap/ to plan my mapping forays. I click on all the streets I want to visit (usually based on the ITO Analysis site) together with my start point and end point and it works out a route for me. I then enter the points as Favourites in my TomTom iPhone app, numbered according to the sequence the optimap site calculated, then navigate from one to another. Sadly, it's based on Google Maps! If anyone knows a better one, let me know. It's a shame the TomTom app doesn't have a file upload facility though: it's a bit tedious entering all the locations manually. I daresay there are other routing apps that do have that capability though.

Tonight's target area is Greenhithe and Stone.

Comment from Sanderd17 on 18 May 2011 at 16:38

I do not know your technical skills, but mapquest has an api for this. You call e.g.

http://open.mapquestapi.com/directions/v0/optimizedroute?json={locations:[{latLng:{lat:51.524410144966154,lng:-0.12989273652335526}},{latLng:{lat:51.54495915136182,lng:-0.16518885449221493}},{latLng:{lat:51.52061842826141,lng:-0.1495479641837033}},{latLng:{lat:51.52850609658769,lng:-0.20170525707760403}}]}

and as response, you get a JSON file, including a field like

"locationSequence":[0,2,1,3]

which means that the best order of locations is 0-2-1-3, it will always begin with the first (0) and end with the last.

It also contains a route description.

I do not know if there is some website with an easy GUI that implemnts this feature.

Hide this comment

Comment from Sanderd17 on 18 May 2011 at 16:54

It seems that mapquest implements their own api. so you can just go to http://open.maquest.com (this uses openstreetmap data), there you can right-click on the map or search by address to enter locations. You set the first and last location like you want and finally, check the "Allow MapQuest to re-order stops" checkbox under driving options.

It will take a while before you get your route. the Travelling Salesmen problem is an NP-complete problem. So it asks a lot of work, and the mapquest site is optimised to update all the time, not to do big calculations. So wait a bit before you force the site.

I do not know if the mapquest site has an export feature or what export format you should like. But it is at least as good as what you got.

Hide this comment

Comment from sdoerr on 19 May 2011 at 12:08

Thanks, Sanderd17. The Mapquest site looks good, but the final bit looks more difficult - getting the locations into the satnav (the other site gives me the co-ordinates for each one).

Hide this comment

Leave a comment

Parsed with Markdown

  • Headings

    # Heading
    ## Subheading

  • Unordered list

    * First item
    * Second item

  • Ordered list

    1. First item
    2. Second item

  • Link

    [Text](URL)
  • Image

    ![Alt text](URL)

Login to leave a comment