pgr_trsp via mode should return each via route ID like v2.0 pgr_ksp(route ID) and pgr_kdijkstra(path ID)

[sanak]

I think that v2.1 pgr_trsp via mode should return pgr_costResult3 type like v2.0 pgr_ksp(route ID) and pgr_kdijkstra(path ID).

• pgr_trsp (v2.1): http://docs.pgrouting.org/v2.1.0-rc1/src/trsp/doc/index.html
• pgr_ksp (v2.0): http://docs.pgrouting.org/v2.1.0-rc1/src/ksp/doc/ksp_v2.html
• pgr_kdijkstra (v2.0): http://docs.pgrouting.org/v2.1.0-rc1/src/kdijkstra/doc/index.html

[woodbri]

I don't have a strong feeling one way or the other on this from an implementation point of view. I can see how having the route number to indicate which leg of the via's you are on might be helpful in some cases.

On the other hand, I'm not sure that we should delay the release to just make this change. I think @cvvergara will say that the vias are experimental and therefore subject to change in the next release. And I think the current implementation is based on a plpgsql wrapper and we have actual C++ implementation in github, that has not be fully integrated and test that is much faster because we only build the graph once than solve it multiple times.

[robe2]

Since we are already at RC1, it's politcally too late to change structure of outputs. In theory RCs are supposed to have only bug fixes,and serious ones at that. What a user tested with is what they expect to get in final. So I would agree with @woodbri that release should not be delayed for this and would make your RC designation of last tarball spurious.

[sanak]

@woodbri, @robe2
Okay, thanks for answer,
and sorry for too late notification...
I will change title and remove 2.1 milestone.

By the way, I have one more question.
Is there some plan to change via mode return type at next version 2.2 ?
(For example, don't use pgr_costResult, but use direct columns like new pgr_dijkstra/pgr_ksp/pgr_drivingDistance.)

[sanak]

@cvvergara
Okay, thanks for confirmation about return type !

[sanak]

To add route ID as one of result columns, via edge mode should return "segmented" result.
http://docs.pgrouting.org/v2.1.0-rc1/src/trsp/doc/index.html#examples
Also, current duplicated result seq values may cause some trouble.

select * from pgr_trsp(
    'select id, source::integer, target::integer,cost,
         reverse_cost from edge_table',
    ARRAY[1,11,6]::integer[],           -- array of eids
    ARRAY[0.5, 0.5, 0.5]::float8[],     -- array of pcts
    true,
    true);

Before

 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |  0.5
   1 |   2 |   4 |    1
   2 |   5 |   8 |    1
   3 |   6 |  11 |    1
   1 |  11 |  13 |    1
   2 |  12 |  15 |    1
   3 |   9 |   9 |    1
   4 |   6 |   8 |    1
   5 |   5 |   7 |    1
   6 |   8 |   6 |  0.5
(10 rows)

After (assume id1=route ID, id2=node ID, id3=edge ID)

 seq | id1 | id2 | id3 | cost
-----+-----+-----+-----+------
   0 |   0 |  -1 |   1 |  0.5
   1 |   0 |   2 |   4 |    1
   2 |   0 |   5 |   8 |    1
   3 |   0 |   6 |  11 |  0.5
   4 |   1 |  -1 |  11 |  0.5
   5 |   1 |  11 |  13 |    1
   6 |   1 |  12 |  15 |    1
   7 |   1 |   9 |   9 |    1
   8 |   1 |   6 |   8 |    1
   9 |   1 |   5 |   7 |    1
  10 |   1 |   8 |   6 |  0.5
(11 rows)

[sanak]

I fixed this issue temporarily on my pgrouting4w repository's develop_issue392 branch.
sanak@5f7bfbb
If there will be an intermediate release before v2.2(or v3.0?), the commit may be useful.
(One of our customer needs this via edge function by this September, so I may use above routing_trsp_via.sql with renaming function name like pgr_trsp to pgr_trsp2 .etc.)

[cvvergara]

@sanak
I think we can always do a 2.1.1 (no need of alpha, beta, etc)
and I like the idea of a different name (I am not used to American acronyms).
the one you have make it such that has the meaningful return name columns.
Here is a motivation for different name.
TSP is a known Acronym for Traveling Salesman Problem, and TRSP migth lead people to think that is "Traveling Restricted Salesman Problem" which is not.
So as it is based on Dijkstra (So it says in the documentation) what about:
pgr_DijkstraWithTrunRestrictions?

[cvvergara]

@sanak
I am starting to change my mind, about the new name thing for 2.1.1 (not for 3.0).
because for 3.0:

1. support ANY-INTEGER for id's
2. support ANY_NUMERICAL for cost

[sanak]

@cvvergara
Okay, thanks for confirmation.

About the naming, I prefer TRSP than long name. :-)
(pgr_trsp page ranking is top by searching "turn restricted shortest path" on Google. :-))
https://www.google.co.jp/?gws_rd=ssl#q=turn+restricted+shortest+path

