HOME > アズビルについて > 会社PR > 会社紹介資料 > azbil Technical Review > 2020 > 組合せ最適化手法によるLPガス容器配送方法とその効果

組合せ最適化手法によるLPガス容器配送方法とその効果

1．はじめに

近年、物流業全般において、人手不足や長時間残業が深刻な問題となっており、経験やノウハウの少ない配送員が働きやすい環境を整備し労働時間を削減するなどの労働環境改善が求められている。

笹山ら^（1）によりLPガス容器の配送に関して、配送計画問題とIoTによりLPガス消費量を取得することで解決できることが提案されている。

本論文の構成は次のとおりである。2章でLPガス容器配送最適化の概要を説明し、3章でLPガス容器残量予測とLPガス容器配送計画の解法を説明する。4章で本手法を用いた実験結果を示す。最後にまとめを述べる。

2．遠隔検針導入によるLPガス容器配送効率化

本章ではLPガス容器の配送に関する配送計画問題に対し遠隔検針により得たLPガス消費量を基に解決する方法を述べる。

LPガス容器は空になる前に、ガスが充填された別の容器と交換する必要がある。充填済み容器の配送タイミングは、LPガス供給事業者が月1回の検針データを基に決定しており、データが少なく推定が困難であった。そのため使用中の容器内に多くのガスが残った状態で充填済み容器と交換されることがあり、配送コストの無駄、および、回収した容器に残るガスを考慮することにより不要な在庫が発生するなど、非効率なものであった。

この課題を解決し効率の良いLPガス容器の配送計画を得ることができる方法を提案する。

図1に提案する方法の概要を示す。LPガス容器配送計画を実行するには、毎日のLPガス消費量をIoTにより取得し、LPガス容器内のガスの残量がなくなる日を予測する。

次にLPガス容器内のガスがなくなる前にLPガス容器の回収/交換を行うLPガス容器の設置住所を抽出し、その住所へLPガス容器を配送する配送計画を作成する。

LPガス容器を配送する配送計画問題を解くにあたりこの問題の特徴を述べる。抽出した住所にLPガス容器を配送するには、配送車両のキャパシティの制約から、複数回LPガス容器の充填所に立ち寄り、充填済みLPガス容器を配送車両に積み込み、未回収/未交換の住所へ引き続きLPガス容器を配送する必要がある。この種の配送計画問題はMulti-Depot Periodic Vehicle Routing Problem^（2）と呼ばれる。

3章ではLPガス容器配送最適化を実現するために必要なLPガス容器残量予測方法およびLPガス容器配送計画方法について論じる。

3．LP ガス容器配送効率化の実現方法

3.1　LPガス容器残量予測

LPガス容器は空になる前に、ガスが充填された別の充填済みタンクと交換する必要がある。本章ではLPガス容器内の残量を予測する手法を説明する。

図2は本手法が想定する毎日のLPガス消費量とLPガス容器内残量の関係を示したグラフである。◇はLPガス消費量を示し、□はその結果としてのLPガス容器残量を示す。このグラフはLPガス容器満充填量を200LとしたときのN日経過時点でのLPガス消費量とLPガス容器残量の関係である。特に□のプロットでLPガス容器残量が負となっている領域については、3.2で述べるLPガス容器残量予測モデルで予測し外挿^（3）した結果である。

3.2　アンサンブル予測モデル

複数の予測器が同じLPガス消費量データを使って将来のLPガス消費を予測し、結果としてLPガス容器内の残量を予測する。

図3は3種類の予測器によるアンサンブル学習^{（4）（5）}による予測モデルの概要である。

ヒューリスティクス予測器はLPガス消費における曜日効果に着目した予測方法である。月曜から日曜の各曜日のLPガス消費量が一とおり得られたなら、7日先のLPガス消費量は直近の7日とほぼ同じであると仮定した場合はこの方法は簡単な方法だが高い予測精度が期待できる。

しかし、この方式は月曜から日曜の7日間を学習期間とした場合に、この学習期間内にカレンダー上の特異日が含まれる場合は予測精度の低下が懸念される。この予測精度の低下を改善する目的で図3のように異なる種類の予測器結果と組み合せることでLPガス消費量予測の予測精度の低下を回避することが可能となる。

