Recalculate shortest path if previously calculated path has an Impedance

[srividya-p]

Firstly, kudos for making such a great Plugin! I am using the Shortest Path Algorithm in the Routing section to find the shortest path between two points and the feature which accounts for points outside the network has helped me greatly!

However, Is there some way to exclude a path from consideration while finding Shortest Path?

For instance this is the shortest path calculated by QNEAT3

Now if the User decides that this path is not suitable (Say there is a block on the road), How can I recalculate a new shortest path by ignoring this particular path? Or in terms of Graph Theory, If there is an impedance on that edge the algorithm should ignore that edge and find the next shortest path.

This is the code I have written for finding the Shortest path -

def shortest_path(self):
        roads_layer = QgsProject.instance().mapLayersByName('Roads')[0]
        params = {
            'INPUT':roads_layer,
            'START_POINT':'{},{}'.format(self.origin_coords[0], self.origin_coords[1]),
            'END_POINT':'{},{}'.format(self.destination_coords[0], self.destination_coords[1]),
            'STRATEGY':0,
            'ENTRY_COST_CALCULATION_METHOD':0,
            'DIRECTION_FIELD':'SUMMARYDIR',
            'VALUE_BOTH':'',
            'DEFAULT_DIRECTION':2,
            'SPEED_FIELD':None,
            'DEFAULT_SPEED':5,
            'TOLERANCE':0,
            'OUTPUT':'memory:Shortest Path'
        }

        route_layer = processing.run("qneat3:shortestpathpointtopoint", params)['OUTPUT']
        route_layer.renderer().symbol().setColor(QColor("#17137c"))
        route_layer.renderer().symbol().setWidth(0.86)
        route_layer.triggerRepaint()

        QgsProject.instance().addMapLayer(route_layer)

Where origin_coords and destination_coords are QgsPointXY objects.

I have been struggling for a pretty long time with this task and any kind of help or insights will be greatly appreciated!

[root676]

Thanks for your message! You just worked out the solution to your problem all by yourself. :wink:

Is there some way to exclude a path from consideration while finding Shortest Path?

By definition this is not possible in network analysis. This would imply that the path that has been found is not the "shortest" in terms of routing costs. In this case you have to update the cost set on your edges (eg. impedance) you are working with. There are two ways of solving this (the first one you mentioned yourself):

1. Run the graph analysis with an adapted streetgraph (eg. don't include the edges that are causing the shortest paths in your input graphy) by running a query on the layer.
2. Choose to work with the time based routing and apply a negative or 0 speed to the edges you want to exclude from analysis.

I hope this helps!

[srividya-p]

Thank you very much for your insights! I considered both the solutions,

I did not find the first one feasible in my case because the Road Network I am using is very dense and has over 40000 features. (There probably is an efficient way of implementing this but I did not look into it further :sweat_smile:)

2. Choose to work with the time based routing and apply a negative or 0 speed to the edges you want to exclude from analysis.

The second one however worked like a charm! I added a maxspeed attribute to all features of the Road Network with a default value of 5 and used it as the SPEED_FIELD in the INPUT parameters while running the algorithm with Time Optimisation. Each time a new Shortest Path is found I set the maxspeed of the corresponding Road Network feature to 0 and Recalculate the Shortest Path.

Here is a screenshot of the Output:

If someone needs it, the code for this solution can be found here.

Thank you once again for your timely response, My doubts have been resolved!

[root676]

Glad I could help. 😉