物流業界と最適化技術を繋ぐオプティマインドの取り組み

はじめに

株式会社オプティマインドでは「世界のラストワンマイルを最適化する」というビジョンを掲げ、物流のラストワンマイルと呼ばれる街中での配送を行う事業者に対し配送計画を自動で計算し提案する Loogia（ルージア）というサービスを提供しています。

オプティマインドは2015年に名古屋大学大学院情報科学研究科計算機数理科学専攻（現在は情報学研究科の数理情報学専攻）の柳浦研究室に、当時修士学生として所属していた松下（現在はオプティマインドの代表）が2015年に設⽴した会社です。柳浦研究室では組合せ最適化という分野の研究を行っており、コンピューターでも解くのが難しい最適化問題という問題に対して、その難しさの解析をしたり、効率的に良い答えを出すようなアルゴリズムを作ったりということを主要な研究テーマとしています（研究紹介の記事もありますのでぜひご覧ください）。

この記事を書いている高田も柳浦研究室に所属しており、組合せ最適化問題に対するメタヒューリスティクスの設計・実装を行ってきました。現在は博士後期課程に在籍しながらオプティマインドにも所属し、研究で培った知識や技術を活用して事業に取り組んでいます。

本稿では組合せ最適化の研究を社会で応用することの難しさと、それに対してオプティマインドがどのように挑戦し、社会課題の解決に向けて取り組んでいるかを紹介します。

物流現場の課題

物流業界全体としていくつかの課題が認識されていますが、その中の１つとして人手不足が挙げられます [1]。また物流の中でもラストワンマイルと呼ばれる配送現場では深刻な人手不足に悩まされています。ここでのラストワンマイルとは、サプライチェーンでの最終拠点からエンドユーザーへの物流サービスのことを指します。近年ではより広義に捉え、消費者が生活圏の街中で見かける配送全体を指すこともあります。つまり、個人宅への宅配や小売店へ商品を卸す配送などが含まれます。

物流のラストワンマイルにおける人手不足には複数の要因が考えられます。例えば細かい時間指定や当日配送など配送サービスの品質向上や、電子商取引(electronic commerce, EC)の発達により小口の配送が増えていることなどにより、時間あたりの配送効率が下がる傾向にあります。一日の配送先をどのドライバーに割り当てるかということやどういう順番で配送するかということは、配車係や配送ドライバーがノウハウに基づいて手作業で行っている現場が多く存在しており、時間がかかる上に効率的な配送計画を組むこと自体が非常に難しいものです。また配送中は時間指定への遅れが起きないかといったことに気を配る必要があることや荷物の取り扱いへの要求が高いことなどがあり、働き手にとって負荷が高いものでもあります。

このような課題を解決するために近年では物流業界でもAIやIoTなどといった新技術を導入する必要性が認識されています。

配車最適化システム

上記のような課題を乗り越えるための重要な解決策の一つとして、配車業務をシステム化することで配送ルートを最適化し、現在の人員で配送できる箇所数を増やすことが考えられます。これを本稿では配車最適化システムと呼ぶことにします。配車最適化システムの根幹を担う技術である組合せ最適化の研究は古くからなされており、「どの配送先をどの車両がどの順番で訪問するのが最も効率的か」という問題は配送計画問題（vehicle routing problem）としてモデル化されています。これらの研究成果を活かした様々な配車システムが1990年代から徐々に出現してきましたが、配送の現場ではまだまだシステム化は進んでおらず、人間が紙の地図の上で配車係のノウハウに基づいて配送計画を組んでいることが多いのが実状です。

現場視察やドライバーへのヒアリングなどから、配車システムが現場に普及してこなかった要因として大きく3つあると考えています。それは価格、二点間経路（距離行列）の質、そして制約条件の考慮です。

2000年代ごろまでの配車システムはオンプレミスでの構築が主流であり、初期導入費や保守メンテナンス費が高額となりやすかったため、企業によっては導入までの障壁が高い場合がありました。現在はクラウド技術の普及やSaaS (Software as a Service) といわれるビジネスモデルの台頭により従量課金制のシステムも増えてきましたが、未だに配車システムを従量課金かつ低価格で提供する企業は多くはありません。