線形予測器は図3に示すように異なる種類の予測器として使用する。

式（1）は一般的な線形回帰モデルを示す。

・・・（1）

ただし、LPガス消費予測において\(Y\)はLPガス消費量、\({X}_1\)は使用経過日数、\({X}_2\)はダミー変数化した曜日情報である^（6）。必要に応じその他の変数を説明変数\({X}_p\)に追加。この予測器はカレンダー上の特異日を説明変数として扱うことで特異日効果によるLPガス消費の変化に対応することが可能である。つまり、ヒューリスティック予測器に対してLPガス消費量の補正をすることができる。

非線形予測器は線形予測器と同様に図3に示す異なる種類の予測器として使用する。

式（2）は非線形モデルを示す。

・・・（2）

ただし、\(f\)は非線形モデルを表す。\(y\)はLPガス消費量、\(x\)は使用経過日数および曜日情報を示すベクトル、\(β\)はモデルのハイパーパラメータである。予測器は量的変数と質的変数を取り扱うことができる非線形モデルを選択^（7）。

深層学習^（8）やSVM Regression^（9）などが利用可能である。

以上の3種類の予測器から、ある基準に基づいた投票形式により、1つの予測器の結果を採用する。投票形式で1つの予測器の結果を採用するに当たり、予測器の運用者はAgent^（10）であると考える。Agentには効用関数^（11）が存在しその効用を最大化するように各予測器の結果を選択する。

3種類の予測器の値には常に真値との誤差が存在する。予測器の値から求めるLPガス容器残量も誤差が存在し、この残量から得られるLPガス容器内のガスがゼロになる日も予測器ごとに異なる。

予測器の運用者がリスク回避型の効用関数を持っている場合は3種類の予測器の中で1番直近にLPガス容器残量がゼロとなる日を採用する。なぜなら、予測器の値と真値の差からLPガス容器内の真の残存ガス量が1番多くなることが予想される。結果として予測器を使った場合のLPガス容器内のガスは1番多い値をとるので予測器の値に誤差が含まれていても現実世界においてLPガス容器内のガスがなくなってしまうリスクは1番小さくなる。

逆に予測器の運用者がリスク選好型でかつLPガス容器残量がゼロとなる1日前のLPガス容器内のガス量が1番少なくなることを期待する場合は3種類の予測器の中から1番未来にLPガス容器残量がゼロとなる日を選択する。

このように予測器の運用者はAgentの効用関数に従い3種類の予測器を選択する。これをアンサンブル予想モデルと呼ぶ。

3.3　LPガス容器配送計画問題の数理的アプローチ

3.3.1　LPガス容器配送の特徴

LPガス容器の配送が一般的な宅配便などの配送と異なる大きな点は、配送管理が供給者側に委ねられているというところにある。このような配送はVMI（Vender Management Inventory）方式と呼ばれ、ガス切れに対する責任が供給者側に課せられる一方、配送のタイミングは基本的に供給者側が決定することができる。したがって、複数ある配送候補日の中から最適な配送日を選択する問題ととらえることができるため、LPガス容器の配送計画問題は多期間計画問題に属する。

多期間計画問題を解くに当たっては、その計算を実施する期間を設定する必要があり、期間は長ければ長いほど全体最適に近づくが、より未来の配送計画を立てる際には供給先のガス消費量など不確定な要素が増えることや計算負荷の増加につながる。したがって、計算期間を現実的には区切る必要が生じるが、その際に考えられる懸念としては、ちょうど区切られた前後の日の計画に関しては、お互いの配送計画が考慮されておらず、非効率的な配送になる可能性があることである。

加えて、ガス切れリスクとのトレードオフではあるが、配送日を遅らせて可能な限り容器内のガスを空に近づけた状態で交換する方が訪問頻度を下げられるため、配送の効率化につながるという側面がLPガス容器配送においては存在する。そのため、配送計画は配送先の在庫を考慮しながら作成する必要がある。このような問題はInventory routing（在庫運搬経路）問題と呼ばれる。

3.3.2　LPガス容器配送の問題設計

