【論文紹介】 Using imperfect advance demand information in lost-sales inventory systems with the option of returning inventory

初めに

　弊社の分析チームではライトニングトークを社内勉強会の１つとして取り入れており、本稿で解説する論文はその時に私が紹介したものです。勉強会では証明の話はせず、論文の概要をお話しました。そこで今回は論文で提案されたモデルの最適解が唯一つであることの証明を簡単に解説します。
　論文の証明では、まず最適解の候補を２つに絞り、モデルの性質に基づいて１つであることを導いています。着目している性質は$L^\natural$凸性と呼ばれる、極小値と最小値が一致する性質で、劣モジュラ性と関連します。提案されたモデルは$L^\natural$凸性を持つかは明らかでなく、変数を変換したモデルが持っております。本論文では変数変換したモデルの持つ劣モジュラ性により解の更なる絞り込みを行い、変数変換前の提案されたモデルに議論を移すことで証明しています。
　以上の内容の解説にあたり、本稿の構成は以下としています。まず提案されたモデルの概要として問題設定やモデル説明をします。次に、本記事で着目している性質（$L^\natural$凸性、劣モジュラ性）の定義を述べ、証明に必要なLemma 1やTheorem 1を簡単に説明します。そして最後に、最適解が唯一つであることの証明を見ていきたい思います。

提案されたモデルの概要

モデルの問題設定

　問題設定は、著者らが実務で取り組んだ修理部品の在庫管理に由来しています。修理部品は装置の故障が起きなければ使われることはないため在庫は捌きにくいです。そのため長期間保管することになり、保管にかかる費用がかさんでしまいます。しかし、費用を抑えるために在庫量を減らすと、在庫切れを起こす可能性が高まります。万一在庫切れが生じた場合、修理部品を手配できるまでの期間、装置が止まってしまいます。それにより多大な損失が発生することから、在庫切れは避けなければなりません。そこで著者らは必要最小限の在庫量を保管できるよう、装置にセンサを取り付けて解析し、故障予測を行っています。故障予測では、修理部品の必要数と必要になる日にちを予測していますが、予測を外してしまう時もあります。日にちの予測を外すとは、故障する日にちを早め/遅めに予測してしまうことを指しており、保管費用などに影響を及ぼします。また必要数について、少なく予測した場合は在庫切れの可能性が高まり、多く予測した場合は保管費用の増大につながります。特に後者の場合、筆者らは過剰に抱えた在庫を追加料金を支払って発注元に返品し、在庫費用を抑える工夫をしています。本問題は、このような状況における修理部品の管理費用を最小にする発注計画を考えることです。但し、発注には一定のリードタイムはありますが、返品は即日対応であり、修理部品は装置の近くに建設した倉庫に保管しているため修理部品を届ける時間はかかりません。
　よって以上をまとめると、本問題は需要予測を用いた在庫管理問題となります。具体的には、需要量や需要のタイミングといった需要予測の情報を援用し、発注量や返却量のタイミングと量を調整して管理費用を最小化する問題に取り組むものです。管理費用とは発注費用、返却費用、在庫の保管費用、そして在庫切れに伴う損失を含みます。また、問題を単純化するために修理物品と倉庫は１種類と仮定しています。　　

モデルの意義

　モデルは、前節で述べた設定の問題を解くとともに、不確かであっても需要予測の情報を用いた方が在庫管理にかかる費用が抑えられることを確認するために用いられています。
　論文によると、従来のモデルは需要情報が完全に正しいとしていることが多く、需要のタイミングや予測誤差が考慮されることはあまりなかったそうです。また、在庫を大量に抱えてしまった場合、従来は在庫を捌けるのを待つのみで、発注元への返却は考慮されていませんでした。需要のタイミングや予測誤差、発注元への返却を考慮している点が本モデルの新規性となります。
　このような在庫最適化はある時刻の発注・返却が次以降の発注・返却に影響を及ぼすため、実行可能解の数が爆発的に増え、解析が難しくなります。最適解を唯一つ持つモデルであること（や本稿でほとんど言及しませんが、効率の良いアルゴリズムを構築できるモデルであること）は解析を簡単にし、運用や費用低減の評価を容易にします。

