Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Lightaphyre]

Hello...

Years ago (probably over a decade) someone was on one of these road-fan boards who worked for a mapping company, and if my vague recollection serves me correctly, I think I am now coincidentally working for the same people. So, my task during the day requires driver self-navigation. Because we are inputting into proprietary software in order to aid the application's later use for navigation by others, I need a solution for my own personal navigation of the route assigned to me during my day. Believe it or not, our company does not have voice guidance directions in our equipment, we just happen to drive super fancy custom versions of average little cars.

To give the best comparable analogy, I am faced with what almost amounts to a paper map with highlighted roads *everywhere* that I absolutely must traverse, while very often including almost every adjacent road in its vicinity, in the meanwhile. My goal is to calculate the best way to navigate these plots, if you will... while completing as many roads (viewing as many streets *ahem*), as is possible with as few cases of doubling back and overlapping as we can theoretically muster. Keep in mind, entering addresses is not possible, I must simply achieve stretches of pavement (to include all freeway ramps.)

The job has been great but as I begin the second year of work, I am just trying to figure out how to make it easier. I almost wish I could take a picture of the map plot and input it to an application and have that program say, ok cool turn left and right and circle back here.

[NWI_Irish96]

So, what you're having to do for work sounds similar to one of my clinching trips. I draw out a graph with vertices being route intersections and the segments being road segments, with solid lines representing segments I need to travel and dashed lines representing segments that I don't need to travel but might use to get between segments that I do need to travel.

Then I simply draw the route that covers every solid line with the minimal amount of backtracking/duplication. It may take a bit of trial and error to get it for more complex networks.

It helps that I took a graduate level graph theory class and have experience optimizing routings, but really anybody can do it with a little bit of practice. One thing it doesn't account for is urban vs rural segments and which costs more time to duplicate, but it gets you pretty close to if not exactly on the most efficient route.