数理解析研究所講究録
第 1864 巻 2013 年 110-118

110

自販機サプライチェーンに対する多品種配送計画問題

名古屋工業大学大学院社会工学専攻*

小島貢利 (Mitsutoshi Kojima)

大野勝久 (Katsuhisa Ohno),

田村隆善 (Takayoshi Tamura)

愛知工業大学経営学部**

Department of Industrial Management Engineering, Nagoya Institute of Technology*

Faculty of Management, Aichi Institute of Technology**

1.

はじめに

日本国内における自販機の普及台数は，飲料向けだけでも 260 万台あり，年間自販金額は 2 兆 4 千億円である．たばこ自販機など全ての自販機を含めれば，それらの普及台数は約 400 万台，年間自販金額は 5 兆 3 千億円に達する [1]. 各所に点在する自販機への商品の補充は配送車で行うが，補充量は現地に到着しないと確定せず，補充量に応じて積載量も減少し，途中でデポに戻る必要が生じる．したがって，需要が確率的に変動する場合に，配送車がどのような順番で自販機を巡回すれば良いか？は，配送コスト削減や環境負荷低減の観点から重要な問題となってくる．

本研究では，需要が確率的に変動する，多品種の商品を補充する自販機サプライチ
ェーンに対する配送計画問題の定式化を行い，実用規模の問題に適用可能な最適化アルゴリズムを提案する．

2

自販機サプライチェーンに対する配送計画問題$n$

個所の自販機に$G$

位期間当たりの需要量$Pr\{D_{tg}=k\},$品種の商品を配送する問題を考える．各自販機 の商品 $g$ の単$i$$D_{ig}$$i=1,\cdots,n,$は確率的に変動し， における$i$$g=1,\cdots,G,$$k=1,\cdots,K_{ig}$$g$の需要量が$k$となる確率が与えられるものとする．さらに，

1 配送には各商品の積載容量 の車 1 台を使用する．
2 自販機 $larrow m$ 間の配送費用 (距離等) は $d(l,m)$ である$l\neq m,$$m\in\{0,1,\cdots, n\}$ であり， はデポを表す．
$Q_{g}$$)$

$)$

$l,$

ここで，$0$3 各商品の需要量は互いに独立であり，配送に訪問したときに確定する．配送の順$)$

番に依存した需要量の変動はないものとする．

4$)$

自販機への配送後，次にどの自販機に行く力$\searrow$

または，補充のためにデポに戻る

111かを決定する．

を仮定する．問題は，全ての自販機に配送し終わるまでの総配送費用を最小にする配送政策を求めることである．

ここで自販機 1 に着いて補充した後の商品$q_{1}=(q_{l1}, \cdots,q_{lG})$

とおく$j_{i}g\in\{?,0,1,\cdots,K_{i}g\}$

さらに自販機とおき，$j_{i}=(j_{i1},\cdots,j_{iG})$$i$$g$の積載量を$q_{/g^{\in}}\{0,1,\cdots,Q_{g}\}$における商品$g$とおき，の残存需要量をとおく．ただし，?は 1 度も訪れてぃないた

め未知である状態を表す．
自販機 に着いて補充した後のシステムの状態 を $X=(l,q_{1},j_{1},\cdots,j_{n})$ と表し，状態空$0=(0,\cdots,0)$ ,? $=(?,\cdots,?)$ ,間を とおく．このとき，初期状態を , 最終状態を
$l$

$X$

$S$

$X_{f},$$X_{0}$とおけば，$X_{0}=(0,Q,?,\cdots,?)$$Q=(Q_{1},\cdots,Q_{G})$全状態数は $(n+1) \prod_{g=1}^{G}\{g$,$X_{f}=(0,Q,0,\cdots,0)$で与えられる．

4 の決定を表すために，1 の次に訪問する自販機を$)$需要量が正のとき，直接$larrow m$$X$で決定$\mathcal{U}=(m,a)$とおき，いずれかの商品の残存で取りうる決定の集合 $U(X)$ は，$U(X)=\{\{m\in\{1,2,\cdots,n\}|j_{m}\neq 0\}\cup\{0\}\}\cross\{a$$X$$m$と移動する決定を $a=0$ とおき，補充のため $larrow 0arrow m$ と移動する決定を $a=1$ とおけば，状態状態と表すことができる．

をとり，状態: $a\in\{0,1\}\}$ で与えられる．