多期間計画問題を解くに当たり、まず配送先ごとのガスの使用状況などをもとに配送候補期間を算定する。本配送計画問題においては、その期間内に配送を終えるようにしながら、配送距離や時間を最小化する組合せ最適化問題を解く。期限内に配送できない物件が存在する場合は大きなペナルティを目的関数に課すことで、可能な限り期限内で配送を完了させる計画作成を行うように設計した。

また、多期間計画問題における計算期間の区切りにあたる部分で、その前後の計画が非効率になる懸念に関しては、ローリングホライズン方式を用いることで解決を狙った。ローリングホライズン方式とは、複数日におよぶ配送計画の内、初日のみを採用し、翌日以降の計算に関しては、計算期間を1日スライドして、同様に計画の作成と初日の配送計画の採用を繰り返すというものである。これにより常に数日先の予定を見越した上で、計画が作成されるため、計算期間の区切りにおいて、配送が非効率になることは生じなくなる。

最後に、在庫運搬経路問題を解くに当たっては、与えられた配送候補期間の内、可能であればうしろの日付で配送に行くよう、M. DROR^（12）が示すように前倒しで配送するほど、追加でコストがかかるように目的関数に工夫を加えた。これにより、過剰な前倒しを抑えつつ期限切れのリスク管理も行うことができる。

4．実験結果

実際のLPガス容器配送の実績データを使って3章の方法でLPガス容器配送計画を作成した。問題の規模は1日の配送車両1台当たりLPガス容器を配送可能な住所は最大で50件。利用できる配送車は4.1、4.2は1台、4.3は最大9台とする。また配送車両の運行可能時間は8時間と設定し、8時間を超える場合も残業扱いで運行可能であるが可能な限り回避することにする。

4.1　ヒトの配送計画との差

配送員が配送した実績と3章のアルゴリズムにより解いたLPガス容器配送計画の差異分析を行った。

表1は配送実績として配送員が配送車両1台を運行して1日に移動する総距離と所要時間および、アルゴリズムが同じ住所に配送する場合の配送計画を示す。

配送員の方は10年以上の経験を持ち、担当地域の道路事情に精通した熟練者であるがその熟練者と比較して、総移動距離で18％、所要時間で6.5%アルゴリズムの方が良い配送計画を作成することができた。

この結果からアルゴリズムは少なくともヒト（熟練者）と同等以上であると考える。

4.2　アルゴリズムの視野による差

アルゴリズムがLPガス容器配送計画作成時に利用できる配送先住所の集合の大小をアルゴリズムから見た場合の問題の視野とし、その大小の差から結果がどのように異なるかを実験した。

表2において1日分の視野とはLPガス容器残量予測においてLPガス容器内のガスがゼロになる1日前のLPガス容器交換先住所しか見えない状態である。一方5日分の視野とはLPガス容器内のガスがゼロになる5日前からLPガス容器交換先住所が見えている状態を示す。アルゴリズムにおいては見えているLPガス容器交換先住所の集合に対して住所を選択しLPガス容器配送計画を作成することができる。

LPガス容器の配送交換件数は5日分の視野を持っている方が13件多く、総移動距離は1.0%短縮され、総時間は77分、1日分の視野を持っている場合と比べて増えている。1件当たりの配送にかかる距離と時間で比較すると、1日分の視野では1.19km/件、11.1分/件、5日分の視野では1.02km/件、10.4分/件となっており、与えられたリソースを効率的に使いながら配送ができているといえる。

表3は1日分の視野に対して5月14日、15日のLPガス容器配送計画を作成した結果である。表4は5日分の視野で5月14日、15日のLPガス容器配送計画を作成した結果である。この結果より、アルゴリズムの視野は広い方が毎日の配送計画の総時間の差が少なく1日当たりの業務が平準化されていることが分かる。

これは可能な限り残業を回避する設計であるため、視野が5日の場合には2日間の超過勤務でない時間のリソースをまず使い切ろうとするためである。1日の視野の場合には、直前の配送先しか見えていないため配送日の選択ができず、日をまたいでこのような調整を図ることができない。この例では、1日分の視野での残業時間が93分であるのに対し、5日分の視野では残業時間が38分となり、トータルとして残業時間の削減に成功している。

