Shortest path-planning in road nets with forbidden routes (Q2757738)

This thesis investigates the following problem: given a directed graph \(G=(V,E)\) with every edge \(e\in E\) having a length, a source vertex \(s\), and destination vertex \(t\), find the shortest path from \(s\) to \(t\) subject to a given set of turn prohibitions or path prohibitions. A path prohibition is a specified path in \(G\) that may not appear as a subpath in the path between \(s\) and \(t\); a turn prohibition is a path prohibition of length two; i.e., two successive edges in \(E\) that may not appear in a row in the path. NEWLINENEWLINENEWLINEThe problem is motivated from route planning for cars; turn prohibitions express that at certain corners, a car is forbidden to turn left or right. The thesis also gives concrete examples where a path prohibition involving more than two edges appear in the route planning application. NEWLINENEWLINENEWLINEThe thesis reviews some shortest paths algorithms. Its main result is a modelling of turn and path prohibitions in the graph, showing that either the graph or the shortest path algorithm can be modified such that the optimal route with respect to the prohibitions can be found. The thesis also discusses some implementation aspects.