施設配置問題の概要、解き方と実践例


# はじめに
全ての営利企業にとって、現在の業務、すなわちオペレーションの改善をすることによって、より安くより品質の高いサービスを提供できる体制を維持し続けることは至上命題といえるでしょう。一般にメーカーと呼ばれるモノを作って販売している会社や、メーカーから倉庫管理や輸送業務を請け負っている運送会社などにとってそれは、 **どのように運ぶのが最も効率的なのか** という問題に帰着します。

運び方について、効率化できる観点は多岐に渡ります。例えば
1. どこに在庫、保管拠点を設けるべきなのか
1. 各在庫拠点内では、どのようなレイアウトにして、商品を保管すべきなのか
1. どのような包装形態を用意して、どのように商品を詰めるべきなのか
1. 輸配送のために回る必要のある拠点をどんな順番で回り、何台車両を使うべきなのか

といった悩みは代表的なものでしょう。

こうした複雑な要因が絡み合い、ある種どのようにでも調整ができてしまうため、どうしたらよいか、人間の頭では決めきれない悩みを数学的に解決すべく、従来からオペレーションズリサーチと呼ばれる技法が研究されてきました。
この記事では先に挙げた「どこに在庫、保管拠点を設けるべきなのか」について、最も良い答えを出すための数理最適化を用いたアプローチの方法と、その実践例について、まとめてみました。

# 施設配置問題
一般に今回取り上げる問題は **施設配置問題** と呼ばれます。
画像のような、工場（A）で生産された商品を、工場からコンビニ（ア～オ）へ毎日運んでいるケースを考えてみましょう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3926391/6135dabe-8952-b467-58d5-824b6969fd87.png)

この際、運ぶ商品の物量がトラック一台分必要なケースであれば、これ以上効率の良い拠点配置は見込めないかもしれません。
一方、もし
* 物量がトラック一台分を満たさない
* 各店舗に運ぶ物量が日によって異なる
* 土日祝日は工場が停止してしまい、出荷できなくなる

など現実によくあるような特性がある場合、工場から直接輸送をするのは得策でなく、もっと良い運び方があるかもしれません。こうした際に、工場とコンビニとの間に中継施設を設け、在庫を持つことによる需要波動の調整機能や、複数のコンビニを回る車両を編成する機能を持たせることで改善が見込めます。

さて、そうなると知りたくなることは
* どこに
* どのくらいの規模の施設を

設置するのかという問いの答えです。

この際、いくつかの条件が都合よくそろえば、最もよい回答を自動的に導き出すことが可能です。これは整数線形最適化と呼ばれます。ただ現実社会の問題の中で、そのような条件設定を行えることはほぼありません。（仮に設定できたとしても、もしこの条件をこう緩めてみたらもっと良くなるのでは？と皆考えるでしょう）

では自動的に解けない問題はどうするのか。
いたってシンプル、様々なパターンについて頑張って計算する、しかありません。
闇雲に頑張るのは大変なので、オペレーションズリサーチと呼ばれるような、効率的な頑張り方が日夜研究されているというわけです。
計算の仕方は、普段の生活の中で自然に行っているように、必要な値段を調べて、価値を算出すするだけです。
ここで、価値、とざっくり表現したのは、ここは各社のミッションや哲学、それに応じて決定される経営戦略に応じて様々になるためです。（少しでも早く届けることが価値である、ミスなく届けることが価値である、安いことが価値であるなどなど）
本記事ではより安く、という目的のもと記載しますが、いずれのケースにおいても目的が変わるのみで、解法が変わることはありません。

# 必要なデータは？
細かな条件を挙げていくとキリがありません（例えば、商品の中に運ぶ際の温度管理が必要なものがあり、その場合は冷蔵車を手配しないといけないため、通常の料金とは異なる運賃体系になる場合）ので、この記事では最低限必要な費用についてのみ、以下にまとめます。
抽象化すると、考えられるうる選択肢の一つを取ったときに、その状態を構築するのにいくらかかり、結果いくらで運べるようになったのか、が算出できれば構いません。
* 商品データ（どんなものを運ぶか？）
    * 商品の大きさ、重量（占有する倉庫の広さや、荷室の計算に使用）
* 顧客データ（どこに運ぶか？）
    * 住所
    * 商品別の需要予測（将来の予測は厳密には不可能なので、基本実績データが使われます）
* 施設データ（保管するのにいくらかかるか？）
    * 立ち上げに必要な費用
    * 維持に必要な費用
* 運賃データ（運ぶのにいくらかかるか？）
    * 運ぶ距離、重量に応じた料金表

# 計算の方法は？
先ほど、頑張って計算するしかない、と表現しました。本稿ではその頑張り方の代表的な遺伝的アルゴリズムをご紹介します。ちなみに言葉の通り、自然界に存在する生物の遺伝の仕方を模倣して作られた技法になります。
今回は簡略化のために、
* 候補となる施設の場所は3つしかない
* 施設では保管は行わない
* 顧客の最寄りの施設から配送する（最寄りの施設からの物量が足りない場合は、次に近い施設から追加で調達する）