二つ目の要因は二点間経路（距離行列）の質です。配車計画を作る（配送計画問題を解く）ためには、全ての点間の距離行列を与える必要があります。つまりN箇所の訪問先がある場合は O(N²) の組合せの経路が必要です。また時間指定やドライバーの勤務時間などを考慮するためには距離だけではなく移動時間も算出する必要があります。既存のシステムでは緯度経度から直線距離を計算したり移動時間を手で入力したりと、実際にその通りに配送することが難しいものが多くあります。そのため従来の配車最適化システムはあくまでシミュレーションツールとして必要なドライバー数の算出や配送拠点の配置決めなど、現場のオペレーションのためではなく戦略上の意思決定に用いられるような使い方が多くなされてきました。

配車システムの普及を阻害する三つ目の要因は制約条件の考慮です。いかに効率的な配車計画が組まれたとしても、その現場で求められる制約条件（例えば配送先の時間指定やトラックの積載量上限など）がすべて考慮されていなければならず、使用するアルゴリズムに一つでも考慮できない条件があれば実際に運用することはできません。

それら一つ一つを考慮できるようにアルゴリズムを拡張していく必要がありますが、既存の機能との整合性を保ちつつ、さらに計算時間がかかりすぎないように効率性を維持しなければならないため、開発のコストは非常に高いものとなります。

これらの価格、計画の質、制約の考慮といった問題により、組合せ最適化の分野において配送計画問題やその派生が多く研究されているにも関わらず、未だに現場で活用されきっていないという現状があると我々は分析しています。

オプティマインドの取り組み

株式会社オプティマインドは、組合せ最適化を学ぶ学生が立ち上げた会社であり、組合せ最適化技術をコアとしながらも、データ解析やWeb技術、ITインフラなど複数の高度な技術を組み合わせることで前節で述べたような問題の解決を試み、最適化技術を活かして物流業界や社会全体をより良くしたいというビジョンを掲げて活動しています。本節では先に挙げた問題のそれぞれについてオプティマインドがどのように対処を行い解決に向けて取り組んでいるかということを紹介します。

価格の問題への対処

Loogiaのシステムの裏側はすべてAWS (Amazon Web Services) のようなクラウドインフラを提供する企業のサービスを用いて構築されています。なるべく自社でサーバーなどの資産を保有せず、サービス提供に必要な計算リソースやストレージなどは必要な分だけを適宜仕入れることで、提供価格も使用する分だけ課金するという仕組み（従量課金制）を実現できています。これによりLoogiaのユーザーは事業の規模や資金面の状況によらずサービスの導入がしやすくなっており、さらに一部の事業所や一部の社員だけで使うといったスモールスタートがしやすいことで導入の障壁が下げられています。

2021年現在ではクラウドインフラを用いたシステム構築は一般的な考え方になっており、様々なサービスがSaaSと呼ばれる形態にて従量課金制での利用ができるようになってきています。しかしLoogiaは最適化アルゴリズムを中核としたサービスであり、一度の計算で大量の計算リソースが求められたりする一方で小規模な計画を数秒で計算してほしいという要望があったりするため、一般的なサービスと比較して従量課金を実現しづらいという特徴があります。

例えば小規模な計画を数秒で計算してほしいという要望に答えるために、ある程度余裕を持った量のサーバーを待機させておくというアプローチが考えられます。しかしLoogiaで扱っている配送計画問題（およびそれを拡張した問題）はNP困難に属する問題であり、現実的な時間でよい解を求めるようなヒューリスティックアルゴリズムが必要とする計算リソースの量は、一般的には入力された問題例の規模によって大きく変動するという特徴を持っています。そのため大規模な計画も捌けるようなスペック・台数のサーバーを待機させておくとコストが増大してしまいます。逆に待機する数を減らし過ぎると突発的に大きな問題例が入力された場合に待機しているサーバーのすべてが使われてしまい、余裕がなくなってしまうということが起きます。

