なぜ物流業界では最適化が進まないのか？

Logpose Technologies

こんにちは。株式会社Logpose Technologiesの中原と申します。

弊社では、運送会社の方が簡単に使えるAI配車アシスタントLOGを提供しています。LOGは、高速に配送計画問題を解くことができるアルゴリズムを搭載したWebシステムです。

配送計画問題は、配送センターから複数の顧客へトラックなどの輸送手段を利用して、巡回輸送を計画する問題です。配送計画問題は、1964年にセービング法（Clarke & Wright法）[1]が提案されてから、すでに50年以上に渡り、積極的に研究されています。しかし、未だに物流業界の現場で求められる配送計画問題を完全に解決できるほどのシステムができていないのが現状です。

この記事では、まず配送計画問題について紹介します。そして、なぜ物流業界で最適化システムが導入されてこなかったのを考えてみます。最後に、弊社で扱うAI配車アシスタントLOGも合わせて紹介します。


1. 配送計画問題

配送計画問題（VRP：Vehicle Routing Problem）は、さまざまな制約条件のもとで、複数の車両を利用して全ての客をちょうど一回ずつ訪問するような巡回路（ルート）の中で、コストが最小のものを求める問題です。

図の例では、荷物を積むデポが1箇所、トラックが2台、配達先が8軒あります。配送時間（または配送距離）をコストと考えると最も配送時間（または距離）の少ないルートを求める問題になります。
ただし、制約条件としては、トラックの積載量に基づく容量制約、そして配達先の到着時間が指定されている時間枠制約などがあります。
また、実際に配送計画を立てる場合には、複数のデポを扱う必要があったり、さらに多くの制約条件を考慮する必要があります。

図1
図：配送計画問題


2. 様々な制約問題

例えば、Braekersらの研究[2]では、2009年から2013年に投稿された配送計画問題に関する144本の研究論文をレビューし、延べ15種類の制約条件が考慮されていることを示しています。
その中でも最も多いのは、容量制約(CVRP)で、約90%のアルゴリズムで考慮されており、次に時間枠制約(VRPTW)が約40%、異なる車種の車両(HVRP)が約19%、そして、複数のデポ(MDVRP)は12.5%です。
他にも、ミルクランと呼ばれる、集荷と配達を同じルートに含め、同一の車両で両方を扱う問題(VRPPB)などがあります。更に、ドライバーの労働時間を考慮した問題、時間によって移動時間が変動する問題(TDVRP)、リアルタイム配送計画の問題(DVRP)、そして、周期的な配送計画で顧客への配達は別日に行う問題(PVRP)など、非常に多岐にわたる条件を考慮した配送計画問題が研究されています。

3. 配送計画問題の難しさ

トラックが1台で、全ての客をちょうど一回ずつ訪問するようなルートの中で、コストが最小のものを求める問題を巡回セールスマン問題（TSP)と呼びます[3]。TSP自体が非常に難しい問題（NP困難）として知られており、計算量的に困難な問題です。

配送計画問題は、複数のトラックを扱う問題であり、TSPを包含していることからもさらに難しい問題になります。また、実運用を考えると上記で示したようなさまざまな制約を加味する必要があります。しかし、これまでの研究では、一部の制約を考慮した配送計画問題は検討されていますが、全ての制約を考慮した解法はまだありません。

また実際には、宅配業者や運送会社が扱う配送計画問題は、配達先の客数が1,000以上になる場合もあり、このような大規模な問題に対して、厳密な最適解を計算することは非現実的です。そこで、近似解法によっておおよそ正しい解を求める方法が重要になってきます。我々が開発しているLOGでも、近似解法を採用しています。

4. 実務と研究の垣根

配送計画問題は様々な条件を考慮して、長年に渡り研究が行われてきたにも関わらず、未だに運送会社では、使える自動配車システムの導入が望まれています。実務で必要とされる自動配車システムとはどういうものなのでしょうか？

