東海大学紀要情報通信学部
Vol.15,No.2,2022,pp.1-6
東海大学紀要 情報通信学部
Vol.xx, No.xx, 20xx, pp.xxx-xxx

論文

論文
災害時の救援物資供給活動における多期間在庫流通計画問題に対する緩和固定法
森山 弘海*1，堀 圭佑*2

A Relax and Fix Method for a Multi-period Inventory
Distribution Planning Problem in Disaster Relief Logistics
byHiroumi MORIYAMA*1 and Keisuke HORI*2( received on Sep. 30, 2022 & accepted on Jan. 11, 2023 )あらまし
多期間在庫流通計画問題は，多期間にわたり 1 つの供給点から複数の需要点に単一の品目を輸送するとき，輸送費用と在庫保管費用の総和が最小となるように各期の輸送量とその輸送に使用する車両を決定する問題である．当研究では，この問題を災害時の救援物資供給活動に適用するため，品目数を単一品目から多品目に拡張するとともに，需要点だけでなく供給点における在庫も考慮するように拡張した上で，総品切れ費用の最小化を目的関数とした問題を設定する．そして，この問題を混合整数計画
問題に定式化するとともに，緩和固定法に基づくその近似解法を提案し，提案法の有効性を数値実験を通して検証する．

Abstract
We consider a multi-period inventory distribution planning problem in disaster relief logistics. This problem consists of determining theamount of transportation for each period and the vehicle used for the transportation so as to minimize the sum of lost sales costs when multiple
items are transported from one supply point to many demand points over a finite number of periods. We propose a heuristic algorithm to solve
the problem based on the relax and fix method. We then verify the effectiveness of the proposed algorithm through computational experiments.
キーワード：災害救援ロジスティクス，在庫，流通．混合整数計画法，緩和固定法
Keywords: Disaster Relief Logistics, Inventory, Distribution, Mixed Integer Programming, Relax and Fix Method

1. は じ め に
災害時におけるロジスティクス活動は，人道支援において必要不可欠なものであるが，これまでの災害時の救援物資供給活動においては，必要な物資が必要なときに必要な場所に届けられない事態や，不必要な物資が届けられる事態が発生している 1)．
他方，多期間在庫流通計画問題（Multi-period Inventory
Distribution Planning Problem）と呼ばれる問題が研究されている 2)．この問題は，多期間にわたり1つの供給点から複数の需要点に単一の品目を輸送するとき，輸送費用と在庫保管費用の総和が最小となるように各期の輸送量とその輸送に使用する車両を決定する問題である．
当研究では，この問題を災害時の救援物資供給活動に適用するため，品目数を単一品目から多品目に拡張するとともに，需要点だけでなく供給点における在庫も考慮するように拡張する．さらに，災害時は，供給点における補充量の不足（限られた救援物資）や輸送車両の不足により，需要点（避難所）の需要量をもともと満たせない場合が多く想定されることから，総品切れ費用の最小化を目的関数と*1 経営学部経営学科 教授
School of Business Administration, Department of Business
Administration, Professor*2 情報通信学部経営システム工学科
School of Information and Telecommunication Engineering,
Department of Management Systems Engineering

した問題を設定する．そして，この問題を混合整数計画問
題に定式化し，緩和固定法（relax and fix method）に基づく
その近似解法を提案する．さらに，提案法の有効性を数値
実験を通して検証する．
上述の多期間在庫流通計画問題以外にも，この種の在庫と輸送を同時に計画する問題に関しては，これまでにいく
つかの研究がある．Kim ら 3)は第 𝐾𝐾𝐾最短路問題のアルゴリ
ズムに基づく，Chan ら 4)は最短路問題のアルゴリズムと線形計画法に基づく，Jin ら 5)は動的計画法とラグランジアン
分解に基づく，Kang ら 6)は２段階法に基づく解法を提示している．しかし，これらの研究で取り扱われている問題は，当研究とは異なる観点から設定されたもので，いずれも総品切れ費用の最小化を目的としたものではない．
以下では，次の2.で，災害時の救援物資供給活動における多期間在庫流通計画問題を混合整数計画問題に定式化す
る．次いで3.において，緩和固定法に基づくこの問題の近似解法を提案する．そして4.では，提案した解法の有効性を数値実験で検証し，最後の5.で結論を述べる．

2. 定 式 化
ここでは，災害時の救援物資供給活動における多期間在庫流通計画問題を混合整数計画問題に定式化する．既述のように，当研究の多期間在庫流通計画問題は，文献 2)のそれ
を災害時の救援物資供給活動に適用するために拡張したものであるが，この文献の定式化においては，品目数を単一品目とし，需要点における在庫のみを考慮した上で，輸送――− 11 −

