Posted inDatabase

PostgreSQLでpgRoutingを導入・設定する実践ガイド：最短経路探索システムを内製化する

Database tutorial - IT technology blog
Database tutorial - IT technology blog

深夜2時の障害：配送ルーティングAPIが停止した夜

深夜2時、オンコールのPagerDutyアラートが鳴り響きました。ドライバーへの案件割り当てを担当するマイクロサービスクラスタが次々と「504 Gateway Timeout」を返していたのです。ダッシュボード上では、フラッシュセールの最中に数千件もの配送料金計算クエリがハングアップしていました。これまでは、直線距離でおおまかに算出した後、外部の地図APIへリクエストを集中させていました。その結果、月額のAPI利用料は3,000ドルに達し、ピーク時には100 req/sのレートリミット上限に引っかかって深刻なボトルネックを引き起こしていたのです。

真っ赤に染まったGrafanaの画面を前に、チームはこの混沌とした状況を根本から解決することを決断しました。高額な外部APIへの依存をやめ、ルーティング処理そのものを社内データベースへと移行することにしたのです。PostgreSQLに道路網データを投入してpgRoutingを有効化すれば、高度に最適化されたC言語エンジン上で最短経路探索アルゴリズムを直接実行できるようになります。

PostgreSQLにおけるグラフネットワークの本質

データベースは、単なる二次元の座標点テーブルを保持しているだけでは、2つのGPS座標がどのように接続されているかを理解できません。経路を探索するためには、データを「グラフ（Graph）」構造としてモデル化する必要があります。

1. ネットワークトポロジの構造（Network Topology）

道路の1本1本が「エッジ（Edge）」であり、三叉路や交差点が交差する「ノードまたは頂点（Node / Vertex）」としての役割を果たします。pgRoutingを正常に動作させるための標準データテーブルには、最低限以下のカラムが必要です。

  • id: 道路セグメントの一意の識別子。
  • source: 始点となる交差点（ノード）のID。
  • target: 終点となる交差点（ノード）のID。
  • cost: 順方向の重み／コスト（メートル単位の距離、または秒単位の所要時間）。
  • reverse_cost: 逆方向の重み／コスト。対面通行（双方向）の場合はcostと同値にし、進入禁止の一方通行の場合は負の値（通常は-1）を設定します。
  • geom: PostGISで管理される空間ジオメトリオブジェクト（LineString）。標準測地系WGS 84（EPSG:4326）を使用します。

2. PostGISとpgRoutingの役割分担

PostGISはジオメトリ（空間幾何）部分を担当し、経度・緯度の保持、座標系の変換、実距離の計算を行います。一方、pgRoutingはPostGISを基盤として動作するアルゴリズムライブラリです。ダイクストラ法、A*（A-star）、巡回セールスマン問題（TSP）、到達圏分析（Driving Distance：移動時間に応じた到達可能エリア）などのアルゴリズムがあらかじめ提供されており、ゼロから自前実装する必要はありません。

インストールと実践的な構築手順

ここでは、PostgreSQL 16が稼働するUbuntu 22.04 LTS環境上で、ルーティング環境を直接構築する手順を解説します。

ステップ1：PostGISとpgRoutingのインストール

ターミナルを開き、PostgreSQLのバージョンに対応した2つのパッケージをインストールします。

# パッケージリストの更新
sudo apt update

# PostgreSQL 16向けにPostGIS 3とpgRoutingをインストール
sudo apt install -y postgresql-16-postgis-3 postgresql-16-pgrouting

インストール完了後、PostgreSQLにログインして対象プロジェクトのデータベースで拡張機能を有効化します。

sudo -u postgres psql -d transport_db

-- pgRoutingが依存しているため、事前にPostGISを有効化する必要があります
CREATE EXTENSION IF NOT EXISTS postgis;

-- pgRoutingを有効化
CREATE EXTENSION IF NOT EXISTS pgrouting;

-- インストール成功の確認
SELECT pgr_version();

ステップ2：テーブル設計と道路ネットワークデータの投入

市街地の道路網を表現するためにroadsテーブルを作成します。

CREATE TABLE roads (
    id SERIAL PRIMARY KEY,
    osm_id BIGINT,
    name VARCHAR(100),
    source INTEGER,
    target INTEGER,
    cost DOUBLE PRECISION,
    reverse_cost DOUBLE PRECISION,
    geom GEOMETRY(LineString, 4326)
);

実際のデータソースとしては、OpenStreetMap（OSM）や物流パートナーから提供されるShapefileをCSV/GeoJSON形式にエクスポートしたものがよく使われます。座標を含むCSVファイルをスクリプトで読み込むためにJSONへ素早く変換したい場合は、toolcraft.app/ja/tools/data/csv-to-json を活用すると便利です。ブラウザ側で直接パース処理が行われるため、顧客データのセキュリティ面でも安心です。

それでは、ハノイ中心街（座標105.85, 21.02周辺）を模した閉じた交通ネットワークを形成する、4つのサンプル道路セグメントを登録してみましょう。

INSERT INTO roads (id, name, geom)
VALUES
    (1, 'チャンティエン通り区間A', ST_GeomFromText('LINESTRING(105.850 21.020, 105.855 21.020)', 4326)),
    (2, 'チャンティエン通り区間B', ST_GeomFromText('LINESTRING(105.855 21.020, 105.860 21.020)', 4326)),
    (3, 'ファンチューチン通り区間', ST_GeomFromText('LINESTRING(105.855 21.020, 105.855 21.025)', 4326)),
    (4, 'ハイバーチュン通り区間', ST_GeomFromText('LINESTRING(105.855 21.025, 105.860 21.020)', 4326));

ステップ3：pgr_createTopologyによるトポロジの自動構築

この時点では、sourceとtargetの2つのカラムは空のままです。交差点を手作業で1つずつ特定する代わりに、pgRoutingには端点同士の交差を自動スキャンしてくれるpgr_createTopology関数が用意されています。

-- 構文：テーブル名、許容誤差（tolerance）、ジオメトリカラム名、主キーカラム名
SELECT pgr_createTopology('roads', 0.00001, 'geom', 'id');

許容誤差の0.00001度は、現実世界では約1.1メートルに相当します。このトレランス（許容値）を設けることで、GPS測定などのわずかなズレがあっても端点同士を適切に結合できます。実行後、pgRoutingは頂点一覧を保持する補助テーブルroads_vertices_pgrを自動生成し、roadsテーブルのsourceとtargetカラムに対応するノードIDを自動で補完します。

続いて、移動コスト（重み）の計算を行います。メートル単位の実際の長さを算出するため、geography型に対してST_Length関数を適用します。

-- 楕円体面上のメートル単位の長さを正確に計算するためgeography型へキャスト
UPDATE roads
SET cost = ST_Length(geom::geography),
    reverse_cost = ST_Length(geom::geography);

-- ファンチューチン通り区間を逆走禁止の一方通行と仮定し、reverse_cost = -1 を設定
UPDATE roads SET reverse_cost = -1 WHERE id = 3;

-- グラフ探索を高速化するためsourceとtargetにB-treeインデックスを作成
CREATE INDEX idx_roads_source ON roads(source);
CREATE INDEX idx_roads_target ON roads(target);

ステップ4：ダイクストラ法による最短経路探索の実行

これで準備は完了です。pgr_dijkstra関数を呼び出して、交差点1（ノード1）から交差点3（ノード3）への最適なルートを探索できます。

SELECT 
    path.seq,
    path.node,
    path.edge,
    path.cost AS step_cost,
    path.agg_cost AS total_cost,
    r.name AS road_name,
    ST_AsGeoJSON(r.geom) AS geojson
FROM pgr_dijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM roads',
    1, -- 出発ノード
    3, -- 目的ノード
    directed := true
) AS path
LEFT JOIN roads r ON path.edge = r.id
ORDER BY path.seq;

このクエリにより、各ステップの累積コストと対応するGeoJSON文字列を含む経路リストが返されます。バックエンド側では、このGeoJSON配列をシリアライズしてドライバー向けアプリに返却するだけで、マップ上に一瞬でポリラインを描画できます。

移行後に得られた具体的な成果

本番環境での稼働から2週間が経過し、目覚ましい改善成果が得られました。

  • バックエンドAPIクラスタのCPU使用率が92%から14%へと大幅に低下。
  • 経路計算のp99レイテンシが、外部API経由の420msから内部ネットワーク完結のわずか8〜12msへと激減。
  • 商用地図APIの利用料を毎月約3,000ドル削減。
  • フラッシュセール時におけるレートリミット上限によるボトルネックのリスクを完全に解消。

物流・配送システムの規模が拡大し、APIコストやレイテンシの壁に直面しているなら、PostgreSQL上でPostGISとpgRoutingを活用する内製アプローチは、極めて費用対効果の高い技術投資となるはずです。

Share:
Tags: