実際問題における無限期間の取り扱い方

世の中の多くの最適化の実際問題は無限期間モデルである．つまり，意思決定者はその活動をずっと続くものと仮定して何かを決める必要がある．例外としては，有限の期間で活動が終了するプロジェクトがあげられるが，多くの場合は，企業は永遠に存続するものと想定して，意思決定を行う．無限期間を取り扱う数理モデルもあるが，ほとんどが理論的な枠組みであり，実務に使おうとすると相性が悪い．実務では，時間を止めて静的な問題に帰着させて解決を図ることが多い．しかし，これはあくまでも近似であり，実際の無限期間で動的なモデルと，時間を止めた有限期間の静的なモデルの間には大きなギャップがある．ここでは，無限期間のモデルをどのように有限期間に落とし込んで解決するのかについて考察する．

ローリングホライズン方式

時間軸をもつ最適化モデルを考える際に重要なことは，不確実性情報の取り扱いである．将来の事象はより不確実であり，近未来の事象は確定的である．したがって，不確実な未来の情報は分からないので，考慮の範囲外とし，分かっている情報だけを用いてモデルを構築するというのが有限期間静的モデルである．しかし，ある期間以降の情報を全く無視するといった方法は多少乱暴である．時間が進むにつれて未来の不確定情報が徐々に確定しくので，それを組み込んだ新たな有限期間静的モデルを解き直そうというのがローリングホライズン方式である．たとえば，4週間分の生産計画を作成し，それを求解することによって得られた解にしたがって，最初の１週間の生産を行う．１週間経過した後は，すでに過去になった1週間分は固定し，その先の4週間分の生産計画を作成し直す．これは開始時から数えると5週間後までの計画を作成していることに相当する．この自然な枠組みは，適用が簡単であるため，実務でよく使われる．単に有限期間の問題に帰着させて解決するといった現実では最も良く使われている方法も，ローリングホライズン方式の特殊形と考えられる．

ローリングホライズン方式は，静的な有限期間モデルの最終期以降は無視するので，最終期近辺で誤差が生じる．これを有限期間効果とよぶことにする．この影響は，有限期間モデルの計画期間を長くすることによって緩和できる．生産計画の例だと，4週分ではなく8週分の計画をたて，そのうち最初の1週間だけを用いることに相当する．この方法は長い計画期間内の情報が既知であるというのが前提条件である．翌月（５週目から８週目）の需要が不明な場合には，この方法は用いることができない．

もう1つの有限期間効果の緩和法として，計画の見直し期間の短縮があげられる．上の例では，1週間おきに生産計画の見直しをしていたのを，1日おきに見直しを行うことによって，情報の更新の速度が上がるので，将来事象の変化に対応できることになる．この方法の弱点は，求解する頻度が増すことによる管理費の増大である．また，頻繁な計画の変更は，あまり望ましいことではなく，現場に余計な負担をかけることになる．これは，近未来の意思決定変数は以前決めていたものになるべく近づけるといった制約を付加することによって緩和できる．たとえば，翌日の生産量は以前決めていた量の通り，3日以内は10%以内の変更を認め，7日以内は20%以内の変更を認める，等の制約を加えることが適用例である．こういったヒューリスティクスは，現場でもよく使われている．

階層的アプローチ

現実の問題を解決する場合には意思決定レベルの概念が重要になる．すなわち，長期（ストラテジック），中期（タクティカル），短期（オペレーショナル）に分けて，詳細度の異なるモデルを作成し，段階的に最適化を行うのである．ストラテジックレベルでは，長期の意思決定を行う．このレベルにおいては，計画期間だけでなく，計画時間の単位（期）も長く，データも集約してモデル化する．たとえば，数年後までを考慮した生産計画がこれに相当する．期は年もしくは四半期，製品も製品群に集約してモデル化する．タクティカルレベルでは，中期の意思決定を行う．生産計画では月次生産計画程度に相当する．オペレーショナルレベルでは，短期の意思決定を行う．このレベルでは，日々の生産量（もしくは時間ごとの詳細スケジューリング）を最適化する．

通常は，上位レベルで決めた大まかな解を，下位レベルで詳細化して解き直すということが行われる．たとえば，ストラテジックレベルで決められた年次計画に基づき，タクティカルレベルで月次計画をたて，最後にオペレーショナルレベルで月次計画の満たすように日々の生産計画とスケジューリングが決められる．上位レベルで決められた解は，下位レベルの制約となる．すなわち，上で決めたことを遵守して，その制約の中で最適化を行うのである．進んだ階層的アプローチでは，上位から下位への情報伝達だけでなく，下位から上位への情報伝達も考える．通常，上位レベルでは下位レベルの細かい制約を無視して求解するので，下位レベルでは様々な不具合が生じる．段取り替えが必要な製品が頻繁に同じ期内で生産されていたり，時には実行不可能になったりする．下位レベルで困っていることを，上位レベルに伝えるための方法は問題に依存するが，上位レベルの問題に制約を追加したり，新たな変数を追加したり，パラメータを変更することによって解決する．制約や変数が追加された上位レベルの問題を再び求解し，上位も下位も納得するような解が出るまで，この反復を繰り返すのである．これは，会社内での意思決定プロセスに似ている．上司が決めた大まかな方針の下で部下が解を求め，無理な場合には上司に方針を変えるように伝える．これを繰り返すことによってお互いに納得する解を求めるのであるが，階層的アプローチはこれをフォーマライズしたものである．

