2016年9月17日

巡回セールスマン問題における最短経路をpgRoutingで探索する

先日、PostgreSQLアンカンファレンスを開催した際、「pgRoutingを使って巡回セールスマン問題を解く」という発表を国府田さんがされていました。
非常に面白そうな機能で、私も少し使ってみましたので、今回はその使い方や使用例などを含めてご紹介します。

■「巡回セールスマン問題」とは何か


「巡回セールスマン問題」というのは、以下のようなものです。
巡回セールスマン問題(じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP)は、都市の集合と各2都市間の移動コスト(たとえば距離)が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める(セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める)組合せ最適化問題である。
巡回セールスマン問題 - Wikipedia
簡単に言うと、「セールスマンが何か所か回る時、回る場所が増えれば増えるほど、可能性のある経路の候補が爆発的に増えていくので、最短経路を導き出すのが困難になる」ということです。回る場所の数「n」に対して、計算量はその階乗「n!」のオーダーとなります。

そのため、データ量が増えると総当たりで解くことが計算量的に困難になる問題のひとつとして知られています。

■「pgRouting」とは何か


pgRoutingは、PostgreSQLおよびPostGISの拡張で、PostgreSQL/PostGISの地理空間データベースの機能に経路探索(routing)の機能を追加するライブラリです。
プロジェクトの紹介文によると、
  • さまざまなクライアント(ライブラリ)を通してデータや属性を加工可能。
  • データの変更はすぐに経路探索に反映される。事前の計算などは不要。
  • 「コスト」のパラメータは動的にSQLで計算され、テーブルのフィールドやレコードから取得可能。
となっています。

経路探索のアルゴリズムはいろいろあるようで、コアの機能としては以下のようなアルゴリズムを使うことができます。
  • All Pairs Shortest Path, Johnson’s Algorithm
  • All Pairs Shortest Path, Floyd-Warshall Algorithm
  • Shortest Path A*
  • Bi-directional Dijkstra Shortest Path
  • Bi-directional A* Shortest Path
  • Shortest Path Dijkstra
  • Driving Distance
  • K-Shortest Path, Multiple Alternative Paths
  • K-Dijkstra, One to Many Shortest Path
  • Traveling Sales Person
  • Turn Restriction Shortest Path (TRSP)
今回は、この中から巡回セールスマン問題(Traveling Sales Person)を解くための関数を使ってみます。

■pgRoutingのpgr_tsp関数


今回使用するpgRoutingの関数はpgr_tspです。
この関数は Simulated Annealing(焼きなまし法)という方法で、最短経路を探索します。
この関数は2つの使い方があります。ユークリッド距離を使って2点間の距離を計算して最短経路を探す方法と、各点間の距離をあらかじめ行列として定義したものを与えて最短経路を探す方法です。

まず、ユークリッド距離を使う方法ですが、引数にSQL文を渡す必要があり、このSQL文は「id, x, y」というカラムを返却するSQL文である必要があります。
pgr_costResult[] pgr_tsp(sql text, start_id integer);
pgr_costResult[] pgr_tsp(sql text, start_id integer, end_id integer);

もう一つの各点間の距離を行列で与える場合には、float型の二次元配列として与えます。
record[] pgr_tsp(matrix float[][], start integer)
record[] pgr_tsp(matrix float[][], start integer, end integer)

今回は、前者のユークリッド距離を使うバージョンを使います。

