Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

Together with a collegue we're thinking about solutions, but we would appreciate it if you could give feedback on this interesting challenge. Now we are thinking about calculating midpoints for every road section and use those as destinations to calculate the route. If someone has better suggestions, please share!

Cheers,

Mark

share|improve this question
2  
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 '13 at 12:38
    
Very true. Do you have tips on solving this kind of routing questions? –  Mark Verschuur Jul 18 '13 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 –  dassouki Oct 17 '13 at 14:52
    
It can be reduced to multiple vehicle pickup and delivery problem and there are plenty of papers on that. –  Jakub Kania Oct 17 '13 at 18:31
    
Related: gis.stackexchange.com/questions/99886/… –  Chris W Nov 21 at 22:48

2 Answers 2

up vote 3 down vote accepted
+50

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 (http://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.

share|improve this answer

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.

share|improve this answer
    
Thanks for the suggestions. I will definately check out RouteSmart –  Mark Verschuur Oct 23 '13 at 6:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.