How does the Google Streetview driver decide what path he will take to get the most coverage with the least repetition?

January 14, 2009 2:10 PM

I have a task where I have a bunch of streets that I need to drive on, (but not all streets like StreetView) and I would like to know how is the best method to accomplish this while limiting the amount of extra un-needed driving?

I have poked about into the "Travelling Salesman Problem" and it is geared towards travelling to different "cities or points" not paths or streets.

I also have thought about doing a "zigzag" where I start at the north west corner of the map and travel east on the northernmost street and then go south at the end of that street until I get to the next east-west street and go west until I get to the westernmost part of the street and then go south again... rinse repeat,
and then do it again but at a 90 degree rotation so now my primary direction of travel is north/south and i use the east-west streets to move over one street again...

That sounds so much more complicated than it really is...

Its more like... Go west until you are done with the street. Now go down one block and go East until you are done with that street. Now go down another block and go west until you are done...

Where this gets problematic is when you have weird layouts in your city like angled streets or circular neighborhoods or big blocks taken out of your map like for airports or schools.

Any suggestions or research material I could look at?

Thank you

posted by farmersckn to grab bag (8 comments total)

Well, if the streets you needed to drive along constituted an Eulerian graph—that is, every intersection involved was the intersection of an even number of streets that you needed to drive on—you could do it without any extraneous driving by following an Eulerian circuit. Or an Eulerian path, if you had exactly two intersections with an odd number of streets, and you didn't need to start and stop at the same point. (Note: a dead end counts as the "intersection" of one street.)

This is unlikely to be the case; you probably have a bunch of intersections where an odd number of streets you need to traverse meet. Get a map of the area you need to cover, and mark all such intersections. Now, pair up those odd intersections in such a way that the total driving distance between the paired intersections is minimized. (This is the hard part, but if the number is small enough, you may be able to brute-force it. Or you may be able to eyeball it if you don't absolutely need the best possible route but merely a pretty good one.) The routes between those pairs of intersections are the streets you'll be driving on twice—you've now converted your non-Eulerian graph to a Eulerian one by doubling some of the routes, in a way that minimizes the total distance.
posted by DevilsAdvocate at 2:35 PM on January 14

I'd load the data into ArcMap and fiddle around with the network analyst extension...

Not trying to be flip, but people do actually study precisely this sort of logistics/mobility problem, in both urban and undeveloped areas. ESRI's (blow-your-hair-back-expensive) software package is the industry standard.
posted by Emperor SnooKloze at 5:45 PM on January 14

Saving distance I don't know, but using right turns (left in Europe) saves time.
posted by gjc at 6:55 PM on January 14

Yeah, people like UPS and FedEx spend a fair amount of money/effort/software on this problem.

I'm not sure what sort of answer you're looking for, farmersckn— do you have a one-off instance of this problem you need to solve, or a recurring need, or do you want to understand the theory behind its solution, or what?
posted by hattifattener at 7:50 PM on January 14

I currently just have a hand drawn map of streets that I need to drive and want something fairly easy to figure out while I"m driving (like... always make a right turn if you come to an intersection and the street you turn onto hasn't been driven yet). I need to drive this group of streets in the next 2 weeks so writing a program to draw a map for me is out of the question... however I do want to know the theory behind this... I have toyed with the idea of making a google maps mashup that does this sort of thing for the average joe who has a bunch of stops to make and just wants to quickly find the shortest path (that for sure is Traveling Salesman).

Thanks for the replies I am going to look up the info on Euler's graphs and also ArcMap.
posted by farmersckn at 9:16 PM on January 14

The problem you're looking at is very similar to that of traversing a maze.

The "right hand rule" that you propose (analogous in a maze to "always keep your right hand on the wall and just keep going) may actually be a fairly good bet. The advantage is making right turns at intersections does actually speed up your trip some. The potential downside is this: The right-hand rule only "works" for certain types of configurations (known as "perfect" mazes, see the Wiki article I linked above).

This may be no big deal as your route may well resolve into 3 or 4 perfect mazes meaning you just need to transfer and start over with the right-hand scheme 2 or 3 times. OTOH if your route includes all the streets in, say, certain sections of a city your network will look a lot like a grid and that won't work well with the RH rule (basically every city block interior to your area will require the reset/reposition thing).

However the Wiki article on Mazes has what I think is your solution:

Tremaux's algorithm
Tremaux's algorithm is an efficient method to find the way out of a maze that requires drawing a line on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages. On arriving at a junction, pick a direction and mark it and the direction you came from. When arriving at a marked junction pick an unmarked passage if possible. If it is not possible to pick an unmarked passage take a marked one, marking it again (you can pick the path you came from). Never pick a twice marked path, where you will never need to take any passage more than twice. If there is no exit, this method will take you back to the start.

Obviously you don't have to mark directly on the street, you could just keep track of things on a map (or maybe you have a really good memory . . . ).

For driving, you could preferentially choose right turns over straight, straight over left turns, and left turns over u-turns whenever you have the choice, because that minimizes your wait time at intersections.

Tremaux's algorithm will take you around the entire maze eventually and at least at reasonable efficiency (traversing each street segment twice at most--you could do a lot worse). If you add some common sense heuristics (ie, try to cover all streets in a general area before leaving it--so you don't to make a long drive back just to catch one or two little segments; in the cases where you have a choice of directions, you will probably be able to choose the "best" direction to take, based on common sense factors, rather than just picking one at random) it will likely be both simple and very close to the best reasonable solution.

BTW this is indeed just a form of the traveling salesman problem (model it as traveling salesman with one destination on each block or street segment you need to visit). One take-home from the last few centuries/millenia working on that problem, is that there is one single "best" solution, but (for a problem of reasonable size, say a couple dozen stops or more) you'll never find it so just stop trying to find "the best" solution and be satisfied with "a good" solution.

Once you've found a reasonably good solution you're 80% or 90% of the way there. You can waste a lot of time & resources modeling the problem, trying different combinations, writing a computer program, etc. and the result will be (something like) to move from a solution that is 80% as good as the ideal to 82%.

That's worth it for an outfit like UPS that spends millions on fuel. But for your personal project, just find a decently good solution, which something like Tremaux will be, and then don't worry about it.
posted by flug at 11:03 AM on January 15

If you can think of this as a farmer plowing a field you might find it easiest (not necessarily the most efficient) to start in the middle and circle right at the ends. Just a thought.
posted by ptm at 3:27 AM on January 16

"Tremaux's algorithm is an efficient method to find the way out of a maze"

Also I should mention that although you are not "trying to find your way out of a maze" the problem Tremaux's algorithm solves is the same as yours.

How Tremaux's algorithm works is by (eventually) traversing every portion of the maze in an efficient way. So following the same process you'll be able to traverse all streets, which is your goal.
posted by flug at 11:11 AM on January 16