This is a static archive of our old OpenStreetMap Help Site. Please post any new questions and answers at community.osm.org.

Traveling salesman routing

4
1

Is there a Traveling Salesman routing program or website where I can feed a list of lat lon coordinates or similar and it outputs the shortest route passing through all points, reordering as necesary, preferably with car, bicycle and walking options.

asked 02 May '17, 15:38

nevw's gravatar image

nevw
9.8k2690178
accept rate: 9%


One Answer:

7

All major OSM routing engines support this:

  • Mapzen's Valhalla ("Valhalla also includes tools like time+distance matrix computation, isochrones, elevation sampling, map matching and tour optimization (Travelling Salesman)."),
  • Mapbox's OSRM ("The trip plugin solves the Traveling Salesman Problem using a greedy heuristic...")
  • Graphhopper uses the JSPrit library for route optimization ("TSP problem can be modelled by defining a vehicle routing problem...")

None of these services have a free and unlimited online offering (it would quickly be abused by people trying to save on their own AWS cost). Mapzen has an offer where you register a free API key and use that. OSRM doesn't need an API key, you can just use it. Graphhopper requires registration and while they have a free trial, I don't think they have a free tier.

All three are Open Source and you can install and use them without limits locally.

answered 02 May '17, 16:05

Frederik%20Ramm's gravatar image

Frederik Ramm ♦
82.5k927201273
accept rate: 23%

edited 02 May '17, 16:06

Thanks Frederik, helpful and comprehensive as always.

(02 May '17, 16:15) nevw

Source code available on GitHub .