[pgrouting-users] Problem using TRSP
Stephen Woodbridge
woodbri at swoodbridge.com
Thu Aug 30 08:36:17 PDT 2012
The important part is to do the test with no turn restrictions because
dijkstra and astar do not do restrictions. So if the route is bad
without any restrictions then we need to look into what is happening
there. Also remember the TRSP depending on how it is called also looks
at the direction of the start and end segments and computes a partial
length along those segments which the other algorithms do not do and
that can impact the results if two routes are close to the same length.
It would really be great if you can do some testing and report your results.
Thanks,
-Steve
On 8/30/2012 11:27 AM, Christy Nieman wrote:
> I'll see if I can come up with a simple test case that demonstrates
> this. I think it's taking the "wrong" route, but it may possibly be a
> route of lower cost than the other two algorithms are using. I'll look
> into that too.
>
> Christy
>
> On 08/30/2012 11:22 AM, Stephen Woodbridge wrote:
>> On 8/30/2012 11:08 AM, Christy Nieman wrote:
>>> All,
>>>
>>> I'd just like to note that I have noticed this too, and it only seems to
>>> happen for me if I'm not using a directed graph (e.g. reverse_cost and
>>> the two booleans to true).
>>
>> Tao, make sure you try your graph with a directed graph.
>>
>>> TRSP also seems to not calculate the same routes as A-Star or Dijkstra
>>> if not using a directed graph.
>>
>> It is possible that there are multiple paths with the same length, in
>> which case the result will vary depending on the algorithm sets up the
>> queue. If you are say that it is compute the "wrong" route as in there
>> is a shorter route if you are not applying restriction. then you
>> should probably create a simple test case and fill it with a bug so we
>> can look into it.
>>
>> -Steve
>>
>>> Christy
>>>
>>> On 08/30/2012 07:32 AM, Tao Romera Martinez wrote:
>>>> Can you think of anything I could try to find the source of the
>>>> problem?
>>>>
>>>> 2012/8/24 Tao Romera Martinez <taoromera at gmail.com>:
>>>>> Sorry, Stephen, this did not fix the problem. I still have 0 in the
>>>>> cost column.
>>>>>
>>>>> 2012/8/23 Stephen Woodbridge <woodbri at swoodbridge.com>:
>>>>>> Try renaming column "cost" and see if the fixes it.
>>>>>>
>>>>>> alter table japan rename column cost to old_cost;
>>>>>>
>>>>>> Let us know if this fixes the problem, because it means we have a
>>>>>> bug.
>>>>>>
>>>>>> You can rename the column back the way it was with:
>>>>>>
>>>>>> alter table japan rename column old_cost to cost;
>>>>>>
>>>>>> Thanks,
>>>>>> -Steve
>>>>>>
>>>>>>
>>>>>> On 8/23/2012 2:06 AM, Tao Romera Martinez wrote:
>>>>>>> Hello Stephen,
>>>>>>>
>>>>>>> Thank you very much for your quick answer.
>>>>>>> The query you asked to me to run gives some rows with cost_car=0,
>>>>>>> but
>>>>>>> none of them is in the list of edges returned by
>>>>>>> turn_restrict_shortest_path.
>>>>>>> Here is the query result with the cost_car for each edge:
>>>>>>>
>>>>>>> vertex_id | edge_id | cost | cost_car
>>>>>>> -----------+---------+-------------------------------------
>>>>>>> 284867 | 211472 | 0 | 0.07751676
>>>>>>> 284794 | 211471 | 0 | 0.2359118
>>>>>>> 134058 | 205895 | 0.15 | 0.14653888
>>>>>>> 284826 | 205894 | 0 | 0.042989656
>>>>>>> 131290 | 205893 | 0 | 0.074959315
>>>>>>> 127938 | 201505 | 0 | 0.054259572
>>>>>>> 132923 | 201504 | 0 | 0.022826955
>>>>>>> <...>
>>>>>>> 282198 | 425307 | 0 | 0.07132499
>>>>>>> 282197 | 795399 | 0.021921627 | 0.021921627
>>>>>>> 282276 | 795400 | 0.05221079 | 0.05221079
>>>>>>> 282035 | 425170 | 0.15 | 0.0967519
>>>>>>> 282034 | -1 | 0 | -
>>>>>>>
>>>>>>> I am eager to try to find the reason of this strange behaviour, so
>>>>>>> tell me if there is anything I can do to figure it out.
>>>>>>>
>>>>>>> Best regards,
>>>>>>>
>>>>>>> Tao
>>>>>>>
>>>>>>> 2012/8/20 Stephen Woodbridge <woodbri at swoodbridge.com>:
>>>>>>>> Please keep the queries on the list.
>>>>>>>>
>>>>>>>> No, I have no idea, I've never seen anything like that before.
>>>>>>>>
>>>>>>>> What does this query return?
>>>>>>>>
>>>>>>>> select count(*) from japan where cost_car=0;
>>>>>>>>
>>>>>>>> -Steve
>>>>>>>>
>>>>>>>>
>>>>>>>> On 8/20/2012 7:26 AM, Tao Romera Martinez wrote:
>>>>>>>>>
>>>>>>>>> Dear Stephen,
>>>>>>>>>
>>>>>>>>> I have been trying to use your function for turn restricted
>>>>>>>>> shortest
>>>>>>>>> path routing.
>>>>>>>>> I installed the postgresql functions, prepared a table with the
>>>>>>>>> turn
>>>>>>>>> costs, and now I am able to route through a network using turn
>>>>>>>>> restrictions. Well, almost.
>>>>>>>>>
>>>>>>>>> When I launch a request, the column "cost" contains 0 values
>>>>>>>>> except
>>>>>>>>> for the rows where there is a turn (the cost is the one set for
>>>>>>>>> turns).
>>>>>>>>> The request is:
>>>>>>>>>
>>>>>>>>> SELECT * FROM turn_restrict_shortest_path(
>>>>>>>>> 'SELECT id AS id, source::integer, target::integer, cost_car AS
>>>>>>>>> cost
>>>>>>>>> FROM japan WHERE japan.geom_way && ST_MakeEnvelope(139.675,
>>>>>>>>> 35.729,
>>>>>>>>> 139.705, 35.762)',
>>>>>>>>> 284867, -- node_id of start
>>>>>>>>> 282034, -- node_id of end
>>>>>>>>> false, -- directed graph?
>>>>>>>>> false, -- has_reverse_cost?
>>>>>>>>> 'SELECT to_cost::double precision, teid::integer AS target_id,
>>>>>>>>> feid||coalesce('',''||via,'''') AS via_path FROM turn_costs WHERE
>>>>>>>>> teid
>>>>>>>>> IN (select id FROM japan WHERE japan.geom_way &&
>>>>>>>>> ST_MakeEnvelope(139.675, 35.729, 139.705, 35.762)) ');
>>>>>>>>>
>>>>>>>>> The ST_MakeEnvelope is just to create a window and limit the
>>>>>>>>> otherwise
>>>>>>>>> huge amount of ways.
>>>>>>>>>
>>>>>>>>> The table "japan" looks like:
>>>>>>>>>
>>>>>>>>> id | osm_id | osm_name | osm_source_id | osm_target_id |
>>>>>>>>> clazz |
>>>>>>>>> flags | source | target | km | kmh | cost | reverse_cost | x1 |
>>>>>>>>> y1 |
>>>>>>>>> x2 | y2 | geom_way | cost_car
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> ----+---------+----------+---------------+---------------+-------+-------+--------+--------+-----------+-----+-----------+--------------+----------+------------+-------------+------------+----------------------------
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> 1 | 4847506 | | 31236733 | 31236584 |
>>>>>>>>> 11 |
>>>>>>>>> 1 | 24690 | 24758 | 1.6335903 | 1 | 6.5343612 | 1.6335903 |
>>>>>>>>> 139.7578 | 35.6437952 | 139.7688252 | 35.6349433 | <snip> |
>>>>>>>>> 3.2671806
>>>>>>>>>
>>>>>>>>> And the table "turn_costs" looks like:
>>>>>>>>>
>>>>>>>>> rid | to_cost | teid | feid | via
>>>>>>>>> -----+---------+--------+------+-----
>>>>>>>>> 1 | 0.15 | 22 | 10 |
>>>>>>>>> 2 | 0.15 | 21 | 10 |
>>>>>>>>> 3 | 0.15 | 163 | 10 |
>>>>>>>>> 4 | 0.15 | 27 | 10 |
>>>>>>>>> 5 | 0.15 | 26 | 10 |
>>>>>>>>> 6 | 0.15 | 27 | 11 |
>>>>>>>>> 7 | 0.15 | 26 | 11 |
>>>>>>>>> 8 | 0.15 | 229 | 11 |
>>>>>>>>> 9 | 0.15 | 232698 | 11 |
>>>>>>>>> 10 | 0.15 | 229 | 12 |
>>>>>>>>>
>>>>>>>>> The result of the query looks like:
>>>>>>>>>
>>>>>>>>> vertex_id | edge_id | cost
>>>>>>>>> -----------+---------+-------------
>>>>>>>>> 284867 | 211472 | 0
>>>>>>>>> 284794 | 211471 | 0
>>>>>>>>> 134058 | 205895 | 0.15
>>>>>>>>> 284826 | 205894 | 0
>>>>>>>>> 131290 | 205893 | 0
>>>>>>>>> 127938 | 201505 | 0
>>>>>>>>> 132923 | 201504 | 0
>>>>>>>>> <...>
>>>>>>>>> 282198 | 425307 | 0
>>>>>>>>> 282197 | 795399 | 0.021921627
>>>>>>>>> 282276 | 795400 | 0.05221079
>>>>>>>>> 282035 | 425170 | 0.15
>>>>>>>>> 282034 | -1 | 0
>>>>>>>>>
>>>>>>>>> Do you have an idea about why the "cost" values are 0?
>>>>>>>>>
>>>>>>>>> Thank you very much for your help,
>>>>>>>>>
>>>>>>>>> Tao
>>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Pgrouting-users mailing list
>>>>>>> Pgrouting-users at lists.osgeo.org
>>>>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>>>>>
>>>>>> _______________________________________________
>>>>>> Pgrouting-users mailing list
>>>>>> Pgrouting-users at lists.osgeo.org
>>>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>> _______________________________________________
>>>> Pgrouting-users mailing list
>>>> Pgrouting-users at lists.osgeo.org
>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>> _______________________________________________
>>> Pgrouting-users mailing list
>>> Pgrouting-users at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
More information about the Pgrouting-users
mailing list