以上のような課題があるため、オプティマインドでは組合せ最適化アルゴリズムの特性とユーザーのニーズの双方をよく理解した上で、アルゴリズムやインフラ、サービスとして提供する内容、お客様への説明方法などをトータルで設計することで、サービスの利用者と提供者がどちらも満足できるような状態を実現しています。

二点間経路の質の問題への対処

先に書いたとおり、実際に配送できる計画を立てるためには二点間の移動経路とその所要時間を精度高く求める必要があります。しかし各道路の移動時間は一般にデータとして公開されてはおらず、そもそもその時の道路状況によって変わるなど不確定要素も多いため、移動時間をどう見積もるかというのは非常に難しい問題です。

そこでLoogiaでは実際に自動車が走ったときのデータを収集しそれらを統計的に処理することで道路ごとの走行速度を算出しています。自動車に備え付けられたドライブレーコーダーやLoogiaのスマートフォンアプリなどを通じて時刻と緯度経度の系列データを取得することができます。それらのデータと地図データとを突き合わせることで、どの道を走行しているデータなのかという判定を行ったり、道路の平均速度を算出したりすることができます。

ではデータさえあれば速度は簡単に算出できるかというとそういうわけでもありません。例えば、交差点の信号機の状態などによっても平均速度は大きく変わるため、ある道路はある自動車が10秒で通過しているがある自動車は1分かかっているなどといった状況がありえます。その場合はどのデータを参考にすればよいかということは簡単には決められません。このような場合のアプローチとして、例えば平均速度のデータとしては信号機を無視したものを算出し、経路探索アルゴリズム側で交差点で減速および停止する場合の期待時間を加味するなどといったことが考えられます。もちろん他にも様々な問題が存在しますが、データ解析とアルゴリズムの両方の技術を持っているからこそ、それらを組み合わせたシステム全体の設計を行うことができ、より現実に近い移動時間の算出が可能となっています。

また走行実績のデータは日本中のすべての道路に対して簡単に十分な量が得られるわけではありません。例えば宅配業者が配送計画を立てるためには住宅街の中の道路の走行速度情報が必要ですが、Loogiaのスマートフォンアプリを持った大量の自動車が日本中の住宅街のすべての道路をくまなく走るという状況はまだ考えづらいといえます（早くそうなってくれると嬉しいですが）。また日本中の自動車のうちオンラインでデータを収集できるものを考えたとしても十分なデータがある保証は無く、そもそもそのすべてのデータを手に入れることも自動車メーカーのセキュリティ基準やコストなどの面を考えると簡単なことではありません。

では少ないデータを元に解析をしてしまった場合にどうなるでしょうか。実際に通行したデータが非常に少ないような道路がある場合、そのデータを元に解析を行うとその道路だけ周りの道路と比べて走行速度が早過ぎたり遅過ぎたりということが起きえます。するとその速度情報を元に最短経路探索を行った場合、不自然に寄り道したり迂回したりする経路が出力されることになります。またそもそも実績データが無い道路に対しては速度を定義することすらできず、計画を立てることすら不可能となってしまいます。

これらの問題があるため、Loogiaでは道路ごとの速度の不自然なばらつきが起きないような工夫をしたり実績データが存在する道の特徴を分析することで道路の特徴から速度を推定する予測モデルの構築も行ったりしています。そうすることで日本全国の道路に対する走行速度を精度高く算出することができています [2]。

多様な制約を求められるという問題への対処

配送の現場で実際に使える計画を作るためには、求められる多様な制約を考慮できるアルゴリズムを作る必要があります。問題をモデル化しそれを解くアルゴリズムを設計することも大変難しいですが、それを既存の機能と不整合を起こさないように設計することも非常に難易度の高いことです。考慮できる制約が増えるほどアルゴリズムは肥大化していき、設計で気にしなければならない機能の組合せは爆発的に増えていくため、自社サービス・製品として継続的に開発運用していくには大きなコストがかかります。そこでオプティマインドではアルゴリズムを “シンプルに作る” ということを心がけています。

