第4回：在庫問題と配送問題をドッキング！大規模最適化時代で何が変わる！？【ブレインパッドの数理最適化ブログ】

本記事は、当社オウンドメディア「Doors」に移転しました。

約5秒後に自動的にリダイレクトします。

ブレインパッドの社員が「数理最適化技術」に関して連載するこの企画。
第4回は、当社のデータサイエンティストがこれまでに取り組んだ業務経験と絡め、サプライチェーンビジネスを例に数理最適化がどのように役立てられるのかを紹介しています。

はじめまして、ブレインパッドアナリティクス本部に所属するリードデータサイエンティストの魚井と申します。本記事は、【連載】ブレインパッドの数理最適化ブログ（目次） - Platinum Data Blog by BrainPadの第4弾として、数理最適化の技術面に関心のある方だけでなく、数理最適化をビジネスにどう活かすのか等ビジネスサイドの方も対象としております。ぜひ、様々な職種の方々にお読みいただき、感想をいただけると嬉しいです。

リードデータサイエンティストの仕事
サプライチェーンビジネスにおける問の切り出し
在庫-配送計画の複合問題を解く意義
在庫計画、配送計画の単一ソリューション
- 在庫計画最適化
- 配送計画の最適化
在庫計画と配送計画の複合問題の定式化
- 結果と考察
まとめ
最後に

リードデータサイエンティストの仕事

最適化問題の技術的な話をする前に、リードデータサイエンティストの仕事の話を簡単に紹介させてください。

私はブレインパッドで、様々なクライアント企業の課題を数理モデルに落とし込み、解決するという仕事をしてきました。その中には、うまく解決できたと感じるものもありますが、課題が残るものも多くあります。課題と言った場合、精度の良いモデルを作れなかったという意味だとよく誤解されます。そのケースもありますが、「課題の切り出し方が良くなかった」というケースもとても多くあります。

データサイエンティストの働き方のイメージとして、難しい問を与えられ、それを解くためのモデル開発に尽力していると世間一般では捉えられがちですが、私のようなリードポジションになってくると少し違います。

現実では、企業の課題が複数あり、どれも抽象度が高いため、「どの課題を、どの順序で、どの粒度で、数理モデルに落とし込み、どう解くか」といった問を企画する仕事が求められます。この問の切り出しは、とてもセンスの問われる仕事で、技術的な知識が多くあれば良いと言った話ではないと感じています。

例えば、特定の部署の課題を解決しても、その結果を実行するのは別の部署といった組織レベルの問題もあれば、全ての課題のデータが揃っていないといったデータの問題、そして問が数理問題として定式化可能なのか、という高度な技術レベルの問題もあります。データサイエンティストはこれらの問題を意識した上で、現実世界から問を切り出さないといけません。これは非常に高度ですが、この要素がデータサイエンティストが今世の中で必要とされている理由であり、今後いくら技術が発達したとしても、データサイエンティストという職種は決してなくなることはないと感じます。

少し話は逸れますが、ブレインパッドには毎年多くの新卒・中途社員が入社しており、若手の割合が増えています。私は、データサイエンティストの成長過程は以下の２段階あると考えています。

１. 「問を解ける」サイエンティストになること
２. 「問を企画できる」サイエンティストになること

クライアント企業と話をしていて感じるのは、「解くべき問がこれで良いのかわからない」「発注する側としてどこまで課題を明確にしてから、発注したら良いかわからない」という悩みを抱えていらっしゃるということです。

一方、データサイエンティストは、できるだけ問を具体化して、極論、大学入試問題のような形式（大問１. （1）といった形式）で、問を用意してほしい、と心の奥底では考えているように思います。私自身も、入試問題のように具体的で答えがある程度見えるような仕事であれば、取り組みやすいだろうなと思うときもあります。しかし、そのようなケースはとても稀です、ほぼ出会ったことはありません。

そのため、上級データサイエンティストはこのギャップを埋めるために能力を身に着ける必要があります。複雑な現実世界から、適切に問を切り出すというのは、「言うは易し」で実際はとても難しいです。勘違いしないでいただきたいのは、切り出しだけが重要であり、それだけを身に着けていれば良いというのは違います。それでは、発言に責任のない人と見なされます。自分で解くことはしないにしても、解ける問と難しい問の境目を知っていることはとても重要です。予測精度を高く出る技術、数理最適化で良い解を出力できるようになる技術、この点は自分で解く人も解かない人も追求する必要があり、その次のステップとして現実世界から上手く問を切り出す技術を身に着ける必要があると考えます。

