物流現場サイドから見る数理最適化やヒューリスティックアルゴリズムを使った配車計画の歴史

なぜ書こうと思ったか

2000年代以降、物流業界では、数理最適化やヒューリスティックアルゴリズムを利用した配車システムを活用して大きな成果をもたらしており、現在でもさらなる進化を続けています。
最近、多くの皆さんから、アルゴリズムの違いは？どのアルゴリズムが一番いいの？量子コンピューターで世界は変わる？という問いを頂く機会が非常に多くなったと感じてます。正直なところ、現在利用されている「コアとなるアルゴリズムはそれほど進化していない」と考えているので、それを書いてみます。

利用され始めたのは2000年以降

そもそも、配送最適化問題のもとは、
　「第2次世界大戦時に前線に武器、食料などのリソースをどう供給していけばよいか？」
というのを考えるところから始まっています。コアとなる考え方は、80年も前から存在するものです。
その後、
　・最適ルートを計算する基礎となるDijkstra法
に加え、
　・巡回セールスマン問題（ＴＳＰ）
　・Vehicle Routing Problem（ＶＲＰ）
を解く様々な手法が考え出されてきました。研究分野では、かなり昔に確立されている手法です。

その後、80年代後半のカーナビの登場により、ルート計算機能の実用化され、地図を利用した出発地から目的地のルート計算ができるようになりました。地図データのサイズは、当時のストレージでは膨大なサイズであり、計算するＣＰＵも高性能ではなかったため、リアルタイムの状況変化に応じて対応を迫られる物流分野で利用されることはほとんどありませんでした。これは、ＴＳＰ、ＶＲＰでも同じで、毎日の配送をコンピュータに考えさせるには、当時からするとものすごいスペックのコンピュータが必要となるため、ほとんど普及していなかったかと思います。

Windows95等の登場以降、PCの普及により、この問題は少しずつ改善されました。PCを使ってルート計算ができるようになり、特定のアルゴリズムを使えば、TSPやVRPの問題を解くことができるようになりました。しかし、当時のPCの性能では、計算に一晩かかることもあり、そのため、前日の荷物の情報を手で入力して、配車計算を回して、翌朝確認という使い方が主な方法でした。

第一世代　【2000年代前半以降】　

先程も述べたように、第一世代は配送先のデータをPCで手で入力して、システムに取り込み、車両の条件をもとに各車両の配送ルートを決めるものでした。
　主に前日までに荷物情報が整う業態での利用、
もしくは、
　固定ルートを策定するために数理計画アルゴリズム
を利用しているケースが多い状況でした。

また、スタンドアロン式のアプリケーションが主流で、アプリケーションがインストールされたＰＣの数も限られていたので、ご担当者さんが入力データを手入力するとなると、かなりの時間と負荷がかかり、取り扱えるデータの量、つまり、配送先数、車両数なども限定されたものでした。

第二世代　【2000年代後半以降】

クラウドサービスの登場により、大きく状況が変わってきます。
ＰＣ側にアプリをインストールせずに利用できるようになることで、多くの方が利用できるようになりました。さらに、サーバー側で様々なデータを流通できるようになったため、入力の手間が大きく削減できるようになりました。さらに、ハイスペックのサーバーを安価に利用できることで、計算時間も大きく改善したことで、利用シーンが大きく拡大しました。つまり、取り扱えるデータ、配送先、車両数のデータも一気に拡大し、身近に利用できるようになりました。

しかしながら、通信回線の速度向上により情報密度も格段に大きくなったため、入力データに入ってくる条件の数も大きくなり、車両に積む荷物の種類、訪問先の数、時間帯などなど、システムでベストなルートを導き出すには、大量の種類データを準備しておく必要が出てきました。

第三世代　【2010年代以降】

2010年頃から、物流現場にもスマホやIoT機器が普及していきます。これまではロット単位、パレット単位で配送を行っていたものが、個口、商品単位でのバラで配送する荷物の管理が可能になります。
こちらにより、１配送先につき納品できる商品の種類や数がかなり細かく配送でできるようになり、配車計画に求められるインプットの数が一気に増大します。サーバーの計算スペックもさることながら、アルゴリズムも進化しているものの、大量のインプットに耐えられるアルゴリズムが求められるようになります。こうなってくると、最適を求めるよりもいち早く答えを返し、ドライバーを出発させる方が優先なケースも多く出てきました。

