ja/OneWayStreets

一方通行の取扱方法

ダイクストラとA*のアルゴリズムはともにグラフのエッジの両端にかかるコストを計算することができるため、一方通行の通りを持つ道路ネットワークの経路探索に利用できます。

この小さな例は、その利用方法を図解しています。このサンプルデータは OpenJumpを利用して作成され、またpgRoutingがインストールされている PostGISデータベースに格納されています。

グラフは下図のようなものです。ほとんどのエッジが左から右にデジタイズされているにも関わらず、エッジ#2は右から左にデジタイズされていることに注意してください。これは一方通行の通りをシミュレートするために行いました。
http://files.postlbs.org/pgrouting/img/howto_onewaystreets_1.png

経路探索アルゴリズムを用いてエッジの両端のコストを計算する際には、reverse_costフィールドが必要です。

初めに、costとreverse_costの両方にエッジの長さをセットします。 

routing=# UPDATE rtest SET cost=length(the_geom), rcost=length(the_geom); 
UPDATE 5

次に、エッジ#2のreverse_costを増やすため、エッジ#2のreverse_costフィールドに1,000,000を追加します。 

routing=# UPDATE rtest SET rcost=rcost + 1000000 WHERE gid = 2;

routing=# SELECT gid,cost,rcost,source,target FROM rtest ORDER BY gid;  

gid |        cost      |         rcost       | source | target 
----+------------------+---------------------+--------+--------
 1  | 90.4777391240398 | 90.4777391240398    |      1 |      2
 2  | 266.663211021467 | 000266.663211021467 |      3 |      2
 3  | 74.7975644284963 | 74.7975644284963    |      2 |      4
 4  | 264.887335603738 | 264.887335603738    |      4 |      5
 5  | 49.0618009646755 | 49.0618009646755    |      3 |      5
(5 rows)

ダイクストラとA*の両アルゴリズムの最後のパラメータは、グラフ上で経路を探索する際に逆方向コストを計算するかどうかを決定します。

falseを設定した場合、両アルゴリズムはcostパラメータ(この場合は各エッジの長さ)のみを用いて探索を行います。falseを設定した場合、ノード#1からノード#3までの経路が次のように探索されます。 

routing=# SELECT * FROM shortest_path_astar('SELECT gid AS id,source::int4,
    target::int4, cost::double precision, rcost::double precision AS reverse_cost,
    x1,y1,x2,y2 FROM rtest',1,3,false,false);

 vertex_id | edge_id |      cost
-----------+---------+------------------
       1   |     1   | 90.4777391240398
       2   |     2   | 266.663211021467 
       3   |    -1   |  0
(3 rows)

http://files.postlbs.org/pgrouting/img/howto_onewaystreets_2.png

さて、reverseパラメータにtrueをセットした場合、これらのアルゴリズムはreverse_costを利用します。その結果エッジ#2のノード2が非常に高いコストを持っていることを発見し、別の経路を探索します。 

routing=# SELECT * FROM shortest_path_astar('SELECT gid AS id, source::int4,
     target::int4, cost::double precision, rcost::double precision AS reverse_cost,
     x1,y1,x2,y2 FROM rtest',1,3,false,true);

vertex_id | edge_id |       cost
----------+---------+------------------
       1  |      1  |  90.4777391240398           
       2  |      3  |  74.7975644284963           
       4  |      4  |  264.887335603738
       5  |      5  |  49.0618009646755
       3  |     -1  |   0
(5 rows)

http://files.postlbs.org/pgrouting/img/howto_onewaystreets_3.png

エッジの両端のコストを計算する能力を持つことは素晴らしい特徴ですが、パフォーマンスに影響を与えるため、本当に必要なときにだけ使用してください。 

routing=# EXPLAIN ANALYZE SELECT * FROM shortest_path_astar('SELECT gid
    AS id,source::int4, target::int4, cost::double precision, rcost::double
    precision AS reverse_cost,x1,y1,x2,y2 FROM rtest',1,3,false,false);

                               QUERY PLAN 
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar  (cost=0.00..12.50 rows=1000 width=16) 
(actual time=0.954..0.958 rows=3 loops=1)  Total runtime: 1.020 ms
(2 rows)


routing=# EXPLAIN ANALYZE SELECT * FROM shortest_path_astar('SELECT gid
    AS id, source::int4, target::int4, cost::double precision, rcost::double
    precision AS reverse_cost,x1,y1,x2,y2 FROM rtest',1,3,false,true);

                               QUERY PLAN 
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar  (cost=0.00..12.50 rows=1000 width=16) 
(actual time=11.088..11.093 rows=5 loops=1)  Total runtime: 11.155 ms(2 rows)

終わり

この日本語訳の著作権は、日本ユニシス株式会社に帰属しています。また、この日本語訳は、GNU FDLのもとで提供されています。