JP7632689B2 - 配送支援装置、配送支援方法、及び配送支援プログラム - Google Patents

Description

実施形態は、配送支援装置、配送支援方法、及び配送支援プログラムに関する。

配送車は、資源を配送先へ供給する主要な手段の一つである。

複数の配送先へ効率的に資源を配送するために、配送車の経路を適切に決定する問題は、関心の高い問題である。例えば、大規模災害時では、配送先における電力や水等の資源が枯渇する時間が最小となるような経路を選択することが要求される。

上述のような経路を選択するための手法として、分枝限定法を利用する手法が知られている。分枝限定法は、配送計画問題（ＶＲＰ：Vehicle Routing Problem）で厳密解を求める際にしばしば用いられる技術である。

例えば、非特許文献１では、複数の配送先における資源が枯渇している時間の最大値（最大枯渇時間）が目的関数として設定される。そして、当該目的関数を最小化する最適化問題が分枝限定法によって解かれる。

M.Ogawa et al. "A route searching method using two-dimension coordinates," IEICE, DOI:10.34385/proc.63.E4-3, 2020.

しかしながら、非特許文献１では、分枝限定法の限定操作で用いる緩和問題について、以下の点について懸念がある。

まず、地点間の移動時間がユークリッド距離に比例するため、地図上の移動時間を用いることができない。このため、資源が枯渇する時間が実際とずれてしまう可能性がある。

また、緩和問題がＮＰ困難であるか否かを判定不可能であるため、最適解を得られる保証がない。このため、分枝限定法で最終的に得られる解が、厳密解でない可能性がある。

また、配送車が配送先に滞在する時間が考慮されていない。このため、配送先毎に配送車が滞在する時間が異なる場合に対応することが困難である。

本発明は、上記事情に着目してなされたもので、その目的とするところは、資源の最適な配送経路を効率的に求める手段を提供することにある。

一態様の配送支援装置は、複数の第１地点において資源が枯渇する時間の最大値を最小化するための、配送機器による前記資源の経路を導出する導出部を備える。上記導出部は、上記複数の第１地点のうち配送順が確定していない複数の第２地点を一点に集約する緩和問題を用いた分枝限定法に基づき、前記経路を導出する。上記複数の第１地点の各々は、上記資源の枯渇時刻及び上記配送機器の滞在時間に関連づけられる。上記導出部は、上記複数の第２地点へ上記資源を配送するための第１経路を、上記枯渇時刻及び上記滞在時間の和に基づいて選択する第１経路選択部と、上記第１経路に基づいて、上記最大値の下限値を算出する第１算出部と、上記複数の第１地点へ上記資源を配送するための第２経路を、上記枯渇時刻に基づいて選択する第２経路選択部と、上記第２経路に基づいて、上記最大値の上限値を算出する第２算出部と、を含む。

実施形態によれば、資源の最適な配送経路を効率的に求める手段を提供することができる。

図１は、実施形態に係る配送システムの構成の一例を示す模式図である。 図２は、実施形態に係る配送支援装置のハードウェア構成の一例を示すブロック図である。 図３は、実施形態に係る配送支援装置の機能構成の一例を示すブロック図である。 図４は、実施形態に係る配送車情報の構成の一例を示す図である。 図５は、実施形態に係る配送先情報の構成の一例を示す図である。 図６は、実施形態に係る移動時間情報の構成の一例を示す図である。 図７は、実施形態に係る配送支援装置における配送支援動作の一例を示すフローチャートである。 図８は、具体例における猶予時間及び滞在時間を示す図である。 図９は、具体例における移動時間を示す図である。 図１０は、具体例におけるアイドル時間を示す図である。

以下、図面を参照して実施形態について説明する。なお、以下の説明において、同一の機能及び構成を有する構成要素については、共通する参照符号を付す。また、共通する参照符号を有する複数の構成要素を区別する場合、当該共通する参照符号に後続して付される更なる参照符号（例えば、“－１”等のハイフン及び数字）によって区別する。

１． 構成
実施形態に係る配送システムの構成について説明する。

１．１ 全体構成
まず、実施形態に係る配送システムの構成について説明する。図１は、実施形態に係る配送システムの構成の一例を示すブロック図である。

図１に示すように、配送システム１は、配送車４を用いて或る領域内に資源を供給するためのシステムである。配送システム１は、配送支援センタ２と、配送拠点３と、複数の配送先５－１、５－２、５－３、５－４、５－５、及び５－６を備える。以下では、複数の配送先５－１～５－６の各々を特に区別しない場合、“配送先５”と呼ぶ場合がある。

配送支援センタ２は、配送システム１における資源の配送を統括的に制御するための配送計画を生成する。配送支援センタ２は、配送拠点３と無線接続するように構成される。これにより、配送支援センタ２は、生成した配送用の最適経路を配送拠点３に無線送信する。

また、配送支援センタ２は、配送支援装置１０を含む。配送支援装置１０は、配送支援センタ２における配送用の最適経路の生成を支援するコンピュータである。配送支援装置１０に関する詳細は、後述する。

配送拠点３は、例えば、資源が格納される場所である。配送拠点３には、少なくとも１台の配送車４が配置される。配送拠点３は、配送支援センタ２から受信した最適経路に基づいて、配送車４に対して資源の配送を指示する。

配送車４は、資源を配送可能な車両等の機器である。配送車４は、配送支援センタ２から受信した最適経路に沿って、資源を配送先５に配送する。配送車４の行動目的は、例えば、複数の配送先５－１～５－６において資源が枯渇している時間（枯渇時間Ｔ）の最大値（最大枯渇時間Ｔ_ｍａｘ）を最小化することである。当該配送車４の行動目的は、配送支援センタ２から送信される最適経路によって実現される。

配送先５は、配送車４によって資源が配送される地点である。配送先５は、例えば、災害発生時における避難場所である。資源とは、例えば、水や電力等のインフラ資源である。配送先５には、予め資源が備蓄されている。災害発生時では、配送先５に備蓄された資源は、避難者によって徐々に消費される。

以下では、地図上（すなわち、２次元平面上）における配送車４及び配送先５の場所は、頂点ｖに対応づけられる。図１の例では、配送車４は、頂点ｖ_０に対応づけられる。複数の配送先５－１～５－６はそれぞれ、頂点ｖ_１～ｖ_６に対応づけられる。

１．２ 配送支援装置
次に、実施形態に係る配送支援装置の構成について説明する。

１．２．１ ハードウェア構成
図２は、実施形態に係る配送支援装置のハードウェア構成の一例を示すブロック図である。図２に示すように、配送支援装置１０は、制御回路１１、メモリ１２、通信モジュール１３、ユーザインタフェース１４、及びドライブ１５を含む。

制御回路１１は、配送支援装置１０の各構成要素を全体的に制御する回路である。制御回路１１は、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、及びＲＯＭ（Read Only Memory）等を含む。

メモリ１２は、配送支援装置１０の補助記憶装置である。メモリ１２は、例えば、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、及びメモリカード等を含む。メモリ１２には、配送支援動作に使用される各種情報、及び配送支援プログラムが記憶される。配送支援管理プログラムは、ネットワーク（図示せず）を介して配送支援装置１０の外部から送信されることにより、メモリ１２内に記憶され得る。

配送支援動作は、配送システム１内における資源の配送計画の生成を支援するために実行される一連の動作である。配送支援動作は、例えば、どのような順番で配送先５に資源を配送すると最大枯渇時間Ｔ_ｍａｘを最小化できるかを調べるための動作を含む。配送支援プログラムは、配送支援装置１０に配送支援動作を実行させるためのプログラムである。配送支援動作に関する詳細は、後述する。

通信モジュール１３は、ネットワークを介したデータの送受信に使用される回路である。

ユーザインタフェース１４は、ユーザと制御回路１１との間で情報を通信するための回路である。ユーザインタフェース１４は、入力機器及び出力機器を含む。入力機器は、例えば、タッチパネル及び操作ボタン等を含む。出力機器は、例えば、ＬＣＤ（Liquid Crystal Display）及びＥＬ（Electroluminescence）ディスプレイ、並びにプリンタを含む。ユーザインタフェース１４は、ユーザからの入力（ユーザ入力）を電気信号に変換した後、制御回路１１に送信する。ユーザインタフェース１４は、制御回路１１から受信した配送支援プログラムの実行結果を、ユーザに出力する。

ドライブ１５は、記憶媒体１６に記憶されたプログラムを読込むための装置である。ドライブ１５は、例えば、ＣＤ（Compact Disk）ドライブ、及びＤＶＤ（Digital Versatile Disk）ドライブ等を含む。

記憶媒体１６は、プログラム等の情報を、電気的、磁気的、光学的、機械的又は化学的作用によって蓄積する媒体である。記憶媒体１６は、配送支援プログラムを記憶してもよい。

１．２．２ 機能構成
図３は、実施形態に係る配送支援装置の機能構成の一例を示すブロック図である。

制御回路１１のＣＰＵは、メモリ１２又は記憶媒体１６に記憶された配送支援プログラムをＲＡＭに展開する。そして、制御回路１１のＣＰＵは、ＲＡＭに展開された配送支援プログラムを解釈及び実行することによりメモリ１２、通信モジュール１３、ユーザインタフェース１４、ドライブ１５、及び記憶媒体１６を制御する。これによって、図３に示されるように、配送支援装置１０は、入力部２１、記憶部２２、経路管理部２３、最適経路導出部２４、及び出力部２５を備えるコンピュータとして機能する。

入力部２１は、ユーザからの入力に基づき、各種情報を記憶部２２に記憶させる。記憶部２２に記憶される各種情報は、例えば、配送車情報２２ａ、配送先情報２２ｂ、及び移動時間情報２２ｃを含む。

図４乃至図６はそれぞれ、実施形態に係る配送車情報、配送先情報、及び移動範囲情報の構成の一例を示す概念図である。

図４に示すように、配送車情報２２ａは、配送車４に関する情報である。具体的には、配送車情報２２ａは、配送車頂点、及び位置の情報を含む。

配送車頂点は、配送車４に対応づけられる頂点名を固有に識別する。