という前提条件を敷いて、どれをどのくらい使う（どのくらいの物量を保管、分配させる）のかを検討してみます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3926391/ab67a4f4-1686-df96-ef96-2bd09d3a55ce.png)

まずテキトーに各施設をどのくらい使うか、を数値に起こしてみます。
```
{
    １：1.2,
    ２：3.5,
    ３：0, //0は使用しない、を意味します
}
```
この例では、施設１には毎日1.2kgの物量が流れ込み、施設２には3.5kgが流れ込み、...という場合になりますね（以降パターン1と呼びます）
前述した必要なデータを駆使することで、この条件のもと配送を行った場合はいくらかかるのか、を計算することができます。
例えばその結果が年間100万円だったとしましょう。

同じようにテキトーな数値で別のパターン2も試してみます。
```
{
    １：2.0,
    ２：2.1,
    ３：0.6,
}
```
この例では年間80万円となりました。

この調子で計算していってすべて計算しきれれば、最も良いことが保証できる使い方を算出できるのですが、施設の使い具合というのは連続値（定められた区間がなく、どんな数値でも設定可能）なので、計算は無数にできてしまうことが直感的にわかるかと思います。

さて、こうしたテキトーなパターンを100個ほど用意したとします。
100個の中で、配送の費用が安かったものをいくつかピックアップし、その中で2組の組み合わせを形成します。
（これが生物でいうところの、両親から染色体を1本ずつ受け取って、子供を作る行為に相当します。）
先ほどのパターン1と2が選択された場合、まずどちらのパターンを選択するかをランダムに決定します。
そして、自然界で観測されている交叉や突然変異、といった事象を発生させます。
* 交叉
本来、1本まるごと受け継ぐはずの染色体だが、一部分だけ選択されなかった染色体の情報に上書きされてしまう現象
* 突然変異
一部の染色体の情報に突拍子もなく変化が生じる

その結果、以下のような子供が誕生します。
```
パターン2が選択され、3には交叉が発生し、2には突然変異が発生した例
{
    １：2.0,
    ２：2.7,//突然変異により、パターン1でも2でもない情報が引き継がれている
    ３：0, //交叉により、パターン1の情報が引き継がれている
}
```
この新しく誕生した子供にて、配送費の計算を行います。
最初に用意したパターンの中で生き残った（配送費の安かった）染色体から、様々な組み合わせで子供が生成できるので、一度目と同じようにたくさんのパターンを作ることができます。

これを配送費に変化がなくなるまで繰り返すのが、遺伝的アルゴリズムの具体的な解法です。まさに生物が進化を遂げていくように、少しずつより良いパターンを生み出していく手法になっているのが想像できるかと思います。
こうした問題を解く際によく陥る現象として、局所解に陥ってしまう、というケースがあります。これは大胆な変更を施せば、もっと良い解がある可能性があるにも関わらず、その変更を施せないようなアルゴリズムでよく発生します。遺伝的アルゴリズムではこの点が突然変異や交叉や、その他今回はご説明していない様々な工夫によって対策されています。

# 実際の効果、実例は？
こうしたオペレーションズリサーチの技術を駆使した成果は例年OR学会で世界的に発表されています。施設配置問題でいうと、2012年にEdelman Award賞を受賞したオランダの運送会社[TNT Expressの取り組み](https://www.informs.org/News-Room/INFORMS-Releases/Awards-Releases/TNT-2012-Edelman-Winner?)が有名です。
ヨーロッパでの運送はその複雑に行くんだ地形や、面積の広さの具合から、飛行機を使った航空輸送と、トラックを使った陸送が混在して行われているそうです。どこに航空輸送の施設を持ち、どこにトラック輸送の施設を持つべきなのか、という問題に対し、種々のOR技法を用いて取り組み、SCM全体の改善に取り組み、実際に3年間で2億700万ユーロ以上の節約と利益を実現したとされています。（参考：2011年度の売り上げ72.5億ユーロ）

# おわりに
物流に携わる企業が持つ施設の配置の問題に関する数学的な解法と、その実例をご紹介しました。オペレーションに変更を加えるということは様々なリスクを伴います。一方で、実行した結果が数字によって一定の裏打ちがされているとなれば、意思決定も容易になると考えています。
株式会社LOKIARでは、こうした業務の効率化をするための物流コンサルティング、システム開発業務を承っております。ぜひお気軽にお問合せくださいませ。[物流について相談する](https://www.lokiar.com/contact)

また、弊社では開発にご助力いただける方を募集しています。
まずはカジュアルに情報交換させて頂ければと思いますので、
ぜひ[こちら](https://www.lokiar.com/recruite/entry)からお問い合わせください。