災害時の救援物資供給活動における多期間在庫流通計画問題に対する緩和固定法

ヘッダー

費用と在庫保管費用の総和の最小化を目的としている．これに対して以下では，品目数を多品目とし，需要点に加えて供給点の在庫も考慮した上で，総品切れ費用の最小化を目的とした定式化を示す．
需要点の集合を 𝑀𝑀 𝑀 {1,2, ⋯ , 𝑚𝑚}，供給点を 0 とし，需要点と供給点を併せた拠点の集合を 𝑀𝑀� = 𝑀𝑀𝑀𝑀𝑀{0} とする．また，品目の集合を 𝑁𝑁 𝑁 {1,2, ⋯ , 𝑛𝑛}，車両タイプの集合を 𝑉𝑉 𝑉
{1,2, ⋯ , 𝑣𝑣}，計画期間の集合を 𝑇𝑇 𝑇 {1,2, ⋯ , 𝑡𝑡}，期間 0 を含む
計画期間の集合を𝑇𝑇� = 𝑇𝑇 𝑇 {0} とする．さらに，次を定義す
る．
𝑐𝑐���

:

𝑑𝑑���

:

𝑏𝑏�

:
:

𝑟𝑟�

:

𝑒𝑒��

𝑅𝑅

:
:

𝑔𝑔��

：

𝑓𝑓��

𝑎𝑎�

:

𝐼𝐼���

:

𝑥𝑥���

:

需 要 点 ℎ ∈ 𝑀𝑀𝑀 に お け る 品 目 𝑖𝑖 𝑖𝑖𝑖 の 期 間
𝑘𝑘 𝑘𝑘𝑘𝑘の単位バックオーダー量あたりの品
切れ費用
需 要 点 ℎ ∈ 𝑀𝑀𝑀 に お け る 品 目 𝑖𝑖 𝑖𝑖𝑖 の 期 間
𝑘𝑘 𝑘𝑘𝑘𝑘の需要量
車両タイプ 𝑗𝑗 𝑗𝑗𝑗𝑗の最大積載量
供給点 0 における品目 𝑖𝑖 𝑖𝑖𝑖𝑖の期間 𝑘𝑘 𝑘𝑘𝑘の補充量
供給点 0 と需要点 ℎ ∈ 𝑀𝑀𝑀間の１往復あたりの輸送時間
１計画期間の規定時間
拠点 ℎ ∈ 𝑀𝑀� における品目 𝑖𝑖 𝑖𝑖𝑖𝑖の初期在庫量
需要点 ℎ ∈ 𝑀𝑀𝑀における品目 𝑖𝑖 𝑖𝑖𝑖𝑖の初期バックオーダー量品目 𝑖𝑖 𝑖𝑖𝑖𝑖の単位量あたりの積載容量

𝑦𝑦���

:

:

拠点 ℎ ∈ 𝑀𝑀� における品目 𝑖𝑖 𝑖𝑖𝑖𝑖の期間 𝑘𝑘 𝑘𝑇𝑇� の在庫量
需要点 ℎ ∈ 𝑀𝑀𝑀における品目 𝑖𝑖 𝑖𝑖𝑖𝑖の期間 𝑘𝑘 𝑘𝑇𝑇� のバックオーダー量
需 要 点 ℎ ∈ 𝑀𝑀𝑀へ の 品 目 𝑖𝑖 𝑖𝑖𝑖𝑖の 期 間 𝑘𝑘 𝑘𝑘𝑘の輸送量
供 給 点 0 と 需 要 点 ℎ ∈ 𝑀𝑀𝑀間 の 車 両 タ イ プ
𝑗𝑗 𝑗𝑗𝑗𝑗による期間 𝑘𝑘 𝑘𝑘𝑘𝑘の往復輸送回数とすると，災害時の救援物資供給活動における多期間在庫
流通計画問題は次のような混合整数計画問題に定式化され
る．
(P)

min.
s. t.

� � � 𝑐𝑐��� 𝑠𝑠���(1)�∈� �∈� �∈�𝐼𝐼��� = 𝐼𝐼�,�,��� + 𝑒𝑒�� − � 𝑥𝑥��� , 𝑖𝑖 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖�∈�ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀

� 𝑎𝑎� 𝑥𝑥��� ≤ � 𝑏𝑏� 𝑦𝑦��� , ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀
�∈�

�∈�

� 𝑟𝑟� 𝑦𝑦��� ≤ 𝑅𝑅𝑅 𝑗𝑗 𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗

�∈�

(3)

(4)

(6)

𝑠𝑠��� = 𝑔𝑔�� , ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀(8)𝐼𝐼��� = 0, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀

(7)

(10)

𝑦𝑦��� ∈ {0, 1, 2, ⋯ }, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀

(12)

(11)