まず、以下のように位置情報をx,yとして持つテーブルを作成しておきます。
pgr=>  CREATE TABLE vertex_table (
pgr(>      id serial,
pgr(>      x double precision,
pgr(>      y double precision
pgr(>  );
CREATE TABLE
pgr=>
pgr=>  INSERT INTO vertex_table VALUES
pgr->  (1,2,0), (2,2,1), (3,3,1), (4,4,1), (5,0,2), (6,1,2), (7,2,2),
pgr->  (8,3,2), (9,4,2), (10,2,3), (11,3,3), (12,4,3), (13,2,4);
INSERT 0 13
pgr=> SELECT * FROM vertex_table;
 id | x | y
----+---+---
  1 | 2 | 0
  2 | 2 | 1
  3 | 3 | 1
  4 | 4 | 1
  5 | 0 | 2
  6 | 1 | 2
  7 | 2 | 2
  8 | 3 | 2
  9 | 4 | 2
 10 | 2 | 3
 11 | 3 | 3
 12 | 4 | 3
 13 | 2 | 4
(13 rows)

pgr=>

この位置情報のテーブルから「id,x,y」を取得するSQL文を与えて、pgr_tspを実行すると、以下のように最短経路を表示してくれます。
pgr=>  SELECT seq, id1, id2, cost FROM pgr_tsp('SELECT id, x, y FROM vertex_table ORDER BY id', 6, 5);
 seq | id1 | id2 |       cost
-----+-----+-----+------------------
   0 |   5 |   6 |                1
   1 |   6 |   7 |                1
   2 |   7 |   8 |  1.4142135623731
   3 |   9 |  10 |                1
   4 |  12 |  13 |  1.4142135623731
   5 |  10 |  11 |                1
   6 |  11 |  12 |                1
   7 |   8 |   9 |                1
   8 |   3 |   4 |                1
   9 |   2 |   3 |  1.4142135623731
  10 |   0 |   1 |                1
  11 |   1 |   2 | 2.23606797749979
  12 |   4 |   5 |                1
(13 rows)

pgr=>

出力で重要なのは「seq、id2、cost」です。seqは経路の順番、id2はノードのid(vertex_tableのidカラム)、costは次のノードに移動するためのコスト(距離)です。

■聖地巡礼の最短経路探索問題


世間では今、映画「君の名は。」が大ヒットしています。(唐突感)



アニメのヒット作には、聖地の存在が欠かせません。そしてそのファンは聖地巡礼をすることになっています(?)。

しかし、聖地といってもたくさんありますし、時間は限られていますので、効率よく回ることが求められてきます。巡るべき聖地が増えれば増えるほど計算量が爆発的に増大し、最短経路を求めることが困難になってきます。多分。

というわけで、「君の名は。」の聖地を巡礼するための最短経路を巡回セールスマン問題としてpgRoutingを使って探索してみます。(手段の目的化)

なお、本エントリはここからが本題です。

■PostGIS/pgRoutingとpykmlのインストール


まず、PostGIS/pgRoutingをインストールします。

PostgreSQLコミュニティのyumレポジトリを使っている場合には以下のコマンドでインストールできます。今回はPostgreSQL 9.5と一緒に使っています。
$ sudo yum install -y postgis2_95 pgrouting_95
(...)
$ rpm -qa | grep pgrouting
pgrouting_95-2.0.1-1.rhel6.x86_64
$ rpm -qa | grep postgis
postgis2_95-2.2.2-1.rhel6.x86_64
$

また、三次元地理空間情報のデータ形式であるKMLファイルを扱うPythonのライブラリpykmlもインストールします。
$ sudo pip install pykml
(...)
$ pip list | grep pykml
pykml (0.1.0)
$

インストールが終わったら、今回使うデータベースにPostGISとpgRoutingのEXTENSIONをインストールします。
pgr=# create extension postgis;
CREATE EXTENSION
pgr=# create extension pgrouting;
CREATE EXTENSION
pgr=# \d
               List of relations
 Schema |       Name        | Type  |  Owner
--------+-------------------+-------+----------
 public | geography_columns | view  | postgres
 public | geometry_columns  | view  | postgres
 public | raster_columns    | view  | postgres
 public | raster_overviews  | view  | postgres
 public | spatial_ref_sys   | table | postgres
(5 rows)

pgr=#

■データの準備をする


最初、自分で聖地の位置情報のデータを作成しようかとも思っていたのですが、いろいろ探していたらGoogle Mapsに「君の名は。」の聖地マップが公開されていましたので、今回はこれを使います。
まず、この聖地マップを自分のアカウントにコピーしてきます。

コピーの方法は、マップの右上にあるプルダウンメニューから「Copy map」を選ぶだけです。




次に、聖地マップのデータをKML形式でエクスポートします。

コピーの時と同じく、プルダウンメニューから「Download KML」を選んで、マップ全体のデータをKMLとしてダウンロードして保存します。


エクスポートしたKMLファイルは以下のようなXMLファイルになっているはずです。
$ head Copy\ of\ 【君の名は。】聖地巡礼マップ【831現在】.kml
<?xml version='1.0' encoding='UTF-8'?>
<kml xmlns='http://www.opengis.net/kml/2.2'>
        <Document>
                <name>Copy of 【君の名は。】聖地巡礼マップ【8/31現在】</name>
                <description><![CDATA[]]></description>
                <Folder>
                        <name>無題のレイヤ</name>
                        <Placemark>
                                <name>予告映像カット
</name>
$

次に、KMLファイルの中に含まれている位置情報をPostgreSQLに投入するためのINSERT文に変換します。

今回テーブルは以下の構造にします。
CREATE TABLE seichi (
  sid serial primary key,
  name text not null,
  descr text,
  img text,
  lat float8 not null,
  lon float8 not null
);

sidはシーケンス番号、nameはGoogle Mapsに登録されていた名前、descrは説明文です。imgは位置の画像が設定されたいた場合のURL、lat/lonは緯度経度をfloat8の精度で持ちます。

場所の情報はKMLファイル内の「Placemark」というタグに囲まれていますので、この情報を取得します。

KMLファイルの解析はpykmlモジュールを使って行います。
kml_to_sql.pyスクリプトにKMLファイルを引数として渡すと、KMLファイル内のPlacemarkのデータをINSERT文に変換して以下のように出力します。
$ python kml_to_sql.py Copy\ of\ 【君の名は。】聖地巡礼マップ【831現在】.kml  > ins.sql
$ head ins.sql
INSERT INTO seichi (name,descr,img,lat,lon) VALUES
    ('予告映像カット','新宿警察署裏交差点','',139.6944129,35.6925938)
  , ('君の名は。第1弾キービジュアル','瀧が立っている横断歩道の背景建物','https://blogger.googleusercontent.com/img/proxy/AVvXsEgLXxyhLQGYjVApXbrHHFw6IQRERj_ElP9jq75ll8YSfZgTToH4FBtM0n5tX5T2hSzDf0E3SZoZAl2mghpnwqvhM-h5XfPChG5Nyj1FrE5G06KFP4ddvnajkQDWHXgRU59VRY8RvW9_rupQI1sR_aylQ8M_w6-TfJMk=',139.723177,35.6607657)
  , ('三葉が座っていた総武線ホームのベンチ','','https://blogger.googleusercontent.com/img/proxy/AVvXsEjs-Qf1ula5UcaavKPNgW5l1RrPOblkLW8M_nRWTB2PeNVwCnlApcOEpyeCbWHKU2k3fCFFZGChkPbFPYK152VboPYJRZ478d09RMisUsKnzh7QxyQ7dATT7oGQvuQrS0qqZWHmau5rluf3SaBk6-RaAIwhdPpOBBbp=',139.7020626,35.6840715)
  , ('瀧と奥寺先輩がお茶していたスタバ','看板TSUTAYAのTSUの部分にあたるカウンター席','https://blogger.googleusercontent.com/img/proxy/AVvXsEjJovc3KVdT6rnstEyq4eZOWc_r_WCuZNXm57S6nuA24SKQ-C-GZChGQnTsqGUJOj-F-qkYvmcEFEytmTLdLYJ6bEQ_2ErDThFYRZFv_HNZho-BQOhRkzUDUpDjiU-es86G0H86fSYcadNB6ro8q7bZbRF-25PU2vWG=',139.7003701,35.6598526)
  , ('君の名は。第1弾キービジュアル','背景の六本木ヒルズ','',139.7293139,35.6603647)
  , ('君の名は。第1弾キービジュアル','背景の東京ミッドタウンビル','',139.7312933,35.6662877)
  , ('君の名は。第1弾キービジュアル','瀧が立っている横断道','',139.7228122,35.6613584)
  , ('道路標識案内板','瀧と奥寺先輩が別れる歩道橋についている道路標識案内板','https://blogger.googleusercontent.com/img/proxy/AVvXsEig76fE_x43p9U6vuYakLKM1xZkH-TgIosQ9dl7hAAb0NxvaCys-MuIIzeby4ElYN0xCMyGSRkKZ8KTDCyaXT3acNn8D5iFdR8FKLecoXTTrepfY86ITUhHA_NFPTa8vtoN2iIAhZ_dpNd-7_FnFhs-4t_yXvqyKTd9=',139.7233808,35.6743456)
  , ('歩道橋背景1','瀧と奥寺先輩が別れる歩道橋の背景','https://blogger.googleusercontent.com/img/proxy/AVvXsEg0KNNAo6DX5jUntHLJw-Cen_ySf035voZcrPRCPAQbIldwNNFERUcZ7ixRdaw9PiLcaCY2NP6aoekUvtMCeTqM6M0CEBMKl5fDDdP_NI91NlQgjrEVmGCZWB2mPxiMaZhRvet_vfklN9T6GTXuRP86mg_E26luvq2fyus=',139.7238582,35.6723802)
$

そして、作成したテーブルにINSERT文でデータを流し込みます。
$ psql -f ins.sql pgr
INSERT 0 38
$

データができたことを確認したら、準備は完了です。
pgr=> \x
Expanded display is on.
pgr=> select * from seichi limit 3;
-[ RECORD 1 ]-----------------------------------------------------------------------------------------------------------------------------------------
sid   | 1
name  | 予告映像カット
descr | 新宿警察署裏交差点
img   |
lat   | 139.6944129
lon   | 35.6925938
-[ RECORD 2 ]-----------------------------------------------------------------------------------------------------------------------------------------
sid   | 2
name  | 君の名は。第1弾キービジュアル
descr | 瀧が立っている横断歩道の背景建物
img   | https://blogger.googleusercontent.com/img/proxy/AVvXsEgLXxyhLQGYjVApXbrHHFw6IQRERj_ElP9jq75ll8YSfZgTToH4FBtM0n5tX5T2hSzDf0E3SZoZAl2mghpnwqvhM-h5XfPChG5Nyj1FrE5G06KFP4ddvnajkQDWHXgRU59VRY8RvW9_rupQI1sR_aylQ8M_w6-TfJMk=
lat   | 139.723177
lon   | 35.6607657
-[ RECORD 3 ]-----------------------------------------------------------------------------------------------------------------------------------------
sid   | 3
name  | 三葉が座っていた総武線ホームのベンチ
descr |
img   | https://blogger.googleusercontent.com/img/proxy/AVvXsEjs-Qf1ula5UcaavKPNgW5l1RrPOblkLW8M_nRWTB2PeNVwCnlApcOEpyeCbWHKU2k3fCFFZGChkPbFPYK152VboPYJRZ478d09RMisUsKnzh7QxyQ7dATT7oGQvuQrS0qqZWHmau5rluf3SaBk6-RaAIwhdPpOBBbp=
lat   | 139.7020626
lon   | 35.6840715

pgr=>

■聖地巡礼の最短経路を求める


それでは、聖地巡礼の最短経路を巡回セールスマン問題として探索してみます。

前述したように、pgr_tsp関数にユークリッド距離を使って計算させます。

pgr_tspに与えるクエリは
SELECT sid id, lat x, lon y FROM seichi ORDER BY sid

となります(エイリアスでカラム名を指定)。

pgr_tsp関数に与える2つ目の引数は、スタートの点のidを示しています。(今回は1番目から出発)

さて、クエリを実行してみましょう。
pgr=> SELECT * FROM pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1);
 seq | id1 | id2 |         cost
-----+-----+-----+----------------------
   0 |   0 |   1 |  0.00276786017347617
   1 |  16 |  17 |  0.00336861318052751
   2 |  21 |  22 |  0.00418150821235386
   3 |  26 |  27 |  0.00070285384682649
   4 |  18 |  19 |  0.00103679575616323
   5 |  17 |  18 | 0.000724005262411046
   6 |  14 |  15 |  0.00040594088239891
   7 |  25 |  26 |  0.00420010183685812
   8 |   2 |   3 |  0.00965949435530557
   9 |  19 |  20 |  0.00786443285746516
  10 |  24 |  25 |  0.00638462619110202
  11 |  30 |  31 | 0.000613460422526542
  12 |  31 |  32 |   0.0020755731593899
  13 |  36 |  37 |  0.00521034970899676
  14 |  34 |  35 |  0.00453278438158901
  15 |  23 |  24 |  0.00214997988828621
  16 |  22 |  23 |  0.00338756302081414
  17 |  20 |  21 |  0.00901689128802769
  18 |  13 |  14 | 4.29288947063113e-05
  19 |  33 |  34 |  0.00758742562995817
  20 |  35 |  36 |  0.00655833544277088
  21 |  37 |  38 |  0.00662867080567097
  22 |  32 |  33 |   0.0076538252201047
  23 |  29 |  30 | 0.000494603275347511
  24 |  28 |  29 |  0.00116522954392147
  25 |  11 |  12 |  0.00340343115400377
  26 |  12 |  13 |  0.00387475855377472
  27 |   7 |   8 |  0.00202254985600024
  28 |   8 |   9 | 0.000924678733398354
  29 |   9 |  10 |  0.00108906486492197
  30 |  10 |  11 |  0.00636705982066888
  31 |  15 |  16 |  0.00573513230013025
  32 |   4 |   5 |  0.00657719868789178
  33 |   6 |   7 |   0.0222159042861008
  34 |  27 |  28 |  0.00284098090455204
  35 |   3 |   4 |   0.0228251711761441
  36 |   1 |   2 |  0.00981665980311944
  37 |   5 |   6 |   0.0453009359877922
(38 rows)

pgr=>

最短経路が出ました。id2カラムの順番に巡礼していけば、最短経路で聖地巡礼ができることになります。

なお、これだけではちょっと分かりづらいので、元の地理のデータをJOINしてnameとdescrを表示してみましょう。(不要なid1とcostカラムも省きます)
pgr=> SELECT
pgr->   t.seq,
pgr->   t.id2,
pgr->   s.name,
pgr->   s.descr
pgr-> FROM
pgr->   pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1) t
pgr->     LEFT OUTER JOIN seichi s ON t.id2 = s.sid;
 seq | id2 |                       name                       |                                                          descr
-----+-----+--------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------
   0 |   1 | 予告映像カット                                   | 新宿警察署裏交差点
   1 |  17 | オープニング                                     | ・作中のオープニングの背景・大人になった瀧と三葉がすれ違う歩道橋
   2 |  22 | ユニカビジョン                                   |
   3 |  27 | 大人になった瀧が走り出てくる改札                 | 三葉を探しに飛び出す南口改札
   4 |  19 | 瀧の通学路&大人になった瀧が走っていく場所       | ・はじめて瀧と入れ替わった三葉が学校へ向かう通ったルミネのショップウィンドウ沿い・大人になった瀧が三葉を探しに走っていく
   5 |  18 | 作中背景                                         | 連絡橋からバルト9方面
   6 |  15 | 風景カット                                       | サザンテラス口店 スタバの入口階段と手前の花壇
   7 |  26 | 大人になった瀧が来ていたスタバ                   | ここで式の話をしている大人になったテッシーとさやちんが登場
   8 |   3 | 三葉が座っていた総武線ホームのベンチ             |
   9 |  20 | 大人の三葉                                       | ラスト、 瀧を見つけた大人の三葉が駆け出してくる千駄ヶ谷駅の改札
  10 |  25 | 走る三葉                                         | 大人になった三葉が瀧を見つけに走って通る場所
  11 |  31 | 君の名は。 第2弾キービジュアル&作中ラストシーン | 瀧と三葉がすれ違う階段・物語の最後のシーン
  12 |  32 | 十字路                                           | みつはが走ってくるシーン
  13 |  37 | 風景カット                                       | 道路標識
  14 |  35 | 瀧が息を整える場所                               |
  15 |  24 | 瀧と奥寺先輩が四ッ谷駅方面を眺める場所           | 就活中の瀧と奥寺先輩
  16 |  23 | 瀧(大人)と奥寺先輩が話しながら歩いている道     |
  17 |  21 | 瀧と奥寺先輩のデート                             | 物語終盤、就活中の瀧と奥寺先輩のデートで渡っていた弁慶橋
  18 |  14 | 瀧と奥寺先輩の待ち合わせ1                        | 四ッ谷駅赤坂方面改札
  19 |  34 | 瀧と奥寺先輩の待ち合わせ2                       | アトレの方角
  20 |  36 | 風景カット                                       | 郵便ポスト
  21 |  38 | 風景カット                                       | 四谷三丁目の交差点
  22 |  33 | 分かれ道                                         | 瀧が走っていくシーン
  23 |  30 | 太陽の光とドコモタワー                           |
  24 |  29 | 瀧が立っていた歩道橋                             | JR総武線信濃町駅前の歩道橋
  25 |  12 | 歩道橋背景4                                      | 瀧と奥寺先輩が別れる歩道橋の下に見切れている道路標識板
  26 |  13 | 瀧の通学路                                       | 瀧と司と真太の下校シーン
  27 |   8 | 道路標識案内板                                   | 瀧と奥寺先輩が別れる歩道橋についている道路標識案内板
  28 |   9 | 歩道橋背景1                                      | 瀧と奥寺先輩が別れる歩道橋の背景
  29 |  10 | 歩道橋背景2                                      | 瀧と奥寺先輩が別れる歩道橋
  30 |  11 | 歩道橋背景3                                      | 瀧と奥寺先輩が別れる歩道橋
  31 |  16 | 国立新美術館                                     |
  32 |   5 | 君の名は。第1弾キービジュアル                    | 背景の六本木ヒルズ
  33 |   7 | 君の名は。第1弾キービジュアル                    | 瀧が立っている横断道
  34 |  28 | あおい書店前歩道橋                               | 作中、瀧が数回通っていた歩道橋
  35 |   4 | 瀧と奥寺先輩がお茶していたスタバ                 | 看板TSUTAYAのTSUの部分にあたるカウンター席
  36 |   2 | 君の名は。第1弾キービジュアル                    | 瀧が立っている横断歩道の背景建物
  37 |   6 | 君の名は。第1弾キービジュアル                    | 背景の東京ミッドタウンビル
(38 rows)

pgr=>

「新宿警察署裏交差点」を出発点として、聖地巡礼のルートがより具体的に見えてきました。

■求めた最短経路を可視化する


最後に、この巡礼の経路をGoogle Mapsに取り込んで可視化してみます。

経路を可視化するには、2点間に線を引かなければなりません。Google Maps上で線を引かせるには、出発点の緯度経度と、到着点の緯度経度情報が必要です。ウィンドウ関数の匂いがします。

まず、先ほどのクエリを少し修正して、場所の名前ではなく緯度経度を表示させます。
pgr=> SELECT
pgr->   t.seq,
pgr->   t.id2,
pgr->   s.lat,
pgr->   s.lon
pgr-> FROM
pgr->   pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1) t
pgr->     LEFT OUTER JOIN seichi s ON t.id2 = s.sid;
 seq | id2 |     lat     |    lon
-----+-----+-------------+------------
   0 |   1 | 139.6944129 | 35.6925938
   1 |  17 | 139.6971166 | 35.6931863
   2 |  22 | 139.7004586 | 35.6936089
   3 |  27 | 139.7002923 | 35.6894307
   4 |  19 | 139.7009951 |  35.689422
(...)
  33 |   7 | 139.7228122 | 35.6613584
  34 |  28 | 139.7010112 | 35.6570849
  35 |   4 | 139.7003701 | 35.6598526
  36 |   2 |  139.723177 | 35.6607657
  37 |   6 | 139.7312933 | 35.6662877
(38 rows)

pgr=>

次に、ウィンドウ関数を使って「前の地点の緯度経度」を表示させます。
pgr=> SELECT
pgr->   t.seq,
pgr->   t.id2,
pgr->   s.lat,
pgr->   s.lon,
pgr->   lag(s.lat) OVER (ORDER BY seq) prev_lat,
pgr->   lag(s.lon) OVER (ORDER BY seq) prev_lon
pgr-> FROM
pgr->   pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1) t
pgr->     LEFT OUTER JOIN seichi s ON t.id2 = s.sid;
 seq | id2 |     lat     |    lon     |  prev_lat   |  prev_lon