期末調整法

静的な有限期間の問題を解くアプローチは，計画期間後の情報を無視しているので，不具合が生じた．これはローリングホライズン方式を用いても同じであり，計画期間後の情報は使うことはできない．最終期以降の情報を利用して，本来の無限期間の問題を解くための枠組みとして，動的最適化（計画）もしくはMarkov決定過程と呼ばれるもの（もしくはその近似法）がある．

動的最適化では，有限期間問題の最適値（費用）にその後に発生する期待費用を加えたものを最小化することを考える．無限期間の費用の期待値は無限大に発散するので，通常は将来の費用を適当な率で割引して期待値をとるか，確率1で到達する終端状態が存在すると仮定してモデル化を行う．計画期間後の費用は，最終期の期末のシステム状態に依存して決まるものと仮定する．すなわち，それ以前の期の状態には依存しないものとするのである．これはMarkov性と呼ばれ，動的最適化の別名であるMarkov決定過程の名前はここからとられたものである．状態とは，生産計画の場合には，各製品（原材料，部品）の在庫量，各工程の段取り状態などを指す．多期間の船やトラックなどの輸送手段による輸送計画を考えると，最終期の輸送手段の位置や，積載量が状態と考えられる．

最終期末のシステム状態を入れるとその後の費用の期待値を返してくれる関数を到達費用関数(cost-to-go function)と呼ぶ．この関数が既知であるとすると，動的な無限期間の問題は，静的な有限期間の問題に帰着することができるが，実際には状態の数が膨大になり，各状態に対する期待値の計算も難しいので，このようなアプローチは不可能である．実際的なアプローチとしては，状態をより小さな空間に写像した特徴ベクトルとして保管し，特徴ベクトルに対する到達費用関数を，シミュレーションを用いて近似的に計算することによって最適化を行う．特徴ベクトルは対象とする問題の構造を熟慮して決められる．生産計画の例では，（一例ではあるが）各製品に対する在庫量が特徴ベクトルであり，輸送計画の例デイでは，地域別の輸送手段の数などが特徴ベクトルの候補となる．

データが定常な分布として与えられている場合には，反復法によって到達費用関数を近似的に求めることができるが，非定常な場合には到達費用関数を計算すること自体が難しい場合もある．そのようなときには，望ましい期末の状態に近づけるような（ソフトな）制約を追加したり，期末の状態に対して適当な費用を設定したりすることによって，近似的な動的最適化を行う方法が現実的な解決策である．たとえば生産計画の例では，最終期の在庫量の目標値を制約として加えたり，在庫量に応じたペナルティ費用を追加したりすることに相当する．輸送計画の場合には，地域ごとの輸送手段の数の制約を付け加えたり，同じ地域に輸送手段が集中した場合のペナルティを付け加えたりすることに相当する．

周期性を用いたアプローチ

多くの実際問題の意思決定は周期性（サイクル）をもつ．たとえば，毎日同じような活動を繰り返す現場においては，1日がサイクルになり，毎週同じパターンの輸送を繰り返す場合には，1週間がサイクルとなる．サイクルの末尾と先頭をつなげたモデルを作成することによって，無限期間の問題が有限期間に問題に帰着される．

意思決定がサイクル性をもつことは，需要が周期的に変動することに起因するが，通常，需要は様々な周期をもって変動する．１日，１週，１ヶ月，１年などが主なサイクルとなるが，どの周期性を用いてモデル化すれば良いかということが問題になる．答えはなるべく長いサイクルを用いるというのが答えであるが，当然，長いサイクルを用いると問題規模が増大し，計算量的に解けなくなる．これを避けるためには，モデルの基本単位である期を長くする方法が考えられるが，計画の精度が悪化する．たとえば，１週間の周期性を考慮し，1時間を1期としたモデル化を行うと，計画期間数が128に増大する．問題規模が大きすぎて解けないと言って6時間を1期とすると，計画期間数は28となり小規模になるが，6時間内の細かい活動は考慮できなくなり，計画が粗いものになってしまう．

実際には，日時，週次，月次，年次の周期のどれが重要かを考えた上で，求解可能な問題規模から期の長さを決定する方法が必要になる．計画期間が長すぎる場合には，その一部だけにターゲットを絞って求解し，求解した一部を次々と変えていくことによって，問題全体を近似的に解く方法も推奨される．どの部分を取り出して最適化し，それをどのような順序で実行するかは，問題依存であり，問題の構造を考慮した特殊解法が必要になる．

まとめ

現場によってどの方法が良いかは変わってくる．

上の方法の組み合わせを巧く現場の事情にあわせて使うことが望ましい．

参考文献

ロットサイズ決定の論文（緩和固定法，期末調整）

Silver-Mealの階層的スケジューリング

近似DP，ニューロDPの論文