最短?最安?さまざまな最適ルートについて考えてみよう

2016.11.17専門家コラム
Pocket

私は地図関係のサービスや業務アプリケーション開発に長年関わっていますが、「最適な運転ルートを教えてくれる機能が欲しい」というリクエストをよくいただきます。
実際にリクエストの中身を聞いてみると、様々な課題が存在していることに気がつきます。
そこで、今回は「最適ルート」について整理をしてみましょう。
kousaten
【最適は人によって違う】
鉄道乗換案内アプリを使うと、「到着時刻が早いもの」「所要時間が短いもの」「乗換回数が少ないもの」「料金が安いもの」など、”最適”の定義がその都度選べるようになっています。そして、その選択は人によって違います。

同様に、クルマによる移動も、”最適”という定義は人によって違ってきます。

タクシーの場合、乗客からは「料金が安いもの」「到着時刻が早いもの」が好まれるのですが、タクシー会社の視点からは「乗客を満遍なく拾いやすい=実車率が高くなる」ことは高い要求項目です。

トラックの場合、荷主からは「指定時刻に届くこと」「料金が安いもの」が期待されますが、運送会社の視点からは、「待機時間を最短に」「荷物が空で走るのを避ける」ことが強く求められます。

このように、どちらの視点に立つかで、アプリケーションを設計は大きく異なってきます。

【最適は時期、時刻によっても違う】
朝晩の通勤ラッシュによる渋滞だけでなく、法則性のある渋滞が各所で発生します。五十日(ごとおび)、つまり5の付く日や0の付く日の午後に商用車が増えて渋滞が発生しやすいことは知られています。また、雨降りの朝など、天候による影響で渋滞が発生します。ゴールデンウィークやお盆、年末年始はマイカーで高速道路は激しく渋滞します。高速道路は平日日中よりも夜間の方がトラックが多くなります。

このように、道路の混雑状況は、時期や時刻によっても違ってきます。これを加味して”最適”な結果を導くアプリケーションを設計する必要もあります。
PAK86_koutuujyuutai20130815_TP_V

【最適ルートを導く「ルート検索エンジン」】

いずれの視点に立つにしても、最適ルートを導く際には「ルート検索エンジン」が利用されます。ルート検索エンジンは、道路、鉄道、配管、送電線などのあらゆる「ネットワーク」データに対して、出発点から目的点までの最適なルートを導くソフトウェアです。

一般的なネットワークデータには、経路(リンク)と経由地(ノード)があり、そのリンクとノードそれぞれに「コスト」と呼ばれる値が設定されています。クルマの場合は、一方通行や右左折禁止などの交通規制、標準的な走行スピードが設定されます。また、渋滞の場合には、走行スピードの値を下げることで、実態に近いルート検索結果を導きます。

ルート検索のアルゴリズムは、基本は幾何学の応用で、代表的なものとしてダイクストラ法が知られています。
Dijkstra_Animation
画像出典:
https://ja.wikipedia.org/wiki/ダイクストラ法
ダイクストラ法はバランスのよい検索結果を返してくれるのですが、出発点から全てのネットワークデータを総当たりで検索するので、結果を導くのに時間がかかります。このため、距離に応じてネットワークデータを間引いて計算する、事前に計算結果を作成しておく、データとプログラムをコンピュータのメモリに格納するなどの実装上の工夫を加えることなどで、実用的な速度を実現しています。

【テクノロジーは渋滞をどこまで解消してくれるか?】
ルート検索エンジンは年々高性能化しています。最近ではAI(人工知能)の力を使う試みもあるようです。
そして、自動運転が登場することで、移動が最適化されて、渋滞の解消を実現してくれるという意見を耳にします。実際にはどうでしょうか?

99c4b98b6eee2682d51d8bdd5cae2b1d_s自動運転は交通事故の減少に大きく寄与すると思いますが、
出勤退社時刻が今と変わらなければ、朝晩の通勤ラッシュによる渋滞はなかなか改善されないように思われます。
納品や集金の日付が五十日のままでは、午後の渋滞は減りません。
荷物の到着時刻が荷主都合で決められている現状が変わらなければ、待機時間の無駄は避けられません。
渋滞の解消のためにはテクノロジーだけではなく、私たちの社会習慣から変えていく必要がありそうです。

タグ : 地図 ルート検索
Pocket