$X’=(m,q_{m},j_{1},\cdots, j_{m}’,\cdots,j_{。})$

へ推移したときの費用を $g(x, u, x’)$ とおけば，$g(x,u,x’)=\{\begin{array}{ll}d(l,m) if u=(m, 0)d(l, 0)+d(0,m) if u=(m,1)\end{array}$

であり，状態$x’$(1)の $q_{mg},j_{mg}$ は$q_{mg}=\{\begin{array}{l}[q_{lg}-D_{mg}]^{+}, ifu= 伽，0 ),jmg=?{[}q_{1g}-j_{mg}]^{+}, ifu=(m,0),j_{mg}\neq?\end{array}$$[Q_{g}-D_{mg}]^{+},$$ifu=(m,1),j_{ng}=$ ?

$[Q_{g}-j_{mg}]^{+},$$ifu=(m,1),j_{mg}\neq$(2)?

$j_{mg}’=\{\begin{array}{l}[D_{mg}-q_{lg}]^{+}, ifu=(m,0),j_{mg}=?{[}j_{mg}-q_{lg}]^{+}, ifu=(m,0),j_{mg}\neq?{[}D_{mg}-Q_{g}]^{+}, ifu=(m,1),j_{mg}=?{[}j_{mg}-Q_{g}]^{+}, ifu=(m,1),j_{mg}\neq?\end{array}$(3)$[q]^{+}= \max(0,q)$ である．また，そのときの遷移確率はで与えられる．ただし，り$P_{a’}(u)=$$P_{xx},(u,g)$
$g=1$

(4)

112

(5)

$P_{\alpha^{}}’(u,g)=\{\begin{array}{l}Pr\{D_{mg}=k\}if[Case]1 if [Case]\end{array}$で与えられる．状態 から出発し，最終状態$x$$x_{f}$に至る最小の配送費用を $J(x)$ とおくと，問題は最適性方程式(6)$J^{\cdot}(x)= \min_{u\in U(x)}\sum_{x’\in S}P_{\alpha’}(u)\{g(x,u,x’)+J^{\cdot}(x’)\}x\in S$をみたす最小費用$J^{*}(x_{0})$と (6) 式右辺を最小化する最適政策を求めることである．

3. SBMPIM

本研究では，生産システムの最適制御問題で有効性が示されている，
SBMPIM(Simulation Based Modified Policy Iteration Method) $[5,6]$ を用いた，有限期間の最適性方程式 (6) 式に基づく，近似 $DP$ アルゴリズムを提案する．
Stepl : (初期設定)
初期状態 , 最終状態
$x_{0}$

正整数$c_{\max}$$x_{f}$, シミュレーション回数, 収束判定のための$\epsilon’\geq\epsilon>0,$を定める．台の自販機への配送が完了していない状態の集合を$i$

シミュレーションで訪問済の状態の集合を$i=0,1,\cdots,n$$k_{\max}$$S_{u}=\emptyset$とおき，Svl (空集合),とおく．各自販機において$S_{v}=\{S_{v}^{0},S_{v}^{1},\cdots,S_{v}^{n}\}$とおく．さらに，補助的な状態の集合$S_{v}^{i}$,$=\emptyset$

需要を各商品の平均需要量の総和でおきかえた、単一品目の VRP を解き [7], 自販機の訪問順を$\tau=(0,i_{1},i_{2},\cdots,i_{N},0)$

とおく．ここで自販機の番号を$\tau$( $i_{j}=0$ デポ も含む)

(7)に現れる順に $i_{1}=1,i_{2}=2,\cdots,i_{N}=n$ とデポをスキップしてつけ直す．初期政策を$f(i, q_{i},0,\cdots,0, j_{i}, \cdot,\cdots, \cdot)=\{\begin{array}{l}\}_{i+1,0)}^{i,1)} j_{i}=0j_{i}\neq 0 の\hslash ] つと q_{i}\neq 0 き のとき (i+1,1) j_{i}=0 かつ q_{i}=0 のとき\end{array}$