配送車位置は、配送車４の現在の位置情報である。配送車位置は、例えば、２次元座標（Ｘ，Ｙ）で表される。配送車位置は、緯経度で表されてもよい。

図４の例では、配送支援装置１０は、配送車情報２２ａにより、頂点ｖ_０に対応づけられた配送車４が、配送車位置（ｘ_０，ｙ_０）にいることを把握することができる。

図５に示すように、配送先情報２２ｂは、資源の配送を待つ配送先５の情報である。具体的には、配送先情報２２ｂは、配送先頂点、配送先位置、猶予時間、及び滞在時間の情報を含む。

配送先頂点は、配送先５に対応づけられる頂点名を固有に識別する。

配送先位置は、配送先５の位置情報である。配送先位置は、例えば、２次元座標（ｘ，ｙ）で表される。配送先位置は、配送車位置と同様、緯経度で表されてもよい。

猶予時間ｄは、基準時刻から、配送先５に備蓄された資源が枯渇するまでの時間を示す情報である。基準時刻は、例えば、配送支援動作の開始時刻に固定される。これに伴い、猶予時間ｄは、配送支援動作が実行されている間、固定される。猶予時間ｄは、資源の枯渇時刻と置き換えてもよい。

滞在時間ｐは、配送車４が配送先５に到着した後、資源の供給を開始してから終了するまでの時間を示す情報である。滞在時間ｐの間、配送車４は、配送先５から移動しない。配送車４が配送先５に到着してから、滞在時間ｐの経過後に、配送車４は、次の配送先５に向けて出発する。

図５の例では、配送支援装置１０は、配送先情報２２ｂにより、頂点ｖ_ｉに対応づけられた配送先５－ｉが、配送先位置（ｘ_ｉ，ｙ_ｉ）にあることを把握することができる。また、配送支援装置１０は、配送先５－ｉが、資源の枯渇まで猶予時間ｄ_ｉを有し、かつ配送車４の到着から資源の供給を終えるまで滞在時間ｐ_ｉを要することを把握することができる（ｉは、１以上６以下の任意の整数）。このように、猶予時間ｄ及び滞在時間ｐは、配送先５毎に互いに独立な値が適用される。

図６に示すように、移動時間情報２２ｃは、移動時間ｔを示す情報である。移動時間ｔは、配送車４と任意の配送先５との間、及び任意の２個の配送先５の間（以下、“頂点間”と言う）を移動する際に要する時間である。移動時間ｔは、頂点間のユークリッド距離には必ずしも比例しない。移動時間ｔは、例えば、頂点間を結ぶ道路等の情報を考慮して決定され得る。すなわち、移動時間ｔは、地図に記載された道路を実際に移動する場合に要する時間に対応する。

図６の例では、配送支援装置１０は、移動時間情報２２ｃにより、頂点ｖ_ｉと頂点ｖ_ｊとの間の移動時間ｔがｔ（ｖ_ｉ，ｖ_ｊ）であることを把握することができる（ｊは、０以上６以下で、ｉと異なる整数）。

再び図３に戻って配送支援装置１０の機能構成について説明する。

経路管理部２３は、配送車４が配送先５に資源を配送する際に取り得る経路を管理するための機能ブロックである。各経路は、例えば、配送車４の現在位置からスタートして、資源を配送すべき全ての配送先５を１回ずつ経由する制約の下で規定される配送順である。経路管理部２３は、配送車情報２２ａ及び配送先情報２２ｂに基づいて、経路リストＬを生成する。経路リストＬは、経路の集合である。

経路管理部２３は、最適経路導出部２４からの要求に応じて、経路リストＬから、経路群Ｐを抽出する。経路群Ｐは、経路リストＬ内の経路の部分集合である。具体的には、例えば、経路群Ｐは、経路リストＬにおいて配送順が確定していない配送先５のうち、最初に配送する配送先５が共通する少なくとも１個の経路を含む。経路管理部２３は、抽出された経路群Ｐを最適経路導出部２４に送信する。そして、経路管理部２３は、最適経路導出部２４に送信された経路群Ｐを、経路リストＬから削除する。

経路管理部２３は、最適経路導出部２４による分枝処理によって生成されたサブ経路群Ｐ’を新たな経路群Ｐとして経路リストＬに追加する。サブ経路群Ｐ’は、或る経路群Ｐ内の経路の部分集合である。具体的には、例えば、サブ経路群Ｐ’は、或る経路群Ｐにおいて配送順が確定していない配送先５のうち、最初に配送する配送先５が共通する少なくとも１個の経路を含む。分枝処理については、後述する。

最適経路導出部２４は、分枝限定法によって、経路リストＬから最適経路を導出するための機能ブロックである。最適経路は、最大枯渇時間Ｔ_ｍａｘを最小にする経路である。最適経路導出部２４は、上限値用経路選択部３０、上限値算出部３１、第１判定部３２、更新部３３、緩和問題設定部３４、アイドル時間算出部３５、下限値用経路選択部３６、下限値算出部３７、第２判定部３８、及び分枝部３９を含む。

