Title
ニューロDPによる多品目在庫管理の最適化 (不確実で動
的なシステムへの最適化理論とその展開)
Author(s)
大野, 勝久; 伊藤, 崇博; 石垣, 智徳; 渡辺, 誠
Citation
数理解析研究所講究録 (2004), 1383: 64-71
Issue Date
2004-07
URL
http://hdl.handle.net/2433/25715
Right
Type
Departmental Bulletin Paper
Textversion
publisher
ニューロ
$\mathrm{D}\mathrm{P}$による多品目在庫管理の最適化
愛知工業大学
大野勝久 (Katsuhisa
$\mathrm{O}\mathrm{m}\mathrm{o}$)
Aichi Institute of
Technology,
名古屋工業大学
伊藤崇博 (Takahiro
Ito)
Nagoya
Institute of
Technology,
大阪府立大学
石垣智徳
(Tomonori
Ishigaki)
Osaka
Prefecture
University,
NTT
ドコモ東海
渡辺
誠 (Makoto Watanabe)
NTT
DoCoMo
Tokai
1.
序論
在庫管理問題は
,
古くは
1913
年の
F.WHarris
の経済的発注量
(EOQ)
の研究に始まり
,
経営工学
分野の中で長年にわたり中心的課題として, 多く
の研究が行われてきた。今田こおいては
, 原材料
の調達から消費者にいたる SCM
を中心に
, 多品
目在庫管理問題の最適化が切望されている。
本発表てはます 7
2
章で離散時間多品目在庫管
理問題を平均費用を最小化する時間平均マルコ
フ決定過程問題として定式化する。
動的計画法
(
以下
DP
と略す
)
の枠組みとマルコフ決定過程
(MDP)
は
,
Bellman
によって
1950
年代に提案
されたが
, 政策反復法 (Policy
Iteration
Method,
PIM)
を初めとするアノレゴリズムは
Howard[l],
Puterman[2]
等にまとめられている。離散時間多品
目在庫管理問題にたいしても
,
Omo et
a1.[31
は
,
PIM を改善したアルゴリズムを提案している。し
かし
,
MDP
は
DP
同様
, 品目数の増加とともに
次元の呪いを引き起こし,
実用規模の問題を事実
上解くことができない。そこで本研究では,
人工
知能 [4]
の分野において強化学習
(Reinforcement
Leaming)[5]
とも呼ばれている,
ニューロ・ダイナ
ミツクプログラ
ミング
(NeurO-Dynamic
Programming,
ニューロ
$\mathrm{D}\mathrm{P}$)[
$6,7$
1
の適用を試みる。
ニューロ
$\mathrm{D}\mathrm{P}$は
MDP
の枠組みの中で
,
シミュレ
ーション,
学習
, ニューラルネットワークなどを
組み合わせ
,
大規模な問題に対する近似最適政策
を計算する手法として開発されてきた。最近 Das
et
a1.[8] と Gosavi[9] は,
MDP を含むより一般的な
セミ
マルコフ決定過程
(SMDP)
の時間平均費
用を最小化するアルゴリズムとして
SMART,
RELAXED-SMART
を提案し
, 保全問題へ適用し
ている。 また
He
et a1.[10]
は
,
PIM の値決定ルー
チンをシミュレーションで置きかえた
SBPI
アノレ
ゴリズムを提案し,
在庫管理問題へ適用している。
さらに
Gosavi
et
al.[
垣
]
は
,
SMART
に
$\mathrm{T}\mathrm{D}$(Temporal
Differnce) をとり入れた
$\lambda$-SMART
を開発し
,
航空運賃の収入管理問題へ応用している。
本発表では,
ます
Omo
et
a1.[3]
に基つき次章て
多品目在庫管理問題を説明し
,
3
章で時間平均マ
ルコフ決定過程 (UMDP) への定式化を行い, 若
干の理論的性質を定理として示す。
4
章で修正政
策反復法
(
$\mathrm{M}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{f}_{1}\mathrm{e}\mathrm{d}$Policy
Iteration
Meffiod,
MPIM)
[12-14]
の値決定ルーチンにシミュレーションを
用いる
SBMPIM
アルゴリズム
[15]
を述べる。
5
章
では
SMART,
旺
$\mathrm{L}\mathrm{A}\mathrm{X}\mathrm{E}\mathrm{D}-\mathrm{S}\mathrm{M}\mathrm{A}\mathrm{R}\mathrm{T}$と
SBPI
アノレゴ
リズムを簡単に説明する。
6
章てはこれらアルゴ
リズムを
2
品目在庫管理問題へ適用し
,
SBMPIM,
SMART,
旺
$\mathrm{L}\mathrm{A}\mathrm{X}\mathrm{E}\mathrm{D}-\mathrm{S}\mathrm{M}\mathrm{A}\mathrm{R}\mathrm{T}$,
SBPI
に対する結
果をも含めて
Omo et
a1.[31
による厳密解との比
較を行う。
2.
多品目在庫管理問題
発注費用の形が一般的であり,
超過需要が部分
的もしくはすべてバックログされ,
周期的な観測
を行う
$N$
品目在庫管理システムを考える。
もし
ロストセールを仮定するならば,
品物の納入遅れ
はないものとする。
ここで
$\mathrm{x}=$$(x_{1},x2’\cdots, x_{N})^{T}$
を
各期首における発注前の手持ち在庫水準とする。
ここで
$x_{n}\in \mathrm{Z}=\{0,\pm 1,\pm 2,\cdots\}(n\in \mathrm{N}=\{1,2,\cdots,N\})$
であり,
$T$
は転置を表す。
Johnson[16]
を除くすべ
ての論文は連続状態を論じているが
,
より現実的
な離散状態を議論する。発注は
$\mathrm{x}$と発注政策
f
に
よって決定され
,
$\mathrm{y}=$$(y_{1},y2’\cdots,y_{N})^{T}\in \mathrm{z}^{N}$
まて発
注したとき
,
段取り費用を含む発注費
$K$
(X,y)
が
発生する。 各期の需要
$\mathrm{D}=$$(D_{1},D2’\cdots,D_{N})^{T}$
,
$D_{n}\in \mathrm{Z}_{+}=\{0,1,2,\cdots\}$
$(n\in \mathrm{N})$
は独立な同一分布
$\phi(\mathrm{y},\mathrm{D})$
に従うものと仮定する。
その期に需要
$\mathrm{D}$が発生したならば
,
1
期間当たり在庫・品切れ費
用
$l(\mathrm{y},\mathrm{D})$が発生する。
したがって
, 各期における
95
$L( \mathrm{y})=\sum_{\mathrm{D}\geq 0}\phi(\mathrm{y},\mathrm{D})l(\mathrm{y},\mathrm{D})$
求される条件である。また
, 確率
1
で需要
0
をと
る品目は在庫管理の対象として無視できるので
で与えられる。ここで
$\mathrm{x}\leq \mathrm{y}$(x,
$\mathrm{y}\in \mathrm{Z}^{N}$)
(ま
$x_{n}\leq y_{n}$
条件
4
は一般的な在庫管理システムについて成
立する。目的は計画期間が無限にわたる在庫管理
$(n\in \mathrm{N})$
を表し
,
$\mathrm{x}<\mathrm{y}$
は
$\mathrm{x}\leq \mathrm{y}$かつ
$\mathrm{x}\neq \mathrm{y}$を意味
システムの単位期間当たりの期待費用を最小に
するものとする。また
, 次期の期首在庫は
$u(\mathrm{y},\mathrm{D})$する最適発注政策を見つけることである。
によって与えられるものとする。例えば
,
バック
ログを仮定する場合
,
$u_{B}$(y,
$\mathrm{D}$)
$=\mathrm{y}-\mathrm{D}$となり
,
ロ
3.
マルコフ決定過程による定式化
ストセールを仮定する場合,
前章の多品目在庫管理システムは
UMDP
に定
$u_{L}$(y,
$\mathrm{D}$)
$=([\gamma_{1}-D_{1}\mathrm{r},[\gamma_{2}-D_{2\mathrm{F}},\cdot..,\triangleright_{N} -D_{N}]+)^{T}$
:
式化することができ
,
その最適方程式は次式で与
えられる。
$\int y_{n}-D_{n}\mathrm{r}=\max\{y_{n}-D_{n},0\}$
$(n\in \mathrm{N})$
である。
g(X)+U(x)=y?\sim
々
}){K(x,
$\mathrm{y}$)
$+L( \mathrm{y})+\sum_{\mathrm{D}\epsilon \mathrm{B}}\phi(\mathrm{y},\mathrm{D})$
v(u(y,
$\mathrm{D})$)
$\}$状態
$\mathrm{x}$の値からなる状態空間
$\mathrm{X}$は倉庫容量
$\overline{\mathrm{M}}$と
在庫処理環境
(例えはバックログ
(B),
ロスト
(1)
セール
(L)
$)$によって制約される。
例えば
,
バ
ックログの場合
$\mathrm{X}_{B}=\{\mathrm{x}\in \mathrm{Z}^{N}$
;
$\sum_{n\epsilon \mathrm{N}}a_{n}x_{n}^{+}\leq\overline{\mathrm{M}}\}$$g( \mathrm{x})=\min_{\mathrm{y}\epsilon \mathrm{Y}}\{\sum_{\mathrm{y}\in \mathrm{Y}}\phi(\mathrm{y},\mathrm{D})g(u(\mathrm{y},\mathrm{D}))\}$
(2)
ここで
てあり,
ロストセールの場合
$\mathrm{Y}=\{\mathrm{y}\in \mathrm{X};\mathrm{y}\geq \mathrm{x}\}$
,
$\mathrm{X}_{L}=\{\mathrm{x}\in \mathrm{Z}_{+}^{N}$;
$\sum_{n\epsilon \mathrm{N}}a_{n}x_{n}\leq\overline{\mathrm{M}}\}$$\mathrm{Y}(\mathrm{x})=\{\mathrm{y}\in \mathrm{Y}:g(\mathrm{x})=\sum_{\mathrm{D}\mathrm{e}\mathrm{B}}\phi\langle \mathrm{y},\mathrm{D})g(u(\mathrm{y},\mathrm{D}))\}$
.
となる。
ここで
$a_{n}$は
$n$
番目の品目
1
個当たりの
である。
$g(\mathrm{x}),$ $o(\mathrm{x})$をそれぞれ初期状態が
$\mathrm{x}$であ
大きさであり,
$x_{n}^{+}= \max\{x_{n},0\}$
,
$n\in \mathrm{N}$である。
$X_{B}$
る時の最小期待平均費用と相対値とおく。有限で
は加算集合であり
X
。は有限集合である。
以下の
ある
$X$
の場合
,
確定的な定常マルコフ政策の中
条件を仮定する。
に最適政策が存在することがよく知られている。
条件
1
$\mathrm{x}<\mathrm{y}<\mathrm{z}$であるような任意の在庫水準
定常政策
$f$
は
$\mathrm{X}$の部分集合
$\sigma$と
$\sigma$から
$\mathrm{X}$への写
$\mathrm{x},\mathrm{y},\mathrm{z}\in \mathrm{X}$
に対して以下の式が成立する。
像
$s(\cdot)$
を用いて
$f=(\sigma,S(.))$
と表わすことができ
$K$
(x,
$\mathrm{z}$)
$<K$
(x,
$\mathrm{y}$)
$+K$
(y,z)
かつ
$K$
(x,
$\mathrm{x}$
)
$=0$
.
る。
$\sigma$は
$(\sigma,S(.))$
政策は在庫水準
$\mathrm{x}$において次の
条件
2
もし
$\mathrm{X}$が有限でないならば
ように発注を決定する。
l 而
$\mathrm{x}arrow-\infty$$L(\mathrm{x})=\infty$
てある。 すなわち
, 総ての実数
$\mathrm{x}\in\sigma$のとき
$S(\mathrm{x})$まて発注する。
$M$
に対して
,
$\mathrm{x}\in \mathrm{X}$かつ
$\mathrm{x}\not\geq \mathrm{z}_{M}$を満たすすべての
$\mathrm{x}\in\sigma^{c}\equiv \mathrm{X}-\sigma$のとき
発注しない。
$\mathrm{x}$
に対して
$L(\mathrm{x})>M$
となる
$\mathrm{z}_{7}\in \mathrm{X}$が存在する。
したがって,
$\sigma$を発注状態集合
,
$\sigma^{c}$を非発注状
条件
3
もし
$\mathrm{X}$が有限でないならば各期の需要は
態集合と呼ぶことにする。
有界てある。
すなわち
,
すべての
$\mathrm{x}\in \mathrm{X}$に対して
定理
1
最適発注政策
$(\sigma,S(.))$
は以下を満たす。
$\mathrm{o}\sum_{\mathrm{e}\mathrm{B}}\phi(\mathrm{x},\mathrm{D})=1$
i) もし
$\mathrm{X}$
が有限でないならば
$\sigma^{c}\subset(\sigma^{0}f=\{\mathrm{x}\in \mathrm{X};\mathrm{x}\geq \mathrm{z}_{g^{0}}\},$
(3)
を満たすような有界集合
$\mathrm{B}\subset \mathrm{Z}_{+}^{N}$が存在する。
条件
4
ロストセールの仮定の下ての
$x_{n}=0$
を除
である。ここで
$\mathrm{z}_{\mathrm{g}^{0}}$
は仮定
2
の
$M$
を以下て与えら
くすべての
$\mathrm{x}\in \mathrm{X}$と
$n\in \mathrm{N}$に対し
$x_{n}>u_{n}$
(X,D)
がれる
$g^{0}$
によって置き換えたものである。
確率
1
で成立する。
$K(\mathrm{x},\mathrm{y})=K\delta(\mathrm{y}-\mathrm{x})+\mathrm{c}\cdot(\mathrm{y}-\mathrm{x})$
Johnson[16]
ては固定発注費用
$K>0$
に対して
$g^{0}= \min_{\mathrm{y}\epsilon \mathrm{X}}\{L(\mathrm{y})+\sum_{\mathrm{D}\in \mathrm{B}}\phi(\mathrm{y},\mathrm{D})K$
(u(y,
$\mathrm{D}\lambda \mathrm{y}$)}.
$(4)$
と仮定されている。ここで
$\delta(0)=0$
であり,
$\mathrm{x}>0$$\mathrm{i}\mathrm{i})$ $S(\mathrm{x})\in\sigma^{c}$
,
$\mathrm{x}\in\sigma \mathrm{t}$ならば
$\delta(\mathrm{x})=1$’
$\mathrm{c}$は
$N$
次元の価格行ベクトルで
$\mathrm{i}\mathrm{i}\mathrm{i})$
$v(\mathrm{x})=K$
(x,
$S(\mathrm{x})$)
$+o(S(\mathrm{x}))$
,
$\mathrm{x}\in\sigma$.
ある。 明らかにこの発注費用は条件
1
を満たし
,
(5)
もし
$\mathrm{X}$が有限でないならば
$\mathrm{X}^{0}$を
$(\sigma^{0})^{\rho}’\cup\{u(\mathrm{x},\mathrm{D})$
for
all
$\mathrm{x}\in(\sigma^{0})’$’
かつ
$\mathrm{D}\in \mathrm{B}\}$とおき
,
$\mathrm{X}^{0}$の状態数を
$N^{0}$
とする。定理
1
は最適
政策の候補となるようなすべての発注政策の下
て
$\mathrm{X}^{0}$がすべての再帰的状態を含むことを意味し
ている。
逆に
$\mathrm{X}^{0}$の外側のすべての状態は最適政
策の下て常に過渡的状態であり
,
この状態におけ
る発注政策は最小平均期待費用に影響しない。し
たがって
, 有限集合
$\mathrm{X}^{0}$のみに対して最適政策を
探せば十分である。
$\mathrm{x}\not\in \mathrm{X}^{0}$に対する最適政策
$S(\mathrm{x})$は (5) 式より容易に計算できる。次の定理
2
では
$\mathrm{X}$が有限であるとき
,
$\mathrm{X}^{0}$は
$\mathrm{X}$を意味するものとす
る。
定理
2
最小平均期待費用
$g(\mathrm{x})$は
$\mathrm{x}\in \mathrm{X}$に対して
定数である。すなわち
,
$g(\mathrm{x})=g$
であり
,
最適方
程式 (1) と
(2)
は次式に帰着する。
$g+v( \mathrm{x})=\min_{\mathrm{y}\epsilon \mathrm{Y}}\{K$
(x,
$\mathrm{y}$)
$+L( \mathrm{y})+\sum_{\mathrm{D}\mathrm{e}\mathrm{B}}\phi(\mathrm{x},\mathrm{D})u(u(\mathrm{x},\mathrm{D}))$
},
$\mathrm{x}\in \mathrm{X}^{0}$,
(6)
ここで右辺の最小値を与える決定が最適政策で
ある。
4.
修正政策反復法とニューロ
$\mathrm{D}\mathrm{P}$アルゴリズム
最適性方程式 (6) を解くアルゴリズムが
PIM,
MPIM
であり
,
値反復法
(value
iteration
method) ,
線形計画法
(linear
programming)
である [1,2,
12-14]
。
以下,
表記を簡単化するため
$r(\mathrm{x},\mathrm{y})=K(\mathrm{x},\mathrm{y})+L(\mathrm{y})$ $\mathrm{x}’=u(\mathrm{y},\mathrm{D})$とお
$\text{く}$。
[MPIM]
[14]
ステップ
1:
$u_{0}(s_{r})=0$
をみたす初期ベクトノレ
$u^{0}$,
非負整数
$m_{\mathrm{f}}$初期攻策
$f^{0}$
, 正数
$\epsilon$を定め,
$k=0$
と
お
$\langle$。
ステップ
2:(政策改良ルーチン)
各
$\mathrm{x}\in \mathrm{X}^{0}$に対
して
$g^{k+1}( \mathrm{x})=\mathrm{m}\mathrm{i}\mathrm{P}_{S})\{*\in Kr(\mathrm{x},\mathrm{y})+\sum_{\mathrm{D}\mathrm{e}\mathrm{B}}\phi(\mathrm{x},\mathrm{D})o^{k}(\mathrm{x}’)-o^{k}(\mathrm{x})\}$を計算し
,
$f^{k}$
(X)
が
$g^{k+1}$
(x)
を与えれば:
$f^{k+1}(\mathrm{x})=f^{k}$
(x)
とおき
さもなければ
,
$g^{k+1}$
(x) を与える任意の決定を
$f^{k+1}$
(x) とと
る。
ステップ 3:(値近似ルーチン)
$w^{0}(\mathrm{x})=v^{k}(\mathrm{x})+\mathrm{o}^{k+1}$
(x),
$\mathrm{x}\in \mathrm{X}^{0}$とおき ,
$l=0,1,\cdots m-1$
に対して順次
,
$w^{/+1}(\mathrm{x})=r(\mathrm{x},f^{k+1}(\mathrm{x}))$
$+ \sum_{\mathrm{D}\in \mathrm{B}}\phi(\mathrm{x},\mathrm{D})w^{l}(\mathrm{x}’)$
$\mathrm{x}\in \mathrm{X}^{0}$
を計算し
,
$v^{k+1}(\mathrm{x})=w^{m}(\mathrm{x})-w^{m}$
(xr),
$\mathrm{x}\in \mathrm{X}^{0}$とおく。 すべての
$\mathrm{x}$に対して
,
$|v^{k+1}(\mathrm{x})-o^{k}(\mathrm{x})|<\epsilon$
であれば終了。 最適政策は
$f^{k+1}$
(X),
最小平均
費用は
$g^{k+1}$
(xr),
相対費用は
$v^{k+1}$
(X) で与えられる。
さもなければ,
$k=k+1$
として
, ステップ
2^。
MPIM
は比較的状態数の大きな
MDP
に対して
も有効であるが
,
$\mathrm{D}\mathrm{P}$同様
, 品目数の増加ととも
に次元の呪いを引き起こし
, 多品目問題を解くこ
とは困難である。 したがって,
MPIM
において状
態空間
$\mathrm{X}^{0}$の全ての状態にたいして値近似ルーチ
ンを実行することは実際的ではなく,
シミュレー
ションを用いることが考えられる。すなわち
,
実
際によく生起する初期状態
$\mathrm{x}_{0}$から出発し,
シス
テムの状態変化と費用をシミュレートし
, 訪問し
た状態の集合
$\mathrm{X}_{\nu}$にたいしてだけ相対費用
$v(\mathrm{x})$を
推定する。
このニューロ
DP
アルゴリズムを
SBMPIM
(
Simulation-Based Modified
Policy
Iteration
Method)
と呼ぶことにする
[15]
。
[SBMPIM][15]
ステップ
1:
初期状態
$\mathrm{x}_{0}$と望ましい状態
$\mathrm{x}^{\mathrm{s}}$を定
め,
シミュレーション回数
$m$
および
$\lambda(0\leq\lambda\leq 1)$
を定めて,
訪問した状態の集合
$\mathrm{X}_{v}=\mathrm{X}_{T}=\phi$(空
集合),
累積費用
$TC=0,$
$\mathrm{x}=\mathrm{x}_{0},$$k=l=1$
とおく。
ステツプ
2;
$\mathrm{x}\not\in \mathrm{X}_{v}$ならば
,
$\mathrm{X}_{v}=\mathrm{X}_{v}\cup\{\mathrm{x}\}\mathrm{r}$ $\mathrm{X}_{T}=\mathrm{X}_{\mathit{1}}\cdot\cup\{\mathrm{x}\},$ $\mathrm{x}$の訪問回数
$v(\mathrm{x})=1$
とおき,
$f(\mathrm{x})$を状態
$\mathrm{x}^{l}$へ向かう実行可能な決定と定める。
$\mathrm{x}\in \mathrm{X}_{v}$
ならば,
$\mathrm{x}\not\in \mathrm{X}_{T}$のとき,
$\mathrm{X}_{T}=\mathrm{X}_{T}\cup\{\mathrm{x}\}$,
$v(\mathrm{x})=1$
とおき ,
$\mathrm{x}\in \mathrm{X}_{T}$ならば
,
$v(\mathrm{x})=v(\mathrm{x})+1$
と更新する。
.
状態
$\mathrm{x}$で決定
$f$
(X)
をとったときの
状態推移をシミュレーションし,
次期の状態
$\mathrm{x}’$を
定める。
$TC=TC+r(\mathrm{x},f(\mathrm{x}))$
$\mathrm{x}=\mathrm{x}’$と更新し
,
$l=m$
ならばステップ
3^
。
さもなけ
れば
$l=l+1$
としてステップ
2^
。
ステップ 3:(
$g$
の推定
)
平均費用
$g$
を次式により
推定する。
$g=TC/m$
ステップ
4:
(
$v(\mathrm{x})$の推定
)
$\mathrm{X}_{v}$のなかて
$\mathrm{x}_{r}$を定め,
$o(\mathrm{x}_{r})=(1-\lambda v(\mathrm{x}_{r})/m\mathrm{X}w(\mathrm{x}_{r})_{-g})+(\lambda v(_{\mathrm{X}},)/m\mathrm{X}r(\mathrm{x}_{r},f(\mathrm{x}_{r}))_{-g})$
87
$U(\mathrm{x})=(1-\lambda v(\mathrm{x})/m\mathrm{X}w(\mathrm{x})-g)+(\lambda o(\mathrm{x})/m\mathrm{X}^{\gamma}(\mathrm{x},f(\mathrm{x}))-g)-U(\mathrm{x}_{r})$
ステップ
6:
ステップ
3
で決定
$\mathrm{y}^{\mathrm{t}}$を選択したなら
を計算し
,
$o(\mathrm{x}_{r})=0$
とおく。 ただし
,
$k=1$
のと
ば,
$TC$
と
$g$
を更新する。
き
}
こ
は
$o(\mathrm{x},)=r(\mathrm{x}_{r},f(\mathrm{x}_{r}))-g$
$TC=TC+r(\mathrm{x},\mathrm{x}’,\mathrm{y}^{\mathrm{s}})$
$v(\mathrm{x})=r(\mathrm{x},f(\mathrm{x}))-g-v(\mathrm{x}_{r})$
である。
$T=T+1$
ステップ 5:(政策改良ルーチン)
$\mathrm{x}\in \mathrm{x}_{v}$にたい
$g=TC/T$
して
ステップ
7:
$Q_{old}$
$($X,
$\mathrm{y})=Q_{new}$
(X,y)
と更新する。
$w(\mathrm{x})=\mathrm{m}\mathrm{y}\mathrm{e}N(\mathrm{x}.$
.f(
幻
){r(x,
$\mathrm{y}$)
$+ \sum_{\mathrm{D}\in \mathrm{B}}\phi(\mathrm{y},\mathrm{D})U(\mathrm{x}’)\}$ステップ
8:
$k$
が停止回数に達すれば終了。
さも
な
$\{\}$れぱ
$k=k+1$
,
$\mathrm{x}$’ を
$\mathrm{x}$としてステップ
$2\wedge\circ$
を計算し
,
$v(\mathrm{x})=0$
とおく。
ここで
$N$
(X,
$f$
(x))
は
Gosavi[9]
は
SMART
が必すしも収束しないこ
とを示し,
その改良版
RELAXED-SMART
を提案
$f$
(X)
の近傍であり
,
$\emptyset(\mathrm{y},\mathrm{D})>0$となる
$\mathrm{x}\not\in \mathrm{X}_{v}$[こた
している。
SMART
と旺
$\mathrm{L}\mathrm{A}\mathrm{X}\mathrm{E}\mathrm{D}-\mathrm{S}\mathrm{M}\mathrm{A}\mathrm{R}\mathrm{T}$は
いして (ま,
$\mathrm{x}_{v}=\mathrm{X}_{v}\cup\{\mathrm{x}’\},$$v(\mathrm{x}’)=0$
とおき
,
$f$
(x’)SMDP
にたいするアルゴリズムであるが,
ここて
を
$\mathrm{x}^{*}$へ向かう実行可能な決定と定める。
は
$\mathrm{M}\mathrm{D}\mathrm{P}$にたいするものに修正している。
$w(\mathrm{x}’)=r(\mathrm{x}’,f(\mathrm{x}’))$
とおき
,
[
旺
$\mathrm{L}\mathrm{A}\mathrm{X}\mathrm{E}\mathrm{D}-\mathrm{S}\mathrm{M}\mathrm{A}\mathrm{R}\mathrm{T}$]
$[9]$
$o(\mathrm{x}’)=r(\mathrm{x}’,f(\mathrm{x}’))-r(\mathrm{x}_{r},f(\mathrm{x},))$
ステップ
3\sim 5,7,8
は [SMART]
と同じである。
ステツプ
1:
$\mathrm{Q}$-factor
$Q_{new}$
(x,
$\mathrm{y}$)
$=Q_{\mathit{0}/d}($
X,
$\mathrm{y})=0$
,
として,
$w(\mathrm{x})$を計算する。
$f$
(x)
が
$w(\mathrm{x})$を与えな
$TC=0$
,
$T=0$
,
$g$
=0,
$k=0$
とおき
,
パラメー
ければ
,
$w(\mathrm{x})$を与える任意の決定として
$f$
(X)
を
タ
$\alpha_{0}$,
$p_{0}$,
$\beta$0
を与える。
改良する。
$k$
が停止回数に達すれば終了。
さもな
ければ
$\mathrm{X}_{T}=\phi,$
$TC=0,\mathit{1}$
=l,
$k=k+1$
とおきス
ステップ
2:
反復
$k$
で状態
$\mathrm{x}$にいれば
,
$\alpha_{k},$ $p_{k}$,
テップ
2
へ
$\text{。}$A
を
$\alpha_{k}=a_{0}/k$
,
$p_{m}=p_{0}/m$
’
$\beta_{k}=\beta_{0}/k$
5.
SMART
と
SBPI
アルゴリズム
として定める。
MPIM
と
SBMPIM
を最適制御問題に適用する
ステップ
6:
ステップ
3
で決定
$\mathrm{y}^{\mathrm{t}}$を選択したなら
に先立ち
, 既存の
NDP
アルゴリズムを簡単に紹
ば,
$TC,$
$T,$
$g$
を次式で更新する。
介する。
$TC=(1-\beta_{k})TC+\beta_{k’}$
(x,
$\mathrm{x}’,\mathrm{y}.)$[SMART] [81
ステップ
1:
全ての
$\mathrm{x}\in \mathrm{X}$と
$\mathrm{y}\in K$
(x){
こた
$\mathrm{A}\backslash$して
T=0-\beta T+\beta k
$\mathrm{Q}$-factor
$Q_{new}$
(x,
$f$
)
$=Q_{old}$
(x,
$f$
)
$=0-$
.
累積費用
$g=TC/T$
$TC=0$
,
累積時間
$T=0$
, 平均費用
$g=0$
,
反復
一方
,
He et
a1.[10]
は
$\mathrm{P}\mathrm{I}\mathrm{M}$の値決定ルーチンを
回数
$k=0$
とおき
, 学習率
(learning
rate)
と探検
シミュレーションで置きかえた
SBPI
(Simulation
確率
(exploration probability)
をステップ
2
で定
Based Policy
lteration)
7/レゴリズムを提案して
$\mathrm{a}$
める定数
$(\alpha_{0},\alpha_{\tau},p0’ p_{\mathrm{r}})$を与える。
る。
[SBPI アノレゴリズム
]
[101
ステップ 2:反復
$k$
で状態
$\mathrm{x}$にいれば,
学習率
$\alpha_{k}$,
ステップ
1:
初期政策
$\{f_{0}(\mathbb{X});\mathrm{x}\in \mathrm{X}\}$を定め
,
$k=0$
探検確率
$p_{k}$を
とお
$\langle$。
$\alpha_{k}=\alpha_{0}(\alpha_{\tau}+k)/(k^{2}+k+\alpha_{\tau})$
,
ステップ 2:(値決定ルーチン)
$p_{k}=p_{0}(p_{\mathrm{r}}+k)/(k^{2}+k+p_{\tau})$
2-a:(
$\sim$
の推定)
として定める。
i)
初期状態
$\mathrm{x}_{0}$からシミュレーションにより
ステップ
3:
高い確率
$(1-p_{k})$
で
$Q_{new}$
(x,y)
を最小
$\mathrm{x}_{1},\cdots,\mathrm{x}_{m}$を生成する。
にする決定
$\mathrm{y}^{*}$を選択し
, 確率
$p_{k}$
で
$\mathrm{y}$.
を除く
$\mathrm{i}\mathrm{i}$)
$g^{k}=0$
とおき
,
$n=0,\cdots,m$
-l
にたレルて
$K$
(x)
からランダムに
$\mathrm{y}$を選択する。
$(\mathrm{x}_{n},\mathrm{x}_{n+1})$の推移に伴う
$g^{k}$
を次式て更新す
ステップ
4:
選択された決定
$\mathrm{y}$でシミュレーショ
る。
ンを行い,
状態
$\mathrm{x}’$へ推移すれば
,
直接費用
$g^{k}=(1-1/(n+1))g^{k}+(1/(n+1))r(\mathrm{x}_{n},\mathrm{x}_{n+1},f^{k}(\mathrm{x}_{n}))$
$r(\mathrm{x},\mathrm{x}’,\mathrm{y})$がかかる。
ステップ
5:
$Q_{new}$
(x,y)
を次式により更新する。
2-b:(
$v^{k}($
x)
の推定
)
$Q_{new}(\mathrm{x},\mathrm{y})=(1-\alpha_{k})Q_{\mathit{0}/d}(\mathrm{x},\mathrm{y})$i) ステップ
2-a
で行ったシミュレーション
において訪問回数が最も多い状態を
$\mathrm{x}^{*}$と
$+\alpha_{k}\{$
r(x,
$\mathrm{x}’,\mathrm{y}$)
$-g+ \min_{\mathrm{y}’\in K(\mathrm{x}’)}Q_{old}$(X’,
$\mathrm{y}’$)
$\}$おく。
$\mathrm{i}\mathrm{i})$
過渡状態
$\mathrm{x}_{0}$から出発し,
状態
$\mathrm{x}$.
へ至るト
ラジェクトリーをシミュレーションにより
$L$
本生成する。
$\mathrm{i}\mathrm{i}\mathrm{i})$1
本目のトラジエクトリ
$(\mathrm{x}_{0},\mathrm{x}_{1},\cdots,\mathrm{x}_{N}=\mathrm{x}.),$
$l=1,\cdots,L$
,
にた
$\vee$)
して
,
推移
$(\mathrm{x}_{n},\mathrm{x}_{n+1})$に伴う
$w(\mathrm{x}_{l}),$ $i$=l,
$\cdot$..,
$n$
,
を
次式により更新する。
$w(\mathrm{x}_{i})=w(\mathrm{x}_{j})+\gamma_{j}\lambda^{n-i}d_{n}$
$-$
こで
,
$\gamma_{i}$はそのトラジェクトリ中て
$s_{j}$を訪問
した回数の逆数であり
$0\leq\lambda\leq 1$
$d_{\hslash}=r(\mathrm{x}_{n},\mathrm{x}_{n’ 1},f^{k}(\mathrm{x}_{n}))-g^{k}+w(\mathrm{x}_{n+1})-w(\mathrm{x}_{n})$
であ
る。
$\mathrm{i}\mathrm{v})v^{k}(\mathrm{x})=14^{\mathrm{X}})-w(\mathrm{x}_{r}),$ $\mathrm{x}$
\in X
ステップ
3:(
政策改良ルーチン
)
$f^{k+1}( \mathrm{x})=\arg \mathrm{m}\mathrm{i}\mathrm{P}_{\mathrm{x})}\{\mathrm{y}\in\kappa r(\mathrm{x},\mathrm{y})+\sum_{\mathrm{B}\mathrm{D}\epsilon}\phi(\mathrm{y},\mathrm{D}\}_{2}^{k}(\mathrm{x}’)\}$
:
$\mathrm{x}\in \mathrm{X}$
ステツプ
4:
$f^{k+1}(\mathrm{x})=f^{k}$
(x),
$\mathrm{x}\in \mathrm{X}$ならば停止。
最適政策は
$f^{k}$
(x)
である。
さもなければ
$k=k$ 利
としてステップ
2^
。
算時間を表
2
に示す。
表
3
は
MPIM
による最適政策である。
また
,
訪問回数の多い状態における
MPIM
および各ア
ルゴリズムの政策との比較を表 4
に示す。 表中
「一致」
の列には
MPIM
と政策が等しい場合に
$\mathrm{O}$,
そうでない場合に
$\cross$を記入している。 また
,
「政策一致数」 の行は全
300
状態中で
MPIM
と
政策が一致した状態数を示している。
表
1
アルゴリズムに使用するパラメーター覧
アルゴリズム
パラメータ
$\mathrm{m}=10000,$
$\lambda$=0.l,
SBMPIM
$\mathrm{x}_{0}=(11,12),\mathrm{x}^{*}=(8,9)$
,
停止回数
=50
-$\mathrm{m}=1000000,$
$\alpha_{0^{=}}0.9,$
$\mathrm{p}_{0}\triangleleft-.3$,
SMART
$\alpha=10000,$
$\mathrm{p}_{\tau}=10000-^{\zeta}--$
RELAXED-SMART
$\mathrm{m}$=l000000,
$\alpha 0^{=}0.\underline{9_{-},}\mathrm{P}\mathrm{o}=0.3$SBPI
$\mathrm{m}=10000,$
$\mathrm{L}$=l,
$\lambda=0.9$
表
2
各アルゴリズムの
$\mathrm{g}$およひ計算時間
計算時間
アルゴリズム
$\mathrm{g}$(秒)
MPIM
40.907
0.35
6
$\iota$数値実験
各アノレゴリズムは
VB
(Visual Basic) によりプ
ログラムし,
$\mathrm{D}\mathrm{O}\mathrm{S}/\mathrm{V}$機 (CPU
:Pentium4
$2.4\mathrm{G}\mathrm{H}\mathrm{z}$,
メモリ
:
$2\mathrm{G}\mathrm{B}$)
を用いて計算を行った。
6. 1
数値例
.
各品目の容積はすべて
1
品目数
;2
.
在庫容量 ;23
一期あたりの
$i$番目の需要
$D_{i}$(i=L2) の確率
$\phi_{j}(D_{i})$
;
$\mathrm{A}(0)=1/27$
,
A
$(1)=2/9$
,
$\phi(2)=4/9$
’
$\mathrm{A}(3)=8/27$
$\phi_{2}(0)=1/16$
’
$\emptyset$2
$(1)=1/4$
’
$\emptyset$2 $(2)=3/8$
’
$\phi_{2}(3)=1/4$
,
$\phi_{2}(4)=1/16$
’
発注費用
;
$K(\ \mathrm{y})=15\delta(\mathrm{y}-\mathrm{x})+10\delta(y_{1}-x_{1})+5\delta(y_{2}-x_{2})$
$+6(y_{1}-x_{1})+3(y_{2}-x_{2})$
$|\urcorner$保管
品切れ費用 ;
$l(\mathrm{y},\mathrm{D})=2[y_{1}-D_{1}]^{+}+2[y_{2} " D_{2}]^{+}+21[D_{1}-y_{1}]^{+}$
SBMPIM
$40.910\pm 0.043$
1.11
SMART
62.626
3.98
– $\mathrm{R}\mathrm{E}\mathrm{L}\mathrm{A}\underline{\mathrm{X}}\underline{\mathrm{E}}\mathrm{D}-$-SMART65.500
4.01
SBPI
43.217
$\underline{1.92}$
3
品目在庫管理問題に対して
MP
犬
SBMPIM
により計算を行った結果を表
5
に示す。
ここで
,
2
品目の場合と異なる
SBMPIM
のパラメータは
$\mathrm{x}_{0}=(7,8,8)$
, x*=(5,6,6)
である。 また,
需要およひ
コストのパラメータは品目
1,
2
に関しては
2
品
目の場合と同じであり
, 品目
3
に関しては
, 需要
パラメータは品目
1
と同じ,
コストパラメータは
品目
2
と同じてある。
多品目での
SBMPIM
の優
位性が示されている。
表
5
3
品目問題の
$\mathrm{g}$およひ計算時間
計算時
$\mathrm{F}\mathrm{a}\mathrm{i}$.
$\text{ア}J\triangleright \mathrm{z}\mathrm{f}^{\backslash }|)\text{ス^{}*}\text{ム}$$\mathrm{g}$
(秒)
$–$
–MPIM
$54.\overline{890}-$
45.37
SBMPIM
$54.904\pm 0.041$
113.27
$+14[D_{2}-y_{2}]^{+}$
6.
2
SBMPIM
と従来のアルゴリズムとの比
較
SBMPIM
およひ既存のアルゴリズムのパラメ
ータを表
1
に示す。表
1
のパラメータのもとで各
アルゴリズムにより計算したときの
$\mathrm{g}$およひ計
謝辞
本研究の一部は
, 日本学術振興会平成
14–1 5
年度科学研究費補助金
(
基盤研究
(B) (1), 課
題番号 14380185)
およひ
(基盤研究 (C)
(2), 課題番号 14580477)
の助成を受
けてなされたものてある。
88
参考文献
[11
R. A.
$\mathrm{H}\mathrm{o}\mathrm{w}\pi \mathrm{d}$:Dynamic
Programming
and
Markov
Processes,
MIT PTess
(1960) (
関根
, 羽島,
森共訳「ダイナミックプログラミングとマルコフ
過程」
, 培風館
,
1971)
[2]
M. L. Puteman: Markov Decision
Processes,
John Wiley& Sons
(1994)
[3]
K.
Ohno,
T. lshigaki and
T.
Yoshii:
“
$A$
New
Algorithm
for
$a$
Multi-item
Periodic Review Invenlory
System”,
ZOR-Math. Methods
of
Oper.
${\rm Res}$.
Vol. 39,
$\mathrm{p}\mathrm{p}$
.
$349- 364,1994$
.
$[4]\mathrm{S}$
.
Russell and
P.
Norvig,
古川康一訳「I–
ジェント アプローチ人工知能」,
共立出版
,
1997.
[5]
R. S.
Su
廿
on
and A.
$\mathrm{G}$BaIto:
Reinforcement
Learning,
MIT Press
(1998)
(三上,
皆川共訳「強
化学習」
, 森北出版,
2000)
[6]
D.
P.
Bertsekas
and
J.
N.
Tsitsiklis:
NeurO-Dynamic Programming,
Athena
Scientific
(1996)
[7]
R. V. Roy: “NeurO-dynamic
programming:
overview
and recent
廿
ends,”
pp.431-459,
in
E.
A.
Feinberg and A. Schwartz ed. Handbook of
Markov
Decision
Processes,
Kluwer Academic
Publishers
(2002)
[81
T. K.
Das,
A.
Gosavi,
S.
Mahadevan
and
Nich.
Marchalleck:
“Solving
semi-Markov decision
problem
using
average
reward
reinforcement
leaming”, Management
Science,
Vol.
45, N0.4,
pp560-574
(1999)
[91
A.
Gosavi:
Doctor
Thesis,
h
廿
p
$://\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{y}$.uscolo.
$\mathrm{e}\mathrm{d}\mathrm{u}/\mathrm{g}\mathrm{o}\mathrm{s}\mathrm{a}\mathrm{v}\mathrm{i}/\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{s}$.hbnl
(1999)
[101
Y.
He,
M. C. Fu and S. I. Marcus: “A
Simulation- based policy
iteration
algorithm for
average
cost
unichain Markov decision
processes”,
M. Laguna
and
J. L.
G.
Velarde
$\mathrm{e}\mathrm{d}$,
Computing
Iools
for
Modeling Optimization and
Simulation,
Kluwer
Academic,
pp.161-182(2000)
[111
A.
Gosavi, N.
Bandla and
T. K.
Das:
“A
reinforcement leaming approach to
a
single leg
airline
revenue
management
problem
with multiple
fare classes and
overbooking,”
$IIE$
Transactions,
Vol. 34,
pp.729-742
(2002)
[12]
大野勝久
:“
マルコフ決定過程”-.
システム
と制御,
Vol.
29,
No.
6,
PP.333-341
(1985)
[131
K.
Ohno
and
K. Ichiki:
“Computing
optimal
policies
for controlled tandem queueing
systems”,
Operations
Research,
$\mathrm{V}\mathrm{o}\mathrm{l}$.
35, No. 1,
$\mathrm{p}\mathrm{p}.121- 126$
(1987)
[141
K.
Ohno:
“Modified
policy
iteration
algoriffim
with nonoptimality tests for
undiscounted
Markov
decision
process”,
Working Paper, Dept.
of
Infomation
System
and
Management
Science,
Konan University, Japan
(1985)
[15] 大野勝久, 八鴫憲司
, 伊藤崇博
:“
ニューロ
-ダイナミックプログラミングによる生産ライ
ンの最適制御に関する研究”-.
日本経営工学会
論文誌
,
VO1.
54,
No.
5,
pp. 316-325
(2003)
[16]
E.
L.
Johnson:
“Optimality and
Computation
of
(
$\sigma,S$
)
Policies in
the
Multi-item Infinite
Horizon
Inventory
Problem”,
$\mathit{4}anagement$
Science,
げ
1.
13,
$\mathrm{p}\mathrm{p}$
.
$475- 491(1967)$
[17] 大野勝久
,
田村隆善
, 森健一, 中島健一
:
「生
産管理システム」,
朝倉書店
(2002)
[18] 石塚陽
, 山下英明
:
「サンプルパス最適化の
確率的離散事象システムへの適用」
,
オペレー
ションズ
. リサーチ,
Vol.
46,
No.
4,
pp. 195-201
(2001)
品目
2
23
22
21
35
-35
20
34
–-34
19
32
–
–
-32
18
30
–
– –-3
屋
17
28
28
–
–
–
-28
16
26 26
––
–
–-26
15
24 24
–
– – – –-24
14
22
22
–
–
–
–
–
-22
-13
20 20
–
––
–
–
-20
–
-1218 18
–
––
–
–
-18
–
–-11
16 16
–
–
–
––
-16
– – –-101414
–
–
–
––
-14
– – – –-912 12
––
– – –-12
– ––
– –-810 10
–
–
– –-10
– – – ––
– –-788
–
–
– – –8
91113151719212325
61
1
–
—-
–
1 7
–
–
–
–
–
–
–
–
-27
56
6
—-356
––
– ––
–
–
–
–
–
-29
44
–
–2
–
4
– ––
– ––
–
–
–
–
–
–
-31
31
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
-33
21
–
––
– – – – – – – – – – – – – – – ––
-1
$\mathrm{t}$ $|$ ––
–5
1
7
9
– – – – – – – – – – – – – –01112 3 5
1
7911
13151719
$2\mathrm{t}232527293133-$
$–$
0
1
2
3
4
5
6
7
8
910 11 12 13 14 15
16
17
18 19 20
212223
品日
1
表
2
は最適政策を示す。
表中の数字と,
同表中のゴシック体の数字が対応している。
例えば
, 状態
$[7, 1]$
の数字
“
7
”
は
“7”
に対応し,
つまり状態
[7,
61
まで発注するということを示す。
また,
“–,,
は発注しないことを示す。
71
表
4
各アルゴリズムの政策の比較
SBPI
発注
0
発注
発注
0
発注
6
$\overline{6}$ $\mathit{0}$5
6
00
$\mathrm{O}$0
0
MPIM
SBMF
$|0$
$\partial \mathrm{E}\mathrm{f}\mathrm{f}61$ $\partial \mathrm{g}f\grave{\mathrm{f}}06$ $\mathit{5}_{\frac{\mathrm{g}\grave{\dot{f}}_{-}^{-}}{6}}$
