はじめに

※この記事は、2022年9月に実施した Webinar の内容をまとめたものです。

ある地点からある地点への最短経路は、グラフ理論における最短経路問題として知られており、道路や鉄道などの情報をグラフに帰着することで求めることができます。身近な応用例としては、鉄道などの経路案内があります。 Mathematica にもグラフ理論に関する組み込み関数が数多く用意されており、 Mathematica でもグラフを用意できれば簡単に経路を求めることが可能です。しかし、現状では実際の道路情報などをグラフ形式でダウンロードできるようなサービスはありません。

今回は国土数値情報 (https://nlftp.mlit.go.jp/ksj/index.html) の高速道路データからインターチェンジを「頂点」、各経路を「辺」としてグラフを構築し、指定したインターチェンジ間の最短経路を求めてみます。

グラフの構築

データの読み込み

Webinar 当時に使用した、2020年の高速道路のデータを使用します。

ダウンロードしたフォルダ「N06-20」にノートブックファイルを保存し、NotebookDirectory として指定して進めていきます。

注：2021年のデータを使用する場合は、「utf8」フォルダのデータを使用する必要があります。

路線のデータを読み込む

路線のデータは「N06-20_HighwaySection.geojson」を使用します。

路線の数を調べます。

1420個ある路線のデータの1つ目のデータを表示します。

接合部のデータを読み込む

路線のデータは「N06-20_Joint.geojson」を使用します。

接合部の数を調べます。

2388個あるデータのうちの1つ目のデータを表示します。

位置情報を抽出

路線のデータの1つ目のデータを表示します。

1つ目のデータの位置情報を抽出します。

全てのデータから位置情報を抽出

全ての路線のデータ及び全ての接合部のデータから位置情報を抽出します。

抽出したデータを確認します。

辺の作成

辺のリストを作成する

路線上にある接合部の情報を取得する

フローチャートに従って接合部を求めます。

接合部を近い順にソートする

接合部の位置が路線のどこにあるかを求めます。

リストを並べ替える順番を求めます。

求めた順番で接合部をソートします。

隣接する接合部をペアにする

無向グラフの辺にする

全ての路線に対して実行

各路線上にある接合部を求めます。

表形式で確認します。

辺に変換します。

このエラーは路線 779 に重複する点があるため発生します。

エラーを回避するために、路線の位置情報から重複する点を削除します。

{} を削除し、リストを平坦化します。

平坦化したリストを確認します。

重み (距離) のリストを作成

路線内の各接合部の位置を求めます。

求まった位置をソートします。

位置をペアにします。

範囲指定で使える形式に変換します。

指定した範囲の位置情報を抽出します。

抽出した範囲の距離を求めます。

接合部間の距離が短いとメートル単位で返されることがあるため、単位をキロメートルに変換します。

値を抽出します。

注：QuantityMagnitude[dist] でも値を抽出可能できます。

全ての路線に対して実行

グラフの作成

辺と重み (距離) のリストが完成したので、グラフを作成します。

接合部の位置情報を抽出します。

頂点番号 -> {座標} の形式に変換します。

頂点の位置を指定してグラフを作成します。

オリジナルのグラフィックスと作成したグラフを比較します。オリジナルのグラフィックスは N06-20_HighwaySection.shp を使用します。ファイルを読み込んだ後、並べて表示します。

※分かっている問題点：作成したグラフを確認すると、9 個の頂点が他のどの頂点とも接続されていませんでした。この頂点の接合部を確認したところ、路線上の位置とは一致せずに、点と点の間に存在していました。これらの頂点を自動で辺に変換することは難しいため、個別に手作業で修正する必要があります。ただし、最短経路を求める際の点に指定しなければ今回は支障がないため、このまま進めていきます。