上限値用経路選択部３０は、経路群Ｐから上限値用経路ｒ_１を選択するための機能ブロックである。上限値用経路ｒ_１は、経路群Ｐにおける最大枯渇時間Ｔ_ｍａｘの上限値ＵＢの算出に用いられる経路である。上限値ＵＢは、上界（Upper bound）と読み替えてもよい。具体的には、例えば、上限値用経路選択部３０は、経路群Ｐにおいて配送順が確定していない配送先５について、猶予時間ｄが少ない配送先５から順に向かう経路を、上限値用経路ｒ_１としてから選択する。上限値用経路選択部３０は、選択された上限値用経路ｒ_１を上限値算出部３１に送信する。

なお、上限値用経路ｒ_１において、配送先５－ｉに資源が配送される順番をｋ番目とすると、ｉとｋとの関係は、以下の式（１）のように表される。ただし、ｋ＝０の場合、ｉ＝０であるとする。

上限値算出部３１は、上限値用経路ｒ_１に基づいて、上限値ＵＢを算出するための機能ブロックである。具体的には、例えば、上限値算出部３１は、以下の式（２）に従って、上限値用経路ｒ_１で配送車４が配送先５－ｉに到着する時間ａ_ｉ（ｒ_１）を算出する。ただし、ｐ_０＝０とする。

そして、上限値算出部３１は、以下の式（３）に従って、算出された配送先５－ｉへの到着時間ａ_ｉ（ｒ_１）に基づいて、上限値用経路ｒ_１での配送先５－ｉの枯渇時間Ｔ_ｉ（ｒ_１）を算出する。

枯渇時間Ｔ_ｉ（ｒ_１）の最大値が上限値用経路ｒ_１での最大枯渇時間Ｔ_ｍａｘである。すなわち、上限値算出部３１は、以下の式（４）に従って、上限値ＵＢを算出する。上限値算出部３１は、算出された上限値ＵＢを第１判定部３２に送信する。

第１判定部３２は、分枝限定法における評価関数を更新するか否かを判定するための機能ブロックである。第１判定部３２は、上限値ＵＢが評価関数よりも大きいか否かを判定する。上限値ＵＢが評価関数よりも大きい場合、第１判定部３２は、上限値ＵＢを更新部３３に送信する。上限値ＵＢが評価関数以下の場合、第１判定部３２は、上限値ＵＢを更新部３３へ送信しない。

更新部３３は、評価関数を更新するための機能ブロックである。第１判定部３２から上限値ＵＢを受信した場合、更新部３３は、評価関数を上限値ＵＢで更新する。また、更新部３３は、当該更新された評価関数と、当該評価関数に対応する上限値用経路ｒ_１とを関連付けてメモリ１２に記憶させる。

緩和問題設定部３４は、緩和問題を設定するための機能ブロックである。緩和問題は、元問題（すなわち、地図上の全ての配送先５に資源を配送する経路のうち、最大枯渇時間を最小にする最適経路を導出する問題）に制約を課すことにより、解の導出の難易度が緩和された問題である。緩和問題は、経路群Ｐにおける最大枯渇時間Ｔ_ｍａｘの下限値ＬＢの算出に際して適用される。下限値は、下界（Lower bound）と読み替えてもよい。具体的には、緩和問題設定部３４は、経路群Ｐにおいて配送順が確定していない全ての配送先５を適当な位置に集約させる制約を課す。適当な位置は、例えば、経路群Ｐにおいて配送順が確定している配送先５のうち配送順が最後となる配送先５の位置である。このような制約を課すことにより、位置が集約された配送先５間の移動時間ｔは、０とみなすことができる。

以下の説明では、緩和問題において位置が集約された配送先５－ｉに対応する頂点を、頂点ｖ’_ｉとする。頂点ｖ’_ｉに対応する配送先５－ｉの緩和問題における猶予時間及び滞在時間は、それぞれｄ’_ｉ及びｐ’_ｉとする。また、頂点ｖ’_ｉに対応する配送先５－ｉの緩和問題における到着時刻及び枯渇時間はそれぞれ、ａ’_ｉ及びＴ’_ｉとする。そして、枯渇時間Ｔ’_ｉに基づく最大枯渇時間は、Ｔ’_ｍａｘとする。

なお、全ての頂点ｖ’_ｉの位置は、一致する。猶予時間ｄ’_ｉ及び滞在時間ｐ’_ｉは、猶予時間ｄ_ｉ及び滞在時間ｐ_ｉと等しい値に設定される（ｄ’_ｉ＝ｄ_ｉ、ｐ’_ｉ＝ｐ_ｉ）。

アイドル時間算出部３５は、緩和問題に適用されるアイドル時間Ｉｔを算出するための機能ブロックである。アイドル時間Ｉｔは、例えば、緩和問題において、配送車４が或る配送先５への資源の供給を終えた後、次の配送先５への資源の供給を開始するまでの、供給が不可能な時間と定義される。アイドル時間Ｉｔは、元問題における移動時間ｔに応じて算出される。具体的には、例えば、頂点ｖ’_ｉに対応する配送先５への資源の供給を終えた後、頂点ｖ’_ｊに対応する配送先５へ資源の供給を開始するまでのアイドル時間Ｉｔｊは、以下の式（５）のように表される。

