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:

• 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

I think some of the answer depends on the layout of the road network, and this question might be worth posting on the Math (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.