(8)

113
で与える．

政策反復の繰り返し回数 $r=1$ , シミュレーションの繰り返し回数 $k=1$ , 収束判定の繰り返し回数 $c=1$ とおく，さらに，状態 $x=x_{0},$ $S_{v}=\{x\}$ とおき，Step2 のシミュレー
ションにおいて各反復で訪問する状態の集合を$S_{T}=\{S_{T}^{1},\cdots,S_{\tau^{mx}}^{k}\},$$S_{T}^{i}=\emptyset,i=1,\cdots,k_{\max}$とおく．

Step2 : (シミュレーション)
政策 $f$ のもとでの状態$k$$x_{0}$から状態$x_{f}$へのシミュレーションを砺 ax 回行う．

回目のシミュレーションにおいて訪問した状態の集合を畔

問回数を $v(x)$ , 政策 $f$ のもとでの状態$x$から最終状態$x_{f}$$=\{x\}$, 状態$x$への訪への費用を $J^{k}(x)=0$ とおく．

与えられた確率分布に従って，各品目，各自販機ごとに需要量の乱数を発生させる．
$x’=(m,q_{m},i_{1}’,\cdots,i_{n}’)$ ,Step2-1 状態 $x=(l,q_{1},i_{1},\cdots,i_{n})$ で決定 $f(x)=(m,a)$ をとり，$p(x’)=\{i_{j}’\neq 0$

Step2-2となる数 を定める．
$\}$$y\in S_{T}^{k}$にたいして費用を(9)$J^{k}(y)=\{\begin{array}{l}J^{k}(_{J})+d(l,m) , if a=0,J^{k}(y)+d(l,0)+d(0,m) , if a=1.\end{array}$$J^{k}(x’)=0,$と更新し，$x’\not\in S_{V},x’\not\in S_{u}$$x’\not\in S_{V},x’\in S_{u}$$S_{u}=S_{u}-\{x’\}$$x’\in S_{V}$$S_{T}^{k}=S_{T}^{k}\cup\{x’\}$

とおく．

ならば $S_{V}^{p(x’)}=S_{v}^{p(x’)}\cup\{x’\},$ $v(x’)=1,$ $J(x’)=0,$ $f(x’)=$ 初期政策とおき，

ならば $S_{\nu}^{p(x’)}=S_{V}^{p(x’)_{\cup}}\{x’\},$$v(x’)=1,$$J(x’)=0,$$f(x’)=$ 初期政策，とおく．

ならば $v(x’)=v(x’)+1$

Step2-3 全ての状態 y$\in$$S_{T}^{k}$と更新し，$x’\neq x_{f}$$x=x’$ とおき，Step2-1 へ．
ならば，にたいして，(10)$J(y)=J(y)+ \frac{1}{\nu(y)}(J^{k}(y)-J(y))$$k=k+1$ とおき，と更新し，$k\leq k_{\max}$ならば，$x=x_{0},$$J^{k}(x)=0,$$S_{T}^{k}=\{x\}$とおき，Step2-1

へ．

Step2-4$k_{\max}$

回のシミュレーションで求められた費用$J^{k}(x_{0})$の平均値(11)$\overline{J}^{r}(x_{0})=\frac{1}{k_{\max}}\sum_{k=1}^{k_{\max}}J^{k}(x_{0})$を計算する．

Step3 : (収束判定)$r=1$

ならば，Step4 へ$| \overline{J}^{r}(x_{0})-\overline{J}^{r-1}(x_{0}\int/\overline{J}^{r}(x_{0})<\epsilon’$ならば $c=c+1$とおき，さもなければ$c=1$ とおいて

Step4

114
へ．
$c<c_{m\alpha}$

ならば Step4 へ．

$c\geq c_{ma}$ならば$\{\overline{J}^{r}(x_{0}),\cdots,\overline{J}^{r-c+1}(x_{0})\}$

し，自由度 c-l の 分布の両側$t$$\alpha$の不偏分散

点の値を$\sigma_{s}^{2}$$t_{\alpha}(c-1)$と平均$\overline{J}(x_{0})=\{\sum_{c’=0}^{c-1}\overline{J}^{r-c’}(x_{0})\}/c$を計算としたとき，$t_{\alpha}(c-1)\sigma_{s}/(\sqrt{c}\overline{J}(x_{0}))<\epsilon$$c=c+1$ とおいて Step4 へ．
をみたせば停止．さもなければ，

Step4 : (政策改良)
Step4-1 $p=0,1,$$\cdots,n$の順番に，以下を計算する．

$x\in S_{\nu}^{p}$にたいして(12)$J(x)= \min_{xu\in N(x,f())}\{\sum_{x^{-}\in S}P_{xx},(u)\{g(x,u,x’)+J(x’)\}\}$となるを計算する．ここで $N(x,f(x))$ は $U(x)$ における $f(x)$ の近傍であり，$J(x’)=$ 初期政策から$f(x’)=$ 初期政策，にたいしてはとおき，$P_{xx’}(u)>0$$S_{u}=S_{u}\cup\{x’\}$$x’\not\in S_{V}\cup S_{u}$$f(x)$ を (12) 式右辺を最小化$f(x)$ が $J(x)$ を与えなければ，決まる値を用いて計算する．

する決定に改良する．

Step4-2x。にたいして$\in S$(13)$J(x)= \min_{Xu\in N(x,f())}\{\sum_{\chi^{}\in S}P_{\alpha’}(u)\{g(x,u,x’)+J(x’)\}\}$$P_{r’}(u)>0$ となるを計算する．
Sv 。にたいしては (x’) 初期政策から決まる値を$f(x)$ を (13) 式右辺を最小化する決定に$f(x)$ が $J(x)$ を与えなければ，用いて計算する．
$x’$$\not\in$$\cup S$

$J$$=$

改良する．
$r=r+1,$ $k=1,$$x=x_{0},$$S_{T}=\{S_{T}^{1},\cdots,S_{\tau^{mx}}^{k}\},$$S_{T}^{l}=\emptyset,i=1,\cdots,k_{\max}$

とおいて Step2 へ．

4. 数値例
自販機の台数 $n=8$ , 品種数 $G=3$ ,各品種の積載容量 $Q_{g}=6$ とおき，自販機が図 1 のようにデポを原点に，一辺が 1 の正方格子で配置されているものとする．
自販機の需要量は平均 2 で，項数 2 のシフトした二項分布に従い，$Pr\{D_{l}g=1\}=0.25,$ $Pr\{D_{ig}=2\}=0.5,$ $Pr\{D_{ig}=3\}=0.25,$である．

$K_{ig}=3,$$i=1,\cdots,8,’ g=1,2,3$

115

初期の政策および費用は，文献 [7] の $CD$ -ROM に与えられる，確定的な VRP のTabu-Search プログラムの結果を利用した．各自販機の各商品の需要量が 2 の場合，確定的な VRP の最良解をもとにした訪問順序は以下のようになる．
$0arrow 1arrow 2arrow 0arrow 3arrow 4arrow 5arrow 0arrow 6arrow 7arrow 8arrow 0$

シミュレーション回数砺。$=10000$ ,収束判定の繰り返し回数 $Cmax=5,$$\epsilon=\epsilon’=1.0\cross 10^{-3}$とおく．

現在の政策による決定を $u=(m,a)$ とおくと，以下の 4 つの条件のうち，最大 3 個の政策の近傍 を定義する．
$N_{i}$(1) $a=0$ (直接自販機へ移動) かつ配送後のいずれかの商品の積載量,$q_{lg}<Q_{\wedge}$(最大積載量) の場合$N_{1}=$(m, 殴 訪問箇所は同じで，デポを経由する．

(2) $a=1$ (デポ経由) かっ全ての商品の積載量 $q_{lg}>0$ の場合

訪問箇所は同じで，直接移動する．
(3) 配送を完了していない自販機台数が 2 以上かついずれかの商品の積載量$N_{2}=(m,O)$$q\tau_{g}<Q_{g}$の場合$N_{3}=(m’,1)$

デポを経由する．

ここで，m‘は初期政策における，配送を完了していない の次の自販機とおく．
(4) 配送を完了していない自販機台数が 2 以上かつ全ての商品の積載量 $q_{lg}>0$ の場合$m$$N_{4}=(m’,O)$

直接移動する．

この数値例における全状態数$=1.8\cross 10^{20}$$\neg-(n+1)\prod_{g=1}^{\zeta_{f}^{v}}\{(Q_{g}+1)\prod_{j=1}^{n}(K_{;g}+2)\}=9\cross(7\cross 5^{8})^{3}$(1 咳 8 千京) 状態である．

116

数値計算の結果，最良解の費用は 17.54, 政策反復回数は 171 回，シミュレーションで訪問した状態数は約 78 万状態であった．全状態数と比較して，はるかに少ない状態を訪問して，効率的に最良解を計算していることが分かる．

図 2 において，シミュレーションと政策改良を繰り返しながら，次第に最良解に収束していく様子が観察できる．政策改良を繰り返す途中において，単調にコストが減少しないのは，費用の計算式 (12) 式，(13) 式において未訪問の状態
コスト $J(x’)$$x’\not\in S_{v}\cup S_{u}$におけるを，初期政策から決まる値で近似しているためであると考えられる．

また，各自販機の各品種の需要量が 2(需要の平均値) であった場合の，SBMPIM における最良解の訪問順序は以下のようになる (付録の灰色の部分を参照).
$0arrow 6arrow 7arrow 8arrow 0arrow 5arrow 2arrow 1arrow 0arrow 3arrow 4arrow 0$

上の結果より，各自販機の需要量が同一であっても，確定的な VRP の最良解で求めた訪問順序は，確率的な自販機サプライチェーンにおける最良な訪問順序と一致しないことが分かる．

5. おわりに本研究では，自販機サプライチェーンにたいして，各自販機における需要量が確率的に変動する場合に，1 台の車で積載容量を考慮して，総配送費用 (距離) を最小にする配送政策を求める配送計画問題の定式化を行った．さらに，SBMPIM[5,6] に基づいて開発した，有限期間の最適な配送政策を決定するアルゴリズムを提案し，簡単な数値例でその有効性を検証した．

117
今後の課題は，より大規模な自販機サプライチェーンへの適用である．
参考文献[1] 日本自動販売機工業会:「自販機普及台数及び年間自販金額版」，賃$h$$p:/\triangle$

2010 年 (平成 22 年)

vwvjvma. $orjp/information/fukyu2010$ pdf(2011).

[2] Bertsekas, D. . and Tsitsiklis, J. $N$ .: Neuro-Dynamic Programming, Athena Scientific$P$(1996).
[3] Secomandi, N.:’ Computing neuro-dynamic programming algorithms for the vehicle$|$

routine problem with stochastic demands,“ Computers & Operations Research 27 (2000)

pp.1201-1225.
[4] Powell, W. $B$ .: Approximate Dynamic Programming. Solving the Curses of Dimensionality,$\cdot$Wiley-Interscience, (2007).
[5] Ohno, $K.:”The$ optimal control ofjust-in-time-based production and distribution systems

and performance comparisons with optimized pull systems,/European JoumalofOperational Research 213 (2011) pp. 124-133.
[6] 大野: 「サプライチェーンの最適運用: かんばん方式を超えて」，朝倉書店 (2011).
[7]

大野，田村，伊藤 : 「 Excel によるシステム最適化」，コロナ社 (2001), pp.143-160.

118