提案されたモデル

提案されているモデルは以下のようになります（モデルの表記は原文ママ）。

$$ \begin{align} &\begin{split} f_t(\mathbf{a}, \mathbf{z}) = \min_{(z_L, y) \in \mathcal{A}_x} {J_t({\mathbf{a}, \mathbf{z}, z_L, y}) }, \end{split} \\ &\begin{split} J_t({\mathbf{a}, \mathbf{z}, z_L, y}) &= cz_L + c_ry + L(a_{\tau_u}, \dots, a_{\tau_l}, x+z_0-y) \\ &+ E[ f_{t+1}(\mathbf{\bar{a} - \mathbf{\bar{R}}, \it{W}}, (x + z_0 - y - \sum_{\tau = \tau_l}^{\tau_u}R_{\tau} - D^{u} )^{+}, z_1, \ldots, z_L)], \end{split} \\
&\begin{split} \mathrm{where} \end{split} \\ &\begin{split} L(a_{\tau_u}, \dots, a_{\tau_l}, x+z_0-y) &= hE[(x + z_0-y-\sum_{\tau = \tau_l}^{\tau_u}R_{\tau} - D^{u} )^{+}] \\ &+ c_eE[(\sum_{\tau = \tau_l}^{\tau_u}R_{\tau} + D^{u}-x - z_0+y)^{+}]. \end{split} \\ \end{align} $$

　$f_t$は時刻$t$から終端時刻までにかかる管理費用の最小値で、この値をとるような発注量と返却量の組み合わせである$(z_L, y) \in \mathbb{Z}_{+} \times \mathbb{Z}_{+}$を求めたいということになります。$z$の添字に使われている$L$はリードタイムを表しており、$z_L$は発注したものが時刻$t+L$に納品されることを示しています。発注や返却は時刻$t$のみで行うわけではないため、実際に求めたい値は各時刻における発注量と返却量になります。時刻$t$以降の管理費用は、需要量と時刻$t$以前に発注していた物品の納品量に依存するため、それらを表す$\mathbf{a}, \mathbf{z}$の関数になります。$\mathbf{a}={a_{\tau_u}, \dots, a_{\tau_0}}$であり、時刻$t+\tau$における需要量を$a_{\tau}$としています。$\tau$は需要のリードタイムようなものであり、今回の問題設定において$\tau \in [\tau_l, \tau_u]$を満たす$\tau$について、$t+\tau$に需要は発生するとしています。それ以外のタイミングに需要は発生するかもしれませんが、その場合は予測に失敗したことを意味します。また$\mathbf{z}={x, z_{0}, \dots, z_{L-1}}$であり、$x$は時刻$t$における手持ち在庫量としています。
　次にモデルの構成要素である$J_t$に着目します。$J_t$はその定義から、時刻$t$にかかる管理費用（最初3項）と、時刻$t+1$から終端時刻までの管理費用$\bar{f}_{t+1}$（最終項）に分けることができます。最初3項は順番に、発注にかかる費用（$c$は発注単価）、返却にかかる費用（$c_r$は返却単価）、そして在庫に関する費用になります。在庫に関する費用は$L$としてまとめられており、倉庫の保管費用（$h$は保管単価）と在庫切れに関する損失（$c_e$は損失単価）から成っています。
　本稿では上記モデルの最適解が唯一つであることを見ていきます。

変数変換後の提案されたモデル

