物流における最適化問題

# 物流における最適化問題

物流における最適化問題を紹介する。生産は物流と関係が深いので生産に関する問題も含む。
物流の問題は、一部の問題を除き、難しい問題が多い。また、入力データとなる諸元の入手が困難であることが多い。
以降で紹介する典型問題は理解を補助するため、簡略化しているものが多いので、実務で使う場合は、別途、検討すべきことが多いだろう。
経済発注量モデルは定式化して解く問題ではないので、ここでは省く。また、生産スケジューリング問題も定式化して解かれることが少ないので省く。

- ロジスティクス・ネットワーク設計問題
- 配送最適化問題(運搬経路問題)
- 船舶スケジューリング問題
- クルースケジューリング問題(勤務スケジューリング問題)
- 最小費用流問題
- 安全在庫問題
- ロットサイズ決定問題
- ジョブショップ問題(フローショップ問題)
- パッキング問題
- 収益管理問題

## ロジスティクス・ネットワーク設計問題

> 工場や倉庫などの拠点の配置/削減、生産ライン能力、生産量、在庫量、輸送量などを決定する問題。

- 拠点配置を含むことから物流最適化の最上位に位置する問題であり、この問題を後にして、その他の問題を先に解いても最終的に効率的とはならない。
- 物流最適化問題の中で、最も費用対効果の大きい問題である。
- 輸送量だけに着目すると輸送最適化問題となる。このように部分的に検討することも多い。
- 入力データとなる諸元の準備に手間がかかる場合、概算でもよいので、根拠のある数値を使う。

参考

