はじめに
SAIG(Strategic AI Group)の塚本です。地図・GIS・位置特定連載の4本目です。
私はAIチームにてアルゴリズム案件に携わっているのですが、アルゴリズム案件の代表的な課題のひとつに経路最適化があります。経路最適化自体の方法は以前の記事を参照下さい。
本記事ではユーザ等から登録された住所情報から、ある程度精度を犠牲にすることで安価に経路を探索できる状態する、つまり”そこそこ”な方法について紹介します。なお紹介する内容は当社でアルバイトとして活躍している大森さん・高倉さんの協力を得ています。
経路を探索できる状態ができるまで
複数の住所を順番に訪れる経路を探索するには、各訪問先をノード、訪問先と訪問先の最短の道をエッジとしたグラフネットワーク構造で表す必要があります。
入力情報がすでに構造化されたデータであれば良いのですが、実際は絶対的な位置である緯度経度ですら記録されておらず、曖昧な住所情報という形で記録されている事が多いです。
そのため、住所情報から経路探索をするために、以下のstepが必要です。
- 文字列である住所情報から緯度経度を求める
- 求めた緯度経度同士をつなぐ最短の道の長さを求める
各stepの実現方法を以下で紹介します。なお、本記事では地図情報を Google Maps API にて取得します。
1. 文字列である住所情報から緯度経度を求める
多くの場合、住所は文字で書かれており表記に揺れがあります。また、住所としては正しくても、地図情報中に存在しなかったり、複数の可能性が発生することは珍しくありません。実際の住所情報をもとに説明します。
なお、以下はWebページでの Google Maps の結果を記載しておりますが、APIでの結果も同様の傾向にあります。
例えば、当社の下記住所を Google Maps に入力すると、その所在は一意に求まります。Google Map東京都品川区大崎1-2-2アートヴィレッジ大崎セントラルタワー
ところが、この住所を少し変えると、複数の候補がサジェストされます。Google Map東京都品川区大崎1-2-2アートヴィレッジ
一方、建物名を除外するとまた一意に求まります。Google Map東京都品川区大崎1-2-2
例として説明した「アートヴィレッジ大崎セントラルタワー」は、商業ビルであり建物自体が Google Maps に登録されていますが、これが小さなマンションや個人宅等になると未登録や、表記ゆれで一意に求めることが困難になります。先の例はそれほど距離が離れてませんが、実際の住所データで検証した所、1駅以上離れた候補が複数サジェストされる状況はよく発生し、複数の所在からどれを正しいものと選択するかによって経路が大きく変わってしまいます。
そこで、私は住所情報から所在がわからなかったり複数サジェストされた場合、後ろから記載を削り経路に大きく影響を及ぼさない番地までの所在を求められるよう、加工処理を加えるようにしています。Google Map東京都品川区大崎1-2
住所情報からの所在特定は地域性に大きく左右されるのですが、実際にあった顧客リストの住所情報をそのまま Google Maps API を用いて所在を特定しようとした所、無加工の場合全体の80％程度しか取得ができませんでしたが、上記工夫を入れることで90％超の所在特定ができました。
2. 求めた緯度経度同士をつなぐ最短の道の長さを求める
step1 で求めた所在(緯度経度)について、全ての地点を結ぶ最短の道の長さを Google Maps API を用いて取得する事は現実的でありません。有料のサービスであるため、金額的にもなるべく少ない取得回数で妥当な結果を得たいです。
実世界の特に日本では、訪問先までの最短路の長さは2点間の直線距離に比例すると期待できます。そこで、どの程度の精度で近似できるのか、実際に下図で示したエリアにランダムに点を打ち、各2点間を結ぶ距離と、Google Maps API による実際の最短路の長さの誤差を検証します。
初めに打った20点から、各2点の直線距離(ユークリッド距離)とGoogle Maps API による実際の最短路の長さを比較し、最小二乗法にて誤差最小となる相関係数 C を求めます。
再度ランダムに20点打ち、ユークリッド距離に相関係数 C を書けた値と、Google Maps API による実際の最短路の長さを比較したグラフが下図です。近距離の場合は誤差が大きいですが、それ以外は1.2～0.8倍に収まっており、それほど悪くない精度です。
上記結果より、緯度経度から求められるユークリッド距離にて経路の候補を探索し、上位数点の候補のみ実際に Google Maps API にて最短路を取得することで、API使用頻度を落としつつ、それなりの解を得ることができます。
まとめ
本記事では住所情報から経路を探索を実現するために、住所の加工による所在特定成功率の向上と地点間の最短路の長さを近似する、”そこそこ”な方法について、実際の Google Maps API の動作を交えて紹介しました。世の中にはすでに優れたルート最適化サービスが存在する一方、利用シーンやコスト対効果に合致しない場面も多いかと思います。そのような場合に簡易な処理と安価な汎用サービスの組み合わせでは、どの程度の精度で実現できるかの指標となれば幸いです。
次は岸下さんによるBluetoothで位置推定 です。