アイドル時間算出部３５は、式（５）に従って、アイドル時間Ｉｔを算出する。アイドル時間算出部３５は、算出されたアイドル時間Ｉｔを下限値用経路選択部３６に送信する。

下限値用経路選択部３６は、経路群Ｐから下限値用経路ｒ_２を選択するための機能ブロックである。下限値用経路ｒ_２は、経路群Ｐにおける最大枯渇時間Ｔ_ｍａｘの下限値ＬＢの算出に用いられる経路である。具体的には、例えば、下限値用経路選択部３６は、緩和問題によって位置が集約された配送先５について、猶予時間ｄ’及び滞在時間ｐ’の和（ｄ’＋ｐ’）が小さい配送先５から順に向かう経路を、下限値用経路ｒ_２としてから選択する。下限値用経路選択部３６は、選択された下限値用経路ｒ_２を下限値算出部３７に送信する。

なお、上述の下限値用経路ｒ_２は、緩和問題によって位置が集約された配送先５における最大枯渇時間Ｔ’_ｍａｘを、経路群Ｐ内で最小にする。これは、スケジューリング問題における納期遅れ時間最小化問題の枠組みを使用することで、容易に証明される。

なお、下限値用経路ｒ_２において、配送先５－ｉに資源が配送される順番をｋ番目とすると、ｉとｋとの関係は、以下の式（６）のように表される。ただし、ｋ＝０の場合、ｉ＝０であるとする。

下限値算出部３７は、下限値用経路ｒ_２に基づいて、下限値ＬＢを算出するための機能ブロックである。具体的には、例えば、下限値算出部３７は、以下の式（７）に従って、下限値用経路ｒ_２で配送車４が配送先５－ｉに到着する時間ａ’_ｉ（ｒ_２）を算出する。

そして、下限値算出部３７は、以下の式（８）に従って、算出された配送先５－ｉへの到着時間ａ’_ｉ（ｒ_２）に基づいて、下限値用経路ｒ_２での配送先５－ｉの枯渇時間Ｔ’_ｉ（ｒ_２）を算出する。

枯渇時間Ｔ’_ｉ（ｒ_２）の最大値が下限値用経路ｒ_２での最大枯渇時間Ｔ’_ｍａｘである。すなわち、下限値算出部３７は、以下の式（９）に従って、下限値ＬＢを算出する。下限値算出部３７は、算出された下限値ＬＢを第２判定部３８に送信する。

第２判定部３８は、分枝限定法における分枝処理を実行するか否かを判定するための機能ブロックである。第２判定部３８は、下限値ＬＢが評価関数よりも小さいか否かを判定する。下限値ＬＢが評価関数よりも小さい場合、第２判定部３８は、下限値ＬＢを分枝部３９に送信する。下限値ＬＢが評価関数以上の場合、第２判定部３８は、下限値ＬＢを分枝部３９へ送信することなく、判定結果を経路管理部２３に送信する。

分枝部３９は、分枝処理を実行するための機能ブロックである。分枝処理は、経路群Ｐ内の複数の経路を、各々が少なくとも１個の経路を含む複数のサブ経路群Ｐ’に分類する処理である。具体的には、例えば、第２判定部３８から下限値ＬＢを受信した場合、分枝部３９は、経路群Ｐにおいて配送順が確定していない配送先５のうち、最初に配送する配送先５が共通する少なくとも１個の経路を、同一のサブ経路群Ｐ’に分類する。分枝部３９は、生成されたサブ経路群Ｐ’を、経路管理部２３に送信する。

出力部２５は、最適経路をユーザに出力するための機能ブロックである。経路管理部２３が管理する経路リストＬが空集合となった場合、出力部２５は、更新部３３によって記憶された評価関数及び当該評価関数に対応する経路の組を、最適経路としてユーザに出力する。

以上のように構成することにより、ユーザは、配送支援装置１０から、配送計画を支援する情報として、最大枯渇時間Ｔ_ｍａｘを最小にする経路を最適経路として得ることができる。そして、ユーザは、当該情報に基づき、配送計画を生成することができる。

２． 動作
次に、実施形態に係る配送支援装置の動作について説明する。

２．１ 配送支援動作
図７は、実施形態に係る配送支援装置における配送支援動作の一例を示すフローチャートである。図７の例では、ユーザ入力によって予め配送車情報２２ａ、配送先情報２２ｂ、及び移動時間情報２２ｃがメモリ１２内に記憶されているものとする。

図７に示すように、ユーザから最適経路を選択する旨の指示を受けると（開始）、経路管理部２３は、経路リストＬ及び評価関数を初期化する（Ｓ１１）。例えば、経路管理部２３は、経路リストＬに、資源を配送する配送先５によって実現され得る全ての経路を含める。また、経路管理部２３は、最小化すべき評価関数を、暫定的に無限大（＝＋∞）に初期化する。

経路管理部２３は、経路リストＬが空集合であるか否かを判定する（Ｓ１２）。