　$v_l = x + \sum_{t=0}^l z_t$、$l = -1, \dots, L$とし、新たに変数$\mathbf{v} = (v_{-1}, v_0, \dots, v_l)$を導入します（変数の表記は原文ママ）。但し、$v_{-1} = x$となります。新しく導入した変数により例えば$z_L = v_L -v_{L-1}$のように記述できるため、 $\mathbf{z}$を$\mathbf{v}$で記述できるようになります。これにより$f_t(\mathbf{a}, \mathbf{z})$から$\bar{f_t}(\mathbf{a}, \mathbf{v})$が、$J_t({\mathbf{a}, \mathbf{z}, z_L, y})$から$\bar{J_t}({\mathbf{a}, \mathbf{v}, v_L, y})$が得られます。

着目している性質

劣モジュラ性

　実効定義域が空でない関数$g:\mathbb{Z}^n \rightarrow \mathbb{Z} \cup {\infty}$ が以下を満たす時、$g$は劣モジュラであるといいます。
$$ \begin{align} g(p)+g(q)\ge g(p \vee q)+g(p \land q), \quad p, q \in \mathbb{Z}^n. \end{align}
$$ 但し、$\vee, \land$はベクトルの要素ごとに最大値、最小値を出力する演算です。

$L^\natural$凸性

　上で定義した関数$g$が以下に示す並進劣モジュラ性を満たす時、関数$g$は$L^\natural$凸であるといいます。 $$ \begin{align} g(p)+g(q)\ge g((p-\alpha \mathbb{1}) \vee q)+g(p \land q+\alpha \mathbb{1}), \quad p, q \in \mathbb{Z}^n, \alpha \in \mathbb{Z}_+. \end{align} $$ 但し、$\mathbb{1}$は全ての要素が$1$のベクトルです。
　この性質は離散中点凸性と同値であり、また$g$が整凸性と劣モジュラ性の両方を持つことにも等しくなります。本論文では$L^\natural$凸の持つ劣モジュラ性を用いて、Lemma 1を含め種々のLemmaの証明がなされています。

証明に必要なLemma 1, Theorem 1

Lemma 1

For each $(\mathbf{a}, \mathbf{z}) \in \mathcal{U} \times \mathcal{Z}$ and $t = 1, \dots, T$, the optimal decisions are characterized by $z_L^{*}(a, z) \times y^{*}(a, z) = 0$.

このLemmaは最適解の満たす性質を言及したもので、管理費用を最小にする発注量と返却量の積は0になると述べています。この主張をもう少し説明すると、発注量と返却量の両方が正であるときは、返却している分だけ余分に発注していることになり、その分を減らせると言っています。

Theorem 1

a) $\bar{J_t}({\mathbf{a}, \mathbf{v}, v_L, y})$ is $L^\natural-convex$ in $(\mathbf{v}, v_L, y) \in Q$ for each $\mathbf{a} \in \mathcal{U}$ and $t = 1,\dots,T$.
b) $\bar{f_t}(\mathbf{a}, \mathbf{v})$ is $L^\natural-convex$ in $\mathbf{v} \in \mathcal{V}$ for each $\mathbf{a} \in \mathcal{U}$ and $t = 1,\dots,T$.

　本稿で言及する主張のみ掲載しています。この主張は、提案されたモデルについては不明ですが、変数変換後のモデルは$L^\natural$凸性、つまり劣モジュラ性を持つと言っています。変数変換後のモデルを議論の対象にすると、任意の実行可能解の組に対して、劣モジュラ性が満たす不等式を適用できるため、最適解についての議論ができそうだと分かります。
　Theorem 1の証明は$\bar{f}_{t}(\mathbf{a}, \mathbf{v})$の持つ再帰構造に着目した帰納法に基づいています。具体的には、$\bar{f}_{t+1}(\mathbf{a}, \mathbf{v})$が$L^\natural$凸性を持つと仮定し、$\bar{f}_{t}(\mathbf{a}, \mathbf{v})$の内部で再起的に記述される$\bar{f}_{t+1}$が$L^\natural$凸性を持つことと、それに対する期待値や最小化の操作が$L^\natural$凸性を保存することより$\bar{f}_{t}(\mathbf{a}, \mathbf{v})$も$L^\natural$凸性を持つことを導いています。
　変数変換は、再帰的に記述されるモデル$\bar{f}_{t+1}$が$L^\natural$凸性を持つことを保証するために行なった操作になります。本稿では言及しませんが、前に定義した関数$g(p)$が$L^\natural$凸性を持つならば、$p-\alpha \mathbb{1} \ge \mathbf{0}$となる$\alpha$に対して$g(p-\alpha \mathbb{1})$は$L^\natural$凸性を持ちます（Lemma 2）。変数変換をしなければ、再起的に記述される$f_{t+1}$はイメージ$\mathbf{z}-y\mathbf{e}_1$についての関数となることから$L^\natural$凸性を持つとは限りませんが、$\bar{f}_{t+1}$はイメージ$\mathbf{v}-y\mathbb{1}$についての関数となることから保証されます。

