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

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.