上記と関連して、面白い問を解きたい、面白い仕事をしたいのであれば、問を待つのではなく、問を提案できるようになることです。そのための手段は年々増えています。当社の過去のプロジェクトもそうですが、OR学会誌なども、他企業様のデータ活用の実例など、とても参考になります。私自身も、1と2共に完璧にできているわけでは決してなく、両者とも修行中ですが、どちらか一方に片寄った人間にならないことを日々意識しています。

サプライチェーンビジネスにおける問の切り出し

さて、上記ではデータサイエンティストは、「問の企画・切り出し」の要素も重要だという話をしました。それは、これから紹介する最適化問題とも密接に絡んできます。

昨今、数理最適化ソルバーが急速に発達していることで、今まで分けて解いていた2つの問が1つの問として解けるようになってきました。これにより、上で述べた問の切り出しがさらに自由度が広がり、ビジネスが多様化していくと感じます。例としてサプライチェーンビジネスの例を紹介させてください。

サプライチェーンは、チェーンと呼ばれるだけあり、工場での生産、倉庫での在庫の1次保管、2次保管、小売店への配送など、すべてつながっており、独立の問にはなっておらず、必然的に複合問題に発展します。例えば、工場での生産量を決めるためには、生産費用だけでなく、倉庫の保管費用まで意識して生産量を決めた方がよりビジネス効果はありますし、配送においても、配送コストだけでなく、配送先の在庫費用まで意識した配送を行えると、より意義深い意思決定ができます。このような各ステークホルダーは互いに複雑に絡み合っているため、ステークホルダー個別の最適化だけでは、サプライチェーン全体を最適化することはできません。

このような複合問題による課題意識は以前からあったのですが、ある個別の問に特化した研究やツールが多いように感じます。その理由として、ツールが複雑になってしまうという問題、結果に対する人の理解が難しくなるという問題が考えられますが、技術的には数理最適化ソルバーが複合問題に耐えきれなかったという側面もあると考えています。最近では数理最適化ソルバーの進化が凄まじく、このような複合問題を現実時間内で解けるようになってきました。以下では、配送問題と在庫問題の複合問題を考え、数理最適化ソルバーを用いて実際に解いて行きたいと思います。

在庫-配送計画の複合問題を解く意義

在庫計画と配送計画が複合された状況を考えてみましょう。
倉庫と配送先があり、配送先には商品の在庫があります。今回は、配送先から明示的な「発注」という行為は存在しなく、配送先の在庫量を予測して、配送するという状況を考えます。例えば、自動販売機の補充、ガスボンベの補充、公共の水タンクの補充、といった公共物を補充する状況を思い浮かべてください。これらは、明示的な発注という行為は（あまり）なく、配送する側が配送先の状況を予測して配送する必要があります。こういったケースでは、配送問題と在庫問題を切り分けて考えることはナンセンスです。それについて、より深く考察していきましょう。

例えば、上記のように2地点の配送先があり、片方は在庫が多く、もう片方は少ないとします。そのとき、あなたならどういう配送計画を立てますか？一度に2地点を補給するのも一つの答えです。こちらは配送便が1便で済みます。しかし、在庫が多い地点を補給しにいくのは、補給効率としては良くありません。例えば、自動販売機で言えば、在庫が多い方が電気代がかかりますし、訪問回数が増えるため、人件費もかかります。

一方、在庫が少ない地点に今日は行き、在庫の多い地点が少なくなるのを待ってから行くのはどうでしょう？こちらは補給という意味では効率的です。しかし、配送便としては2便使っているので配送費は高くつきます。
上の例では2地点だけで考えましたが、このような状況の異なる地点が100や200あったとしたらどうでしょう？もはや人の頭で理解が追い付かなくなるのが想像できるかと思います。さらに配送費用や在庫費用の額によっても意思決定が変化するのが、想像できるのではないでしょうか？こういった状況は現実問題ではいくつかあり、配送最適化ソリューション、在庫最適化ソリューションといった単一の問の切り出しでは、全体最適にはなりません。

