Most efficient way to get to multiple places?

March 14, 2023 8:51 AM

Is there an app or existing map function that will allow me to plug in multiple locations around a large metro area and come up with a map that will show me how to drive to them in the most efficient order?

I'm scouting 5-7 locations for a small film shoot in the wider NYC metro area (including north NJ, Westchester, Long Island). I really only have a day to go hit all the locations so I need to be able to do it in the most efficient way.

*I know that traffic and timing are a huge factor in this, but I want to start with the shortest course to hit them all, then I'll work around schedules and traffic.

Does Google maps or Waze have a function like this? Or is there another app that might?

Thanks!

posted by greta simone to Travel & Transportation (13 answers total)

This is actually a super complicated math problem, or it can be when there's no obvious option. I think in your position I would not look for the one true answer, but for an answer that would let you hit them all, maybe grouping them by borough/county and then trying to game rush hour as well as possible and avoid trying to park in Manhattan entirely unless you can plan well ahead.
posted by chesty_a_arthur at 9:07 AM on March 14, 2023

You also might be able to compare a few versions in Google or Waze, but obviously every permutation will be a lot of effort for maybe not much incremental payoff.
posted by chesty_a_arthur at 9:08 AM on March 14, 2023

There are Ph.D. dissertations on this (on preview, jinx). But Microsoft MapPoint used to do it. It's discontinued now.
posted by kevinbelt at 9:10 AM on March 14, 2023

Hahaha yes you're about to have a bunch of mathematics and computer scientists in this thread telling you it's NP-hard. I would use your intuitions to develop a half dozen "likely best" maps and compare them in your driving app of choice.

That said, this problem being well known to be hard, lots of people have attempted to solve it. I can't vouch for any particular solution but there are a lot of hobbyist implementations of traveling salesman solvers on real world maps out there; you can definitely waste your day on Google trying to find a good one. However, I would expect that the only people who have ready access to implementations that take typical traffic patterns, current construction, and road closures into account, which I'd want for any big city, are route planners for UPS, FedEx, and Amazon.
posted by potrzebie at 9:16 AM on March 14, 2023

You might find these previous AskMe's helpful:

https://ask.metafilter.com/307790/App-that-solves-the-traveling-salesman-problem

https://ask.metafilter.com/291279/How-to-get-from-here-to-thereto-thereto-thereand-back-here
posted by vacapinta at 9:21 AM on March 14, 2023

Someone may know something better that is more automated, but the Roadtrippers app lets you plug in all your "waypoints" and it kinda tries to put them in some kind of order but you will probably want to tweak it - luckily they make that super easy.
posted by Lyn Never at 9:59 AM on March 14, 2023

Don't know an automatic app but I add the addresses in google maps and shift the order and review the output. Add the first address and then there is an "add destination" under the first two addresses. Then once there are more than two they can be dragged up and down. Maxes out somewhere after 10-15.

One trick I use is to click on the walk and bike directions to get a sense of the straightest route and if a non-obvious jog or reversing the order would help.

It still can't handle some addresses and occasionally creates funny loops that obviously are just bad, but still an amazing tool.
posted by sammyo at 10:19 AM on March 14, 2023

5 is a small enough number that it wouldn't be too hard to figure this out with brute force. 5! is only 120 (the number of possible routes) and there are only 10 combinations of stops that you need to find the distance between. Once you get to 7, there are 5,040 possible routes and 21 combinations. A lot more but still doable in a spreadsheet or similar.

At this scale, I think the human eye seeing the points on an accurate map would be more efficient at determining an optimal route, even if it isn't the perfect route.
posted by soelo at 12:25 PM on March 14, 2023

you could try https://www.routora.com/

pretty sure it was designed for this concept, but does not as of yet have a mobile app
posted by Sprocket at 1:36 PM on March 14, 2023

I'm currently writing an app for a client that does exactly this and I've been planning to use the Google Maps API - they have a "Distance Matrix" API that seems relevant. The client used to do this by "brute force" every day for many more stops and I've been appreciating the challenges - glad it's not just me who thinks this is hard.

I'd second visualizing the route on a map and tweaking it from there.

I'm going to check out routora.
posted by bendy at 5:10 PM on March 14, 2023

Not sure what method they use for optimizing but MapQuest has this option
posted by Medw at 5:50 PM on March 14, 2023

I had a job that touched on the problem. I doubt any if the fancy math is going to be real help in a real city. For example, it's not going to come up with the "no left turns" rule the UPS is rumored to have in some cities. (Tested by Mythbusters.)

Basically, there are two efficient routes which we may label as "out and back" and "around the circle". The former is best if the stops are spread out in a line, and the latter is best when they make a blob. You may want to reduce a blob to a couple of circles. The message of the former is you don't have get all the stops on the way out.
posted by SemiSalt at 5:35 AM on March 15, 2023

Wanderlog does this! Add your locations and then click Optimize route.
posted by anotheraccount at 5:55 AM on March 15, 2023