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

Question

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:

• vehicles start and stop at a single loading point
• 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.

Answer 1

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.

Answer 2

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.