在庫計画、配送計画の単一ソリューション

上では在庫、配送それぞれの単一ソリューションでは全体最適にならないと述べましたが、単一ソリューションを知らないのでは、話が始まりません。単一ソリューションについて簡単に解説します。

在庫計画最適化

在庫計画の最適化は在庫量を表す連続変数（S[t][i]）を用意します。Sは各期（日）の地点iの在庫量を表します。在庫量何もなければ、昨日の在庫量が今日の在庫量になります。式で書くならば、

$S^{t}_i = S^{t-1}_i$

と書けます。そこで地点iにイベントを追加します。イベントとは地点iに在庫を補給する補給イベントと、地点iから在庫量が消費される消費イベントのそれぞれが考えられます。補給イベント、ここでは補給量をa^t_i、消費量をb^t_iとしましょう。そうすると上記は以下のようになります。

$S^{t}_i = S^{t-1}_i + a^t_i - b^t_i$

この式を全ての期tと地点iに対して、入れれば、良いです。また在庫量は、0もしくは、ある値を下回ってはいけないという制約がよくあります。それは単純に不等式で簡単に表現できます。 Capⁱは地点iの在庫量の最大の保管量を表します。

$0 \leq S^{t}_i \leq Cap^i$

配送計画の最適化

こちらは、前回の岡崎さんの記事も参考にできます。第3回：はじめての配送計画の列生成法【ブレインパッドの数理最適化ブログ】 - Platinum Data Blog by BrainPad

今回は改めて、初学者がつまづきやすい、MTZ制約（訪問順序を表す制約）について復習します。トラックvの地点iの訪問時刻をu[v][i]、トラックvが地点iから地点jに移動すると1を出力するバイナリ変数をx[v][i][j]とします。今トラックvが地点iから地点jに移動する場合を考えます。そのとき、当たり前ですが、地点jの到着時刻は地点iの到着時刻よりも大きくなります（移動時間を足した値よりも大きくなります）。

$u^v_i + MoveTime_{i, j} \leq u^v_j$

ただ、数理最適化の厄介な点として、上記では不十分なのです。それは不等式の性質上、地点iから地点jに移動しない場合でも、上記成り立たなければなりません。そのような現象は、時間は後には戻らないのでありえません。よって、地点iから地点jに移動しない場合にも当てはまるように、上の不等式を拡張する必要があります。

$u^v_i + MoveTime_{i, j} \leq M \cdot (1 - x^v_{i, j}) + u^v_j$

Mは大きい値に設定してください。xが0（移動しない）場合は、上の不等式はMの効果により、合ってもなくてもよい、意味のない制約式となり、xが1の場合は、Mがなくなるため、拡張前の制約式に戻ります。

在庫計画と配送計画の複合問題の定式化

さて、前置きが長くなりましたが、ここからは数式をふんだんに使って、上記で取り上げた在庫計画と配送計画の複合問題を立式していきましょう。

上のように赤丸がデポ（供給地点）で緑丸が配送地点です。さらに各配送地点には以下のような在庫の残量（予測値）が与えられているとします。

予測誤差をエラーバーで表示しています。今回は簡単にするため、エラーバーは無視（予測誤差なし）として考えます。

このまま黙って何もしていないと、全ての地点の在庫量が０になり在庫切れ状態になってしまいます。それをうまくトラックを使って補給することで、補います。そこで、ただ補うだけでなく、数理最適化を使うことで、配送費用（トラックの使用によってかかる費用）と在庫費用（各地点の在庫量に比例してかかる費用）を最小化するように補給計画を作成します。地点の在庫量を０すれすれまで許すのは現実的ではないため、地点ごとに許容可能な最低在庫量が設定されているとします。

今回は、地点の最大在庫量の2割を最低在庫量としました（以下のMinInventoryAmountを指します）。この最低在庫量を下回らないように補給計画を作成します。今回はさらに簡単にするため、各地点には1日に1回しか訪問（補給）できないとします。

まず、各集合を用意します。

$\begin{aligned} I \cdots 配送先の集合 \\ I_0 \cdots 出発デポと配送先の集合 \\ I_+ \cdots 帰還デポと配送先の集合 \\ V \cdots 車両の集合 \\ T \cdots 計画日の集合 \end{aligned}$