実際の配車計画では、労働基準法などの、トラックドライバーの労務規定を守り、貨物の性質（冷蔵冷凍など）を考慮した上で、荷物とトラックをマッチングし、最適な輸送ルートを考える必要があります。配車システムを導入していない企業では、経験豊富な配車担当者が時間をかけて配車計画を作成するという極めて属人的な業務を行っています。

NECソリューションイノベータが実施した「物流や配送、物流システム（TMS/WMS）に関するリサーチ結果2021」[4]では、300社中、輸配送管理システムを利用している企業が約50%、人手による配車計画は35.7%でした。ただし、従業員が100人未満の企業になると、輸配送管理システムの利用は、約20％まで下がります。つまり、中小の運送会社では、配車システムが受け入れられていないことを示しています。ある程度の荷物量がなければ、導入コストに見合うメリットが得られないため、中小企業におけるコストの問題は大きいと思いますが、それ以外にも導入を妨げている理由としては、以下のような点が考えられます。

  1. 商慣習があり、さらに細かい制約条件などを考慮する必要がある。

  2. システムが複雑で使いこなすことができない。

1.は、これまでの配送計画問題でも様々な制約条件を考慮した研究が行われていますが、実務ではさらに細かい条件を考慮する必要があります。例えば、これも属人的ですが、荷主によっては、配達NGのドライバーがいたり、荷物によっては担当するドライバーが決まっていたりもします。このような商慣習的な制約を考慮した研究は、研究成果としては大きくないため、研究の世界では見過ごされがちになりますが、このような個別の制約を導入できることは実務では非常に重要になります。

2.は、弊社でも、サービスを利用していただいている企業様に配送結果のフィードバックを伺ってみると、パラメータのチューニングによって対応できる部分が多くあることがわかっています。しかし、そのようなチューニングを配車担当者が簡単にすることは難しいため、より簡単に利用できる使いやすいシステムに改善して行くことが重要になります。これは、使いやすいUIをどのように提供できるかという問題でもあり、ヒューマンインタラクションの研究などにも関係してきます。

実務で利用される配車システムを提供するためには、これまでの最適化研究で提案されてきた配送計画問題のアルゴリズムを実務のレベルまで落とし込み、システムとして使いやすいUIを提供できるかが重要になります。それには、高度なアルゴリズム理解と開発能力に加えて、エンジニアリング力が必要になってきます。

5. LOGが扱う制約条件

弊社が開発したAI配車アシスタントLOGでは、高精度な配車アルゴリズムに加え、柔軟に制約条件を追加できるシステム設計のもと、既に以下の制約条件を同時に加味した配送計画問題を高速に解くことができます。

- [ O ] 容量制約
- [ O ] 時間枠制約
- [ O ] 異なる車両タイプ
- [ O ] 複数のデポ
- [ O ] ミルクラン
- [ O ] 労働時間制約
- [ O ] ドライバー指定配達
- [ O ] 積み置き（トラック荷物を積んだまま別日に降ろす）
- [ O ] 休憩時間
- [ O ] 移動距離の上限下限

今後はさらに研究開発を進め、以下の制約にも対応していく予定です。
-  時間による移動時間の変動
- リアルタイム配送計画

仲間募集！

世界中の荷物情報を整理し、流通を最適化するというエキサイティングな課題に取り組んでいる私たちですが、実現したいことは次から次に出てきてしまい、一緒に働く仲間を多く必要としています。自分が持っているスキルを存分に活かして、ぜひ一緒にこの課題に取り組みませんか？ご興味のある方は、採用サイトよりご連絡ください。


参考文献

[1] Clarke, G. and Wright, J.R.Scheduling of Vehicle Routing Problem from a Central Depot to a Number of Delivery Points. Operations Research, Vol.12, pp.568-581, 1964.
[2] Kris Braekers, Katrien Ramaekers, Inneke Van Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering, Vol. 99, pp. 300-313, 2016.
[3] ウィキペディア：巡回セールスマン問題（最終アクセス2021/12/28) 
[4] NECソリューションイノベータが実施した「物流や配送、物流システム（TMS/WMS）に関するリサーチ結果2021（最終アクセス2021/12/28）


この記事が気に入ったらサポートをしてみませんか？