上記の考察はアルゴリズム同士の比較であったが、人手による複数日にまたがる視野を持ちながら最適な配送先住所を選択することは容易ではないので、扱う情報が多くなり問題の規模が大きくなるに従いヒトとアルゴリズムの差は大きくなると考えられる。

4.3　配送先住所の担当制がない場合

4.1と4.2は配送車両が1台の場合であった。今度はより大規模な問題として、より多くの配送先住所に対して複数の車両を利用できる条件下で配送計画を考える。アルゴリズムの視野は1日分とし、LPガス容器内のガスがゼロになる1日前のLPガス容器交換先住所しか配送できないとする。

表5においてエリア担当制とは配送車両ごとに担当する配送先が決まっていることを表す。エリア担当制なしがエリア担当制ありと比べて使用する車両数において4台減、総移動距離において21%短縮、総時間は10%減で同じ配送先を巡回することができる。

エリア担当制なしがエリア担当制ありと比べて車両や時間など配送で利用できるリソースの使用が少なくて済む理由として、例えばエリア担当制ありの場合、各担当の境界付近においては効率的に配送できないことや、車両の荷量を最大限活用することができず結果として車両数が増えてしまうということが考えられる。

5．おわりに

本論文では次の内容について論じた。LPガス容器の配送における物流問題に対し、IoTによりLPガス消費量を取得し、そのデータを使って複数の予測器を用いLPガス容器内残量予測を行う。予測器の運用者は各人の効用関数^（11）に従いリスク回避型からリスク選好型までの予測値を選択的に採用する。採用した予測値に基づきLPガス容器配送先住所を選択し配送車両や配送時間を最小化する配送計画最適化手法について論じた。

本論文で述べた手法は現在LPガス容器の配送効率化を目的としてフィールドテストを実施している。配送員の高齢化ならびに人手不足の深刻化が問題視されるなか、本手法により配送計画を最適化することで、配送員の業務負荷の低減および働き方改革の実現や業務におけるヒューマンエラー防止への貢献も期待できる。LPガス配送事業の効率化・高度化への一助となれば幸いである。

＜参考文献＞

（1） 笹山晋一、山上伸、片瀬成識、LPGボンベの効率的な配送方法について、オペレーションズ・リサーチ、43（11）、pp.614-617、1998

（2） Roberto Cantu-Funes et al., Multi-depot periodic vehicle routing problem with due dates and time windows, Journal of the Operational Research Society, 2017

（3） Victor A. Bloomfield, Using R for Numerical Analysis in Science and Engineering, Chapman and Hall, 2014

（4） Leo Breiman, Pasting Small Votes for Classification in Large Database and On-Line, Machine Learning 36, no. 1-2（1999）:85-103

（5） Gilles Louppe et al., Ensembles on Randam Patches, Lecture Notes in Computer Science 7523（2012）:346-361

（6） 塚本邦尊 他、東京大学のデータサイエンティスト養成講座、マイナビ出版、2019

（7） Aurélien Géron, Hands-On Machine Learning with Scikit-Learn, Keras, and Tensorflow: Concepts, Tools, and Techniques to Build Intelligent Systems, O’Reilly, 2019

（8） Lai, Guokun, et al., Modeling long-and short-term temporal patterns with deep neural networks, The 41st International ACM SIGIR Conference on Research& Development in Information Retrieval., ACM, 2018.

（9） C.M. ビショップ、元田 浩 （監訳）、 パターン認識と機械学習 上下、丸善出版、2012

（10） S.Russell, P.Norvig, Artificial Intelligence A Modern Approach, Pearson, 2016

（11） P.A. Samuelson, Foundations of Economic Analysis, Harvard Univ. Press, Cambridge, 1947

（12） M. DROR, M. BALL and B. GOLDEN, A COMPUTATIONAL COMPARISON OF ALGORITHMS FOR THE INVENTORY ROUTING PROBLEM, Annals of Operations Research 4（1985/6）3 -23

＜著者所属＞
村上　英治　アズビル金門株式会社 経営企画部
土岐　爽真　東京ガス株式会社 デジタルイノベーション本部基盤技術部

この記事は、技術報告書「azbil Technical Review」の2020年04月に掲載されたものです。