次に、変数を用意します。

$\begin{aligned} &z^{t, v} \cdots t日にトラックvを利用する場合に1（バイナリ変数）\\ &y^{t, v}_i \cdots t日にトラックvが地点iに訪問する場合に1（バイナリ変数）\\ &w^{t, v}_i \cdots t日にトラックvが地点iへ供給する量（連続変数）\\ &x^{t, v}_{i, j} \cdots t日にトラックvが地点iから地点jへ移動する場合に1（バイナリ変数）\\ &S^t_i \cdots t日の地点iの在庫量（連続変数）\\ &u^{t, v}_i \cdots t日のトラックvの地点iにおける到着時刻（連続変数） \end{aligned}$

次に、定数を用意します。

$\begin{aligned} &Cap^i \cdots 地点iの最大在庫量 \\ &Cap^v \cdots トラックvの容量 \\ &Service_i \cdots 地点iでの固定作業時間 \\ &Demand^t_i \cdots t日の地点iの（予測）消費量 \\ &MoveTime_{i, j} \cdots 地点iから地点jの移動時間 \\ &MaxWorkTime \cdots トラックの1日の最大稼働時間 \\ &MinInventoryAmount_i \cdots 地点iの下回ってはいけない最低在庫量 \\ &RouteCost \cdots 1ルートあたりの配送費用 \\ &InventoryCost \cdots 単位在庫量における保管費用 \end{aligned}$

これらを用いて、今回の問題を定式化すると、下記の通りになります。

$\begin{align*} &\min: \sum_{t, v}RouteCost \cdot z^{t, v} + \sum_{i, t} InventoryCost \cdot S^t_i \tag{1} \\ &s, t: S^t_i = S^{t-1}_i + \sum_{v \in V} w^{t, v}_i - Demand^t_i \qquad (i \in I, t \in T) \tag{2} \\ &\qquad w^{t, v}_i \leq Cap^i \cdot y^{t, v}_i \qquad (t \in T, v \in V, i \in I) \tag{3} \\ &\qquad MinInventoryAmount \leq S^t_i \leq Cap^i \qquad (t \in T, i \in I) \tag{4} \\ &\qquad \sum_{v \in V} y^{t, v}_i \leq 1 \qquad (t \in T, i \in I) \tag{5} \\ &\qquad \sum_{j \in I_0} x^{t, v}_{i, j} = y^{t, v}_i = \sum_{j \in I_+} x^{t, v}_{i, j} \qquad (v \in V, t \in T, i \in I) \tag{6} \\ &\qquad \sum_{i \in I}x^{t, v}_{start, i} = z^{t, v} = \sum_{i \in I}x^{t, v}_{i, end} \qquad (v \in V, t \in T) \tag{7} \\ &\qquad u^{t, v}_i + Service_i + Duration_{i, j} \leq M \cdot (1 - x^{t, v}_{i, j}) + u^{t, v}_j \qquad (v \in V, t \in T, i \in I_0, j \in I_+) \tag{8} \\ &\qquad u^{t, v}_{end} - u^{t, v}_{start} \leq MaxWorkTime \qquad (v \in V, t \in T) \tag{9} \\ &\qquad \sum_{i \in I} w^{t, v}_i \leq Cap^v \qquad (v \in V, t \in T) \tag{10} \\ \end{align*}$

それぞれの式を説明します。

(1)・・・目的関数、１項目は計画期間内の配送費用の合計、２項目は計画期間内の在庫費用の合計。
(2)・・・t日の地点iの在庫量はt-1日の在庫量から、供給量を足して、消費量を引いたものに等しい。
(3)・・・トラックvがt日に地点iを訪問しない場合は、当然、補給量も0。
(4)・・・地点iの在庫量の上下限制約。この最低値を下回らないように、うまく車両を使って補給を行う。
(5)・・・t日の地点iの補給はいずれかのトラックが１度だけ行う。
(6)・・・t日の地点iへ訪問したトラックはいずれかの地点に行く。
(7)・・・t日にトラックvを利用する場合は、いずれかの地点へ行く。
(8)・・・t日のトラックvの時刻の訪問時刻の順序を表す制約。
(9)・・・t日のトラックvは最大労働時間以下しか働けない。
(10)・・・t日のトラックvは容量以下しか積めない。