By the way, this is just my question, but are you planning to replace current TRSP internal Dijkstra logic to Boost.Graph one at next version ?

[woodbri]

I think that it would be a good idea to replace the internal logic of TRSP with Boost graph logic. The only reason that it was not using Boost graph was because the GSoC student that developed it was not familiar with Boost so we went with the path of least resistance to get the job done.

In fact it might make more sense to add turn restriction support to the core libraries so all the code the uses them can optionally be run with or without turn restrictions. We have gotten requests for turn restriction support in kdijkstra and ksp also. Then trsp becomes obsolete because all the dijkstra family of functions support restrictions.

[sanak]

@woodbri
Thanks for comment.
I think that combination idea (kdijkstra, ksp, drivingDistance .etc) is quite good, too.

[cvvergara]

As for a plan:
first:
A dijkstra via Points (no turn restrictions involved)
This can be done "fast" as the dijkstra is already using boost and the new library structure.

Then, about the
dijkstra with restrictions aka TRSP
-- a lot has to be done.
-- Its a complete re-factoring of the code.

[woodbri]

I agree, it is a lot of work. I think I have an idea of how to do it conceptually, but without the specific knowledge of how to do it with boost. The idea is this:

Given a visitor at a node being evaluated in the Dijkstra algorithm, we have a list of potential candidates that we can go to from this node. We can eliminate nodes from the potential list based on turn restrictions if the target node has a list of restrictions and the restriction list matches the path that got us to the current node. For example, our current path to node G, is A-B-C-D-E-F-G and at node G we have the option to go to any of nodes H,I,J. Node H has a restriction list E-F-G-H, meaning that if your path passed through the sequence of nodes E-F-G then you may NOT go to H (ie: that path is restricted), but you can still go to I or J provided they are not also restricted. So given you are at node G, the parent node in the path is F and that parents node is E, etc. Another variation might be a path A-B-C-D-EE-FF-G so we approach G from a different path and G still has H,I,J as potential nodes to go to. In this case if H does not explicitly have this path in its list of restrictions, then it would allow continuation to H.

[cvvergara]

We can eliminate nodes <--- Not easy
For ksp:
instead of eliminating nodes I disconnected the node completly (eliminating edges is easy in boost, but not nodes)

Also, there are 5 places where to put a visitor algorithm in boost::dijkstra.

[cvvergara]

Eliminate a node is O(size of nodes) eliminate an edge is O(1)
restore a node is O(size of nodes) restore an edge is O(1)

[woodbri]

Well, that may be the case, but we do not need to eliminate the node, in fact we do not want to eliminate the node because there might be other valid paths that need that node. What we are doing it the visitor is selecting the next node to evaluate in the path. Think about A-Star we use a visitor to select the node based on a heuristic, In this case we just block the path path from continuing on to that node because it is restricted based on the path that got us to that node. But we might come to that node via another path and then the next node is not blocked.

[cvvergara]

@woodbri
What if, we tag this as discussion, (aka a good place to start discussing on idea on how you want to implement it using boost)
what's needed in the general library, etc.

[cvvergara]

So far, deleting and inserting edges is already in the general library.

[cvvergara]

Lots of comnents about trsp are located in the wrong issue list
pgRouting/pgRoutingLayer#4

[cvvergara]

improvements or changes on TRSP are not done yet

[cvvergara]

Work has been done for TRSP on develop branch for version 3.4 (due to be released on September/October 2022:
#2238
Please check the documentation
https://docs.pgrouting.org/dev/en/TRSP-family.html
and the migration guide:
https://docs.pgrouting.org/dev/en/trsp_migration.html

For further similar problems with TRSP functions please open a new issue with the specific function name.