- [ロジスティクス・ネットワーク設計問題](https://qiita.com/SaitoTsutomu/items/3c9fa2c8741236012057)
- [ロジスティクスネットワーク設計問題(OR Wiki)](http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E3%83%AD%E3%82%B8%E3%82%B9%E3%83%86%E3%82%A3%E3%82%AF%E3%82%B9%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E8%A8%AD%E8%A8%88%E5%95%8F%E9%A1%8C%E3%80%8B)
- [輸送最適化問題(最適化におけるPython)](https://qiita.com/SaitoTsutomu/items/070ca9cb37c6b2b492f0#%E8%BC%B8%E9%80%81%E6%9C%80%E9%81%A9%E5%8C%96%E5%95%8F%E9%A1%8C)


## 配送最適化問題(運搬経路問題)

> 複数のオーダを複数の車両(ビークル)を使って配送する問題。オーダとは、決められた荷物を配送元から配送先へ運ぶ要求を指す。

- 難しい問題のため近似解法で解かれることが多い。
- オーダに時間枠(配送先から出荷できる時間帯、配送元に入荷できる時間帯など)が決められているなど、様々なバリエーションが存在する。

参考

- [配送計画の簡単な解説(宇野先生)](http://research.nii.ac.jp/~uno/vrp.htm)
- [運搬経路(配送最適化)問題(典型問題)](https://qiita.com/SaitoTsutomu/items/1126e1493ff601a858c9)

## 船舶スケジューリング問題

> 車両の代わりに船舶を用いた配送最適化問題の海上版となる。

- 入港制限など、海ならではの制約がつくこともあるが、構造としては配送最適化問題と同じである。
- 列生成法を用いた集合被覆問題として解かれるケースがある。

参考

- [船舶スケジューリング(小林先生)](http://mathopt.sakura.ne.jp/shipsche.html)
- [船舶スケジューリング数理モデル作成の具体的手順(小林先生、PDF)](http://www.orsj.or.jp/archive2/or57-04/or57_4_205.pdf)

## クルースケジューリング問題(勤務スケジューリング問題)

> トラック、鉄道車両、航空機などの乗務員のスケジュールを求める問題。

- 機材(鉄道車両、航空機)の割当問題を先に解くこともある。

参考

- [勤務スケジューリング問題(典型問題)](https://qiita.com/SaitoTsutomu/items/e79ad9ca61a82d5482fa)
- [勤務スケジューリング(OR Wiki)](http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E5%8B%A4%E5%8B%99%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%80%8B)

## 最小費用流問題

> 各時刻の需要を満たすように、船舶や車両を用いて、物資が余剰しているところから不足しているところに最小の輸送費用で運ぶ問題。

- 物資が複数種類の場合、多品種最小費用流問題となる。
- 在庫の水準は、リスクを考慮して、別途、定めなければいけない。
- 使用済みのレンタカーや空きパレットなどを需要地に戻す問題もこれにあたる。この場合、在庫水準を複数定めると効果的である。

参考

- [最小費用流問題(典型問題)](https://qiita.com/SaitoTsutomu/items/41d625df63f1946c7216)
- [最小費用フロー問題(OR Wiki)](http://www.orsj.or.jp/~wiki/wiki/index.php/%E6%9C%80%E5%B0%8F%E8%B2%BB%E7%94%A8%E3%83%95%E3%83%AD%E3%83%BC%E5%95%8F%E9%A1%8C)

## 安全在庫問題

> 需要のばらつきに備えて在庫費用と(供給不可の)品切れリスクのバランスをとる問題。

- 品切れリスクをペナルティとして目的関数に入れたり、あるいは制約としたりする。
- 安全在庫量が独立な正規分布を仮定すると凹(非凸)な2次関数となり非線形最適化問題となる。
- 調達先を複数にして、災害などを考慮するようなモデルもある。

参考

- [在庫管理(OR Wiki)](http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E5%9C%A8%E5%BA%AB%E7%AE%A1%E7%90%86%E3%80%8B)
- [安全在庫量(木暮氏)](http://www.kogures.com/hitoshi/webtext/or-zk-anzen/)

## ロットサイズ決定問題

> 段取り費用が発生するなど、まとめて作成すると効率がよい場合に、在庫費用とトレードオフでどれだけまとめて作るかを決定する問題。

- ここでいう「段取り」とは、生産する製品の種類を変更するときに発生する作業を表す。

参考

- [動的ロットサイズ問題(OR Wiki)](http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E5%8B%95%E7%9A%84%E3%83%AD%E3%83%83%E3%83%88%E3%82%B5%E3%82%A4%E3%82%BA%E6%B1%BA%E5%AE%9A%E5%95%8F%E9%A1%8C%E3%80%8B)

## ジョブショップ問題(フローショップ問題)

> ジョブを機械に割当てる問題。処理順序が決まっている場合、フローショップ問題という。

参考

- [ジョブショップ問題(典型問題)](https://qiita.com/SaitoTsutomu/items/d088959bf884d40b2053)
- [ジョブショップ問題(OR Wiki)](http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%B8%E3%83%A7%E3%83%96%E3%82%B7%E3%83%A7%E3%83%83%E3%83%97%E5%95%8F%E9%A1%8C)

## パッキング問題

> コンテナなどの入れ物に荷物を効率よく詰込む問題。

- 切出し(カッティング)と詰込み(パッキング)は、表裏一体であり、問題としては同じとなる。

参考

- [n次元パッキング問題(典型問題)](https://qiita.com/SaitoTsutomu/items/0ac9bd564ae9f91285d7)
- [パッキング問題(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%83%E3%82%AD%E3%83%B3%E3%82%B0%E5%95%8F%E9%A1%8C)
- [カッティングストック問題(OR Wiki)](http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%AB%E3%83%83%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0%E3%82%B9%E3%83%88%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)

## 収益管理問題

> 時間経過により陳腐化する商品に対し、価格を操作し(上げて)、収益を最大化する問題。

- 航空運賃やホテルの価格決定でよく見られる。

参考

- [収益管理(LOGOPT)](http://www.logopt.com/mikiokubo/handbook/s-rm1.pdf)

## 関連書籍

- [サプライ・チェイン最適化ハンドブック(久保 幹雄)](https://amazon.jp/dp/4254270151/)