この数理計画問題を解くことで、各日におけるトラックvの配送ルートを算出することができます。

結果と考察

では、上の最適化モデルを数理最適化ソルバーを用いて解いてみましょう。今回はモデルの理解のために、極端な例のみを紹介します。

i）在庫費用 >> 配送費用とした場合の結果

最適化により、出力されたルートが上の図で、各地点の在庫量の推移が下の図となります。トラックが訪問したタイミングで在庫量が増えている（補給されている）のが見て取れます。配送ルートは直送便が多く、２地点を回るルートは少ないことが見て取れます。これはトラックの利用料が０なため、複数地点を回るような効率の良いルートを作る必要がないためです。

一方、在庫量の推移を見ると、それぞれの地点で在庫量が少なくなってきてから補給をしていることが見て取れます。これは在庫費用が大きいため、在庫量が少なくなるのをできる限り待ってから補給した方が費用が削減されるため、このような結果になります。

ii）在庫費用 << 配送費用とした場合の結果

こちらも同様に、配送ルートと在庫量の推移を考察していきましょう。配送ルートは、地点を複数結んだルートを作成できており、効率の良いルートを作成できていると言えます。これは配送費用が高いため、１度に複数地点を訪問する方が費用が削減されるためです。

一方、在庫量の推移を見ると、i)と大きくは変わっていませんが、地点2は在庫量がまだあるタイミングで補給しています。これはどのタイミングで補給しても、在庫費用が変わらないため、配送費用が安くなるように他の地点の補給タイミングに合わせて一緒に補給したと考えられます。より詳細を見ると、地点6も4日に補給しているため、地点6の補給タイミングに合わせて地点2も補給するのが良いと最適化で判断されたと考えられます。

まとめ

費用の大小によって意思決定が変わるのはいかがだったでしょうか？このようにパラメータによって現実世界をシミュレートできるのは非常に面白く、ビジネスシーンにも非常に重要です。

特に、はじめはお客様のビジネスに合わせて、パラメータを設定しますが、「もし、配送費用が1000円安くなればトラックの利用数はどれだけ削減できるか」であったり、「利用数を4回にするには配送費用はいくらに設定すれば良いか」といった疑問に対しても柔軟に答えることができます。このあたりが、数理最適化モデルを構築する大きなメリットです。技術的には、目的関数と制約式を入れ替えることで、入力と出力を逆転させる、いわゆる逆解析を行うことができます。よりビジネスで勝つための意思決定を、支援できることが伝われば幸いです。さらに今回は制約条件を簡易なものだけにとどめましたが、
・ある地点は午前中しか受け入れしない。
・祝日は道路が混むので移動時間が長い。
・大きいトラックは、駐車場がない配送先には配送できない。
といった複雑な制約が多数考えられます。今回は割愛しますが、上記のような制約条件も数理最適化ならば容易に取り込むことができます。また、紙面の都合上割愛してしまいましたが数理最適化モデルは大規模なデータの場合、現実時間内に解けないという問題がありますが、我々は上記のモデルを大規模で解ける手段も持ち合わせております。機会があれば、大規模問題の場合の解決方法も紹介できればと思っています。

最後に

この記事では、データサイエンティストは問を解けるだけでなく、切り出す能力が必要という話を述べ、さらに最適化ソルバーの発達によって問の切り出しの自由度が増え、例としてサプライチェーンにおける配送計画と在庫計画の複合問題を紹介しました。今回は書けませんでしたが、まだまだ他の複合問題の例も考えられます。特に、サプライチェーンに限った話ではなく、ECサイトのマーケティングのような顧客育成の分析に関する問題も数理最適化として定式化も考えられ、最適化の可能性は無限大です。数理最適化は多くの歴史と研究があり、先人の方々には感謝するばかりですが、これからは先人の方々の知恵を融合した、複合的な最適化問題（全体最適化問題）が多く登場すると思っています。

ぜひともブレインパッドで最適化の可能性を一緒に広げてみませんか？言われた問を解くだけに飽き足らず、切り出す、企画することにもモチベーションのある方、ぜひともお待ちしています。