先日、ドローンを用いた医薬品や食料品の配送について取り上げました。
現状の日本で店舗やビジネスで何かをデリバリーをする場合、飲食店であれば出前館やロケットナウなどの配送プラットフォームに乗ることもあれば、自前でシステムやアプリを作る場合もあるかと思います。
自前で作ること、そして人間が運ぶ有人輸送を前提に、調査も兼ねてフードデリバリーの配達員としてアプリを使ってみました。
トータルで100件以上運びました。（！）
機能については意外とAlexaのような音声会話ボットなどが大きな効果を出しそうだと思いました。走行中にスマホでマップなどを見ていられないので。ARメガネなどはスピーカーもあるので、イヤホンが禁止される自転車乗りの方など意外に向いてるかも知れません。
シリーズとして成り立つかはわかりませんが、たまに備忘録として残してみたいと思います。
たまにはこういうのも良いかなと…
今回は経路探索について触れてみたいと思います。
奥が深い経路探索
出前館、ロケットナウ、ウォルトやウーバーイーツなど様々なサービスの配達員として活動しましたが、それぞれ経路の描き方に特徴があり、特に「配達員に何をさせたいか」という考え方に大きな違いがあるように思いました。
例えばですが、直線距離でルートを描くアプリもあれば、下図のように行ったり来たりするルートが出てくるアプリもあります。①で商品Aを受け取り、②で商品Bを受け取り、③で商品Aを渡し、④で商品Bを渡すような形です。
お店での調理完了タイミングやお客様の待ち時間などが関係しているようで、これはこれで解の一つではあるのでしょう。
ただ、配達当事者としては移動経路に悩むものであり、単純に疲れるものでもあります。④のお客様からしても「なんでソッチに行くんだ？？」と不思議に思ってしまうかも知れません。
そのほか「効率よく、配達員を次の案件につなぐんだ」というような意思を感じるアプリもありました。
過去のユーザーの動向データなどを元に予測しているのだと思いますが、料理をピックして配達、料理をピックして配達の繰り返しになり、気付くと出発点からかなり遠くに居たことがあります。
最近の経路探索アプリ：配達NAVITIME
優れた配達ドライバーは頭の中でルートを描けるそうです。そのため移動中はあまり地図を見ないそう。
しかし誰もがそんなベテラン・ドライバーのようなことができるわけではありません。
新しく配達を始める方にうってつけな、みんな大好きNAVITIMEから以下のようなアプリがリリースされています。
建物の入口までわかるというのは面白いですね。
Googleマップなどでも、なぜか建物の裏に誘導されてしまうことがあります。配達ナビタイムであれば、入口からすんなりと建物に入ることができます。
環境試験装置などを販売している大西熱学という会社の創業者のお孫さんが大学で経路探索の研究をされていて、その関係で社内ベンチャーとしてNAVITIMEが始まったという歴史があります。Google Mapなど様々なマップサービスがありますが、外資系テックジャイアントにも負けずにポジションを築いているのは本当に凄いです。
グラフ理論と経路探索の歴史
そもそも論ですが、どのように経路探索が行われるか歴史を遡ってみましょう。
現在でも通信経路の計画や、物流ネットワークの構成など研究が進められていますが、いくつかグラフ理論と経路探索に関連する歴史的なトピックを挙げてみます。
まず、世の中の経路や、状態遷移などを極限まで簡素化すると「ノードとエッジで構成されたネットワークのようなもの」として捉えることができ、一方通行のエッジがある場合は有向グラフ、一方通行がなければ無向グラフとして扱う事ができます。点と線、これが経路を表す最小構成となります。
18世紀オイラー
18世紀の数学者、オイラーは「川にかかる複数の橋を1回だけ通って元の場所に戻れるか？」という問題に取り組み、橋を通る経路をグラフに換え、一筆書き可能かどうかの判定法を編み出しました。
1937年ごろ～第二次世界大戦
いわゆる軍事作戦におけるOperations Researchの中でも、物流に関する研究はグラフ理論と関連が深く、効率よく物資や兵士を輸送する、補給用の兵站を構築する研究が盛んに行われました。
既にある経路を効率的に扱うだけでなく、新たな経路を創造したり、様々な要素を複雑に組み合わせた輸送経路の分析などが行われました。
1959年ダイクストラ
ダイクストラ先生は2002年に亡くなっており、存命中に本人に会ったことのある研究者も多いのかなと思います。テキサス大学のアーカイブに、本人の手書きメモが保管され見れるようになっています。
https://www.cs.utexas.edu/~EWD
セマフォと呼ばれる仕組みの考案でも有名ですが、COBOLの使用に対して批判的だったということで、敢えて先生と呼ばせていただいています。このダイクストラ先生によって重み付きグラフにおける最短経路を見つけ出すダイクストラ法が考案されました。
Wikipediaのアニメーションがわかりやすいです。一つずつ経路を確認していき、数字が小さいほど採用すべきルートであることが判定できます。以下のネットワークぐらいの規模であれば人間の目でパッと見てわかるかも知れません。
1960年代フェデックス
イエール大学の学生だったフレデリック・W・スミスは、貨物を効率に運ぶため夜間に貨物を集約させて仕分けてから朝までに各地に輸送する「ハブ・アンド・スポーク」方式を思いつきました。
このレポートを読んだ教授はC評価を付けたと言われています。
10年後、フレデリックは自分のアイディアを実現するフェデラル・エクスプレス（FedEx）という会社を作りました。
発送元→配達先ではなく、発送元→集荷場→配達先とすることにより「全体の配送効率」が上がったわけですね。いまでは「一度集荷して仕分ける」というのは運送業の基本のようになっています。
一方で、経路が封鎖されたり破綻した場合にはハブ・アンド・スポーク構造は非常に配送効率が悪くなるため、固定された形で効果を発揮する構造だということもわかっています。
1969年ARPANET
現在のインターネットの起源です。
ネットワークの大部分が失われてもネット通信が機能し続けるなど、非常にシブトい構造的な特徴があります。
例えば以下の海底ケーブルの地図で言えば、日本とアメリカ間の通信ケーブルがすべて断線したとしても、大陸経由やオーストラリアなど経由で通信することができます。最短経路だけでなく「次善経路」など、2番目、3番目の経路に切り替えるようなアルゴリズムも研究されていました。
1998年スモールワールド
自然界に見られるいくつかのネットワーク構造において、ネットワーク内のノードが少数の「近道」を通じて互いに短い距離で結ばれているというスモールワールド現象が明らかになりました。ソーシャルネットワークなどにも見られ、全ての人や物事は6ステップ以内で繋がっているという「六次の隔たり」という考えが広まり現在のテレビ番組の企画などでも扱われることもあります。
つまりスモールワールド状態にないネットワークを、スモールワールド化することで効率の良い経路が生まれることになります。インターネットで言えば、キャッシュサーバーなどを適切に配置することで、大きな規模でネットワーク通信が向上する効果が期待できます。
2000年スケールフリー・ネットワーク
極端に経路が集中するノードと、そうでないノードとが存在するスモールワールドのことで、こちらも自然界によく見られる構造をしています。
逆説的になりますが、「そうなりがち」なネットワーク構造とも言えます。
雷の光跡が、まるで血管や樹のような枝分かれの仕方をするように「そうなりがち」なネットワークはある意味で「効率の良い経路」という場合があります。
粗々にトピックを挙げてみましたが、これからはやはりAIを活用した経路探索などが革新を起こすのでしょう。
3次元的な情報で経路を作る時代が来る？
車にLiDARスキャナを搭載して3次元情報を取得したり、AIカメラで空間を保存するような取り組みが多く行われています。ドローン配送はもちろん、有人の配送だとしても様々な情報をAIに認識させ、新しい経路を考えさせるようなことがあるかも知れません。
しかし複雑性が高まろうが、配達NAVITIMEのように誰にとってどういう価値を生み出すべきか突き詰めるということを忘れてはならないとも思います。