Calculating optimal routes while touching all available roads in ArcGIS network?

For preperation of the winter season we want to calculate the most optimal routes for sprinkling salt on the roads. The analysis knows the following criteria:

• all available roads need to be sprinkled with salt
• one route can take no longer than a certin time (lets assume 2 hours)
• because of the limited load of salt per vehicle, the distance of a route is limited to the amount of salt available. (lets assume 10 km)

Network analyst of ArcGIS (10.0) assumes you have a start- and an endpoint to calculate the route. However, in this case it is not about calculating the fastest route from origin to destination, but about the most optimal routes to cover as much road distance as possible within a limited time frame.

Now we are thinking about calculating midpoints for every road section and use those as destinations to calculate the route.

• This sounds a lot like garbage truck routing only there trucks return to depot to empty while here salt gets re-loaded. Both need to visit all parts of a network.
– PolyGeo
Jul 18, 2013 at 12:38
• Very true. Do you have tips on solving this kind of routing questions? Jul 18, 2013 at 13:18
• In our jurisdiction we have an additional variable, which is Sand. since lower volume roads get sand, and higher volume ones get Salt. If you want start up a chat room with me and we can discuss the problem fully. I can also give you some insight on what we've done and if our solutions can compare Oct 17, 2013 at 14:52
• It can be reduced to multiple vehicle pickup and delivery problem and there are plenty of papers on that. Oct 17, 2013 at 18:31
• Nov 21, 2014 at 22:48

I think some of the answer depends on the layout of the road network, and this question might be worth posting on the Math Stack Exchange (https://math.stackexchange.com/) as it seems like a graph theory problem. I don't think this will be the optimal solution, but it might help get you closer.

You could divide up the road network into natural regions, where the sum of the length of the segments will be roughly equal to the amount that a truck could cover with a given load. Then for each region you could run a eularian tour to get the route that would touch all of the segments. Sample python code

``````def eulerian_tour(network_graph):
graph = network_graph[:]
route = []
def find_route(start):
for (i, j) in graph:
if i == start:
graph.remove((i, j))
find_route(j)
elif j == start:
graph.remove((i, j))
find_route(i)
route.append(start)

find_route(graph[0][0])
route.reverse()
return route
``````

You might then consider routing between regions and the depot, and break up the access route into logical segments for the trucks available. Hope this helps.

I would approach this task this way. ArcGIS Network Analyst has a solver called VRP, which can help you to order and manage your routes. I would convert each road link you have in your network dataset to point features (Feature To Point (Data Management) GP tool, for instance, or maybe first splitting lines to simple two-vertex segments and then get a middle to become a center point).

Speaking in terms of VRP, those will become your orders. Then you assign your routes limiting them to a certain time (2 hours), and your depot place will be both start and stop point. Assuming you have multiple vehicles, you will be able to get either multiple routes for one vehicle or multiple routes for the same vehicle.

I strongly recommend going through tutorial which will help you understand how to get started with VRP in Network Analyst. I have used this solver for multiple projets myself and found it to be extremely powerful and customizable to a very large extent to meet my business workflow.

Remember that Network Analyst would work well with a limited number of input orders (in your case - centroid of roads). I was successful with several thousands orders (up to 9,000). So if you want to serve a really large city, you might limit your routes to operate only within certain city parts (in terms of VRP - Route Zones).

If you are looking for a more out-of-the-box and powerful solution that was designed specifically for high-density point routing, please consider using RouteSmart. It is built on top of ArcGIS and was engineered to solve this type of problems.

• Thanks for the suggestions. I will definately check out RouteSmart Oct 23, 2013 at 6:40