[GIS] How to automatically generate a route between locations

qgisroute

I need to create a route between 70-80 different locations or points in a map, I would like something a la google map, I select my origin and destination and it automatically generates a route between the points

I can't use google maps because it has a limit of 10 destinations per route. And so far I haven't been able to do it with QGIS. Is there any plug-in or way to do what I need?

Best Answer

OSM Tools:

My recommendation would be to use OSM tools for QGIS which you can download as a plugin. OSM tools was created by Nils Rode and is an adaptation of the OSMroute plugin which uses the OpenRouteService API.

Simply download the plugin and request an API key, once you have this you simply use the routing tab (the other tab is for accessibility e.g. isochrones). You can either pick a coordinate from the map or use point shapefiles for your start and end locations.

I believe it limits you to 40 routes per minute and 500 a day, so you may have to split your dataset in two.

pgRouting:

If you are comfortable using PostGIS then the pgRouting is a great extension which can be run behind QGIS and then brought in. This has a wide array of functionality. There is a plugin for QGIS but I believe it is fairly basic at the moment.

Related Solutions

ArcGIS Network Analyst – Calculating Optimal Routes While Touching All Available Roads

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.

Best Answer

Related Solutions

ArcGIS Network Analyst – Calculating Optimal Routes While Touching All Available Roads

Related Question