-----+-----+-------------+------------+-------------+------------
   0 |   1 | 139.6944129 | 35.6925938 |             |
   1 |  17 | 139.6971166 | 35.6931863 | 139.6944129 | 35.6925938
   2 |  22 | 139.7004586 | 35.6936089 | 139.6971166 | 35.6931863
   3 |  27 | 139.7002923 | 35.6894307 | 139.7004586 | 35.6936089
   4 |  19 | 139.7009951 |  35.689422 | 139.7002923 | 35.6894307
(...)
  33 |   7 | 139.7228122 | 35.6613584 | 139.7293139 | 35.6603647
  34 |  28 | 139.7010112 | 35.6570849 | 139.7228122 | 35.6613584
  35 |   4 | 139.7003701 | 35.6598526 | 139.7010112 | 35.6570849
  36 |   2 |  139.723177 | 35.6607657 | 139.7003701 | 35.6598526
  37 |   6 | 139.7312933 | 35.6662877 |  139.723177 | 35.6607657
(38 rows)

pgr=>

このデータをPythonスクリプトでKMLファイルに変換します。

tsp_to_kml.pyスクリプトでは、psycopg2を使ってPostgreSQLに接続してデータを取り出し、XMLファイルをベタに書き出します。

このスクリプトの出力を保存すると、以下のようなKMLファイルを得られます。
$ python tsp_to_kml.py > route.kml
$ cat route.kml

