4

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.

Improve this question
6
  • 9
    en.wikipedia.org/wiki/Travelling_salesman_problem how large is n?
    – jcaron
    Commented Jun 18, 2022 at 10:52
  • @jcaron thanks, yes that's indeed a TSP, n is between 5 and 20 depending on the agenda.
    – Franck Dernoncourt
    Commented Jun 18, 2022 at 11:04
  • I'd be happy to get some feedback from the downvoters.
    – Franck Dernoncourt
    Commented Jun 18, 2022 at 22:32
  • 3
    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
    Commented Jun 19, 2022 at 18:23
  • 5
    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.
    – Saaru Lindestøkke
    Commented Jun 20, 2022 at 8:09

2 Answers 2

Reset to default
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

Improve this answer
6
  • 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.
    – Franck Dernoncourt
    Commented Jun 18, 2022 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
    Commented Jun 18, 2022 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.
    – Franck Dernoncourt
    Commented Jun 18, 2022 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
    Commented Jun 19, 2022 at 12:43
  • I suspect you'd get pretty good results using a DB of locations to produce a range of candidate good routes then selecting from those by feeding them to Google maps. A fairly simple script should be able to produce a bunch of test URLs. The hardest part of that might be that a more diverse set of routes should be tested than simply the shortest few (which might be too similar)
    – Chris H - UK
    Commented Sep 5, 2022 at 12:57
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

Improve this answer
2
  • 1
    Roadtrippers.com probably has this as well.
    – user29788
    Commented Jun 19, 2022 at 4:18
  • 1
    Google has this feature too, but only as a service for software developers.
    – sourcream
    Commented Jun 19, 2022 at 18:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .