技術広報誌 OKIテクニカルレビュー

省エネ ソリューション

物流のCO2削減に貢献する配送ルート最適化技術

物流業界では社会課題として労働力不足が大きくクローズアップされているが、カーボンニュートラルへの対応も求められ、取組みが加速している。トラックのEV化が代表的な例だが実用と普及にはまだまだ時間を要する見込みである。一方で効率的に輸配送することによりCO2排出量を減らす取組みも注目されている。特に物流会社の9割以上を占める中小企業の中には業務のIT化が進んでいないところもあり、アナログで非効率的なやり方が多く残る。この部分を改善することで、カーボンニュートラルに貢献する。

OKIは今回、物流の店舗配送業務に係るCO2排出量削減を目指し、効率の良い配送を実現する配送ルート最適化技術を開発した。実際の配送現場に本技術を適用した際のCO2排出量削減効果を検証したので報告する。

配送ルート最適化

(1)店舗配送業務とは

物流輸送業務は幹線輸送から支線輸送まで多岐にわたる。幹線輸送とは周辺エリアの大量の荷物を集めたデポ(配送拠点)から、他のエリアのデポまで輸送することである。支線輸送とはエリア内の集荷配送を行うことである。本稿では、支線輸送の一形態である店舗配送に着目する。

図1は物流企業が日々行っている店舗配送を模式的に表している。物流企業は複数の車両を使い、デポから複数の配送先へそれぞれ指定された量の荷物を運ぶ。荷物量の単位は重量や体積のほか、定形の容器何個分と数える場合もある。各配送先への配送時間帯が指定されていることも多い。車両がデポを出発し、いくつかの配送先を巡回して再びデポに帰着するまでを1便と数える。車両は1日に複数便運行する場合もある。車両が1便で配送できる荷物量の上限、すなわち最大積載量が定められ、この最大積載量を超えて配送することはできない。

車両が配送先を訪問する順番を、ここでは配送ルートと呼ぶことにする。図1の同色同型の矢印で結ばれた巡回路が配送ルートの一例である。各車両が、どの配送ルートで配送するかを記したものを配送計画という。各配送先が要求する荷物を過不足なく配ることができる配送ルートは多数存在する。全車両が走行する距離の総和(総走行距離)は配送ルートによってそれぞれ異なる。総走行距離が長くなるほど燃料コストが上昇し、同時にCO2排出量も増加する。

配送ルート最適化とは、本稿では総走行距離が最小となる配送計画を立案することと定義する。配送先や需要量などの条件がほとんど変化しない場合、配送計画立案は最初に一度だけ行い、あとは毎回その計画に従って配送すれば良い。逆に条件が毎回変動するような場合、最適な配送ルートも変化するため、基本的に毎回配送計画を立案する必要がある。いずれの場合にも、配送計画の立案は物流会社の配車担当者が経験や勘に基づいて人手で行っていることが多い。人手による計画は必ずしも効率的ではないので、これを改善することが課題である。


図1 店舗配送

(2)分割配送とは

分割配送とは、ある配送先に2台以上の車両で荷物を運ぶ配送手段のことである。分割配送と、分割しない通常配送との違いを図2に示す。この例では車両の最大積載量は4個とし、三つある配送先へ配送すべき荷物数はそれぞれ2個、4個、2個、デポ及び配送先間の距離は図中に示した値とする。通常配送では三つの配送先それぞれに個別の車両が訪問して配送する。それに対し、分割配送では中央の配送先へ配送する荷物を2個ずつに分割し、2台の車両で配送できる。そうすることでより少ない車両数でより短い総走行距離の配送が期待できる。一方、分割配送ではどの配送先の荷物を分割するか、またどの比率で荷物を分割するかといった通常配送では現れない項目も考慮する必要があるため、配送計画立案が複雑になるというデメリットが生じる。この複雑な条件を加味した配送計画を人手で立案するのは困難であるため、機械的に計算する手法を確立することが課題となる。