最適解が唯一つであることの証明

　Lemma 1より、$J_t$の最適解は「発注量=0」である$(0, y^{*})$または「返却量=0」である$(z_L^{*}(\mathbf{a}, \mathbf{z}), 0)$の２通りになります。両方が同時に満たされる場合は明らかに解が唯一つとなるため、そうならない場合を考えます。最適解が唯一つであることを証明するためには、両方が同時に最適解になり得ないことを証明すればよく、背理法を用います。
　同時に最適解になり得ないことを導くために、Theorem 1より得られる変数変換後のモデル$\bar{J_t}$の劣モジュラ性に着目します。劣モジュラ性の式は、実行可能解の組とその組の最小・最大から得られる変数の合計4つを取り扱うことになります。ここで実行可能解の組を上手く選び、「発注量＝0」の最適解$(v_{L-1}, y^{*})$と「返却量=0」の最適解$(v_{L-1} + z_L^{*}(\mathbf{a}, \mathbf{z}), 0)$の２つが得られるようにします。そのような実行可能解を劣モジュラ性が満たす式に代入し、以下の式を作ります。
$$ \begin{align} &\begin{split} \bar{J_t}({\mathbf{a}, \mathbf{v}, v_{L-1}, y^{*}}) - \bar{J_t}({\mathbf{a}, \mathbf{v}, v_{L-1}, 0}) \ge \\ \bar{J_t}({\mathbf{a}, \mathbf{v}, v_{L-1} + z_L^{*}(\mathbf{a}, \mathbf{z}), y^{*}}) - \bar{J_t}({\mathbf{a}, \mathbf{v}, v_{L-1} + z_L^{*}(\mathbf{a}, \mathbf{z}), 0}) \end{split}
\end{align} $$ 　ここで代入している変数が最適解であることから、左辺は非正であり、右辺は非負となることから不等式は成立しなくなります。「発注量=0」と「返却量=0」のときは両辺が一致しますが、本節の冒頭で述べたようにその場合を除外しています。よってTheorem 1に反することから、$\bar{J_t}$の最適解は唯一つになります。
　$\bar{J_t}$と$J_t$の実行可能解は１対１に対応していることから、$J_t$の最適解も唯一つであることが示されます。

所感

　本稿では、不確かな需要情報をもとに在庫管理を行う提案モデルの最適解が一意に定まることの証明を簡単に解説しました。この証明では、変数変換後のモデルが持つ劣モジュラ性と背理法を用いており、比較的シンプルなものになっています。
　提案されたモデルの式は、ある時刻の在庫に関する費用の算出にあたって未来の需要を考慮しています。個人的には、これにより在庫の保管費用を過小評価していると思われるため、改良の余地はあるように見えます。また、本モデルの有用性は発注費用や需要の頻度など問題の細かな設定に応じて変わるため、リグレットを使ってモデルを定式化すると面白いと感じています。解の導出は難しくなりますが、バウンドを求められれば、数値実験と合わせることで有用性の見通しが立ちやすくなるように思います。