Discussion on coding turn restrictions using Boost
Maintainers usually reply within 3 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 30/100
Research direction
The issue discusses re-implementing pgr_trsp functionality using Boost Graph to handle turn restrictions/penalties. Start by reading the linked Boost mailing list and pgrouting-dev archives to understand the challenges. Examine the existing pgr_trsp code and the referenced external projects (itn-for-pgrouting, Tempus) for approaches. The goal is a design for integrating turn penalties into the routing graph, which requires significant graph algorithm and C++ expertise.
Written by the indexing model from the issue text.
Description
The current pgr_trsp function does not use Boost in its underlying implementation, in part because Boost Graph does not support it natively. There has been some discussion about re-implementing the pgr_trsp like functionality using Boost Graph. I'm opening this issue to collect ideas and references regarding this.
- http://lists.boost.org/boost-users/2011/11/71549.php
- https://lists.osgeo.org/pipermail/pgrouting-dev/2011-May/000208.html
- https://github.com/mixedbredie/itn-for-pgrouting (extracting turn-restrictions for OS data)
- https://github.com/Ifsttar/Tempus/blob/master/src/core/road_graph.hh (routing supporting turn restrictions)
- https://groups.google.com/forum/#!topic/opentripplanner-dev/hrsa7V0OSKY (interesting discussion)
There are also two terms that I have come across in this research "turn-penalties" and "turn-restrictions". An infinite penalty can be considered a restriction. From an implementation point of view having penalties is probably preferable because applying a penalty allows you more flexibility like applying a cost to making a turn or applying a greater cost to make a turn across traffic, or at traffic lights ot stop signs, etc.
In my mind "turn-restrictions" could be viewed as dynamic modification to the graph, based on the first link above this might be problematic, while changing the costs to a particular node based on the path to get there might be less problematic.
Please add additional useful comments and research.
- Dominant language
- C++
- Stars
- 1.4k
- Forks
- 397
- Avg merge
- 2d 16h
- Merged PRs (30d)
- 8
Getting set up
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from pgRouting/pgrouting
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
Maintainers usually reply within 3 days
-
Administrative Enhancement
Difficulty 1/5 Under an hour Newbie friendliness 80/100
Maintainers usually reply within 3 days
-
points_input Developers docPossibly taken @withaman69 claimed this 101 days ago. OpenC/C++ Developers Doc. good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
pgRouting/pgrouting#973 · 10 comments ·
Maintainers usually reply within 3 days
-
get_check_data developers docPossibly taken @withaman69 claimed this 102 days ago. OpenC/C++ Developers Doc. good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
pgRouting/pgrouting#972 · 7 comments ·
Maintainers usually reply within 3 days
All issues in pgRouting/pgrouting
Similar issues
-
std::fdim drops partial derivative w.r.t second argument in forward and reverse modePossibly taken @ADITYASINGH1206 claimed this today. Open
Difficulty 1/5 Under an hour Newbie friendliness 85/100
vgvassilev/clad#2534 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
Maintainers usually reply within 1 day
-
HAP.cpp fixOpen
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
KLayout/klayout#2554 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day