経路リストＬが空集合でない場合（Ｓ１２；ｎｏ）、経路管理部２３は、経路リストＬから経路群Ｐを選択し、経路リストＬから当該選択された経路群Ｐを削除する（Ｓ１３）。

上限値用経路選択部３０は、Ｓ１３の処理で選択された経路群Ｐから、上限値用経路ｒ_１を選択する。具体的には、上限値用経路選択部３０は、猶予時間ｄが少ない配送先５に順に向かう平面上における経路を、上限値用経路ｒ_１として選択する（Ｓ１４）。

上限値算出部３１は、Ｓ１４の処理で選択された上限値用経路ｒ_１に基づいて、最大枯渇時間Ｔ_ｍａｘの最小値の上限値ＵＢを算出する（Ｓ１５）。

第１判定部３２は、Ｓ１５の処理で算出された上限値ＵＢが評価関数より大きいか否かを判定する（Ｓ１６）。

上限値ＵＢが評価関数以下の場合（Ｓ１６；ｎｏ）、更新部３３は、評価関数を上限値ＵＢに更新する（Ｓ１７）。また、更新部３３は、更新された上限値ＵＢと、上限値ＵＢに対応する経路をメモリ１２に記憶させる。

上限値ＵＢが評価関数より大きい場合（Ｓ１６；ｙｅｓ）、又はＳ１７の処理の後、緩和問題設定部３４は、経路群Ｐ内で配送順が確定していない配送先５を一点に集約する緩和問題を設定する（Ｓ１８）。

Ｓ１８の処理の後、アイドル時間算出部３５は、移動時間情報２２ｃに基づいて、緩和問題におけるアイドル時間Ｉｔを算出する（Ｓ１９）。

下限値用経路選択部３６は、スケジューリング問題の納期遅れ最小化問題に基づいて最適に選択された点上の経路を、下限値用経路ｒ_２として選択する。具体的には、下限値用経路選択部３６は、Ｓ１８の処理によって一点に集約された配送先５について、猶予時間ｄ’及び滞在時間ｐ’の和（ｄ’＋ｐ’）が小さい配送先５に順に向かう点上の経路を、下限値用経路ｒ_２として選択する（Ｓ２０）。

下限値算出部３７は、Ｓ２０の処理で選択された下限値用経路ｒ_２に基づいて、最大枯渇時間Ｔ_ｍａｘの最小値の下限値ＬＢを算出する（Ｓ２１）。

第２判定部３８は、Ｓ２１の処理で算出された下限値ＬＢが評価関数より小さいか否かを判定する（Ｓ２２）。

下限値ＬＢが評価関数より小さい場合（Ｓ２２；ｙｅｓ）、分枝部３９は、経路群Ｐからサブ経路群Ｐ’を生成し、当該生成されたサブ経路群Ｐ’を経路管理部２３に送信する（Ｓ２３）。経路管理部２３は、分枝部３９から受信したサブ経路群Ｐ’を、新たな経路群Ｐとして経路リストＬに追加する。

下限値ＬＢが評価関数以上の場合（Ｓ２２；ｎｏ）、又はＳ２３の処理の後、経路管理部２３は、経路リストＬが空集合であるか否かを判定する（Ｓ１２）。このように、経路リストＬが空集合となるまで、Ｓ１３～Ｓ２３の処理が繰り返される。これによって、分枝限定法による経路の取捨選択を実行しつつ、評価関数が更新される。

経路リストＬが空集合である場合（Ｓ１２；ｙｅｓ）、最適経路導出部２４は、Ｓ１７の処理によって最終的に更新された評価関数に対応する経路を、最適経路として選択する（Ｓ２４）。

Ｓ２４の処理が終了すると、配送支援動作が終了となる（終了）。これにより、出力部２５は、選択された最適経路をユーザに出力することができる。

２．２ 下限値算出の具体例
次に、緩和問題における下限値ＬＢ算出の具体例を説明する。以下では、配送先５－１～５－６への配送順が確定していない場合における経路群Ｐに対して、緩和問題が適用される場合を想定する。

図８は、具体例における猶予時間及び滞在時間を示す図である。図９は、具体例における移動時間を示す図である。図１０は、具体例におけるアイドル時間を示す図である。

図８に示すように、頂点ｖ_１～ｖ_６における猶予時間ｄ及び滞在時間ｐが与えられる場合を考える。すなわち、（ｄ_１，ｐ_１）＝（１７，３）、（ｄ_２，ｐ_２）＝（２９，５）、（ｄ_３，ｐ_３）＝（２７，４）、（ｄ_４，ｐ_４）＝（１８，５）、（ｄ_５，ｐ_５）＝（２９，１）、（ｄ_６，ｐ_６）＝（１８，６）であるとする。

