Try MapQuest for Many-Stop Route Planning

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 :slight_smile:

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. :slight_smile:

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!!” :slight_smile:

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:

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…

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.” :slight_smile:

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.)