図2 通常配送と分割配送

(3)分割配送路問題定式化

上述した最適な配送計画を立案するという問題を、数理最適化を用いて解決することを考える。数理最適化とは、与えられた制約条件の下で目的関数の値を最小(若しくは最大)にする解を求める手法である(参考文献1)。数理最適化を用いて現実問題(ここでは配送計画立案)を解決するためには、まず、現実問題を数理最適化問題に定式化する必要がある。数理最適化問題は、定数、変数、目的関数、制約条件の要素からなる。

分割配送を適用した最適な配送ルートを求める問題は「分割配送路問題」と呼ばれ一般化されている(参考文献2)。分割配送路問題を定式化すると以下の式(1)から(14)となる。

(定数)
m:車両台数
n:配送先数
b:最大便数
hi:配送先iに訪問できる最大車両数
i,j:デポまたは配送先を表す添え字(0、n+1はデポ、その他は配送先)
v:車両を表す添え字
f:便を表す添え字
di:配送先iの需要量
cij:配送先iからjへ移動する際の距離
ei:配送先iの最早到着時刻
li:配送先iの最遅到着時刻
tij:配送先iからjへ移動する際の所要時間
q:車両の最大積載量

(変数)
uivf:車両vf便目に配送先iに到着する時刻を表す実数変数
wvf:車両vf便目を使って配送するか否かを表す0-1変数
xijvf:車両vf便目に、配送先iからjへ移動したか否かを表す0-1変数
yivf:車両vf便目に配送先iを訪れたか否かを表す0-1変数
zivf:車両vf便目に配送先iへ配送する荷物量を示す整数変数

(目的関数)

式(1)は本問題の目的関数である。車両の総走行距離を最小化することを意味している。

(制約条件)

式(2)及び(3)は各車両の便を1便目から順番に詰めていくことを示す。

式(4)及び(5)は配送先iに1台以上hi以下の車両が訪問することを示す。

式(6)は配送先iへ配送する荷物量と配送先iの需要量が一致することを示す。

式(7)は配送先iを訪問する車両だけがその配送先へ荷物を配送できることを示す。

式(8)は1台の車両が1便で配送する荷物量が最大積載量以下であることを示す。

式(9)及び(10)は配送ルートが巡回路であるという制約である。ある車両がデポまたは配送先を訪問する場合、その前後に必ずどこかの配送先またはデポを訪問していることを示す。

式(11)はある車両が連続して二つの配送先を訪れる場合、各々の到着時刻の差は配送先間の移動時間以上であることを示す。

式(12)は1便目のデポ出発時刻を0であることを示す。

式(13)は2便目以降のデポ出発時刻が、直前の便のデポ到着時刻であることを示す。

式(14)は配送先iの到着時刻がei以上li以下であることを示す。

(4)配送ルート最適化ツール

今回、先述の定式化した分割配送路問題を計算機プログラムとして実装し、求解及び結果出力を自動で行う「配送ルート最適化ツール」を試作した。本ツールは、与えられた入力データ(定式化の定数に相当)に基づいて分割配送路問題を解き、配送計画を出力する。Python3(注1)で実装し、クラウド上の計算機(CPU動作周波数3.1GHz、4コア)で動作させた。問題の求解には数理最適化ソルバー「Gurobi Optimizer® 9.1(注2)」を用いた。

実証実験

配送ルート最適化ツール適用によるCO2排出量削減効果を検証した。今回、株式会社ロンコ・ジャパン殿(以下、ロンコ・ジャパン)の協力を得て、同社が実際に店舗配送業務をほぼ毎日行っている現場で実証実験を行った。