図９に示すように、頂点ｖ_０～ｖ_６における頂点間の移動時間ｔが与えられる場合を考える。すなわち、ｔ（ｖ_０，ｖ_１）＝９．８、ｔ（ｖ_０，ｖ_２）＝１２．０、ｔ（ｖ_０，ｖ_３）＝１０．７、ｔ（ｖ_０，ｖ_４）＝１１．３、ｔ（ｖ_０，ｖ_５）＝１１．３、ｔ（ｖ_０，ｖ_６）＝２．１、ｔ（ｖ_１，ｖ_２）＝５．１、ｔ（ｖ_１，ｖ_３）＝１．０、ｔ（ｖ_１，ｖ_４）＝４．４、ｔ（ｖ_１，ｖ_５）＝４．１、ｔ（ｖ_１，ｖ_６）＝８．１、ｔ（ｖ_２，ｖ_３）＝５．３、ｔ（ｖ_２，ｖ_４）＝４．２、ｔ（ｖ_２，ｖ_５）＝１．０、ｔ（ｖ_２，ｖ_６）＝３．６、ｔ（ｖ_３，ｖ_４）＝５．３、ｔ（ｖ_３，ｖ_５）＝４．４、ｔ（ｖ_３，ｖ_６）＝８．６、ｔ（ｖ_４，ｖ_５）＝３．６、ｔ（ｖ_４，ｖ_６）＝５．０、ｔ（ｖ_５，ｖ_６）＝４．２であるとする。

アイドル時間算出部３５は、上述の移動時間ｔに基づき、上述の式（５）に従って、図１０に示すようなアイドル時間Ｉｔを算出する。すなわち、アイドル時間算出部３５は、Ｉｔ_１＝１、Ｉｔ_２＝１、Ｉｔ_３＝１、Ｉｔ_４＝３．６、Ｉｔ_５＝１、Ｉｔ_６＝３．６を算出する。

下限値用経路選択部３６は、猶予時間ｄ’及び滞在時間ｐ’の和（ｄ’＋ｐ’）が小さい配送先５から順に向かう経路を、下限値用経路ｒ_２としてから選択する。上述の通り、ｄ_ｉ＝ｄ’_ｉ、ｐ_ｉ＝ｐ’_ｉであるから、猶予時間ｄ’及び滞在時間ｐ’の和（ｄ’＋ｐ’）が小さい配送先５は、５－１、５－４、５－６、５－５、５－３、５－２の順となる。このため、下限値用経路選択部３６は、頂点ｖ’１→ｖ’４→ｖ’６→ｖ’５→ｖ’３→ｖ’２の順に資源を配送する経路を下限値用経路ｒ_２として選択する。

下限値算出部３７は、上述の式（７）に従って、到着時間ａ’_ｉ（ｒ_２）を算出する。具体的には、下限値算出部３７は、ａ’_１（ｒ_２）＝１．０、ａ’_４（ｒ_２）＝７．６、ａ’_６（ｒ_２）＝１６．２、ａ’_５（ｒ_２）＝２３．２、ａ’_３（ｒ_２）＝２５．２、ａ’_２（ｒ_２）＝３０．２を算出する。

下限値算出部３７は、上述の式（８）に従って、枯渇時間Ｔ’_ｉ（ｒ_２）を算出する。具体的には、下限値算出部３７は、Ｔ’_１（ｒ_２）＝－１６．０、Ｔ’_４（ｒ_２）＝－１０．４、Ｔ’_６（ｒ_２）＝－１．８、Ｔ’_５（ｒ_２）＝－５．８、Ｔ’_３（ｒ_２）＝－１．８、Ｔ’_２（ｒ_２）＝１．２を算出する。下限値算出部３７は、算出された枯渇時間Ｔ’_ｉ（ｒ_２）の最大値Ｔ’_ｍａｘ＝Ｔ’_２（ｒ_２）＝１．２を、下限値ＬＢとして算出する。

以上のような処理によって、下限値ＬＢが算出される。なお、上述の頂点ｖ_０から頂点ｖ_１～ｖ_６への資源の配送経路における最小遅延時間（最適値）は、総数え上げによって１６．５である。下限値ＬＢは、この最適値を下回るように算出される。これにより、本実施形態で設定される緩和問題を用いた分枝限定法で最終的に得られる解が厳密解であることが保証される。

１．３ 実施形態に係る効果
実施形態によれば、最適経路導出部２４は、配送順が確定していない配送先５を一点に集約する緩和問題を用いた分枝限定法に基づき、最適な経路を導出する。このような緩和問題は、スケジューリング問題における、納期遅れ時間最小化問題の枠組みを使用することで、最適解が得られることが証明できる。これにより、緩和問題を用いた分枝限定法によって得られる解が、厳密解であることを保証することができる。

具体的には、下限値用経路選択部３６は、猶予時間ｄ’及び滞在時間ｐ’の和が小さい順に配送する経路を、下限値用経路ｒ_２として選択する。下限値算出部３７は、下限値用経路ｒ_２に基づいて算出される最大枯渇時間Ｔ’_ｍａｘを、下限値ＬＢとして算出する。これにより、資源の最適な配送経路を効率的に求めることができる。なお、緩和問題における猶予時間ｄ’及び滞在時間ｐ’が、それぞれ元問題における猶予時間ｄ及び滞在時間ｐから変化しないように設定される。これにより、緩和問題で得られる最適値は、必ず元問題の最適値よりも小さくすることができる。

また、滞在時間ｐは、複数の配送先５の間で互いに独立に設定される。これにより、配送先５毎に滞在時間ｐが異なる場合を考慮しつつ、最大枯渇時間を最小にする経路を導出することができる。

