[pgrouting-users] Problem using TRSP
Tao Romera Martinez
taoromera at gmail.com
Thu Aug 30 19:20:14 PDT 2012
Dear Christy, Stephen,
I have tried the query by using a directed graph with reverse cost
(directed_graph and reverse_cost booleans both to "true"), and the
values in the cost column returned by the query are now correct. I
have not performed other checks, such as to see if the route is
actually the one with the lowest cost taking into account turn
restrictions and so. I will look at it later.
Tao
2012/8/31 Stephen Woodbridge <woodbri at swoodbridge.com>:
> 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
>
>
> _______________________________________________
> 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