第四世代　【2020年代以降】

ここまで、第一世代から第三世代まで書いてきましたが、ここまでは発荷主、着荷主の情報を元にした入力データを存在が前提でした。すなわち、指示通り運ぶことを最適化する狙いがありました。
しかしながら、第四世代になるとドライバーのノウハウを生かした生成AI、機械学習を活かしたデータが入力となってきます。
たとえば、
　・同じ住所に同じ建物が１００件以上ある
　・駐車位置がない箇所に運ぶ場合のルート
　・不在傾向
　・表札のない個人宅
等ドライバーが一度行かないとわからないケースについては、ドライバーのノウハウが不可欠です。
また、BtoB配送においても、
　・納品する際のお作法
　・待ちが発生する際の場所
配送指示書に書かれていない数多くのデータを活用していくことに進化していきます。これらの条件は、日毎、時間帯毎、季節毎ですべて異なるケースがありますので、これらをデータ化して計画に生かしていくようになっていきます。究極は、着荷主が注文せずとも、そろそろ在庫がなくなりそうなところをめがけて訪問をするドライバーにリコメンドできる状態です。このレベルになってくると、どれだけのインプットをどのタイミングで利用するか？こちらがユーザー目線で見た時に最適なものになると考えます。

数理最適化ヒューリスティックアルゴリズムの役割

よく数理最適化やヒューリスティックアルゴリズムは、昔よりも計算速度上がったと言われると評価される傾向があると思います。もちろん計算速度は重要です。これは、時々刻々と入力情報が変化する中、最適な解を計算することは非常に重要です。ただ、時々刻々と入力情報してしまうと現在導き出した最適な解が１分後にはそうではなくなっているケースも生まれてきます。だからと言って、最適解を求める意味はないというつもりはないですが、人の経験値で配車が組めるのであれば、無理にアルゴリズムの導入をする必要はないと思います。つまり、人が考えられない入力情報をいかに多く扱えるか？という領域において、既存のアルゴリズムをどんどん活用すべきだと考えます。

量子コンピュータは世界を変えるか

量子コンピュータの考え方は、複雑な問題を高速に解決する手段に対しては、非常に有効だと思います。しかしながら、現時点では、物流現場で取り扱うデータの種類・組合せの制約条件やドライバーノウハウのパターン数に比べれば、まだまだ、数多くのパラメータを取り扱うことはできないと思います。今後ハードウェアが進化し、安価に高性能なものが出てくるかと思いますので、あと10年もすれば追い付いてくると思います。だたし、一方で様々な技術の進化により、さらなる情報量の増加する可能性も十分あり、量子コンピュータを上回るものが出てくるのも否定できません。ドライバーの体調に合わせたルート計画、作業計画などなど、ドライバーを支援する様々な機器の進化によって、もしかしたら、もっと違うコンセプトの世界観になるかもしれせん。

まとめ

具体的な事例を書きにくいので抽象的な表現でわかりにくかったかもしれませんが、整理すると数理計画アルゴリズムを利用した配車計画はこのように世代分けされると思います。

第一世代　PCで配車計画。紙で注文を打ち込む　＜デジタル化＞
・ｵﾝﾌﾟﾚ/ｽﾀﾝﾄﾞｱﾛﾝが主流。大手企業が利用！
・1車両あたり10件以下の配送ルート作成
第二世代　受注データのデジタル化推進　＜クラウド化＞
・データ連携がしやすくなり中小企業も利用可能に！
・種類が少ない商品の30件程度の配送ルートの作成
第三世代　IoT,スマホを活用し荷物単位の最適化の実現＜IoT＞
・小口配送・個宅配送はこのレベルまで
・多品種のバラ商品を50件以上配送ルート作成
第四世代　ドライバーノウハウを活用した配送最適化の実現＜AI活用＞
・生成AIなども含む、蓄積データの活用が進む
・AIを使いこなしたドライバーが能力を最大限発揮

物流と言っても、製造、食品、薬品、農業、建材資材、ガス、小売、流通、個配の動脈物流に加えて、産廃、廃プラなど静脈物流、構内、物流センター内の構内物流と、すべて違う顔を持っていると思います。すべての業界が同じ世代にいるわけではない思いますが、アルゴリズムで解決に向けた議論すべきはこのような観点だと考えます。