<?xml version='1.0' encoding='UTF-8'?>
<kml xmlns='http://www.opengis.net/kml/2.2'>
        <Document>
                <Style id="line-DB4436-5-nodesc">
                        <LineStyle>
                                <color>ff0000ff</color>
                                <width>5</width>
                        </LineStyle>
                </Style>
                <name>Copy of 【君の名は。】聖地巡礼マップ【8/31現在】</name>
                <description><![CDATA[]]></description>
                <Folder>
                        <name>巡礼最短経路</name>

<Placemark>
  <name>Path 1</name>
  <styleUrl>#line-DB4436-5-nodesc</styleUrl>
  <LineString>
    <coordinates>139.6971166,35.6931863,0 139.6944129,35.6925938,0</coordinates>
  </LineString>
</Placemark>

<Placemark>
  <name>Path 2</name>
  <styleUrl>#line-DB4436-5-nodesc</styleUrl>
  <LineString>
    <coordinates>139.7004586,35.6936089,0 139.6971166,35.6931863,0</coordinates>
  </LineString>
</Placemark>
(...)
                </Folder>
        </Document>
</kml>

$ 

なお、KMLファイルのFolder要素がGoogle Mapsで言うところのレイヤーに当たります。今回は、巡礼の経路情報はすべて「巡礼最短経路」という一つのレイヤーにまとめてあります。