継続的な開発や運用に必要なコストを抑えつつアルゴリズムを拡張することは簡単ではありません。特に計算の効率を考えて複雑なデータ構造やアルゴリズムを組み合わせているような場合、その機能単体でもメンテナンスが大変な上に、違う機能を追加することになった場合はその複雑な機能をよく理解した上でさらに新規の要件を組み込むという難しい設計をする必要に迫られます。そこでオプティマインドでは計算の効率の目標値を現実的な妥協ラインに定めることで、必要以上に凝った実装をすることを避ける工夫を行っています。アルゴリズムは基本的には速ければ速いほど良いのですが、実際にサービスとして提供する場合は計算が0.1秒で終わっても3秒かかってもユーザーの体験としては大きく変わらなかったりします。また大きな問題例（例えば車両数が数十台、配送先数が数百箇所を超えるようなもの）については、システム化される前は人が何週間もかけて計画を立てていたりします。そのような問題例に対してシステムが無理に10秒で答えを出さなくても、現状のオペレーションにおいてユーザーが大きくデメリットを感じる場合はそこまで多くはないはずです。それよりも、アルゴリズムがシンプルになることで開発のスピードが向上し、ユーザーにとって無くてはならない機能がより早く追加されていく方が大きなメリットとなりえます。（コンピューターならどんな問題でも一瞬で解けるのが当たり前だと考える方もいるかもしれません。そういった場合は最適化問題というものがどういうものなのかということを丁寧に説明し理解してもらう必要があります。）

ご注意いただきたいのは我々もこのようなアプローチが常に正しいと思っているわけではなく、あくまで今のオプティマインドにとって必要なことを考えた上での選択に過ぎないということです。配車最適化システムが一般に普及しきっていない現状では、いかに早く現場にフィットするサービスを作るかということが重要であり、一つのアルゴリズムにいかに早く必要な機能を追加し続けるかということに重きを置いているということが背景にあります。今後の状況によっては（例えばよりシビアな性能が要求がされるようになったり速さや安さの勝負になったりした場合は）、一部の用途に特化した複雑なアルゴリズムを実装する必要も出てくると思われます。技術や研究を社会へ応用する上では研究のすばらしさを盲目的に信じるわけではなく、逆に理論をないがしろにして表面を取り繕っていればいいわけでもなく、研究も社会もよく理解した上でいかにそれらをうまく結びつけて価値のあるものを作っていくかということが重要であると考えています。

さいごに

物流業界の中でも特に配送現場においてはIT技術があまり普及しているとはいえません。特に組合せ最適化を応用した配車最適化システムは長年研究されてきたにも関わらず、その価値を社会において十分に発揮しているとは言い難い状況です。株式会社オプティマインドでは、最適化を社会に応用する上でビジネス的な難しさと技術的な難しさの両方をよく理解し、それらにしっかりと向き合うことでそれぞれの難しさを乗り越え、物流業界で働く人や物流サービスを受ける人をより幸せにしていきたいと考えています。またこのような活動を通して社会がよりよくなるだけでなく、組合せ最適化という技術がより広く理解され、この研究分野の発展の一助となることができれば嬉しく思います。

筆者紹介

高田陽介

数理情報学専攻博士後期課程
株式会社オプティマインド最適化チームリーダー
- オプティマインドでは一緒に働く仲間を募集中です（詳しくはこちら）
個人ホームページ: http://www.co.mi.i.nagoya-u.ac.jp/~takada/ja/

参考文献

[1] 国土交通省. 総合物流施策大綱. https://www.mlit.go.jp/seisakutokatsu/freight/butsuryu03100.html
[2] 株式会社オプティマインド. 道路走行可能速度推定装置及び道路走行可能速度推定プログラム. 特許第6951672号. 2021年3月18日.