How to calculate the shortest route when running every road in town?

Question

As a fundraiser, a coworker is looking to run every publicly-accessible street in his hometown. Given the street data and the Network Analyst extension, I think I can help him calculate the shortest route to do so, but I am not entirely certain how. Does anyone have thoughts on how to calculate his route using GIS?

JaySandhu · Answer

A solution to optimally visit ALL edges in a network falls under a class of problems called arc routing, also known as Chinese Postman or an Euler tour. Network Analyst does not provide a solution for that class of problems. BUT it can provide a solution to best visit a set of points, also called a travelling salesman problem (TSP). So you could place a point on edge and optimize it. But there are many caveats to using a TSP solution for all edges in a city. How big is the town? How many road segments does it have? How much miles does your friend want to run at a time? You will likely have to partition the town into smaller regions and solve these separately.

An easy way to place a point on every edge is to use the GP tool Feature To Point and checking the "inside" option. This will place a point at the center of each line. Then you can use Network Analyst solver Location-Allocation to "partition" these points into clusters of say 300 points (maximize capacitated coverage problem type in location-allocation). Then you can load these sets of 300 points into the Route solver and choose the Reorder stops to find optimal route option. Couple of things you can do to improve the solution is to set the curb approach property of all the points you load in as Stops with No U-Turn. and set u-turns at dead ends only. You can also turn off restrictions as one-way as a runner can disregard that!

Hope this gives you enough information to set up a running route! More info on Route and Location-Allocation here:

Route analysis—Help | ArcGIS for Desktop

Location-allocation analysis—Help | ArcGIS for Desktop

DanPatterson_Retired · Answer

shortest route normally implies an origin and a destination or destinations.  By chance would the sum of the road lengths provide the same information?  The data returned would be one of, if your friend ran every road in town, how far would the total distance be.  If you have to go from point A to point B, potentially along different roads which form the shortest path, then that is a different question.