最後に、作成したroute.kmlというKMLファイルを、Google Mapsにインポートします。

まず、地図に「Add layer」でレイヤーを追加します。


次に、作成した新しいレイヤーに「Import」というメニューがありますので、そこをクリックしてKMLファイルをインポートします。



インポートが無事に完了すれば、レイヤーの名前が「巡礼最短経路」となり、経路が地図上に表示されます。


やったぜ可視化!

■まとめ


今回は、複数の緯度経度の情報から、それらを結ぶ最短経路を求める演算をpgRoutingを使って実現しました。

また、KMLファイルをエクスポート・インポートすることで、その演算結果をGoogle Mapsのデータを活用して、可視化できることを示しました。

なお、今回は実現できなかったこととして、以下のようなことがあります。
  • KMLのエクスポート、インポートをWebAPIでやりたい。(誰か教えてください)
  • 地理的な距離ではなく、所用時間などでコスト計算やってみたい。
  • 総距離や総時間に制限を設けた上で、「制限時間内にできるだけ多く回る」みたいな探索をしてみたい。
  • など。
演算の部分については、もしかしたらpgRoutingの他の関数などで実現できるかもしれないので、少しずつ調べてみたいと思います。

ぜひ、みなさんも地理情報とPostGISやpgRoutingを使って、何か面白いことにチャレンジしてみていただければと思います。

Enjoy, 聖地巡礼ライフ!!

では、また。

0 件のコメント:

コメントを投稿