ここで，式(1)は目的関数で品切れ費用の総和を最小化す
ることを表す．そして式(2)は，供給点における在庫量，補充量，需要点への輸送量の関係を規定する．式(3)は，各需要点における在庫量，バックオーダー量，輸送量，需要量の関係を規定する．また式(4)は，各期間の各需要点への総輸送（積載）量が，各期間に各需要点へ訪問する車両タイ
プの最大積載量の総和以下であることを規定する．式(5)は，各期間の各車両タイプの総輸送時間が 1 期間の規定時間以下であることを規定する．また式(6)は，各拠点における各品目の初期在庫量を規定する．式(7)は，各需要点における各品目の最終期の在庫量が 0 であることを規定する．そして式(8)は，各需要点における各品目の初期バックオーダー
量を規定する．

混合整数計画問題は NP 困難とよばれる問題クラスに属するため 7)，通常，問題の規模が大きくなると，汎用の混合
整数計画ソルバー（以下では MIP ソルバーと記す）を用いて (P) の最適解を求めることが難しくなる．そこでここでは，混合整数計画問題の一部の整数変数を「連続緩和変数」
または「固定変数」に変更した（MIP ソルバーで求解可能な）問題を解くことにより，元の混合整数計画問題の近似解を求める方法である緩和固定法（relax and fix method）8),9)に着目し，それに基づく (P) の近似解法を提案する．
いま，計画期間の集合 𝑇𝑇 𝑇 {1,2, ⋯ , 𝑡𝑡} を 𝑊𝑊𝑊個の集合 𝑇𝑇 � ={1,2, ⋯ , 𝑡𝑡� }, 𝑇𝑇 � = {𝑡𝑡� + 1, 𝑡𝑡� + 2, ⋯ , 𝑡𝑡� } , ⋯ , 𝑇𝑇 � = {𝑡𝑡��� + 1,
𝑡𝑡��� + 2, ⋯ , 𝑡𝑡𝑡𝑡に分割する．また，これらの集合 𝑇𝑇 � , 𝑇𝑇 � , ⋯,𝑇𝑇 � に 対 応 し た 𝑊𝑊𝑊 個 の 𝑇𝑇𝑇 の 部 分 集 合 𝑈𝑈� 𝑀 �𝑡𝑡� + 1, 𝑡𝑡� +2, ⋯ , 𝑢𝑢� �, 𝜌𝜌 𝑀 1,2, ⋯ , 𝜌 − 1, 𝑈𝑈 � = ∅ と，𝑊𝑊𝑊個の 𝑇𝑇𝑇の部分集
合 𝛺𝛺� 𝑀 �1,2, ⋯ , 𝜔𝜔� �, 𝜌𝜌 𝑀 1,2, ⋯ , 𝑊𝑊を定義する．ただし，(𝑇𝑇� ∪𝑈𝑈� ) ⊆ 𝛺𝛺� , 𝜌𝜌 𝜌𝜌𝜌𝜌𝜌𝜌𝜌 𝜌𝜌であるものとする（𝜔𝜔� は 𝜔𝜔� = 𝑡𝑡𝑡と一意に定まることに注意）．そして，(P) における集合 𝑇𝑇𝑇を集合 𝛺𝛺� に置き換え，制約式(7)の 𝑡𝑡𝑡を 𝜔𝜔� に置き換え，制約式(12)を𝑦𝑦��� ∈ {0, 1, 2, ⋯ }, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 � ∪ 𝑈𝑈��𝑦𝑦��� ≥ 0, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 ∖

(𝑇𝑇 �

∪ 𝑈𝑈

�)

(13)

(14)

に置き換えた問題 (P� ) と，(P) における集合 𝑇𝑇𝑇を集合 𝛺𝛺� に置き換え，制約式(7)の 𝑡𝑡𝑡を 𝜔𝜔� に置き換え，制約式(12)を
���

���

𝑦𝑦��� = 𝑦𝑦��� , ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 ⋃��� 𝑇𝑇 �𝑦𝑦��� ∈ {0, 1, 2, ⋯ }, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀� ∪ 𝑈𝑈�

(5)𝐼𝐼��� = 𝑓𝑓�� , ℎ ∈ 𝑀𝑀� , 𝑖𝑖 𝑖𝑖𝑖

𝑠𝑠��� ≥ 0, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀�

𝑥𝑥��� ≥ 0, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀(2)𝐼𝐼��� − 𝑠𝑠��� = 𝐼𝐼�,�,��� + 𝑥𝑥��� − 𝑑𝑑��� − 𝑠𝑠�,�,��� ,(9)

3. 緩 和 固 定 法

このとき，変数 𝐼𝐼��� ，𝑠𝑠��� ，𝑥𝑥��� ，𝑦𝑦��� をそれぞれ
𝑠𝑠���𝐼𝐼��� ≥ 0, ℎ ∈ 𝑀𝑀� , 𝑖𝑖 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖��𝑦𝑦��� ≥ 0, ℎ ∈ 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀� ∖ ��⋃��� 𝑇𝑇 � � 𝑇 𝑈𝑈� �

(15)

(16)
(17)

に置き換えた問題 (P� ), 𝜌𝜌 𝜌𝜌𝜌𝜌𝜌𝜌𝜌𝜌𝜌𝜌を考える．ただし，����𝑦𝑦��� � は(P��� )の実行可能解である．

ここで，(P� ) は (P) の計画期間を 𝛺𝛺� に限定した上で，計――− 22 −

森山弘海・堀圭佑

ヘッダー

画期間 𝑇𝑇 � ∪ 𝑈𝑈� における (P) の整数変数 ����� � を自由変数（元のままの変数）とし，それら以外の計画期間における(P) の整数変数 ����� � を連続緩和変数とした問題である．

また，(P� ), 𝜌𝜌 𝜌 𝜌𝜌𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌は (P) の計画期間を 𝛺𝛺� に限定し�(P) の整数変数 ����� � をた上で，計画期間 ⋃������ 𝑇𝑇 における(P��� ) の実行可能解に固定した固定変数とし，計画期間𝑇𝑇� ∪ 𝑈𝑈� における (P)の整数変数 ����� � を自由変数とし，それら以外の計画期間における (P) の整数変数 ����� � を連
続緩和変数とした問題である．当研究で提案する緩和固定法は，MIP ソルバーを用いて (P� ), 𝜌𝜌 𝜌 𝜌𝜌𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌の実行可能解（最適解または近似解）を順次算出することで (P) の近似解を求める．
例えば，需要点の集合が 𝑀𝑀 𝑀 {1,2,3}，車両タイプの集合
が 𝑉𝑉 𝑉 {1,2}，計画期間の集合が 𝑇𝑇 𝑇 {1,2,3,4,5} である場合の問題に，𝑊𝑊𝑊𝑊𝑊とし，(a) Problem (P� ) 𝑇𝑇 � = {1}, 𝑇𝑇 � = {2}, 𝑇𝑇 � = {3}, 𝑇𝑇 � = {4,5} 𝑈𝑈� = {2}, 𝑈𝑈 � = {3}, 𝑈𝑈 � = {4}, 𝑈𝑈 � = ∅ 𝛺𝛺� = {1,2,3}, 𝛺𝛺� = {1,2,3,4}, 𝛺𝛺� = {1,2,3,4,5}, 𝛺𝛺� ={1,2,3,4,5}と設定した場合の緩和固定法を適用すると，その手順は次のようになる．
(1)(P) の計画期間を 𝛺𝛺� = {1,2,3} に限定した上で，計画期間 𝑇𝑇 � ∪ 𝑈𝑈� = {1,2} における (P) の整数変数 ����� � を自由変数とし，それら以外の計画期間 {3} における (P)(P� )の整数変数 ����� � を連続緩和変数とした問題
を設定し，その実行可能解をMIPソルバーを用いて求める（Fig.1の(a)参照）．
(2)(b) Problem (P � )(P) の計画期間を 𝛺𝛺� = {1,2,3,4} に限定した上で，計画
期 間 𝑇𝑇 � = {1} に お け る (P) の 整 数 変 数 ����� � を (P� )�� に固定した固定変数とし，計画期の実行可能解 �����
��
間 𝑇𝑇 ∪ 𝑈𝑈 = {2,3} における (P) の整数変数 ����� � を自由変数とし，それら以外の計画期間 {4} における (P)の整数変数 ����� � を連続緩和変数とした問題 (P � ) を設定し，その実行可能解をMIPソルバーを用いて求める（Fig.1の(b)参照）．
(3)(P) の計画期間を 𝛺𝛺� = {1,2,3,4,5} に限定した上で，計画期間 𝑇𝑇 � ∪ 𝑇𝑇 � = {1,2} における (P) の整数変数 ����� ��を(P � ) の実行可能解 �����
� に固定した固定変数とし，
��
計 画 期 間 𝑇𝑇 ∪ 𝑈𝑈 = {3,4} に お け る (P) の 整 数 変 数����� � を自由変数とし，それら以外の計画期間 {5} における (P) の整数変数 ����� � を連続緩和変数とした問題 (P � ) を設定し，その実行可能解をMIPソルバーを用(c) Problem (P � )いて求める（Fig.1の(c)参照）．
(4)(P) の計画期間を 𝛺𝛺� = {1,2,3,4,5} に限定した上で， 計
画期間 𝑇𝑇 � ∪ 𝑇𝑇 � ∪ 𝑇𝑇 � = {1,2,3} における (P) の整数変数�� に固定した固定変����� � を(P � ) の実行可能解 �����
�
�
{4,5}
数とし，計画期間 𝑇𝑇 ∪ 𝑈𝑈 =における (P) の整数
変数 ����� � を自由変数とした問題 (P � ) を設定し，その実行可能解をMIPソルバーを用いて求める（Fig.1の(d)参照）．このとき，(P � ) の実行可能解が元の問題 (P) の近似解となる．
――− 33 −(d) Problem (P � )Fig. 1 Iterations of Relax and Fix Method

災害時の救援物資供給活動における多期間在庫流通計画問題に対する緩和固定法

ヘッダー

なお，緩和固定法の上記のパラメータ 𝑊𝑊，𝑡𝑡� (𝜌𝜌 𝜌 𝜌𝜌𝜌𝜌 𝜌𝜌
𝑊𝑊 𝑊 𝑊𝑊𝑊，𝑢𝑢� (𝜌𝜌 𝜌 𝜌𝜌 𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌 𝜌) ，𝜔𝜔� (𝜌𝜌 𝜌 𝜌𝜌 𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌 𝜌) は，
新たなパラメータ𝜆𝜆(0 < 𝜆𝜆 𝜆 𝜆𝜆) ， 𝜇𝜇(0 ≤ 𝜇𝜇 𝜇𝜇𝜇𝜇𝜇𝜇) ，𝜈𝜈(0 ≤𝜈𝜈 𝜈𝜈𝜈𝜈𝜈𝜈𝜈𝜈𝜈) を導入し，全ての|𝑇𝑇� | ができる限り 𝜆𝜆𝜆に等しくなり，全ての|𝑈𝑈� | ができる限り 𝜇𝜇𝜇に等しくなり，全ての���� � �⋃��� 𝑇𝑇 � � � 𝑈𝑈� � ができる限り 𝜈𝜈𝜈に等しくなることを意図して，次のように定めた．ただし，⌈∙⌉ は ∙ 以上の最小の整数を表す．
𝑡𝑡� = 𝜌𝜌 𝜌𝜌𝜌𝜌𝜌𝜌𝜌𝜌𝜌𝜌 𝜌 𝜌𝜌 𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌 𝜌𝑢𝑢� 𝜌 �

𝑚𝑚

𝑛𝑛

10

𝑧𝑧 ���

28460.0𝑧𝑧 ���

29196.0

𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟

0.975

𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡

101541829.044672.0

0.936

15.50

20

53666.061635.0

0.871

36.23

10

39758.042910.0

0.927

67.69

15

58650.062831.0

0.933

102.64(19)2079176.086120.0

0.919

76.43

(20)

10

47730.051412.0

0.928

45.64

15

71785.079457.0

0.903

74.87

20

88434.0102801.0

0.860

107.541055070.059012.0

0.933

42.86

15

81966.091270.0

0.898

61.99

20

105873.0129695.0

0.816

38.47

10

74732.080497.0

0.928

84.22

15

118164.0

129421.0

0.913

96.97

20

156968.0

185178.0

0.848

113.571095942.0109073.0

0.880

67.23

15

146859.0159302.0

0.922

106.8920190741.0221524.0

0.861

141.5710101428.0111810.0

0.907

35.80

15

145382.0165050.0

0.881

69.84

20

193467.0

233008.0

0.830

72.05

10

141114.0

154576.0

0.913

79.53

15

219435.0254948.0

0.861

107.9020287478.0

327859.0

0.877

145.3310154021.0

189656.0

0.812

82.60

15

234853.0

285868.0

0.822

95.04

20

305363.0

386066.0

0.791

195.20𝑡𝑡(18)

𝑊𝑊 𝑊 ⌈𝑡𝑡𝑡𝑡𝑡⌉

𝑡𝑡� + 𝜇𝜇𝜇𝜇𝜇𝜇𝜇𝜇� + 𝜇𝜇 𝜇𝜇𝜇, 𝜌𝜌 𝜌 𝜌𝜌 𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌 𝜌
𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡その他
𝑢𝑢� + 𝜈𝜈𝜈𝜈𝜈𝜈𝜈𝜈� + 𝜈𝜈 𝜈𝜈𝜈𝜔𝜔� 𝜌 �, 𝜌𝜌 𝜌 𝜌𝜌 𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌 𝜌
𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡その他

Table 1 Computational Results (𝜃𝜃 𝜃𝜃𝜃𝜃)

10

15

20

(21)

例えば，t = 5 である問題において 𝜆𝜆 𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆と設定した場合は，𝑊𝑊 𝑊 ⌈5/2⌉ = 3 となり，𝑡𝑡� =2, 𝑡𝑡� = 4, 𝑢𝑢� =3, 𝑢𝑢� = 5, 𝜔𝜔� = 4, 𝜔𝜔� = 5 と定まる．

10

4. 数 値 実 験

提案した緩和固定法に基づく近似解法（以下では RAF 法と呼ぶ）と (P) を MIP ソルバーで解く方法（以下では MIP法と呼ぶ）を比較するために数値実験を実施した．数値実験で使用した実験データの作成方法と実験環境に関しては以下の通りである．
(1)

(2)

(3)

(5)

20

需要点 ℎ ∈ 𝑀𝑀𝑀における品目 𝑖𝑖 𝑖 𝑖𝑖𝑖の期間 𝑘𝑘 𝑘𝑘𝑘𝑘の需要量 𝑑𝑑��� は次式で定めた．

20

ただし，𝑈𝑈�0,100� は �0,100� の一様整数乱数である．

供 給 点 0 に お け る 品 目 𝑖𝑖 𝑖 𝑖𝑖𝑖の 期 間 𝑘𝑘 𝑘𝑘𝑘𝑘の 補 充 量𝑒𝑒�� は次式で定めた．
(23)

(7)

１計画期間の規定時間 𝑅𝑅𝑅は𝑅𝑅 𝑅𝑅𝑅𝑅𝑅とし，供給点 0 と需要点 ℎ ∈ 𝑀𝑀𝑀間の１往復あたりの輸送時間 𝑟𝑟� は次式
で定めた．

(8)

𝑒𝑒�� 𝜌 � 𝑑𝑑���
�∈�

𝑅𝑅𝑅𝑅
𝑅𝑅𝑅𝑅
,1.0 ∙ �
𝑚𝑚
𝑚𝑚

��

15

(22)

��

(24)

��

��

ただし，𝑈𝑈 �0.5 ∙ � ,1.0 ∙ � � は �0.5 ∙ � ,1.0 ∙ � � の一様整数乱数である．
(6)10

需要点 ℎ ∈ 𝑀𝑀𝑀における品目 𝑖𝑖 𝑖 𝑖𝑖𝑖の期間 𝑘𝑘 𝑘𝑘𝑘𝑘の単位
バックオーダー量あたりの品切れ費用 𝑐𝑐��� は 𝑐𝑐��� =1 とした．

𝑟𝑟� 𝜌 𝑈𝑈 �0.5 ∙1520

需要点数 𝑚𝑚𝑚は 𝑚𝑚 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚の 3 通り，品目数 𝑛𝑛𝑛は𝑛𝑛 𝑛10,15,20 の 3 通り，計画期間数 𝑡𝑡𝑡は 𝑡𝑡 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡の 3 通
りとし，車両タイプ数 𝑣𝑣𝑣は，𝑚𝑚 𝑚𝑚𝑚𝑚の場合は 𝑣𝑣 𝑣𝑣𝑣，
𝑚𝑚 𝑚𝑚𝑚𝑚の場合は 𝑣𝑣 𝑣𝑣𝑣，𝑚𝑚 𝑚𝑚𝑚𝑚の場合は 𝑣𝑣 𝑣𝑣𝑣とした．

𝑑𝑑��� = 𝑈𝑈�0,100�

(4)

15

車両タイプ 𝑗𝑗 𝑗 𝑗𝑗𝑗の最大積載量 𝑏𝑏� は，パラメータ𝜃𝜃𝜃を事前に与えて，次式で定めた．
∑�∈� ∑�∈� ∑�∈� 𝑑𝑑���
𝑏𝑏� 𝜌 �𝜃𝜃 ∙�
(25)𝑚𝑚 𝑚𝑚𝑚(9)

12.01

拠 点 ℎ ∈ 𝑀𝑀� に お け る 品 目 𝑖𝑖 𝑖 𝑖𝑖𝑖の 初 期 在 庫 量 𝑓𝑓�� は𝑓𝑓�� = 0 とした．

需要点 ℎ ∈ 𝑀𝑀𝑀における品目 𝑖𝑖 𝑖 𝑖𝑖𝑖の初期バックオーダ
ー量 𝑔𝑔�� は 𝑔𝑔�� = 0 とした．

品目 𝑖𝑖 𝑖 𝑖𝑖𝑖の単位量あたりの積載容量 𝑎𝑎� は 𝑎𝑎� =1 とした．
(10) 使 用 計 算 機 は Intel(R) Core(TM) i7-7700HQ CPU
2.80GHz（2-core）の CPU と 16GB のメモリを搭載した PC（OS：Windows 10 Home 64bit）で，使用言語は
Python である．
(11) 使用した MIP ソルバーは Gurobi Optimization Version
9.1.210)である．
(12) RAF 法のパラメータ 𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆は𝜆𝜆 𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆𝜆に
設定した．

―
―
− 44 −

森山弘海・堀

圭佑

ヘッダー

𝑡𝑡

10

Table 2 Computational Results (𝜃𝜃 𝜃 𝜃𝜃𝜃)

𝑚𝑚

𝑛𝑛

10

𝑧𝑧 ���

5087.0𝑧𝑧 ���

8269.0𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟

0.615

134.2010157741.014333.0

0.540

262.27209638.017327.0

0.556

107195.010250.0

1511498.0

20

15

20

10

15

15

20

10

20

15

20

𝑚𝑚

𝑛𝑛

10

𝑧𝑧 ���

1908.0𝑧𝑧 ���

2050.0𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟

0.931

111.9910152710.02624.01.033

116.16225.97203232.03702.50.873

107.01

0.702

246.15102692.03360.00.801

174.3818057.0

0.637

255.16154423.07241.00.611

205.2914662.025844.0

0.567

262.16205639.08876.50.635

201.58107387.012030.0

0.614

210.84103197.03843.00.832

145.121511216.016574.0

0.677

187.41154726.05870.00.805

111.862016832.029214.5

0.576

246.76206955.09765.00.712

166.58107276.012690.0

0.573

269.70102756.03380.00.815

168.721510934.020231.0

0.540

277.83153910.06941.00.563

214.882014461.030114.0

0.480

263.67205095.07252.00.703

167.491010248.020919.0

0.490

329.54103927.06749.00.582

178.441516323.030831.0

0.529

373.44156104.08386.00.728

269.522025605.039179.0

0.654

399.46208480.013483.0

0.629

362.071011150.0

17827.0

0.625

261.83104750.07614.00.624

164.8415

18362.049730.0

0.369

290.49156350.010204.0

0.622

255.562024662.053463.0

0.461

402.4720

9560.015490.0

0.617

291.931010963.025016.0

0.438

285.76104244.04416.00.961

183.161516801.038611.8

0.435

327.65155398.06747.00.800

226.202022576.057385.0

0.393

425.14208319.011852.0

0.702

333.651015516.030957.1

0.501

439.58105704.09009.00.633

292.061523784.056544.4

0.421

536.58159564.014877.0

0.643

428.492031296.090948.0

0.344

591.972011737.020490.0

0.573

454.761014777.032800.0

0.451

298.79106178.010488.0

0.589

145.631522069.052642.0

0.419

395.68158877.013212.0

0.672

256.312030582.0118239.4

0.259

542.782012392.021290.0

0.582

421.75𝑡𝑡

𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡

10

10

15

15

20

10

20

15

20

(14) MIP法の計算は，𝑡𝑡 𝑡𝑡𝑡𝑡の場合は計算時間300秒，𝑡𝑡 𝑡
15 の場合は計算時間450秒，𝑡𝑡 𝑡𝑡𝑡𝑡の場合は計算時間600秒で打ち切りとした．なお，打切りの場合には，その時点で求まっている最良の実行可能解を出力した．
以上の環境の下に実施した数値実験の結果を Table 1～3に示す．ただし，Table 1～3 に関しては以下の通りである．

(2)

15

20

(13) RAF 法における各(P� ), 𝜌𝜌 𝜌 𝜌𝜌𝜌𝜌 𝜌 𝜌 𝜌𝜌𝜌の計算は，相対誤差（𝜃 �上界値 − 下界値��上界値）が 0.05 以下の実行可能解の求解，もしくは，計算時間 30 秒で打ち切
りとした．

(1)

Table 3 Computational Results (𝜃𝜃 𝜃 𝜃𝜃𝜃)

Table 1 ～ 3 は 式 (25) の パ ラ メ ー タ 𝜃𝜃𝜃 を そ れ ぞ れ
0.7,0.8,0.9 とした場合の結果である．

Table 1～3 の 𝑧𝑧 ��� は RAF 法で求まった実行可能解の目的関数値である．

𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡(3)

Table 1～3 の 𝑧𝑧 ��� は MIP 法で求まった実行可能解の目的関数値である．なお，MIP 法は全ての問題例で計算打ち切り時間以内に最適解を確認できなかった．

(4)

Table 1 ～ 3 の 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 は 𝑧𝑧 ��� に 対 す る 𝑧𝑧 ��� の 比 率 で
𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑟𝑟𝑟 ��� ⁄𝑧𝑧 ��� である．

(5)

Table 1～3 の 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 は RAF 法の計算時間で単位は秒である．

Table 1〜3 の結果は，全 81 題中（𝜃𝜃 𝜃 𝜃𝜃𝜃𝜃𝜃𝜃 𝜃 𝜃𝜃𝜃𝜃𝜃 𝜃
10, 𝑛𝑛 𝑛𝑛𝑛𝑛の問題例を除く）80 題の問題例において， RAF
法の方が MIP 法よりも，より良い実行可能解がより少ない計算時間で求まったことを示している．また，それら 80 題の問題例における 𝑧𝑧 ��� に対する 𝑧𝑧 ��� の比率 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟は，𝜃𝜃 𝜃
0.7 の場合では 0.791～0.975，𝜃𝜃 𝜃 𝜃𝜃𝜃の場合では 0.259～
0.702，𝜃𝜃 𝜃 𝜃𝜃𝜃𝜃の場合では 0.563～0.961 となり，問題例によ――− 55 −

災害時の救援物資供給活動における多期間在庫流通計画問題に対する緩和固定法

ヘッダーって良さの程度が大きく異なることを示している．
さらに，RAF 法は，解法の性質上，計画期間数 𝑡𝑡𝑡が大きくなるほど計算時間 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡が増加する傾向にあると考えられるが，パラメータ 𝜃𝜃𝜃ごとの各 𝑡𝑡𝑡における 9 題の問題の計算時間 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡の平均値は，𝜃𝜃 𝜃 𝜃𝜃𝜃𝜃の場合では 59.84 秒（𝑡𝑡 𝑡10），83.75 秒（𝑡𝑡 𝑡𝑡𝑡），98.14 秒（𝑡𝑡 𝑡 𝑡𝑡），𝜃𝜃 𝜃 𝜃𝜃𝜃の場合
では 225.66 秒（𝑡𝑡 𝑡𝑡𝑡），318.71 秒（𝑡𝑡 𝑡𝑡𝑡），427.10 秒（𝑡𝑡 𝑡20），𝜃𝜃 𝜃 𝜃𝜃𝜃𝜃の場合では 148.89 秒（𝑡𝑡 𝑡𝑡𝑡），230.38 秒（𝑡𝑡 𝑡15），304.67 秒（𝑡𝑡 𝑡 𝑡𝑡）となり，その傾向があることを示
している．

参考文献
1) 矢野裕児，“東日本大震災での緊急救援物資供給の問題点と課題，” 物流問題研究，Vol.56, pp.11-15, 20112) J.-U. Kim and Y.-D. Kim, “A Lagrangian Relaxation Approach toMulti-Period Inventory/Distribution Planning,” Journal of the
Operational Research Society, Vol. 51, No. 3, pp. 364-370, 2000
3) J.-U. Kim and Y.-D. Kim, “A Decomposition Approach to a Multiperiod Vehicle Scheduling Problem”, Omega, Vol. 27, Issue 4, pp.
421-430, 1999
4) L. M. A. Chan, A. Muriel, Z. J. Shen, D. Simchi-Levi and C.P. Teo,

