[SoC] Final Report (Week 12) - Rewrite of Turn Restricted Shortest Path Algorithm in pgRouting

[vidhan jain]

Hi everyone,


1) TITLE

   Rewrite of Turn Restricted Shortest Path Algorithm in PgRouting

2) SOFTWARE COMMUNITY

   PgRouting, under OSGeo.


3) ABSTRACT

   In graph theory, the shortest path problem is the problem of finding a
path between two vertices (or nodes) in a graph such that the sum of the
weights of its constituent edges is minimized. In real life scenario, the
road network is modeled as a graph where the graph's vertices correspond to
road junctions and the edges correspond to road segments, each weighted by
the positive length of its road segment.

   A turn models a movement from one edge element to another. Often in the
real world scenario, turn restrictions such as no-left-turn, no-right-turn etc.
are imposed on the road network.

   The aim of the project was to come up with a solution for calculating
the shortest path from a given source node to a destination node in the
graph containing turn restrictions.


4) STATE BEFORE

   TRSP is implemented in PgRouting but the code has issues which are not
fixed as yet.

   Wrappers are added to the codebase that enhance the functionality of
TRSP but fail to fix the issues. The following functionality is added
through the use of wrappers:-

   -

   pgr_dijkstraTRSP(one to one) (aka pgr_trsp)
   -

   pgr_withPointsTRSP(one to one) (aka pgr_trsp)
   -

   pgr_dijkstraViaTRSP() (aka pgr_trspViaVertices)
   -

   pgr_withPointsViaTRSP() (aka pgr_trspViaEdges)

   Here
<https://github.com/pgRouting/pgrouting/wiki/Notes-on-pgr_trsp--(2.3.2-release)>
is the link to a wiki page that describes the issues associated with the
current implementation of the pgr_trsp code in PgRouting.


5) THE ADDITION

Pgr_dijkstraTRSP:

   -

   Implemented code that works when the resultant path from source to
   destination does not pass through restricted edges.


   -

   Some tests  for the pgr_dijkstraTRSP for the working case have been done.
   -

   Some documentation has been done.



Pgr_lineGraph:

   -

   Implemented code for pgr_lineGraph for unweighted graphs
   -

   This functionality is to be used by the pgr_dijkstraTRSP.
   -

   Finished the user’s documentation
   -

   Finished the basic tests.


6) PENDING WORK


   -

   Pgr_lineGraphWeighted needs to be implemented.
   -

   Dijkstra algorithm needs to be applied on the weighted line graph.
   -

   The above functions need to be incorporated to pgr_dijstraTRSP to
   process the paths when they pass through a restriction.



7) LINKS


   1.

   Pull request with all the commits:
   https://github.com/pgRouting/pgrouting/pull/910
   2.

   Wiki Page:
   https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP
   3.

   Diff changes:
   https://github.com/vidhan13j07/GSOC17-RewriteTRSP/blob/master/contributions.diff
   4.

   Documentation: http://docs.pgrouting.org/2.5/en/pgr_lineGraph.html
   5.

   Slides:
   https://docs.google.com/presentation/d/1TTSvKvF-a6P1WD_Aezc541vUHsoCUAQXMOfnBX3orcU/edit?usp=sharing


Best Regards,
Vidhan Jain
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20170823/0cb5097c/attachment-0001.html>