3

I'll soon visit some places in the US by car. I'd like to visit n places. How can I see what the fastest driving route is that goes through all these n places?

Google Maps allows users to indicate several stops, but it only gives the route duration for the given order of the stops and I don't want to try all permutations.

7
  • 7
    en.wikipedia.org/wiki/Travelling_salesman_problem how large is n?
    – jcaron
    Jun 18 at 10:52
  • @jcaron thanks, yes that's indeed a TSP, n is between 5 and 20 depending on the agenda. Jun 18 at 11:04
  • I'd be happy to get some feedback from the downvoters. Jun 18 at 22:32
  • 2
    In case you are inclined to do some coding, Google has support for that on its Directions API. See the docs on the optimize:true parameter. The service isn't free though, but Google awards some free credits every month or so.
    – sourcream
    Jun 19 at 18:23
  • 2
    I see there are 3 close votes with the reason "... constructing travel and tour itineraries (including scheduling and budgeting) are off-topic". As it's only 1 close vote away of being closed I wanted to note that the question asker is not asking for an itinerary, but for a tool that can create an itinerary for them given some constraints. I think asking for tools instead of outcomes is commendable and does not fall within the given close vote reason. Jun 20 at 8:09

2 Answers 2

10

As pointed out in the comments, this is the classical Travelling Salesman problem.

It's mathematically tricky to solve. You can always brute force by trying all possible routes but the number of permutation increases with the factorial of the number of cities, so that becomes unwieldy very quickly.

This being said, for 5-20 cities, even something simple as Microsoft Excel can solve this pretty well. Here is an example: https://www.youtube.com/watch?v=-E3rSoClgMI on how to do this.

The input to the algorithm is the distance matrix. You can either use distance or time, either one would work. You either need to get these manually from Google Maps or use one of the existing APIs. For 10 cities, that's 45 numbers you need to pull out of Google Maps. I guess it's up to you to decide whether that's worth the effort or not.

I ran a 13 city simulation and it took less than a minute on my laptop. (source https://developers.google.com/optimization/routing/tsp).

For something larger you probably need a more advanced algorithm and a decent programming language (like Python or Matlab/Octave). See for example: https://www.youtube.com/watch?v=c5395m-nVz4

Here are the results: You can cover 13 major cities in the US in 7386 miles.

enter image description here

4
  • Thanks for the ideas and the code. I was hoping some mapping website had this feature. Concorde TSP can be used if one builds one's own solution and need a faster TSP solver. Jun 18 at 15:52
  • 1
    This all depends on how fancy you want to get. I have a version that uses a public US city data base to get latitude and longitude and that auto creates the distance matrix just based on a list of cities. This assumes co-ordinate distance is proportional travel distance or travel time, which may or may not be good enough. In my neck of the woods travel time to the airport varies from 30 minutes to 2 hours just based on time of day (i.e. traffic).
    – Hilmar
    Jun 18 at 21:24
  • Thanks, indeed taking the actual travel duration into consideration would be more useful. Also in some cases my n locations are within the same metropolitan area. Jun 18 at 22:34
  • 1
    Same metropolitan area is not a problem. I got a list from simplemaps.com/data/us-cities which has 30000+ cities. My (smallish) county has 20+ entries so you get very good resolution.
    – Hilmar
    Jun 19 at 12:43
5

The Android application Wanderlog has a paid feature to view the fastest driving route is that goes through all these n places:

Reddit user quatrotires pointed me to it.


Roadtrippers also has this feature. From https://support.roadtrippers.com/hc/en-us/articles/201310953-Quickly-Customize-a-Trip-s-Route:

Our trip planner looks for the most efficient route between waypoints by default. If you want to take a different route, on our desktop site you can easily customize the route by clicking and dragging it on the map.

enter image description here

SE user Moo pointed me to it.


Google Directions API also has this feature:

In case you are inclined to do some coding, Google has support for that on its Directions API. See the docs on the optimize:true parameter. The service isn't free though, but Google awards some free credits every month or so. sourcream 4 hours ago

3
  • 1
    Roadtrippers.com probably has this as well.
    – Moo
    Jun 19 at 4:18
  • @Moo thanks, added. Jun 19 at 4:28
  • 1
    Google has this feature too, but only as a service for software developers.
    – sourcream
    Jun 19 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.