5. お わ り に“Effective

Zero-inventory-ordering

PoliciesfortheSingle-warehouse Multiretailer Problem with Piecewise Linear Cost

当研究では，災害時の救援物資供給活動における多期間
在庫流通計画問題を設定し，それを混合整数計画問題に定式化した．そして，この問題の緩和固定法に基づく近似解法を提案し，その有効性を検証するための数値実験を実施
した．数値実験では，緩和固定法に基づく近似解法と問題の定式化を MIP ソルバーで解く方法の比較を行った．その結果，需要点数，品目数，計画期間数がそれぞれ 10〜20 である全 81 題中 80 題の問題例において，緩和固定法に基づく近似解法の方が，問題の定式化を MIP ソルバーで解く方
法よりも，より良い実行可能解がより少ない計算時間で求まることを検証した．
しかしながら，提案法の実用性を高めるためには，求まる解を更に改良するとともに，計算時間の更なる短縮が必要である．それゆえ今後，解の改善方法や問題の縮小化方法などを開発し，提案法の一層の効率化を図る必要がある．

Structures”, Management Science, Vol. 4, No. 11, pp. 1446–1460,
2002
5) Y. Jin and A. Muriel, “Single-warehouse Multi-retailer Inventory
Systems with Full Truckload Shipments”, Naval Research Logistics,
Vol. 56, Issue 5, pp. 450-464, 20096) J. -H. Kang and Y. -D. Kim, “Coordination of Inventory andTransportation Managements in a Two-level Supply Chain,”International Journal of Production Economics, Vol. 123, Issue 1,
pp. 137-145, 20107) 久保幹雄, 田村明久, 松井知己 編集, 応用数理計画ハンドブ
ック, 朝倉書店, 2002
8) Y. Pochet and L. A. Wolsey, Production Planning by Mixed Integer
Programming, Springer, 2006
9) L. A. Wolsey, Integer Programming, john Wiley and Sons, 1998
10) Gurobi Optimization, Inc. Gurobi Optimizer Reference Manual
Version 8.1.0, 2018――
− 66 −