実験条件及び方法は以下のとおりである。対象となる店舗配送現場は国内のとある地域で、配送先は約50店舗で固定である。1日に1回配送を行い、各配送先の荷物量は日によって変化する。荷物は定形容器に入れられて配送されるため、荷物量の単位はその容器の個数とする。配送に使用する車両は15台前後で、すべて軽油を燃料とするディーゼル車である。配送計画の立案はロンコ・ジャパンの配車担当者が行った。その際、今回試作した「配送ルート最適化ツール」を利用した。ツールが行う最適化計算の計算時間は、業務の時間的な制約上、最長10分とした。立案した配送計画に従って実際に配送業務を行い、その際の車両の総走行距離を計測した。車両の走行距離はOKIのSaaS型ITSサービス「LocoMobi® 2.0(注3)」を用いて収集した走行軌跡をもとに算出した。比較対象として、上記とは別の日に配車担当者がツールを利用せず従来どおり配送計画を立てる場合の実験も同様に行った。

実験結果を図3に示す。図3は1回の配送で配る荷物の総数とその時の総走行距離の関係をプロットしたものである。荷物数は日々異なり、また総走行距離は荷物数に応じてほぼ線形に増加していることがわかる。今回の配送ルート最適化ツールを利用した場合、従来よりも総走行距離が短縮されていることがわかる。その効果の大きさは荷物数に依存し、荷物数が多いほど効果が高い傾向を示している。今回の実験では、荷物数の平均値は948個であった。この荷物数で代表させると、1回の配送当たりの今回と従来の総走行距離の差は平均して224km(従来総走行距離の5.1%相当)と見積もられる。この現場では年間通じて業務を行うので、年間に換算すると81,780kmに相当する。

最後にこの距離短縮効果をCO2排出量に換算してみる。参考文献3の調査によると、現在走行している大型トラックの燃費は1リットル当たりおよそ3kmである。また参考文献4によると、燃料である軽油1リットル当たりのCO2排出量は2.6kg-CO2である。これらの値を用いると、本現場での店舗配送業務に配送ルート最適化ツールを適用することで一日当たり193kg、年間に換算すると約70.4トンのCO2を削減可能と試算できる。


図3 実証実験結果

まとめ

OKIが研究開発中の配送ルート最適化技術を紹介した。本技術を実際の店舗配送現場に適用して実験した結果から、年間約70.4トンのCO2排出量削減につながると試算した。今後も継続してグリーン社会実現に資する技術を開発していく。

参考文献

(参考文献1)梅谷俊治:しっかり学ぶ数理最適化 モデルからアルゴリズムまで、講談社、2020年
(参考文献2)毛利裕昭・久保幹雄・森雅夫・矢島安敏:分割配送路問題-ラグランジュ緩和を利用した解法について、Journal of the Operations Research Society of Japan, vol. 39, No. 3, 1996.
(参考文献3)全日本トラック協会:トラック早わかり(14 その他)
https://jta.or.jp/ippan/hayawakari/14-sonota.htmlopennew_gray(外部サイト)
(参考文献4)平成十八年経済産業省・環境省令第三号「特定排出者の事業活動に伴う温室効果ガスの排出量の算定に関する省令」

筆者紹介

玉井秀明:Hideaki Tamai. 技術本部 研究開発センター AI研究開発部
川口勝也:Katsuya Kawaguchi. イノベーション事業開発センター ビジネス開発部

用語解説

数理最適化ソルバー
数理最適化問題を解くアルゴリズムが搭載されたソフトウェア。
LocoMobi 2.0
車両の位置情報などを収集・分析するSaaS型のITSサービス。車載器から送られてくる信号を路側センサーで取得することで車両の走行軌跡などを生成することができる。





  • (注1)Pythonは、Python Software Foundationの登録商標です。
  • (注2)Gurobi Optimizerは、Gurobi Optimization, LLCの登録商標です。
  • (注3)LocoMobiは、沖電気工業株式会社の登録商標です。
Get Adobe Reader
PDFの閲覧にはAdobe Readerが必要です。Adobe社のサイトからダウンロードしてください。

ページの先頭へ

公的研究費の不正使用および研究活動における不正行為等に係る通報も上記で受け付けます。

Special Contents

      • YouTube

      お問い合わせ

      お問い合わせ