Try MapQuest for Many-Stop Route Planning
With one of my other hats on, I’m president and chief rabble-rouser for the Finger Lakes Runners Club. Last year, faced with the possibility of more COVID-caused race cancellations, I developed the FLRC Challenge, a series of 10 virtual races around the area in which runners can run courses multiple times, record results with the Webscorer app, and check standings on a dynamic leaderboard. It was a ton of fun to come up with all the rules, coordinate the design work, and put together all the technology to make it happen. It has been a big hit in the community, with 146 runners putting in over 12,000 miles so far this year.
To help promote the FLRC Challenge in the community, I designed and printed lawn signs—those things that sprout like mushrooms every election season. Club members signed up to host them via a simple Google Form that asked for their name and address, and once the signs arrived from Signs.com, I was faced with how best to distribute them. Our area isn’t that large, so Tonya and I decided to spend the afternoon of July 4th driving around and installing them. (It was glorious summer weather, we were driving our all-electric Nissan Leaf, and many of the people who asked for signs are friends, so it was a nice way to spend the day.)
But here’s the question. When faced with needing to visit 43 different addresses, what was the most efficient route? It’s easy enough to enter an address into Apple’s Maps or Google Maps, and even add an extra stop or two. But 43 stops in an optimal route? It’s possible to import a list of addresses into Google’s My Maps, but I could see no way to load a custom map in the Google Maps iPhone app and have it navigate from one spot to another.
A little research revealed that MapQuest—remember MapQuest from the days when we all printed directions?—offers precisely what I needed. MapQuest’s RoutePlanner lets you enter up to 26 addresses that it can rearrange to give you the shortest route. (Initially, I couldn’t see why it should be limited to 26 addresses, but once I previewed a route, I realized that every address gets a single letter identifying its pin.) Being limited to 26 stops when I had 43 addresses didn’t prove to be a problem since it made more sense to make separate trips to some of the outlying stops—there was no need to do it all at once.
You can enter addresses one at a time, but the tool also lets you paste in a list of addresses, one per line, or import an Excel or CSV file, if you already have the address, city, state, and ZIP code in separate columns. I opted to Command-click the addresses in the Google Sheet created by Google Forms, after which I copied and pasted the entire batch into RoutePlanner.
Clicking the Get Directions button switched me to the RoutePlanner’s Line by Line tab, where I scrolled to the bottom (fixing one malformed and thus highlighted address on the way), selected “Allow us to re-order stops on your route,” and clicked View Route Directions to see my route on the map. I then tweaked the order of a couple of stops based on local knowledge.
Good enough, but the next question was how to translate that route into something that an iPhone could use to direct us. The answer was to click the Share button at the top. That produced a dialog with a URL and let me text, email, or copy it to my iPhone.
When I loaded that URL in Safari on the iPhone, it provided an option to open in the MapQuest app. I tapped the little iPhone icon to do that and then tapped the Start button.
(To be upfront, the previous two paragraphs took me over a week to write just now, which doesn’t instill confidence in MapQuest. At first, the short URLs that MapQuest generated for sharing the route produced error pages on most loads. I reported the problem to MapQuest and was told they were working on fixing it but never got a confirmation of a fix. However, it seems to work now. Plus, neither the SMS nor email sharing methods worked on recent tries, though I was able to move the URL over to my iPhone in other ways. While troubleshooting the sharing issues, I tried logging in to MapQuest and saving the route to My Maps, but the site could never maintain a login state long enough to do that. Then, in Safari on the iPhone, the black bar with the option to open in the app wouldn’t appear until I force quit Safari and tried again. I had none of these problems last month, and I eventually resolved them this time, but it was frustrating.)
Once you’re actually navigating in the car, the MapQuest app works more or less like Apple’s Maps or Google Maps. It sometimes gets a little confused if you don’t quite make it to a stop, and we once ended up referring to the list view, trying to navigate using local knowledge, and completely missing the stop in question. I’d recommend following its directions carefully and not deviating to the extent possible, since that’s where you’ll confuse the app.
As with “A Solution for Group “Best Wishes” Certificates During the Pandemic” (6 August 2021), this is a solution for a particular problem that most people won’t have, but if you do, I hope you find it useful.
This is similar to the ‘travelling salesperson’ problem or, the related, ‘Hamilton Path’ problem. Back in the 1990s these were regarded as intractable computing problems that would be solved by DNA computers ( The DNA Computer ) or Quantum Computers ( Quantum-Mechanical Computer ).
I guess the number crunching is done on Mapquest servers but to have the results on a handheld device is remarkable.
I share with you a similar need. Periodically I do a “sweep” of my folks who live on a circuit that would cover about 125 miles.
I managed it (sort of) using Google Maps, but my experience was as though Google went out of its way to make it difficult for me. It was a convoluted combo of favorites and lists and a spreadsheet that sort of got me there.
And like most folks I know, I had completely forgotten that MapQuest still exists!
Thanks for the tip @ace !
Same for me! And it sure beats having to type addresses in after every stop.
This is an interesting topic. I use MapQuest periodically because it’s been faster than some for just bringing up the map of a location without entering a “drive from” address. But I did not know they offered the many-address routing solution.
My guess is that the limit of 26 locations to route doesn’t require extensive number crunching as that’s probably a trivial amount to solve - unless heavily used. For free, that’s great. Makes me wonder what commercial solutions are available. Many of us had to solve the “traveling salesman” problem in school before highly-sophisticated mapping was widespread.
This is the traveling Salesman Problem, which is NP-Hard. Travelling salesman problem - Wikipedia There are approximations and heuristics that can get you to a nearly perfect solution, or you can just hammer out all the possible routes and pick the shortest
If the app keeps track of traffic and weather conditions over the course of the trip, chances are high that number crunching will often be extensive. This is particularly true in cities.
Not quite. The traveling salesman problem involves a graph where you need to visit every node exactly once and return to the starting node.
In this case, we’ve got a graph with a massive number of nodes (every intersection on the map), but you only need to visit 26 points on that graph, with no requirement preventing you from driving past a point more than once and no requirement to end at the origination point.
You could reduce the problem space by computing the shortest path between each pair of points (26 * 25 = 650 paths) and then run a modified traveling salesman heuristic (that doesn’t prohibit visiting a node multiple times) over that graph. The result would probably be “good enough” for most people, even if it’s not the perfect solution.
There was also a need for ice cream in the middle, along with having to get home at the end, but we didn’t harass MapQuest with those requirements. :-)
Makes me wonder how outfits like Amazon, UPS, FedEx et al. solve the same problem every day?
They don’t. I see the UPS truck close by several times a day (you can see it on the UPS map) and they always then go far away and back again a few times before I get my package.
Even if I run out in the street and yell “I’m here!!” :-)
UPS has their own solution called ORION. There are some articles about if you search. One thing I’ve read about UPS routing is that they try to avoid left hand turns, so that may explain why a truck drives by your location. Another is, of course, that the package may be on another vehicle.
Amazon is particularly focused on continually upgrading its delivery route planning app, The Rabbit, which works within Amazon Flex:
https://www.logisticsit.com/articles/2020/12/29/how-amazon-manages-its-delivery-routes-(and-how-to-copy-them)
What I find very interesting is that Amazon has teamed up with MIT to develop a new app that “takes into account the learned knowledge of delivery drivers:”
Delivery truck and car parking congestion is a mega problem here in New York City. Either the Amazon, Target, Peapod, Door Dash, etc., etc., trucks or cars are hogging a substantial % of parking spaces, double parking so you are blocked from moving your car, parked illegally so you can’t see round a corner, etc., so this new initiative could be beneficial. In addition to being more street wise, it might even help reduce fuel consumption. And they often block the entrances to parking garages for apartment buildings.
I’ll bet that routing initiatives for shipping are something Apple is probably thinking about for its not so secret electronic vehicle development.
This kind of problem, and many others involving complex networks, are often solved by slime molds now. Sometimes with ants which can be faster, but slime molds are easier to deal with. It can also be done with fungal mycelium. Fungi can probably handle bigger problems, but the mycelium grows a lot slower than slime molds can move.
And many other sources, it’s been going on for quite a few years. Wouldn’t work for ad hoc use as a web service, but you could get your own slime molds and set up whatever conditions you want for it. Should be pretty easy to do at home. Physarum polycephalum is safe to handle and easy to manage, and you can buy it from wherever it’s sold (science supply, such as Carolina Biological). A 3D printer could be a good way to set the problems. Yet another item on my list for retirement…
Excellent discussion. I think slime mold demonstrates the problem can be reasonably solved, but not perfectly, in linear time. This https://www.logisticsit.com/articles/2020/12/29/how-amazon-manages-its-delivery-routes-(and-how-to-copy-them) eventually led me to https://www.getstraightaway.com/blog-posts/who-has-the-best-delivery-route-planner-app-on-the-market-in-2020 in which the straightaway (app) vendor details competitor offerings.
I still have my Operations Research book that I used in 1985. I had vaguely remembered that we were taught to solve the “shortest distance” problem using matrices (and the book typically lists 7 nodes), but I’m guessing on the matrices. The chapter is Linear Programming: Networks. The preceding chapter is Linear Programming: Transportation, but I think that is more about moving goods. I didn’t read much but I saw multiple solution methods were provided and I see that “probabilities” were made part of the discussion (“she discovered that her shortest route was heavily patrolled by police”).
My thought is if you do not insist on getting the absolute optimal solution, as with the slime mold, you open the door to inventive algorithms. And given that the “shortest” (miles) route usually isn’t the best route anyway, there usually isn’t a perfect solution.
If you are a delivery person and you know most all the streets and the addressing in your designated area, then you would probably never exactly follow a computer generated travel route. You want to know about the few addresses you are unfamiliar with. It could be a good idea to see what the computer suggests for the whole route, but you probably know better for most of it.
The algorithm could probably be accomplished by dividing (all locations) into groups of relatively closely located destinations and solving the routing for those while determining the entry/exit points to another group. In other words, use “divide and conquer” instead of exhausting all possibilities. However, a linear solution is likely to be extremely complicated, and indeed you would want to include plenty of factors like road condition, time-of-day, weather, and events - and miscellaneous probabilites. It could be a great fun problem to get paid for.
That article was great, and worth reading just for the phrase “amoeba-based computing.”
Interesting! If I’d known what to search for, I probably could have solved my problem with one of the free tiers in the reviewed apps.
I’m having a lot of fun imagining an Amazon warehouse full of slime molds solving routing problems… And there’s the job description: “Employee will be responsible for the care and feeding of valuable slime molds used for biological computing.”
Curiously, when would you use MapQuest vs Apple Maps vs (gulp) Google vs (gulp) Waze? I usually know how to get to where I’m going, but will fire up a map app for rerouting around traffic related issues. However, when I’m traveling, like I am now - hello Hawaii!, I have no clue how to get around, so I rely on Apple Maps, while the wife prefers Waze. Today we’re going out to make a few different stops (Costco for gas, being the first), and then hitting a few different stores and towns. I’ll play with MapQuest, and see how it goes … Cheers!
Since we live in NYC and frequently travel around the Metro Area, we prefer different mapping apps for different purposes. WMMV.:
Waze has the best voice information about speed trap cameras. If someone reports it, Waze will notify you about traffic cop speed traps. Although Google owns Waze, they are not quite as good as Waze with the traffic camera info, even though they’ve had this feature for years. Speed trap alerts of any kind are relatively new to Apple Watch, so they are currently a distant third; at least they are here in the NY Metro.
If it’s a route we use frequently and know by heart, we prefer Apple Maps’ traffic info. If we are going somewhere that we’re not that familiar with, Google has better info for restaurants, fast food, gas stations, retailers, etc. along the route. Google does have links to reviews and does give wait times at some restaurants, but we’ve found them to be highly inaccurate; I recommend using them only if you are desperate.
A big plus for Apple Maps is how beautifully and seamlessly it works with Car Play, if you have it. My husband loves the haptic prompts he gets on his Watch, and gives it extra special points for how it reliably signals for regular and slight right or left turns. I don’t have a Watch, but he always praises the haptic feedback to the stars, especially when traveling to destinations we ‘re not familiar with. Google did add haptic feedback to their Maps, but it works sporadically, at least it does with the iPhone 8+s we both have.
And for both of us, privacy is a consideration. Google tracks us enough without using its mapping features. Directions for walking are about equal. Rapid transit info stinks equally on all three, but it stinks worse on Waze; at least it does in NYC metro area, but it does on all mapping apps…
Generally my default is to use Apple Maps. But there are times that the end point is not in Apple’s list but is in Google Maps, so I use Google then. This happened the other day, when I was going to a relatively new brewery to pick up beer. Unfortunately midway through the trip Google Maps stopped announcing turns and prompts (they mysteriously started working again a bit later), and the podcast app I was using also stopped playing. I could have looked up the address and used Apple Maps, and maybe that’s what I’ll do from now on. (I did generally know the directions - it was just the last bit I needed prompting with - so it was fine, though about twenty minutes of silence rather than listening to podcasts was a bit boring.)
Let’s not devolve into a discussion of Apple Maps and Google Maps. That can break out into a new topic if people want to revisit it.
The short answer to your question is that MapQuest’s app isn’t as good as either of them apart from the RoutePlanner feature. Stick with whichever of the other two you prefer for normal navigation.
I use a terrific app for planing vacations-but more important for mapping routes between several wineries each day. It is called Road Trip Planner. I use it on the Mac primarily, but it runs on the iPad and iPhone. It uses Apple Maps to work its magic. Check it out.
If you want a multi stop planner for touring, I highly recommend furkot https://trips.furkot.com/ which I use when touring in my VW campervan. It not only plots multi stops but also finds accommodation nearby and refuelling stops. I regularly take summer touring holidays around Europe and it’s great. Im currently sitting in a campsite in the Dordogne area of France on this summer’s tour.
Cant help but wonder if msft excel solver would work the basic problem
just my .00002 cents worth