はじめに
初めまして、L19 (リクと読みます) と言います。私は学生時代、信号処理や機械学習分野に応用を持つアルゴリズムに関する研究をしていました。
現在はサイバーセキュリティ関連製品メーカーの企業で統合ログ管理ソフトウェアの運用・開発を行っています。
昨年末、株式会社ノマドクリエイティブを経営している友人 (以下 K さん) から「一緒にゴルフをする人を車でピックアップするとき、ゴルフ場までの所要時間が短い順に並べて比較できると良い」という話を聞きました。
今所属している会社の業務内容と直接の関係はありませんが、学生時代にアルゴリズム研究をしていた身としては興味深く、効率的な方法が実現できないか考えてみることにしました。
ゴルフ場までの移動時間が短い順に探せるゴルフ場予約サービス「NearGolf」
この「ゴルフ場探索」は、 K さんがサポートしている NearGolf がサービスとして既に提供しています。
NearGolf は、その特徴として「指定した駅を経由したとき所要時間の短い順にゴルフ場を検索すること」ができます。
出発駅を含め最大 4 駅まで指定することができ、検索結果としてその実際の経路も確認できます。
経路探索には Google Maps API を用いており、検索結果の表示は数秒で終わるほど早いです。
昨年末時点では、しかしながら、1回の検索で API コールする回数が多くなってしまっており、検索当たりの API 使用料金を考えるとこの回数削減が課題でした。
以下ではこの課題解決を目指すために私が取り組んだ内容を紹介します。
課題は「APIのコール回数を規定回数以内に抑え、検索精度を最大化できるか？」
前述の「ゴルフ場探索」は、数学的には以下のようなグラフが与えられたとき S から全ての点を通って F へ行くコスト (c1-c9) の合計が最も小さくなる経路と、その合計コストを求める問題に帰着されます。
具体的にはこの問題を全てのゴルフ場に対してそれぞれ解き、見つけた合計コスト (=所要時間) を小さい順に並べることで所要時間が短い順のゴルフ場のランキングが得られます。
点の間のコストが分かっていれば、点の数が少ないので経路の全探索を行なっても大した計算量にならず、高度な経路探索のアルゴリズムも必要ありません。
しかしながら、正確なコスト、すなわち所要時間を求めるには Google Maps API を用いなければならず、尚且つゴルフ場の数が多くなればなるほどその API コール数も比例して大きくなってしまいます。
この API コール数を減らして使用料金を抑えることが目標なのですが、このコール数がコストの正確性すなわち検索精度とトレードオフの関係にあります。
従って API をなるべく用いず、いかに正確なコストを予想できるかが鍵となります。
どんなアプローチがあるかの検討
具体的な手法の実装の前に K さんとブレストを行って、考えられるアプローチを洗い出しました。
以下はその時に K さんが作ってくれた図です:
この中から 3 つほどピックアップして、具体的にどのように検討していったのかをご紹介します。
アプローチ 1: 総当たり検索を都度行う
これは検索のたびに前述のすべてのコストを Google Maps API で取得する方法です。
検索精度が最も良くなりますが、一方で API 使用回数は最大となってしまいます。
今回は API 使用回数を抑えることが目的なので、このアプローチは使えそうにありませんでした。
アプローチ 2: 過去の検索データを保持しておく
過去に検索された駅・ゴルフ場の組み合わせに対する経路や所要時間を保持しておき、同じ条件で検索された時に再利用する方法です。
サービス利用回数が多くなるにつれて保持するデータも増えていくため、長期的に見ると API 使用回数が削減できそうです。
しかし、交通情報は時事刻々と変化するためデータの「鮮度」が落ちていき、実際の最短経路や所要時間とのずれが生じてしまう可能性があります。
結果的に検索精度が下がってしまう可能性があるため、このアプローチも見送ることとなりました。
アプローチ 3: リクエストを行うゴルフ場を減らす
API でリクエストを送るゴルフ場を予め何らかの基準によって絞り込むことで、合計の API 利用回数を減らす方法です。
指定した駅の位置情報は事前にわかっているので、そこから所要時間ランキングの上位に入りそうなゴルフ場を API を使わずに絞り込めれば良いわけです。
この絞り込みに用いる基準はいくつか考えられましたが、直線距離の近さという直感的で扱いやすいものを採用し、試しにランキングを作ってみようということになりました。
駅・ゴルフ場間の所要時間が短い≒直線距離が短い?
前述のコスト (=所要時間) は点同士 (=駅同士または駅とゴルフ場) の間の直線距離と関係があると考え、以下の手続きでゴルフ場までの所要時間ランキングを作ってみました:
- 選択した駅同士とゴルフ場との直線距離を計算する
- 出発駅から全ての駅を経由してゴルフ場まで行く時の最短直線距離を計算する
- この最短直線距離を全ての $N$ ゴルフ場に対して計算する
- 最短距離が短い順の上位 $n (< N)$ 番目までのゴルフ場について Google Maps API を用いて実際の最短経路と所要時間を取得する
この方法のキモは「コストを直線距離で代用してゴルフ場の絞り込みを行っていること」です。
ランキング上位に現れそうなゴルフ場に対してのみ API を用いて本当の経路とその所要時間を調べるようにすることで、合計の API コール数を減らすことができます。
上の手続きを Python で実装したソースコードは GitHub で公開しているので、興味があればご覧ください。
所要時間ランキング上位の予想は高精度
この方法の精度を数値実験で確かめてみました。
出発、および経由駅は関東圏の駅に限定して、その位置情報は こちらのページ から取得しました。
また、ゴルフ場も関東圏に限定し 楽天 GORA ゴルフ場検索 API を用いて位置情報を取得しました。
正確な経路とその所要時間の取得には Google Maps API の Direction API を用いました。
出発および経由駅をランダムで 4 つ選び、上記の 1-4 の手続きを適用するまでを 1 反復とし、これを 10 回繰り返しました。
以下は、最短距離が短い順の上位 $n=64$ 番目までのゴルフ場が、本当の所要時間ランキング 64 位までに入る確率を示しています。
特に 1 位から 15 位くらいまでのゴルフ場は完璧に絞り込みが成功していることがわかります。
関東圏のゴルフ場全てに対してではなく、絞り込んだ $n=64$ ゴルフ場に関してのみ Google Maps API を用いれば 15 位くらいまでは完璧に所要時間ランキングが作れそうだということです。
一方で 16 位以降は比較的に絞り込みに失敗してしまっていることもわかります。
そこで、最短距離が短い順に 65-79 番目までのゴルフ場も追加で計算して、改めて 16位以降の確率を計算してみました。
以下の図からは 16 位から 30 位くらいまでは 8 割程度の精度でランキングが作れそうだということがわかります。
ちなみに NearGolf では 1 ページに 15 件のゴルフ場を表示するので「2ページ目までであれば API コール数 79 回で 8 割以上の精度のゴルフ場ランキングが生成できる」ということになります。
まとめと今後の展望
所要時間ランキング上位のゴルフ場に対しては、最短の直線距離によって絞り込むことが有用であることがわかりました。
一方でランキングが下位になるにつれて精度が悪くなるのは、有料道路を考慮できていないことが原因の一つとして挙げられます。
駅とゴルフ場に加えて、有料道路のインターチェンジやジャンクションを前述のグラフの点として追加できればもっと精度よく絞り込みが行えるのではないかと考えています。
なお、本稿で紹介した方法は、その精度の観点から NearGolf には現在採用されておりません。
表示される所要時間は十分信頼性の高いものになっているので、安心してご利用いただけると幸いです。
また、課題の整理から本稿を書き上げるまでの間に、株式会社ノマドクリエイティブ経営者である友人 K さんにはたくさんの助言をいただきました。
本稿を読んで気になったことや「こんなことはできるかな？」などのご相談事がありましたら、ぜひご連絡をお願いいたします。