パイオニアが難問「巡回セールスマン問題」に挑戦!?
パイオニアが業務用車両向けの運行管理サービスを機能強化しました。目玉は「訪問順最適化機能」の搭載です。
……これって巡回セールスマン問題じゃないか？
ビークルアシストとは？
今回機能強化されたのは「ビークルアシスト」というサービスです。
ビークルアシストは業務用車両向けの管理サービスです。カーナビなどの車両端末をインターネット上のサーバーと接続し、業務用車両の状態やコース管理、進捗状況を確認したりメッセージを送って業務指示を行うなどの機能があります。
今回このビークルアシストがアップデートされたというわけです。それだけなら別に取り上げるほどでもない「使う人だけに関係する話」なんですが、ちょっと面白そうな機能が追加されていたので紹介します。
「訪問順最適化機能」の搭載
今回の機能強化で「訪問順最適化機能」という機能が搭載されました。
訪問しなければいけない複数の地点に順に向かう場合、その順序はたくさんあります。たとえば、上の「1からスタートして2～5の4地点を訪れる」という場合では24通りの回り方があります。この訪問順を最適化して、最も効率良く訪問できる順序を提示してくれるのがこの機能です。
巡回セールスマン問題
この手の問題は、実は有名な計算機科学の問題でもあります。「巡回セールスマン問題」と呼ばれるこの問題は、地点が増えると計算量が爆発的に増加して、現実的に計算できなくなります。
先ほどの4地点では24通りでしたが、6地点だと720通りの回り方があります。
10地点では362万通り、20地点では243京（243億の1億倍）通りにも達します。
全通り比較しなくても良いようにするアルゴリズムは考案されていますが、計算量が爆発的に増加しない（多項式時間で計算可能）アルゴリズムは見つかっていません。巡回すべき地点が20ヶ所以上になってくると、計算量的に現実的ではなくなってきます。
用途が微妙に限られる
探索する地点数が多くなると、現実的な計算時間では結果が得られません。今回のシステムはクラウドサービスなので、計算能力の高いサーバー上で計算が実行されることになりますが、それでも243京通りのような莫大な計算量を処理しきれるわけではありません。
現実的には「一人のセールスマンが100ヶ所の巡回先を最適なルートで回るためにナビを使う」なんて状況はほとんど無いでしょう。でもセールスではなく宅配便のように1件あたりにかける時間が短い訪問の場合では、1日の訪問先だけでも計算しきれなくなる可能性はあります。
さらに言えば、今後はより効率化するためにもっと複雑な問題を解かなければならない可能性があります。例えば宅配便配送において、「時間帯指定のある宅配物」「過去の配送情報から得られる在宅している（再配達にならない）確率」「地理的条件」などを加味した最適な配送ルートを自動的に生成するなどが考えられます。タクシーにおいて予約状況・渋滞情報などを踏まえた最適な配車というのもあるでしょう。そういった用途ではより難しい問題を解く必要が出てきます。（参考：配車配送計画ソフト - Wikipedia）
今回のビークルアシストのアップデートでも、
訪問先の滞在時間や到着指定時刻を考慮して訪問順を並び替えることも可能です。
と書いてありますが、この書き方だと滞在時間や到着指定時間を人間が考慮して並び替えろってことでしょうね。そこまで自動化してくれることが理想なんですが、そこまではできていないようです。
まとめ
コンピューターの計算とクラウド接続、それにナビゲーションシステムという組み合わせによって提供される省力化サービスですね。決められた条件の中で最も効率的なものを導くというのは、（計算量の爆発という問題があったとしても）コンピューターが得意とするところです。
こういった技術は数年～十数年経つと一般消費者向けにも下りてくるというのが一般的です。現在のカーナビは追加目的地（あるいは経由地）を入れると「どの順番で回るか」を聞かれます（上の画像）。今後はここに「最短になる順序にする」という選択肢が出てくることでしょうね。