また、アイドル時間算出部３５は、アイドル時間Ｉｔを、配送車４による配送先５間の移動時間ｔに応じて算出する。これにより、緩和問題において、元問題の設定を反映し、かつ下限値ＬＢが元問題の最適値から大きく乖離することを抑制できる。

また、上限値用経路選択部３０は、猶予時間ｄが小さい順に配送する経路を、上限値用経路ｒ_１として選択する。上限値算出部３１は、上限値用経路ｒ_１に基づいて算出される最大枯渇時間Ｔ_ｍａｘを、上限値ＵＢとして算出する。これにより、分枝限定法における評価関数の値を更新することができる。

また、出力部２５は、導出された最適経路をユーザに出力する。これにより、ユーザは、配送車４をどの順で配送先５に向かわせれば最大枯渇時間を最小化できるか、を把握することができる。したがって、配送支援装置１０は、より精度の高い配送計画の作成を支援することができる
２． その他
なお、上述した実施形態には、種々の変形が適用可能である。

例えば、上述した実施形態では、配送支援プログラムが、配送支援センタ２内の配送支援装置１０で実行される場合について説明したが、これに限られない。例えば、配送支援管理プログラムは、クラウド上の計算リソースで実行されてもよい。

なお、本発明は、上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は適宜組み合わせて実施してもよく、その場合組み合わせた効果が得られる。更に、上記実施形態には種々の発明が含まれており、開示される複数の構成要件から選択された組み合わせにより種々の発明が抽出され得る。例えば、実施形態に示される全構成要件からいくつかの構成要件が削除されても、課題が解決でき、効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。

１…配送システム
２…配送支援センタ
３…配送拠点
４…配送車
５－１，５－２，５－３，５－４，５－５，５－６…配送先
１０…配送支援装置
１１…制御回路
１２…メモリ
１３…通信モジュール
１４…ユーザインタフェース
１５…ドライブ
１６…記憶媒体
２１…入力部
２２…記憶部
２２ａ…配送車情報
２２ｂ…配送先情報
２２ｃ…移動時間情報
２３…経路管理部
２４…最適経路導出部
２５…出力部
３０…上限値用経路選択部
３１…上限値算出部
３２…第１判定部
３３…更新部
３４…緩和問題設定部
３５…アイドル時間算出部
３６…下限値用経路選択部
３７…下限値算出部
３８…第２判定部
３９…分枝部

Claims (6)

1. 複数の第１地点において資源が枯渇する時間の最大値を最小化するための、配送機器による前記資源の経路を導出する導出部を備え、
   前記導出部は、前記複数の第１地点のうち配送順が確定していない複数の第２地点を一点に集約する緩和問題を用いた分枝限定法に基づき、前記経路を導出し、
   前記複数の第１地点の各々は、前記資源の枯渇時刻及び前記配送機器の滞在時間に関連づけられ、
   前記導出部は、
   前記複数の第２地点へ前記資源を配送するための第１経路を、前記枯渇時刻及び前記滞在時間の和に基づいて選択する第１経路選択部と、
   前記第１経路に基づいて、前記最大値の下限値を算出する第１算出部と、
   前記複数の第１地点へ前記資源を配送するための第２経路を、前記枯渇時刻に基づいて選択する第２経路選択部と、
   前記第２経路に基づいて、前記最大値の上限値を算出する第２算出部と、
   を含む、
   配送支援装置。
2. 前記滞在時間は、前記複数の第１地点の間で互いに独立である、
   請求項１記載の配送支援装置。
3. 前記導出部は、前記複数の第２地点の各々に関連づけられたアイドル時間を、前記配送機器による前記複数の第２地点間の移動時間に応じて算出する第３算出部を更に含み、
   前記第１算出部は、前記アイドル時間に更に基づいて、前記下限値を算出する、
   請求項１記載の配送支援装置。
4. 前記第１経路は、スケジューリング問題における、納期遅れ時間最小化問題に基づく最適解である、
   請求項１記載の配送支援装置。
5. 配送支援装置による配送支援方法であって、
   複数の第１地点において資源が枯渇する時間の最大値を最小化するための配送機器による前記資源の経路を、前記複数の第１地点のうち配送順が確定していない複数の第２地点を一点に集約する緩和問題を用いた分枝限定法に基づいて導出することを備え、
   前記複数の第１地点の各々は、前記資源の枯渇時刻及び前記配送機器の滞在時間に関連づけられ、
   前記導出することは、
   前記複数の第２地点へ前記資源を配送するための第１経路を、前記枯渇時刻及び前記滞在時間の和に基づいて選択することと、
   前記第１経路に基づいて、前記最大値の下限値を算出することと、
   前記複数の第１地点へ前記資源を配送するための第２経路を、前記枯渇時刻に基づいて選択することと、
   前記第２経路に基づいて、前記最大値の上限値を算出することと、
   を含む、
   配送支援方法。
6. コンピュータを、請求項１乃至請求項４のいずれか１項に記載の配送支援装置が備える各部として機能させるための配送支援プログラム。

Images