Originally published at: Try MapQuest for Many-Stop Route Planning - TidBITS
Faced with a need to drive to as many as 43 different spots in the same trip, Adam Engst found a mapping solution that calculated the optimal route and provided stop-by-stop voice navigation on the iPhone.
3 Likes
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 !
2 Likes
Same for me! And it sure beats having to type addresses in after every stop.
1 Like
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.
3 Likes
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. :-)
5 Likes
Makes me wonder how outfits like Amazon, UPS, FedEx et al. solve the same problem every day?
1 Like
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!!ā :-)
1 Like
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.
5 Likes
Amazon is particularly focused on continually upgrading its delivery route planning app, The Rabbit, which works within Amazon Flex:
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ā¦
4 Likes
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.
1 Like
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.
1 Like
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.ā
3 Likes
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ā¦
2 Likes
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.)