【手続補正書】
【提出日】平成18年3月31日(2006.3.31)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】      明細書
【発明の名称】  在庫管理の際のカバレッジプロフィールのレンジを最大化する方法及びシステム
【特許請求の範囲】
【請求項１】  コンピュータ内で経過するコンピュータプログラムを用いて、カバレッジプロフィール（Ａｂｄｅｃｋｕｎｇｓｐｒｏｆｉｌｅｎ）のカバレッジレンジ（Ｌａｇｅｒｒｅｉｃｈｗｅｉｔｅ）を最大化する方法において、以下の各ステップ：
ａ．オンライントランザクション処理システムに接続し；
ｂ．前記オンライントランザクション処理システムからトランザクションデータを読み出し；
ｃ．カバレッジプロフィール関数（Ａｂｄｅｃｋｕｎｇｓｐｒｏｆｉｌｆｕｎｋｔｉｏｎ）の領域用の前記トランザクションデータを入力し；
ｄ．カバレッジプロフィール用のカバレッジレンジ関数（Ｌａｇｅｒｒｅｉｃｈｗｅｉｔｅｎｆｕｎｋｔｉｏｎ）を形成し；
ｅ．少なくとも１つの開始値パラメータを用いて前記カバレッジレンジ関数を初期化し；
ｆ．前記カバレッジプロフィール用の前記カバレッジレンジ関数を解くために最適なストック量を求め：
ｉ．所要ストック量輸送用の最適解を求めるために最小コストフローアルゴリズムを用い；
ｉｉ．前記カバレッジプロフィール関数の領域用の前記最小コストフローアルゴリズムを前記開始値と共に用いて、解が見つかったかどうか検出し；
ｉｉｉ．解が求められない場合前記開始値をインクリメントに小さくし、前記最小コストフローアルゴリズムでの最適解が求められる迄、解の算出を繰り返し；
ｇ．解が求められた場合、前記開始値をインクリメントに大きくし、解の算出が前記最小コストフローアルゴリズムでの最適解となる迄、解の算出を繰り返す
各ステップを有することを特徴とするカバレッジプロフィールのカバレッジレンジを最大化する方法。
【請求項２】  コンピュータにより読み出し可能なメディアであって、
カバレッジプロフィールのカバレッジレンジを最大化するための複数の指示が媒体に記憶されており、その際、前記複数の指示は、プロセッサによって実行する際に前記プロセッサが以下の各ステップ：
ａ．オンライントランザクション処理システムに接続し；
ｂ．前記オンライントランザクション処理システムからトランザクションデータを読み出し；
ｃ．カバレッジプロフィール関数の領域用の前記トランザクションデータを入力し；
ｄ．１つの開始値を用いて前記カバレッジレンジ関数を初期化し；
ｅ．前記カバレッジプロフィール用の前記カバレッジレンジ関数を解くために必要なストック量を算出し：
ｆ．最適解を算出し、その際、前記算出は以下の各ステップを有しており：
ｉ．所要ストック量輸送用の最適解を求めるために最小コストフローアルゴリズムを用い；
ｉｉ．前記カバレッジプロフィール関数の領域用の前記最小コストフローアルゴリズムを前記開始値と共に用いて、解が見つかったかどうか検出し；
ｉｉｉ．解が求められない場合前記開始値をインクリメント状に小さくし、前記最小コストフローアルゴリズムでの最適解が求められる迄、前記解の算出を繰り返し；
ｇ．前記解が求められた場合、前記開始値をインクリメント状に大きくし、前記解の算出が前記最小コストフローアルゴリズムでの最適解となる迄、前記解の算出を繰り返す
各ステップを有することを特徴とするコンピュータにより読み出し可能なメディア。
【請求項３】  カバレッジプロフィールのカバレッジレンジを最大化するシステムにおいて、
以下の各手段：
ａ．オンライントランザクション処理システムに接続するための手段；
ｂ．前記オンライントランザクション処理システムからトランザクションデータを読み出すための手段；
ｃ．カバレッジプロフィールの領域用のカバレッジプロフィール関数内に前記トランザクションデータを入力するための手段；
ｄ．前記カバレッジプロフィールの領域用の関数を開始値で初期化するための手段；
ｅ．前記カバレッジプロフィール用のカバレッジレンジ関数を解くために所要ストック量を算出するための手段；
ｆ．最適解を算出するための手段、その際、前記最適解を算出するための手段は、以下の各手段を有しており：
ｉ．前記所要ストック量輸送用の最適解を求めるために最小コストフローアルゴリズムを用いるための手段；
ｉｉ．前記カバレッジプロフィール関数の領域用の前記最小コストフローアルゴリズムを前記開始値と共に用いて、解が見つかったかどうか検出するための手段；
ｉｉｉ．解が求められない場合前記開始値をインクリメント状に小さくし、前記最小コストフローアルゴリズムでの最適解が求められる迄、解の算出を繰り返すための手段；
ｇ．解が求められた場合、前記開始値をインクリメント状に大きくし、前記解の算出が前記最小コストフローアルゴリズムでの最適解となる迄、前記解の算出を繰り返すための手段
を有することを特徴とするカバレッジプロフィールのカバレッジレンジを最大化するシステム。
【発明の詳細な説明】
【０００１】
本発明は、輸送プランニングの最適化法、殊に、複数の配送区域（Ｖｅｒｔｅｉｌｅｂｅｎｅｎ）を有する輸送ネットワーク内でのストックのレンジを、殊に、発送品及び製品用の期日プランニングを迅速に特定するためのコンピュータ支援最適化アルゴリズムによって最適化する方法に関する。
【０００２】
一般的な従来技術：
製造及び貨物の配送（Ｖｅｒｔｅｉｌｕｎｇ）が関係する多くの産業分野で、保有資源及び輸送資源の割当の必要がある。
【０００３】
ドイツ連邦共和国特許公開第１９６１２６５２号公報からは、製造業者から顧客への商品用の材料フローを最適に形成するための配送方法が公知である。この方法は、中央コンピュータ制御卓並びにこれに接続されたデータ検出及び処理装置を用いて実行される。例えば、注文商品の需要に合ったストック保有及び配送を行うために、商品の実際の需要を指示する所定の注文リストが用いられる。実際の注文リスト、想定リスト、又は、その他の設定リスト及び需要リストを用いることによって、商品生産を、実際の商品需要に相応して、過剰生産せずに制御することができる。更に、販売乃至供給商品の個数を考慮して、中央コンピュータ制御卓内に記憶された過去３年間の商品販売に基づく統計的な方法を用いて、今後供給すべき商品を算出し、想定リストが作製される。所要商品の単なる個数を越える、最適な商品配送に影響を及ぼす別のパラメータ、例えば、コスト、ストック容量、配送区域の個数は、ドイツ連邦共和国特許公開第１９６１２９５２号公報には記載されていない。
【０００４】
割当の決定は、一般的にプラントの構成（Ａｕｓｒｕｅｓｔｕｎｇ）、時間、コスト、ストック容量（Ｌａｇｅｒｋａｐａｚｉｔａｅｔ）及び他のパラメータに関して制限され、これらは、分配（Ｄｉｓｔｒｉｂｕｔｉｏｎ）プロセス、殊に、商品分配プロセスの結果に影響を及ぼす。ここで、特に関心のある例として、複数の製造工場がある連鎖状の供給部（Ｖｅｒｓｏｒｇｕｎｇｓｋｅｔｔｅ）の分配量及び在庫量を最適化する必要があり、その際、複数の配送センタがストラテジーにより顧客の近傍に位置付けられる。
【０００５】
資源の割当についての決定は、一般的に制限されている。一方では、資源は、その利便性全体によって常に制限されており、更に、所定資源の効用が同様に制限されることがある。つまり、例えば、各個別連結区間のトラフィックコントロール容量（Ｖｅｒｋｅｈｒｓｆｕｅｒｕｎｇｓｋａｐａｚｉｔａｅｔ）がテレコミュニケーションシステム内に制限され、このコミュニケーションシステムに適した（ａｎｇｅｂｏｔｅｎｅ）トラフィック全体が同様に制限される。資源の個別の割当（Ｚｕｔｅｉｌｕｎｇ）は、「利回り（”Ｒｅｎｄｉｔｅ”）」を有しており、即ち、この割当のコスト又は利益を有している。従って、問題点は、全ての制限を考慮すると同時に前述の利回りを最大化する、即ち、欠点、例えば、コストを最小化し、乃至、利点、例えば、利益を最大化するように資源を割り当てる点にある。
【０００６】
その種の割当決定問題を表現する方法は、線形計画モデルとして公知である。その種のモデルは、マトリックス形式で表現される一連の線形関係からなり、定量的に、割当、制限と最適化プロセスの結果との間の関係を表す。線形関係では、未知の割当値と乗算された一定係数の和が表現される。線形計画のその種のモデル形成は、多次元空間内で達成され、その際、多次元ベクトルにより、多次元図形乃至ポリトープ（多胞体）が提供され、その際、各ファセット（Ｆａｃｅｔｔｅ：或いは極大面）は、当該各面の内の１つの面上で、プロセス中に割り当てられた資源間の関係を定義する方程式によって限定される。線形計画問題の解の式は、例えば、１９４７年にゲオルク・ダンツィク（Ｇｅｏｒｇｅ  Ｄａｎｚｉｇ）によって開発された単体乃至シンプレックスアルゴリズムを示す。択一選択的な解は、カーマーカー（Ｋａｒｍａｒｋａｒ）アルゴリズムである。最小コストフローネットワーク問題を解決することができる別の最適化アルゴリズムがある。その際、ネットワークフロー問題は、線形計画の特殊な場合を示す。
【０００７】
ネットワークフローアルゴリズムは、産業分野での計画問題で多面的に使用される。ネットワークフローアルゴリズムは、例えば、対応関係（Ｚｕｏｒｄｎｕｎｇ）、輸送、最小コストフロー、最短経路及び最大フローに関する問題設定の場合、ネットワークによって利用することができる。
【０００８】
対応関係問題では、２部（ｂｉｐａｒｔｉｔｅ）グラフがあり、この２部グラフは、多数の生産的ノードと消費的ノード（例えば、労働者及び任務）を有している。労働者と任務との間の弧（Ｂｏｅｇｅｎ）は、労働者と任務との対応関係に対するコストで重み付けされている。このような、全コストを最小に低減するという、各労働者に対する任務の対応付けの際のシナリオでは最適化問題がある。輸送問題では、生産的ノードと消費的ノードが工場施設と配送センタである２部グラフがある。各工場施設は、ユニットを生産し、各分配センタ（Ｄｉｓｔｒｉｂｕｔｉｏｎｓｚｅｎｔｒｕｍ）は、このユニットに需要を有する。工場施設と分配センタとの間の弧は、ユニットの輸送コストによって重み付けされる。最適化問題は、この場合、全ての需要が分配センタ内で充足されるという付帯条件付で、輸送コストを最小に低減することにある。最小コストフロー問題は、単に、ネットワーク内でのノード間の輸送問題に過ぎない。更に、弧は、最小及び最大容量を有している。
【０００９】
最短経路の問題では、正の重み付けされた弧を有するグラフがある。最適化問題は、輸送ネットワーク内での所定の２つのノード間で、最短経路を見つけることにある。ネットワークによる最大フローの問題は、輸送問題と同様であるが、但し、輸送容量を限定するノード間の弧が、輸送コストを有していない場合を除く。最適化問題は、輸送容量を損なわずにネットワークにより輸送される最大フローを達成することにある。しかし、従来技術では、ネットワークフロー問題は、各ノードと各ノード間の弧を有するネットワークに限定されており、その際、フローには各ノード間の輸送コストにより線形のペナルティ乃至「罰金」（Ｓｔｒａｆｅ）が課せられる。輸送コストの最小化の際比較的低い優先度を有していて、消費ノード内のカバレッジプロフィール（Ａｂｄｅｃｋｕｎｇｓｐｒｏｆｉｌｅｎ）の領域の最小化の際、突出して重要であるネットワークフローを解く必要がある。この問題は、従来技術の場合のように、線形最適化問題として定式化することができず、ネットワークフロー問題としても定式化することができない。
【００１０】
本発明の簡単な説明：
本発明の課題は、産業生産でのプランニングシステムで生じる配送問題でのカバレッジプロフィールの領域を最大化するための新規なアルゴリズムを提供することにある。この問題に使用可能な複数のアルゴリズムが提案されている。所与の配送問題に対して、どのアルゴリズムが適しているのか、という問題に関しての判断は、問題の大きさ及び計算用の最大受容可能ＣＰＵ時間に依存する。本発明は、種々の輸送形式、時間及び期日制限、需要の優先度及び決定された生産フローを考慮する、ネットワークフロー問題の新規な定式化を提案するものである。その際、アルゴリズム関数は、この定式化に使用される。
【００１１】
アルゴリズムの任務は、領域プロフィール定式化の自由変数（ｆｒｅｉｅｎ  Ｖａｒｉａｂｌｅｎ）の選定を、先ず、カバレッジプロフィールの領域が最大化され、その後、輸送コストが最小化されるようにすることにある。提案されたアルゴリズムは、基本的なモジュールとして任意の各最小コストフローアルゴリズムに使用することができる。
【００１２】
本発明の詳細な説明：
本発明は、新規の効率的なアルゴリズムを使用して、複雑な分配ネットワークでの商品及び貨物のフローの最適化のためのプランニングシステムに関する。先ず、プランニングシステムの定式化について検討し、その後、この定式化に使用できる新規なアルゴリズムについて説明する。アルゴリズムが使用されるシナリオの構成では、考察している時間期間に配送すべき製品の総量が予め決められていて、需要データも分かっているものと仮定する。ここで説明する配送アルゴリズムは、主として生産過程での障害又は配送プロセスでの短時間の変化に応答する必要がある。システムは、大量生産され、且つ、需要がかなり変動する製品に良好に適している。ここに示した最適化過程は、未来プランニング（プッシュ・ディストリビューション：Ｐｕｓｈ−Ｄｉｓｔｒｉｂｕｔｉｏｎ）により、輸送コストを最小に低減し、障害を回避するようにする。それにも拘わらず、障害が発生した場合には、需要に優先順位を設定して、最適に応答する（フェア・シエア・ディストリビューション：Ｆａｉｒ−Ｓｈａｒｅ−Ｄｉｓｔｒｉｂｕｔｉｏｎ）ようにされる。
【００１３】
本発明を用いることができる、商品の配送用システムの基本構造は、３つの要素を有している：つまり、生産プラント、中央倉庫及び配送センタである。
【００１４】
図面の簡単な説明：
以下、本発明について図示の実施例を用いて説明する。その際：
図１は、簡単な配送ネットワークのグラフ図、
図２は、複雑な配送ネットワークのグラフ図、
図３は、双方向グラフの形式で示した、対応関係問題のグラフ図、
図４は、等しい配送のネットワークのグラフ図、
図５は、種々の可能な対応関係の生産及び需要ノードのグラフ図、
図６は、供給及び需要のある生産プラントを示す図、
図７は、複数の輸送形式を有する配送ネットワークのグラフ図、
図８は、複数の輸送形式を有する最適化された配送ネットワークのグラフ図、
図９は、可能であって最適化もされた輸送区間の流れ図、
図１０は、可能且つ最適化された輸送区間の別の例を示す流れ図、
図１１は、許容されない区間が、配送ネットワーク内の可能な輸送プションに及ぼす影響を示す図、
図１２は、時間値を弧で示した簡単な配送ネットワークのグラフ図、
図１３は、配送ネットワークの生産及び需要プロフィールのグラフ図、
図１４は、可能な対応関係用のグローバルな領域プロフィールのグラフ図、
図１５は、別の可能な対応関係用のグローバルな領域プロフィール用のグラフ図、
図１６は、単調に最適化された輸送プラン用の例を示す図、
図１７は、最大の単調な領域プロフィールの探索を示す図
である。
【００１５】
図１には、配送ネットワークの最も簡単な場合が示されている。生産プラント（Ｐｒｏｄｕｋｔｉｏｎｓａｎｌａｇｅ）１０２では、限定して利用可能な生産装置を使用して、商品が生産される。この商品は、続いて（例えば、倉庫内に）一時的に保管される１０４。顧客に対する短い商品輸送区間と、迅速且つ経済的な配送を行うために、一時的な倉庫施設乃至配送センタ１０６が必要である。一時的な倉庫施設（一時的なノード）乃至中央倉庫１０４を用いると、比較的大きな輸送総量を達成することができる。中央倉庫１０４を使用すると、比較的長期の配送時間となるが、輸送コストは、比較的低くなる。配送センタが、必要な場合、直接配送するようにしてもよい。この特別な構成は、略示した構造でしか示していない。実際には、ネットワーク構造は、極めて多数のプラント、倉庫、配送センタからなるかなり大規模なものとなることがある。図２に示されているように、このネットワーク構造は、複数の製造プラント２０２、中央倉庫２０４及び配送センタ２０６を有している。
【００１６】
配送問題の課題は、以下のようにまとめることができる。典型的な連鎖状の供給部（Ｖｅｒｓｏｒｇｕｎｇｓｋｅｔｔｅ）内には、ソース、シンク及び輸送ネットワークがある。ソースは、プランニングされた製造プロフィールが呈示されているプラントである。シンクは、需要プロフィール（顧客の注文又は予測された需要）が呈示されている配送センタである。輸送ネットワークは、輸送コストと各中間ノード間の時間値とを有する弧からなる。本発明は、空間的及び時間的に配送される製造物（Ｐｒｏｄｕｋｔｉｏｎ）の、同様に空間的及び時間的に配分された需要に対する最適な対応関係（Ｚｕｏｒｄｎｕｎｇ）を探索し、その結果、カバレッジプロフィールのカバレッジレンジが最大化される。上述のように、２つの場合が区別される。”ブッシュ：Ｐｕｓｈ”の場合には、利用できる生産物の個数が需要を超過し、生産物は、カバーレッジ（Ａｂｄｅｃｋｕｎｇ）の領域が各領域から均等に増大するように配送される。”フェアシェア：Ｆａｉｒ  Ｓｈａｒｅ”の場合には、利用できる生産物の個数は需要を下回っており、生産物の配分は、比較的重要な顧客に優先的に供給され、同じ優先順位の顧客は同様に扱われるようにされる。本発明によると、比較的高い優先順位の顧客の需要がサービスされるよりも前に、比較的低い優先順位の顧客の需要がサービスされるのを阻止することができる。”ブッシュ：Ｐｕｓｈ”の場合には、カバレッジプロフィールの領域の最小値が全ての配送センタに使用される。”フェアシェア：Ｆａｉｒ  Ｓｈａｒｅ”の場合には、各優先順位クラスが順次連続的に扱われ、この優先順位の高い需要にサービスするために、このカバーレッジが最大化される。更に種々の輸送形式、輸送経路及び供給源が利用される場合、更に、全コストが出来る限り低くなるように全配送プランを最適化する必要がある。
【００１７】
上述の配送問題を解決しようとする際には、輸送問題乃至対応関係問題が中心的な役割を果たす。基礎となる対応関係問題は、以下のように定義される：同じ大きさの個数の左側及び右側ノードを有する２部グラフ表示では、左側部の各ノードは、右側部のノードに対応する必要があり、その結果、各ノードは、正確に１つのパートナーを持っている。その結果得られる２つのノード間の結合（弧”Ｂｏｇｅｎ”）は、所定のコストで結合される。その結果得られる全コストは、最小にする必要がある。図３には、対応関係問題がグラフ表示の形式で記載されている。矢印３０２は、左側部のソース３０４の、右側部のシンク３０６への可能な対応関係を示す。この対応関係のコストは、弧の値３０８として記入されている。古典的な輸送問題が、対応関係問題から区別されるのは、任意個数のノードの左側部のノード（ここでは生産者（”Ｐｒｏｄｕｚｅｎｔ”）と呼ばれる）が、右側部（ここでは消費者（”Ｖｅｒｂｒａｕｃｈｅｒ”）と呼ばれる）に対応することができる点である。解決すべき問題は、各ノード間で材料の適切な配分をどのようにして見つけることができるかという点にあり、その結果、所謂在庫量領域が最大化される。つまり、最小在庫量が、全てのノード及びサイクルに亘って最大化される。更に、可能な解（解群）から、最小輸送コストの解が選択される。倉庫のストック領域は、実際の在庫量にとって十分な、幾つかの順次連続するサイクル（現在のサイクルを含む）として定義される。従って、１の領域は、在庫量が正確に個別の、つまり、現在のサイクルの需要にカバーされるということである。
【００１８】
提案のアルゴリズムに使用される問題の展開について、以下、詳細に説明する。
【００１９】
古典的な場合
最も簡単な場合、一方の側に複数の生産プラント（ＰＡ）があって、他方の側に複数の配送センタ（単数の配送センタ）がある簡単な双方向ネットワークについて考察する。この古典的な場合には、供給は常に、プラントから配送センタの方に行われ、反対方向には行われない。生産プラントＰＡは、任意の配送センタに供給することができる。図４には、２つのプラント４０２，４０４及び２つのセンタ４０６，４０８を有する例が示されている。通常のように、生産プラントとして極めて多数の配送センタを有している。
【００２０】
生産プラントｉは、１サイクルｔ内に１つの生産速度ｐｉ（ｔ）を有している。配送センタｊ内には、顧客の需要ｏｊ（ｔ）が入れられている。全プラント及びセンタの初期在庫量はゼロである。１サイクル用の領域がセットされた場合（即ち、配送センタの在庫量は、所定サイクル内で当該サイクルに対して極めて精確に達する必要がある場合）、以下の状況となる：所定サイクルｔ内の配送センタｊの需要は、全ての生産物（Ｐｒｏｄｕｋｔｉｏｎｅｎ）によってカバーすることができ、この生産物は適時配送センタに供給することができる（即ち、サイクルｔよりも遅くなく）。そのため、この需要をカバーするために、全てのプラントｉの生産が全てのサイクルｔ′≦ｔ−Ｔｉｊ（その際、Ｔｉｊは、輸送時間である）内で使用することができる。この第１の例では、輸送時間は１サイクルで均等に調整されている。材料ユニットの輸送の場合、輸送コストＣｉｊが生じる。図５には、ここで説明しているネットワークで、窓が順次連続する３つのサイクルに拡張されている（それにより、ネットワーク算定時に付加的な時間変数が導入される）状況が示されている。考慮しているサイクルの個数は、地平乃至範囲（Ｈｏｒｉｚｏｎｔ）と呼ばれる。この新規なシナリオの場合、各ノード５０２は、図では、一日当たりの生産乃至一日当たりの需要である。矢印５０４は、輸送経路に直接相応するのではなく、その代わりに、所定の生産ユニットと所定の需要ユニットとの間の論理的な対応関係に相応する。そのために、各弧は、ソースの位置と目的の位置（ｉ及びｊ）によって、及び、開始時点及び終了時点（ｔｉ及びｔｊ）によって一義的に識別することができる。左側部のノードから右側部のノードへの所定材料量の対応関係は、フロー（流れ）として弧上に示される。このフローは、分配ネットワーク内の相応の輸送コストＣｉｊの高さのコストにつながっている。
【００２１】
見て分かるように、これは、オペレーションリサーチから公知であるような、古典的な簡単な輸送問題である。そのような古典的な簡単な輸送問題として、オペレーションリサーチからの標準的なアプローチ（Ａｎｓａｔｚ）を介して解決することができる（例えば、従来技術から公知のＭＯＤＩアルゴリズムを介して）。本来の最適化器（Ｏｐｔｉｍｉｅｒｅｒ）は、輸送問題の面上で作動するので、輸送ネットワークは、ここからは、最適化ネットワークと呼ばれ、最適化器は、輸送最適化器と呼ばれる。配送ネット内のノードは、分配ネットワークノード（Ｄｉｓｔｒｉｂｕｔｉｏｎｓｎｅｔｚｗｅｒｋｋｎｏｔｅｎ）と呼ばれ、最適化ネットワーク内のノードは、最適化ネットワークノード（Ｏｐｔｉｍｉｅｒｕｎｇｓｎｅｔｚｗｅｒｋｋｎｏｔｅｎ）と呼ばれる（両者に言及する際）。最適化ネットワーク内のノードは、ソース及びシンクに分けられる。
【００２２】
分配ネットワークの、この特別な場合は、簡単に処理することができる。と言うのは、この場合には、最適化されるネットの生産及び需要は、分配ネットワーク内での個別サイクルの生産及び需要に相応しているからである。領域が複数の時間期間に拡大されている場合には、このことは最早妥当しない。この値を、配送ネットから最適化されたネット内に正確に伝送する点について、以下（直ぐ次の段落で）説明する。
【００２３】
古典的な場合での配送問題から輸送問題へ
先行する段落では、所定１サイクルの決定された領域に対する配送問題が、輸送問題に投射されている。目的は、ここでは、各可能な領域用の投射を一般化する点にある。最適化されたネットワーク内でのシンクの値は、既に１サイクル以上の所定領域だけ、配送ネット内の需要から偏移しているので、及び、ソース値は、分配ネットワーク内の生産値から区別することができるので、最適化されたネットワークのデータに関して、特に配送ネット内のオリジナルデータから更に区別される。更に、最適化されるネットワークに関して、常に供給及び需要について言及される。つまり、生産及び注文という表現は、常に配送ネット内の値に関係している。最適化されたネット内の所定ノードｉの所定サイクルｔ内での供給は、ｓｉ（ｔ）として定義され、需要は、ｄｉ（ｔ）として定義される。
【００２４】
カバーレッジ領域の定義
所定領域Ｒ（ｔ）用の所定サイクルｔ内での目的在庫量は、後続のサイクルの注文から得られる（この際、安全商品在庫量）ｍｉ（ｔ）は未だ算入されない）：
【００２５】
【数１】
2002519265.tif 000001
【００２６】
カバーレッジ領域の択一選択的な定義／一般化
カバーレッジ領域（カバレッジレンジ（Ｌａｇｅｒｒｅｉｃｈｗｅｉｔｅ））についての一般的な表現は、択一選択的に、安全商品在庫量の乗数の最大化を含む：
Ｌｉ（ｔ）＝ｏｉ（ｔ）＋Ｒ（ｔ）＊安全商品在庫量
又は、単調に（ｍｏｎｏｔｏｎ）上昇する関数ｆに対して一般的に
Ｌｉ（ｔ）＝ｆ（Ｒ（ｔ））
である。
【００２７】
分かり易くするために、以下、カバーレッジ領域の最初に挙げた定義だけを考察する。
【００２８】
１つの配送センタの場合、需要ｄｉ（ｔ）は、目標在庫量の差Ｌｉ（ｔ）−Ｌｉ（ｔ−１）に依存し、目標在庫量は、更に、領域Ｒ（ｔ）と顧客の注文ｏｉ（ｔ）に依存する。需要ｄｉ（ｔ）は以下のように形成される：
配送センタ：ｄｉ（ｔ）＝ｏｉ（ｔ）＋Ｌｉ（ｔ）−Ｌｉ（ｔ−１）
［制約条件：  ｄｉ（ｔ）≧０  ⇔  Ｒ（ｔ）≧Ｒ（ｔ−１）−１  は、この場合充足される］
プラントの供給ｓｉ（ｔ）は、この簡単なモデルの場合、実際の生産に相応する。このプラントは、通常のように、固有の需要を有しておらず、即ち、達成する必要がある目標領域を有していない。プラントｓｉ（ｔ）の供給は、以下のように形成される：
ｓｉ（ｔ）＝ｐｉ（ｔ）
輸送問題は、先行の段落で示されているように、定義することができる。図５では、単に、ｐｉ（ｔ）は、ｓｉ（ｔ）によって置換され、ｏｉ（ｔ）は、ｄｉ（ｔ）によって置換される。
【００２９】
一般的な場合での配送問題から輸送問題へ
従来示されている輸送問題の投影用のモデルは、主要値に限定されている。安全商品間隔及び注文の際に複数の優先度クラスが考慮される：
【００３０】
【数２】
2002519265.tif 000002
【００３１】
（上述の非整数のＲ（ｔ）に対する一般化）
注意：通過貨物ｔｒｉ（ｔ）（決定された供給）も考慮される場合、需要は以下のように低減される：
ｄｉ（ｔ）＝ｏｉ（ｔ）−ｔｒｉ（ｔ）＋Ｌｉ（ｔ）−Ｌｉ（ｔ−１）
通過貨物が十分に大きい場合には常に、この需要は、場合により負となることがあり、即ち、このノードは、正の供給での供給ノードに対して変化する：
ｓｉ（ｔ）＝−（ｏｉ（ｔ）−ｔｒｉ（ｔ）＋Ｌｉ（ｔ）−Ｌｉ（ｔ−１））
つまり、決定された供給ｔｒｉ（ｔ）が十分に大きい場合には常に、配送センタは所定時間ｔで、供給ノード（需要ノードの代わりに）となることがある。この場合には、配送センタｉの、その種の供給は、輸送時間に関する所定時間ｔで、他のノードの任意の需要に対応することがある。殊に、同じ配送センタｉの未来の需要の輸送時間及び輸送ノードはゼロにセットされる。プランニング範囲の開始時点ｔ＝０では、配送センタの初期在庫量は、決定された供給ｔｒｉ（０）によってモデリングすることができる。図６には、製造プラント６０２と２つの配送センタ６０４，６０６を有する小さなネットワークが示されている。配送センタ１では、例えば、サイクル１の非常に大きな初期在庫量に基づいて過剰供給状態が生じている。これは、サイクル２の需要又は配送センタ２の需要に対応付けることができる。
【００３２】
種々の輸送手段
先行の段落では、２つのノード間の輸送手段を有する簡単なネットワークが考慮されている。種々の輸送方法が利用される解決手段を見つけるプロセスとなる変更点について調べる。種々の輸送方法は、必ずしも、経路での択一選択にも関係することがある種々の輸送手段（例えば、貨物自動車輸送の場合）とは限らない。即ち、比較的長い経路の場合、それにより比較的低い輸送コストになる場合に限って有意義である値にする必要がある。
【００３３】
図７には、例えば、貨物自動車７０２又は飛行機７０４によるような、複数の輸送用の可能な手段を有する分配ネットワークが示されている。種々の弧は、この場合、種々の輸送手段に相応している。区間は、常に、使用された輸送手段及び（サイクル内の）輸送の時間７０６でマーキングされる。最適化されたネットワークの図では、各弧は最大輸送サイクルに相関している。例えば、サイクル１からの供給の、サイクル２での需要への対応関係のために、単に１つの、輸送のために最早１サイクル以上必要としない輸送手段しか選定しないでよい。更に、実行可能な手段のみならず、最良の手段を選定することが有意義である。その際、基礎となっている仮定は、比較的遅速な輸送手段が選定されている場合、比較的安価な手段でもあると定式化することができる。そのために、この付加的な仮定は、原理的には、相応の輸送問題での対応関係のコストしか変えない。輸送問題との結合は、図８に示されており、この図では、複数の輸送形式がある最適化ネットが示されている。輸送コストの投影は、利用される種々の輸送形式によって拡張される。
【００３４】
一時倉庫を介しての輸送
更に、先ず、２つのノード間の各直接区間用の輸送の１つの手段しかない場合について考察する。続いて、その種の区間に対して、幾つかの択一選択肢が許容される場合に生じる変化について考慮する。
【００３５】
区間当たりの輸送の１手段の場合での一時倉庫施設
これまでは、単に１つの２段階分配ネットワークしか考慮してこなかった。消費者（この場合配送センタ）は、製造プラントによって直接供給される。分配ネットワークは、中央の一時的な倉庫施設も利用することが頻繁にある。この施設を導入することによって、配送センタへの輸送経路を部分的に束ねることができる。供給も同様に束ねることができ、従って、場合によっては低廉になる。中央の倉庫は、供給の最適化をサポートするために、通過ステーションのように機能する。この理由から、プラントの生産を分配センタに直接対応付けることができる。全輸送のサイクル（一時的な倉庫施設を介して）のために、中央の倉庫への輸送時間と、中央の倉庫から配送センタへの輸送時間との和を利用することができる。輸送時間には、場合によっては倉庫に入れる時間及び倉庫から出す時間が含められている。本発明の方法は、倉庫のカバレッジプロフィールの領域を最大化する必要があるので、出来る限り早機に供給し、そのために、輸送時間が短時間となる利点がある。この理由から、必ずしも直接的な経路でない場合であっても、２つのノード間を最も高速の経路にすると常に有利である。任意に選択された２つのノード間で最短の全輸送サイクルを得るために、輸送時間をグラフィックに表示する際、グラフィック表示の移行部の輪郭を考慮するとよい。図９には、２つのノード間の最短輸送時間の一例が示されており、上側は、所定のネットを示し、下側は、そのネットに所属する移行部の輪郭である。
【００３６】
第１の流れ図９０２には、種々の輸送経路及び輸送時間が示されている。ノード９０４からノード９０６に来るのに３サイクル続く。何れにせよ、ノード９０４からノード９０８を通ってノード９０６に来るのに、僅か２サイクルしか続かない。このことを考慮して、流れ図９１０が形成され、この流れ図は、各ノード間を動くのに必要な最小時間を示す。
【００３７】
このようにして、最も早い経路の時間が算出される場合、その経路でのコストが算出される。時間と同様に、このコストは、経路の各部分のコストの和から構成される。幾つかの経路がある場合、その中で最も効率的及び／又は最も有利な経路のコストが使用される。
【００３８】
各区間用の輸送の択一選択的な手段の場合での一時的な倉庫施設
上述のように、本発明の方法によると、分配ネットワーク内で択一選択的な弧を考慮することができる。中間ノードを介して輸送する際、種々のセグメントに対して、どの弧を利用すべきかという問いが立てられる。全ての組合せが許容される場合、幾つかの中間ノードで、各終端ノード間の輸送の非常に多数の迅速な手段が得られる。詳細に調べると、何れにせよ、この弧の組合せの何れかは有意義でないということが分かる。例えば、通常のように、第１のセグメントでは、エキスプレスコネクションは利用されず、第２のセグメントでは、遅速なコネクションが利用される。この理由から、コネクションに入るためには、以下の方法が選択される：
先ず、許容可能な最大の輸送形式の数がネット内で特定される。この輸送形式は、ここでは、種々の速度クラスに相応する（例えば、ノーマル及びエキスプレス）。２つのノード間に直接的なコネクションが定義される必要がある場合、各輸送形式（即ち、速度、クラス、等）に対してコスト及び持続時間が与えられる。それから、最適化器が、各クラスに対して別個に、最良の経路を算出する（最後の段落に記載されているように）。その際、このデータは、最適ネットワーク内で使用される。複数セグメントを有する経路では、輸送形式が相互に混合されない。しかし、所定区間で、１つの輸送手段しか許容されてはならない場合、全ての輸送形式に対して、同じデータが使用される。図１０には、一例が示されている。この図には、上側に、入りのネットワークが示されており、下側に、そのネットワークから最適化器によって形成されたネットワークが示されている。経路１００２は、製造センタ１００４、中央倉庫１００６及び配送センタ１００８を示す。経路１００２は、１サイクル必要な、列車による輸送経路１０１０、３サイクル必要な、貨物自動車による輸送経路１０１２、それぞれ１サイクル必要な、飛行機による輸送経路１０１４，１０１６を示す。通常モードの弧は、点で示されており、エキスプレス作動形式の弧は、直線で示されている。ノード１００６及び１００８間には、実際のコネクション、即ち、飛行機を介しての輸送だけがある。経路１０１８は、製造センタ１００４、中央倉庫１００６と配送センタ１００８との間で最適化器によって圧縮された経路を示している。
【００３９】
許容し得ないサイクル
以下、許容し得ない弧の実行について説明する。各輸送コネクション及び各分配ノードには、許容し得ないサイクルのリストを付けるとよい。許容し得ないサイクルは、例えば、輸送が休んでいる又は商品の受け渡しを行えない休日のような時間窓である。上述の古典的な場合が思い起こされるのであり、つまり、最適化ネット内の各ノードに、所定の材料割当の出発点ｉ、開始時点ｔｉ、目標位置ｊ及び所定の目標時間ｔｊが示される場合である。休日を考慮するために、各弧は、ｔｉが、ノードｉで商品を送出するのに許容されているサイクルになるような、未来の時点にシフトされる（即ち、開始時点にも目標時間にも、共通の時間デルタが加算される）。その後、ｔｊは、同様に、和が相応の輸送にとって十分な、ｔｉとｔｊとの間の許容されている輸送サイクルであり、ｔｊが、ノードｊで商品を受け取るのに許容されているサイクルになる迄シフトされる。図１１には、６個のサイクル１１０２，１１０４，１１０６，１１０８，１１１０，１１１２からなる範囲を有する最適化ネットワークが示されている。ノードは、分配ネットノード番号ｉ及び所属のサイクル番号ｔｉがマーキングされている。許容し得ないサイクルは、それぞれ陰影線／グレイで表示される。サイクル２内では、分配ネットノード１内での商品の受け取りは禁止されている。商品の引き渡し（Ｗａｒｅｎａｂｇａｂｅ）は、サイクル５内では許容されていない。サイクル３の１１１４内では、輸送は許容されていない。許容されていないサイクルの既述の分配は、当然極端な場合である。大抵の場合、休日は、少なくとも同時の商品受け取り及び商品引き渡し領域に影響を及ぼす。
【００４０】
最大領域プロフィールの探索
本発明の目的は、在庫量のレンジプロフィールが全てのストックに亘って最大となるように、需要ノードの配送センタに、利用できる材料を納品することにある。そのために、課題は、供給ノードと需要ノードとの適切な対応関係を見つけることにある。これまでは、所定の領域プロフィールに対して、上述の制約条件を充足する（最小輸送コスト、休日等が考慮される）対応関係が決められるやり方について、説明してきた。これは、輸送問題の投影及び効率的な輸送アルゴリズム、例えば、本発明により提案される改善されたアルゴリズムの基礎として利用することができるＭＯＤＩアルゴリズムを使用する、この輸送問題の解法によって行われる。以下、カバーレッジ領域最大化の問題について定義する。
【００４１】
過剰供給時のレンジプロフィールの最大化
過剰供給とは、プランニングされた顧客需要に完全に相応することができるということである。従って、輸送最適化器は、所定サイクルの最小レンジプロフィールの場合に全ての配送センタ及び時点に亘って所定の解法を見つける。レンジプロフィールは、最大化する必要がある。唯一のオプションは、所定の手段を用いて、種々のプロフィールを予測して、例えば、トライアル−アンド−エラー−方法によって、徐々に最適なものにしていく点にあることは直ぐに分かる。プロセスの一般的な妥当性が過剰に制限されない、既存の供給及び需要状況に関しての仮定は、何れにせよ、探索を強く加速することができる。何れにせよ、最早最適な解法を見つけることはできないという危険性は受容する必要がある。詳細に説明する前に、最大レンジプロフィールで何を意味することができるのかという問いに応える必要がある。
【００４２】
最大レンジプロフィールとは、どのようなものであるか？
全ての配送センタのレンジをネットワーク内に記述したい場合、各個別配送センタのレンジプロフィールを記述する必要がある。本発明の課題は、何れにせよ、所定の特定時点での各倉庫間のレンジを、出来る限り均衡させて、各配送センタに対して下側限界値として妥当するグローバルなレンジプロフィールによってしか応答しないのに十分であるようにすることにある。もっと正確に言うと、グローバルプロフィールＲ（ｔ）は、ノードｉに亘っての位置プロフィールＲｉ（ｔ）の最小値である。位置プロフィールは、場合によってはグローバルなプロフィール以上に位置することが時としてあり、つまり、この位置プロフィールは、何れにせよ、グローバルなプロフィール以下に位置することは一度たりともなく、即ち：Ｒ（ｔ）＝ｍｉｎｉ｛Ｒｉ（ｔ）｝が成立する。
【００４３】
これまでの場合同様に、これ以降も、レンジプロフィールによってのみ応動される（全ての配送センタに該当する）。最大レンジプロフィールは、各サイクル内で最大であるようなプロフィールであるということは直感的に予想される。しかし、この予想は失当である。所定サイクル内の最大レンジは、先行する他のサイクルのレンジから有意義に区別することができる。
【００４４】
図１２には、例として、２つの製造プラント及び２つの配送センタを有するネットワークが示されている。弧には、相応の輸送時間が記入されている。図１３には、所属の製品及び需要プロフィールが示されている。この例は、分配ネットワークの簡単なモデルにより構成されており、安全商品在庫量、初期倉庫在庫量又は固定アクセスである。全ての需要クラスは、同じ優先度を有しており、１つの輸送形式しかない。レンジプロフィールの以下の考察のために、常に、この簡単なモデルを用いる。所定サイクル内では、最大の可能なグローバルなレンジは、両配送センタが、このサイクル内で同時に達成することができるようなレンジである。サイクル２内では、レンジは、値３を有している。この値は、工場１２０２（４０ユニット）による第１のサイクルの生産が、配送センタに同じ部分で対応付けられている場合に限って達成される。工場１２０２は、第２のサイクル中では、この領域に何ら影響を及ぼさない。と言うのは、材料は、この工場１２０２によっては第３のサイクルの前では供給することができないからである。この対応関係では、配送センタ１に対して、第４のサイクル内で自動的にレンジ１となる。と言うのは、この配送センタは、工場２によって初めて、第５のサイクル内で達成され、製造プラント１の初期生産は既に「構築されている」からである。図１４には、この第１の対応関係に対する最大のグローバルなレンジが示されている。各サイクルの開始時の両センタ１２０６，１２０８の最小倉庫在庫量は、括弧内に示されている。倉庫在庫量が、後続サイクル全てに対して十分である場合には、常に無限のレンジとなる。と言うのは、範囲を越えるサイクルでは、需要は０のユニットによって占有されているからである。
【００４５】
サイクル４内のグローバルなレンジを１から２に上昇したい場合、以下の対応関係が提供される。サイクル１内で工場１２０２によって生産される４０ユニットの内、３０ユニットが配送センタ１２０６に対応付けられ、１０ユニットが配送センタ１２０８に対応付けられる。プラント１２０４内の第１のサイクルの４０ユニットの内、少なくとも２０ユニットが配送センタ１２０８に対応付けられる。プラント１２０２の残りの生産の適切な配分の際（例えば、両センタ１２０６，１２０８で同じ部分に）、図１５に示されているグローバルなレンジが達成される。
【００４６】
この対応関係は、付加的な利点を有している。つまり、グローバルな領域の最小値が、全てのサイクルに亘って１から２に上昇されるのである。この例は、開始時に最大の可能なグローバルなレンジを形成していることが、常に有利であるとは限らないことを示す。つまり、事後の時点で、グローバルなレンジの最小値に等しくすることができなくなることが度々ある。在庫量を等しくする、このプロセスは、どんな場合でも、良好な全プロフィールを得るのには所望である。図１４及び図１５のレンジプロフィールは、そのために、図１５のレンジプロフィールが、評価の際に、図１４のプロフィールよりも一層良好なものとして形成されるように段階付けする必要がある。（考え得るように）プロフィールのグローバルな最小値だけを比較すれば十分ではない。と言うのは、レンジが場合によっては最小値のほんの僅かしか上側でない他のサイクルは、比較を考慮することができないからである。そのために、グローバルなレンジプロフィールに対しては、以下の順序が定義される：
グローバルな領域プロフィールの段階付け：
２つのグローバルな領域プロフィールＲ１及びＲ２に対しては：
Ｒ１＞Ｒ２：⇔ｍｉｎ｛Ｒ１（ｔ）／Ｒ１（ｔ）≠Ｒ２（ｔ）｝＞ｍｉｎ｛Ｒ２（ｔ）／Ｒ１（ｔ）≠Ｒ２（ｔ）｝
が成立する。
【００４７】
この段階付けの完全性のために、２つの要素は等しくなることはあり得ず（プロフィールは、種々の点で同じ最小値を有する）、常に、他の２つの要素よりも大きな要素が１つあるということを示すとよい。
【００４８】
単調レンジプロフィール
公知の方法（トライアル−アンド−エラー−方法）を用いると、最適なレンジプロフィールを特定するのに非常に時間コストが掛かり、つまり、例えは、以下の方法を用いた場合である：所定の各時点で、１の均等な最小レンジから開始して、レンジは、サイクル１内でレンジの小さなデルタだけ拡大する。解が見つかった場合、レンジはサイクル２内で同様に拡大する、等である。全てのサイクルが処理された後、プロセスは再度第１のサイクルで開始する。レンジが所定サイクル内で拡大することができない場合、このサイクルは、後続の繰り返しの際拡大しないようになる。このアプローチの時間的な複雑さは、輸送最適化器のＯ（Ｒｍａｘ／Ｒｍｉｎ・Ｈ）呼び出し（Ａｕｆｒｕｆｅ）によって制限されており、それにより、場合によっては、かなりの時間が要求され、その際、Ｒｍａｘは、このサイクル内で生起することがある最適なレンジとして定義され；その際、Ｒｍｉｎは、精度（Ｐｒａｅｚｉｓｉｏｎ）乃至粒度（Ｇｒａｎｕｌａｒｉｔａｅｔ）として定義されており、この精度乃至粒度を用いて、この領域が特定され、及び、Ｈは、範囲を示す。この場合には、最適化器は、常に全範囲のデータを最適化する必要がある。
【００４９】
この理由から、本発明によると、先ず、単調なレンジプロフィールについて考察する。第２のステップでは、このアプローチはレンジプロフィールの単調でない領域で改善される。単調に増加する関数の場合、最大値は常に始点にあるので、単調に増加するプロフィールの下で最大値があるプロフィールは、他のプロフィールよりも大きな値に達する第１のプロフィール（最小値ｔを有する）である。最大の単調な領域プロフィールに基づいて算出される輸送プランは、非常に良好であるが、残念ながら常に最適であるとは限らない。このことを例で説明する。図１６の表は、１つの工場と２つの配送センタを有する分配ネットワーク内の可能な１状況を示す。輸送時間は、均一に１サイクルである。
【００５０】
最大の単調なレンジプロフィールＲＭ１６０２は、各サイクル内で値１を有している（範囲を越えたところのサイクルの需要には値０が仮定されるから、最後のサイクルは除外される）。と言うのは、サイクル５内では、比較的大きな領域は可能でないからである。この表には、最適化ネット内で供給が需要に対応付けられていて、配送が即座に開始される場合に得られるプランが示されている。ＺＭ１６０４では、例えば、第１のサイクル内での３０ユニットの生産は、配送センタ１２０６（図１２参照）の第１の３つの需要に対応している。全部で３つの対応した配送が即座に、即ち、この第１の生産サイクル内で開始されると、３０ユニットが全て配送センタ１２０６に輸送される。輸送プランＺＭ１６０４は、最大の単調なレンジプロフィールにとって十分である：しかし、輸送プランＺＭ１６０４は、最大の可能なレンジＲ１６０８よりも小さなＲ’Ｍ１６０６（対応関係Ｚの場合）の実際のグローバルなレンジ（即ち、配送センタの実際のレンジの最小値）を形成する。つまり、プランＺＭ１６０４は、最大の単調な領域にとっては非常に良好（単調に最適である）であるが、さほど、完璧に最適であるとは言えない。
【００５１】
第１のサイクルでの最適な輸送プランは、以下のように形成される：第１のサイクルの供給の対応関係は、全サイクル内の領域に否定的な影響を及ぼさないようにされる。以下の仮定によって、このプランによる、その種の探索のコストを著しく低減することができる。第１のサイクルの単調な最適な輸送プランを得るためには、最大レンジプロフィールの探索を、開始領域内に限って一定でないプロフィールに限定すれば十分であり、即ち、ｔ≦ｍａｘｉ，ｊ｛Ｔｉｊ｝、但し、Ｔｉｊは、ノードｉとｊとの間の輸送時間である。レンジプロフィールは、単に最大輸送時間のサイクルに至る迄上昇すればよく；後続の全てのサイクル内で、プロフィールは一定値を有することができる。
【００５２】
最適化ネットワークの特定の際、全範囲Ｈを考察するのではなくて、所定時点Ｈｋｕｒｚ＜Ｈに至る迄のサイクルｔ≦Ｈｋｕｒｚだけを考察する、即ち、ｔ≦Ｈｋｕｒｚの際、単に供給ｓｉ（ｔ）及び需要ｄｉ（ｔ）だけを考察する場合、最適化ネットワークは、最大レンジプロフィールＲｋｕｒｚｍａｘを供給し、この最大レンジプロフィールは、各サイクル内で少なくとも、全範囲（Ｈｏｒｉｚｏｎｔ）に亘って最大プロフィールＲｍａｘと同じ大きさである：
∀ｔ≦Ｈｋｕｒｚ：Ｒｋｕｒｚｍａｘ（ｔ）≧Ｒｍａｘ（ｔ）
高速レンジプロフィール
短い範囲が定義された後、この範囲は、１サイクルに短縮する必要がある。その結果得られる最適化ネットワーク（１サイクル内で輸送することが可能である場合に限って有意義である）は、非常に小さく、弧のフローは、非常に速く算出することができる。サイクル１内での最大レンジは、２進探索によって求められる。直ぐ次のステップでは、第２のサイクルが付け加えられ、両サイクルに亘って、最大レンジプロフィールを探索することが試みられる。その際、これまでは単に第１のサイクルに対してのみ該当していた、第１のステップのレンジプロフィールが含まれており、第２のサイクルは、先行するサイクル（この場合には第１のサイクル）の値を用いて初期化される。このプロフィールの解が探索された場合、第２のサイクルのレンジは、２進探索を用いて再度最大化することができる、等である。短い範囲で、レンジＲ（Ｈｋｕｒｚ）がＲ（Ｈｋｕｒｚ−１）によって受け取られた場合、即ち、解が探索されない場合、サイクルＨｋｕｒｚ内のレンジが１サイクルだけ低下される。この結果得られるプロフィールは、常に単調に含まれ、即ち、全てのサイクルｔ＜Ｈｋｕｒｚ内で、レンジは、Ｒ（ｔ）＝ｍｉｎ｛Ｒ（ｔ），Ｒ（Ｈｋｕｒｚ）｝にセットされる。遅くとも、この時点で、１つの解が可能である必要がある。と言うのは、領域Ｒ（Ｈｋｕｒｚ−１）のＲ（Ｈｋｕｒｚ）＝Ｒ（Ｈｋｕｒｚ−１）−１のレンジがサイクルＨｋｕｒｚ内で得られるからである。もう一度、このステップで、レンジが変えられる第１のサイクルから初めて、このサイクル及び後続のサイクルの値を上昇することが再度試みられる。考察している範囲は、Ｈｋｕｒｚのままである。Ｔｍａｘ＝ｍａｘｉｊ｛Ｔｉｊｊ｝が短い範囲で特定された後、直ぐ次のステップでは、それに後続する全てのサイクルが唯一のサイクルのように処理される。考察している範囲は、全範囲に拡張され、後続する全てのサイクルは、値Ｒ（Ｈｋｕｒｚ）にセットされる。このステップの後、この方法は終了し、最大単調プロフィールは探索される。これは、所定点Ｔｍａｘに至る迄上昇し、その後一定である。
【００５３】
図１７には、本発明の方法の一例が図示されている。ステップ４  １７０２は、バックステップ（Ｒｕｅｃｋｓｃｈｒｉｔｔ）を示す。サイクル（時間間隔）４内のレンジは、サイクル３の値に含むことはできず、そのために、１．２５の値に低減される。比較的大きな領域の先行サイクルは全て、この領域に低減される。その後、当該サイクルの領域を拡大することが再度開始される。各ステップで、丁度考察している範囲の最終サイクル内で、このレンジに対して探索された値、即ち、Ｒ（Ｈｋｕｒｚ）は、このサイクル内で達成することができるレンジの上側境界値を示す。最大単調プロフィールは、概して最大のプロフィール（例えば、この部分内での）を達成するのを不可能にする輸送プランも許容するので、算出された単調なプロフィール内での可能なエラーを可視にして、場合によっては、そのエラーにインタラクティブに応動するために、この境界値を使用することができる。
【００５４】
Ｏｐｔ（Ｈ）は、範囲Ｈ用の輸送最適化器の作動時間である場合、この作動時間は、最も不利な場合：
Ｏ（ｌｏｇ（Ｒｍａｘ／Ｒｍｉｎ）・Ｔｍａｘ・Ｏｐｔ（Ｈｍａｘ））
である。
【００５５】
Ｒｍａｘは、所定サイクル内で生起することがある最大レンジであり、Ｒｍｉｎは、このレンジを特定することができる精度（粒度）であり、Ｔｍａｘは、（最も遅速な輸送形式の場合）２つのノード間の最大輸送時間であり、Ｈｔｏｔａｌは、（輸送最適化器の作動時間を含む全作動時間の）全範囲である。
【００５６】
実際に使用する際、リセットステップは殆ど必要ないことが明らかである。比較的大きな確率の障害が最初に生起し、生産体積が、全体として需要体積を僅かに超過する（プッシュ・ディストリビューション：Ｐｕｓｈ−Ｄｉｓｔｒｉｂｕｔｉｏｎ）ことに基づく場合、最後のステップでは（全てのサイクルがＴｍａｘ後最適化ネット内に受け入れられる）、リセットステップは行われず、輸送最適化器の呼び出しの回数は、全範囲で僅かにｌｏｇ（Ｒｍａｘ／Ｒｍｉｎ）である。その際、初期領域でのコストと一緒に、以下の作動時間が得られる：
Ｏ（ｌｏｇ（Ｒｍａｘ／Ｒｍｉｎ）・（Ｔｍａｘ・Ｏｐｔ（Ｔｍａｘ）＋Ｏｐｔ（Ｈｔｏｔａｌ）））
本発明の方法は、第１のサイクルの単調最適化輸送プランを迅速に形成する。
【００５７】
不十分な供給
先行する段落では、需要を全て常に適時カバーするのに生産は十分であるということが仮定されている。これは、いつも成り立つわけではないことは当然のことである。不十分な供給がある場合、需要の状況を適切に緩める必要がある。これは、２種類のやり方で行うことができる：
１．  需要自体が低減され、即ち、幾つかの顧客の注文が、部分的に限って、又は、全く実行されない。
【００５８】
２．  注文の充足の際遅延される。
【００５９】
また、両方のやり方を組み合わせることができる。殊に、不十分な供給が単に短期間の問題ではない、即ち、生産が概して需要を下回っている場合には、組み合わせると有意義である。この状況では、需要を短縮せずに更に遅延量を大きくすることができる。
【００６０】
需要短縮
第１の場合（遅延なし）から説明する。需要を適切に短縮するために、顧客の注文（Ａｕｆｔｒａｅｇｅｎ）に種々の優先度が割り当てられる。サイクルｔ内の配送ノードｉの注文（Ｂｅｓｔｅｌｌｕｎｇ）ＯＰｉ（ｔ）には、付加的に当該注文の優先度Ｐがマーキングされる。重要でない優先度クラス（即ち、このクラスでの注文）のものは、利用できる材料体積が、未だ残っている注文を適時充足するのに十分である限り、削除される。前述のアプローチと同様の本発明のアプローチについて言及する。
【００６１】
【数３】
2002519265.tif 000003
【００６２】
１．Ｐｈｏｃｈ：高い優先度の顧客需要。
【００６３】
２．Ｐｎｏｒｍａｌ：通常優先度の顧客需要。
【００６４】
３．Ｐｎｉｅｄｒｇ：低い優先度の顧客需要。
【００６５】
４．Ｐｐｒｏｇｎｏｓｔｉｚｉｅｒｔ：単に予測されるにすぎないが、未だ、顧客によって注文されていない付加的な需要。
【００６６】
カバー領域Ｒ（ｔ）＝２．７とは、時点ｔで、高い優先度及び通常優先度の顧客の需要全てが充足可能であるということである。低い優先度の顧客の場合、充足度は、７０％である。
【００６７】
最大レンジプロフィールの本発明の定義によると、比較的高い優先度の需要が、比較的低い優先度の需要の不利になるように充足されないようにすることができる。
【００６８】
遅延した配送
上で考察した事例では、遅延した配送は生じない。つまり、注文に適時に配送することができない場合には常に、その注文には、全く配送されない。例：ｔ＝１の高い優先度の需要と、ｔ＝２の低い優先度の需要とがある場合、及び、第１の供給がｔ＝２で行われる場合、低い優先度の需要には、全て供給されるが、高い優先度の需要には全て供給されるとは限らない。
【００６９】
この問題は、本発明によると、輸送時間を低減した付加的な弧を導入することによって解決される。遅延時間Δの配送は、相応の輸送時間をΔだけ低減した配送に相応する。
【００７０】
この付加的な弧の場合、コストは以下のように定義される：
ペナルティ（Ｓｔｒａｆｅ）＝Δ２＊２Ｃｍａｘ
Δ：遅延時間
Ｃｍａｘ：遅延時間のない弧の最大コスト
で定義される。
【００７１】
式２Ｃｍａｘにより、交換、即ち、対応関係
ｓｉ（ｔｉ）−＞ｄｊ（ｔｊ）とｓｉ′（ｔｉ′）−＞ｄｊ′（ｔｊ′）
を    ｓｉ（ｔｉ）−＞ｄｊ′（ｔｊ′）とｓｉ′（ｔｉ′）−＞ｄｊ（ｔｊ）
により交換することによって、遅延を阻止することはできないようにされる。
【００７２】
対応関係を交換しても遅延しない場合、そのコストは、≦２Ｃｍａｘ＜Δ２＋２Ｃｍａｘであり、従って、遅延のない対応関係よりもコスト安である。最適化器は、この理由から、交換によって阻止できる遅延のある解を生成しない。それと同様にして、式Δ２により、長い遅延を交換によって短縮することができないようにされる。
【００７３】
配送問題での展開（ｄｅｐｌｏｙｍｅｎｔ）問題の投影の記述
更に、輸送問題に関して示された従来の配送問題の説明について、もう一度数学的形式でまとめる。
【００７４】
場合１：過剰供給
先行する計算
第１に、最適化ネットワークの生産及び需要について算出する必要がある：
配送センタ：
【００７５】
【数４】
2002519265.tif 000004
【００７６】
Ｄｉ（ｔ）＞０の場合、
ｄｉ（ｔ）＝Ｄｉ（ｔ）          ｛需要ノード｝
が成立し、そうでない場合には、
ｓｉ（ｔ）＝−Ｄｉ（ｔ）                ｛供給ノード｝
が成立する。
【００７７】
配送センタのターゲットの倉庫在庫量を用いると：
【００７８】
【数５】
2002519265.tif 000005
【００７９】
最適化問題
最小化：
【００８０】
【数６】
2002519265.tif 000006
【００８１】
場合２Ａ：供給不足時の需要の低減
先行する計算
先ず、最適化ネットの生産及び需要を算出する必要がある：
配送センタ：
【００８２】
【数７】
2002519265.tif 000007
【００８３】
Ｄｉ（ｔ）＞０の場合、ｄｉ（ｔ）＝Ｄｉ（ｔ）    ｛需要ノード｝
そうでない場合、ｓｉ（ｔ）＝−Ｄｉ（ｔ）    ｛供給ノード｝
配送センタのターゲットの倉庫在庫量を用いると：
【００８４】
【数８】
2002519265.tif 000008
【００８５】
【数９】
2002519265.tif 000009
【００８６】
【数１０】
2002519265.tif 000010
【００８７】
最適化問題
最小化：
【００８８】
【数１１】
2002519265.tif 000011
【００８９】
場合２Ｂ：供給不足時の遅延
先行する計算
再度、上述の場合と同様にして、最適化ネットの生産及び需要について、先ず計算する必要があり、遅延弧にペナルティコスト（Ｓｔｒａｆｋｏｓｔｅｎ）を付けることによって、最適化関数を変えるだけである。この付加的な弧だけに、受け入れ可能な遅延を導入することによって時間遅延を制限してもよい。
【００９０】
最適化問題
最小化：
コスト＝輸送コスト＋遅延ペナルティコスト
【００９１】
【数１２】
2002519265.tif 000012
【００９２】
変数及び定数
自由決定変数：
【００９３】
【数１３】
2002519265.tif 000013
【００９４】
結合された変数（制約された決定Ｒ（ｔ）で最大化すべき）：
Ｒ（ｔ）＝時点ｔでの全ての配送センタのレンジ
Ｌｊ（ｔ）＝時点ｔでの配送センタｊ内のターゲットの在庫量
ｓｉ（ｔ）＝時点ｔでのノード（製造工場）ｉの供給
ｄｊ（ｔ）＝時点ｔでのノード（配送センタ）ｊの需要
定数：
Ｐｉ（ｔ）＝所定時点ｔでの製造工場ｉでの製造速度
ｔｒｉ（ｔ）＝所定時点ｔでの配送センタ又は中央倉庫ｊでの予め決定された供給（通過時）
【００９５】
【数１４】
2002519265.tif 000014
【００９６】
Ｐ＝需要優先度Ｐ，Ｐ∈｛Ｐｈｏｃｈ，．．．，Ｐｐｒｏｇｎｏｓｔｉｚｉｅｒｔ｝＝｛１，２，３，．．．｝その際、Ｐｈｏｃｈ＝１＜．．．＜Ｐｐｒｏｇｎｏｓｔｉｚｉｅｒｔ
ｏｊＰ（ｔ）＝時点ｔでの配送センタｊの優先度クラスＰでの注文（＝頻繁な需要）
ｍｊ（ｔ）＝時点ｔでの配送センタでの安全倉庫在庫量
Ｄ＝輸送形式
Ｄ∈｛最遅、・・・、最早｝
ＣｉｊＤ＝ノードｉとｊとの間の輸送形式Ｄでの材料ユニットの輸送用の輸送ノード
ＴｉｊＤ＝ノードｉとｊとの間の輸送形式Ｄでの材料ユニットの輸送用の輸送時間
Ｄｓｃｈｎｅｌｌｓｔｅ＝最早輸送形式：      ∀Ｄ，ｉ，ｊ：
ＴｉｊＤｓｃｈｎｅｌｌｓｔｅ≦ＴｉｊＤ
Ｄｌａｎｇｓａｍｓｔｅ＝最遅輸送形式：      ∀Ｄ，ｉ，ｊ：ＴｉｊＤｌａｎｇｓａｍｓｔｅ
【００９７】
【数１５】
2002519265.tif 000015
【００９８】
【数１６】
2002519265.tif 000016
【００９９】
アルゴリズム
プログラムを定式化した後、適用すべきアルゴリズムについて説明する。このアルゴリズムの基本的な技術思想は、最適プロフィールが見つけられる迄、レンジプロフィールＲ（ｔ）を増分的に変化させる点にある。このアルゴリズムの基本的な方法ステップは、以下の点を有している：
１．  レンジプロフィールＲ（ｔ）の初期化（例えば、Ｒ（ｔ）＝１）
２．  プロフィール制約条件を充足するために、需要ノードでの所要需要ｄｊ（ｔ）の算出
３．  任意の最小コストフローアルゴリズムを用いて、この需要の最も格安のフローの構成
４．  解が見つけられない場合、レンジプロフィールＲ（ｔ）を縮小化し、そうでない場合には当該レンジプロフィールＲ（ｔ）を拡大する。
【０１００】
５．  最適な解が見つけられない場合、ステップ２に戻る。
【０１０１】
ステップ２は、上の段落で説明したような全てのアルゴリズムに対して同じである。
【０１０２】
【数１７】
2002519265.tif 000017
【０１０３】
ステップ４に対する本発明の種々の択一選択は、以下の段落で提案される。先ず、全問題、即ち、レンジプロフィールの最大領域の効率的な構成の問題について説明する。このアルゴリズムは、下で説明するレンジプロフィールの単調な領域に制約することによって、かなり加速化することができる。以下、レンジプロフィールの最大化用の単調なプロフィール用の高速アルゴリズムについて説明する。
【０１０４】
Ａ．カバレッジプロフィール（ＡＢＤＥＣＫＵＮＧＳＰＲＯＦＩＬＳ）の最大領域
レンジプロフィールの最大（整数）領域の構成のために、全プランニング範囲を数回スウィープする各時間ステップで可能である場合に、実際のプロフィールを常に繰返し１だけ増大する。
【０１０５】
ステップ４用のアルゴリズム
While Profile enlarged do begin
｛プランニング範囲をスウィープ：Den Plannungshorizont ueberstreichen｝
enlarged=false；
for all t （プランニング範囲：Plannungshorizont） do begin
R(t)：＝R(t)＋1；                              ｛Ｒ      拡大｝
Generate min cost flow problem F(R) for profile R(t)
｛＝第２ステップ（上述の記載参照）｝
If min cost flow (F(R)) solvable
then enlarged=true
else R(t)：＝R(t)-1                      ｛リセット｝；
end；
１の代わりに比較的小さなステップ幅Δ＜１だけ、プロフィールを拡大するための一般化が行われる：
プロフィールＲ用のステップ幅Δを有するステップ４のアルゴリズム
While Profile enlarged do begin
｛プランニング範囲をスウィープ：Den Plannungshorizont ueberstreichen｝
enlarged＝false；
for all t  ≦プランニング範囲    do begin
R(t)：＝R(t)＋Δ；                                ｛Ｒ      拡大｝
Generate min cost flow problem F(R) for pofile R(t)
｛＝第２ステップ（上述の記載参照）｝
If min cost flow (F(R)) solvable
then enlarged＝true
else R(t):＝R(t)−Δ                      ｛リセット｝；
end；
end；
Ｂ．レンジプロフィールの最大単調領域
基本的な技術思想は、問題を帰納的に解決することにある：
・空のプロフィールで初期化。
【０１０６】
・ｔの時間ステップ用の解の構成及び当該解の、ｔ＋１時間ステップ用への改善。
【０１０７】
・ｔ＝プランニング範囲  になる迄繰り返す。
【０１０８】
ステップ４用のアルゴリズム
Initialize R(t)：                      ∀t：R(t)＝0
ｔ＝ｔ０；    ｛プランニング開始時点｝
While t＜プランニング範囲    do begin
｛帰納ステップ｝
R(t+1)＝R(t)；
Generate min cost flow problem F(R) for profile R(t)
｛＝第２ステップ（上述の記載参照）｝
If min cost flow (F(R)) solvable
Then Begin                                  ｛R(t+1)拡大｝
Repeat
R(t+1)：＝Ｒ(t+1)+1；
Generate min cost flow problem F(R) for
profile R(t)
Until min cost flow (F(R)) not solvable
R(t+1)：＝R(t+1)-1                                        ｛リセット｝
End
Else
｛Ｒ  縮小｝
Repeat
Ｒｍａｘ＝R(t+1)
ｔＲ＝min｛t｜R(t)＝Ｒｍａｘ-1｝；
∀ｔ′＞ｔＲ：R(t′)＝Ｒｍａｘ−１；
Generate min cost flow problem F(R) for
profile R(t)
Until min cost flow (F(R)) solvable
ステップ４用のアルゴリズム−ステップ幅Δを有するレンジプロフィールの単調領域
１の代わりに比較的小さなステップ幅Δ＜１だけ、プロフィールを拡大するための一般化が行われる：
Initialize R(t)：    ∀t：R(t)＝0
t＝t0；    ｛Planning Start｝
While t ＜  プランニング範囲      do begin
｛帰納ステップ｝
R(t+1)＝R(t)；
Generate min cost flow problem F(R) for profile R(t) 
｛第２ステップ（上述参照）｝
If min cost flow (F(R)) solvable
Then Begin                            ｛R(t+1)｝  拡大｝
Repeat
R(t+1)：＝R(t+1)；Δ；
Generate min cost flow problem F(R) for profile R(t)
Until min cost flow (F(R)) not solvable
R(t+1)：＝R(t+1)−Δ                ｛リセット｝
End
Else                                  ｛Ｒ  拡大｝
Repeat
Ｒｍａｘ：＝R(t+1)；
ｔＲ＝min｛ｔ′｜Ｒ（ｔ′）＞Ｒｍａｘ−Δ｝
∀ｔ′≧ｔＲ：Ｒ（ｔ′）＝Ｒｍａｘ−Δ；
Generate min cost flow problem F(R) for
profile R(t)
Until min cost flow (F(R)) solvable
Ｃ．回転するプランニングスキーマ用の効率改善
回転するプランニングシナリオにとっては、製品をスタート時点ｔ０で何処に送る必要があるのか、即ち、時点ｔ０での発送プランニングｙｉｔ０ ｊｔｊは、最適プランニングに拡張可能であるようにする必要があるが、後続の時間ステップでの発送プランニングは場合によっては最適ではない。本発明によると、プランニング窓をシフトすることによって補償される。
【０１０９】
以下、レンジプロフィールは、以下のタイプに限定される：最大輸送時間ｔｍａｘに至る迄均一に、及び、ｔｍａｘ後一定となる。この単調プロフィールを解くことができない限り、最後の一定関数部は低減される。
【０１１０】
ステップ４用のアルゴリズム−回転するプランニングスキーマ
最大輸送時間、即ち、ｔｍａｘが設定されている場合、
最大単調レンジプロフィールＲｍａｘ（ｔ）を求めること
プランニング窓内  ［planning start,
planning start＋  ｔｍａｘ  ］；
Initialize R(t)：｛Ｒ  の一定持続｝
∀ｔ  ≦ｔｍａｘ：Ｒ（ｔ）＝Ｒｍａｘ（ｔ）
∀ｔ  ≦ｔｍａｘ：Ｒ（ｔ）＝Ｒｍａｘ（ｔｍａｘ）；
Ｒｍａｘ：＝Ｒｍａｘ（ｔｍａｘ）；      ｛Ｒ  の最後の定数部分変更｝
決定  min cost flow problem F(R)    プロフィール  Ｒ（ｔ）に対して
While min cost flow(F(R)) not solvable do begin
ｔＲ＝ｍｉｎ｛ｔ｜Ｒ（ｔ）≧Ｒｍａｘ−１｝
∀ｔ≧ｔＲ：Ｒ（ｔ）＝Ｒｍａｘ−１；
Ｒｍａｘ＝Ｒｍａｘ−１
決定  min cost flow problem F(R) プロフィール R(t)に対して
End；
一般化
非整数容量プロフィールの構成のために、カバレッジプロフィールＲ（ｔ）の領域用の可能な値のステップ幅Δは制限される必要がある。ステップ幅Δが小さい場合、最大プロフィールが見つけられる迄、数回繰り返す必要がある。後続の段落では、２進探索プロセスによって、最大単調プロフィールを探索するのを、どのようにして加速することができるのかについて説明する。
【０１１１】
１．最大単調プロフィールの２進探索
ステップ幅Δのカバレッジプロフィールの最大単調領域用のアルゴリズムの場合、２つの部分が考慮される：  ”Ｒ（ｔ）  拡大  ”及び  ”Ｒ（ｔ）  縮小  ”  である。
【０１１２】
両方の場合、２進探索を用いての容量プロフィールの最後の一定部分を最適に調整する探索が加速される。本発明のアルゴリズムを２進探索プロセスを用いて簡単に拡張する点について、以下説明する。分かり易くするために、択一選択的な変数は省かれている（例えば、２進探索のステップ幅δを、最小の可能な値δ＝Δの代わりに経験により学習された値を用いて選択すること）。
【０１１３】
ステップ４用のアルゴリズム−ステップ幅Δを有するカバレッジプロフィールの単調領域（２進探索）
Initialize R(t)：          ∀t：R(t)＝０
t＝t0；    ｛プランニングスタート時点｝
While t  ＜  プランニング範囲（horizont) do begin
｛帰納ステップ｝
R(t+1)＝R(t)；
Generate min cost flow problem F(R) for profile R(t)
｛＝ステップ２｝
If min cost flow (F(R)) solvable
Then Begin              ｛Ｒ（ｔ＋１）  拡大｝
δ：＝Δ；
Repeat                                    ｛２進探索−δ  拡大｝
R(t+1)：＝R(t+1)+δ
δ：＝２＊δ；
Generate min cost flow problem F(R) for profile R(t)
Until min cost flow (F(R)) not solvable
Repeat                      ｛２進探索−δ  縮小化｝
R(t+1)：＝R(t+1)+δ；
δ：δ／２；
Generate min cost flow problem F(R) for profile R(t)
If min cost flow (F(R)) solvable
Then  δ：＝／δ／
Else  δ：＝−／δ／
Until  ／δ／＝Δ；
If min cost flow (F(R)) not solvable
Then R(t+1)：＝R(t+1)-δ
End
Else                              ｛Ｒ  縮小｝
δ：＝Δ；
Repeat                              ｛２進探索−δ  拡大｝
Ｒｍａｘ：＝R(t+1)；
δ：＝２＊δ；
ｔＲ＝ｍｉｎ｛ｔ′／Ｒ（ｔ′）≧Ｒｍａｘ−δ｝
∀ｔ′≧ｔＲ：Ｒ（ｔ′）＝Ｒｍａｘ−δ；
Generate min cost flow problem F(R) for profile
R(t)
Until min cost flow (F(R)) solvable
Repeat                    ｛２進探索−δ  縮小｝
Ｒｍａｘ：＝Ｒ（ｔ＋１）；
δ：＝δ／２；
ｔＲ＝ｍｉｎ｛ｔ′／Ｒ（ｔ′）≧Ｒｍａｘ＋δ｝
∀ｔ′≧ｔＲ：Ｒ（ｔ′）＝Ｒｍａｘ＋δ；
Generate min cost flow problem F(R) for profile R(t)
If min cost flow (F(R)) solvable
Then  δ：＝／δ／
Else  δ：＝−／δ／
Until  ／δ／＝Δ；
If min cost flow (F(R)) not solvable
Then    ∀ｔ′≧ｔＲ：Ｒ（ｔ′）＝Ｒｍａｘ−δ；
End
２．回転するプランニングスキーマの２進探索
回転するプランニングスキーマのアルゴリズムの一層の改善は、先行段落で説明した改善と同様である。カバレッジプロフィールの領域の拡大を考慮する必要はないので、アルゴリズムの第２の部分の拡大を
（”Ｒ縮小”）を挿入すれば十分である。
【０１１４】
ステップ４用のアルゴリズム−回転するプランニングスキーマ
最大輸送時間ｔｍａｘが与えられている。
【０１１５】
２進探索プロセスで、プランニング窓内の最大単調レンジプロフィー
ルＲｍａｘ（ｔ）を求める
Ｉｎｉｔｉａｌｉｚｅ  Ｒ（ｔ）：
∀ｔ≦ｔｍａｘ：  Ｒ（ｔ）＝Ｒｍａｘ（ｔ）
ｔ＞ｔｍａｘ：Ｒ（ｔ）＝Ｒｍａｘ（ｔｍａｘ）；
Ｒｍａｘ：＝Ｒｍａｘ（ｔｍａｘ）
Generate min cost flow problem F(R) for profile R(t)
（＝第２ステップ）
Repeat                          （２進探索−δ  拡大）
Ｒｍａｘ：＝Ｒ（ｔｍａｘ）；
δ：＝２＊δ；
ｔＲ＝ｍｉｎ｛ｔ′／Ｒ（ｔ′）≧Ｒｍａｘ−δ｝
∀ｔ′≧ｔＲ：Ｒ（ｔ′）＝Ｒｍａｘ−δ；
Generate min cost flow problem F(R) for profile R(t)
Until min cost flow (F(R)) solvable
Repeat                        ｛２進探索ステップ幅−δ  縮小｝
Ｒｍａｘ：＝Ｒ（ｔｍａｘ）；
δ：＝δ／２；
ｔＲ＝ｍｉｎ｛（ｔ′／Ｒ（ｔ′））≧（Ｒｍａｘ＋δ）｝
∀ｔ′≧ｔＲ：Ｒ（ｔ′）＝Ｒｍａｘ＋δ；
Generate min cost flow problem F(R) for profile R(t)
If min cost flow problem F(R) solvable
Then  δ：＝／δ／
Else  δ：＝−／δ／
Until  ／δ／＝Δ；
If min cost flow (F(R)) not solvable
Then    ∀ｔ≧ｔｍａｘ：Ｒ（ｔ）：＝Ｒｍａｘ−Δ
End
３．カバレッジプロフィールの単調でない領域用の高速アルゴリズム
達成範囲プロフィール（上の段落Ａ参照）の単調でない領域の最大化用の記述のアルゴリズムは、微細なステップ幅Δが利用された場合、非常に緩慢になることがある。以下、カバレッジプロフィール（上の段落Ｂ参照）の単調な領域用のアルゴリズムを基本モジュールとして利用するアルゴリズムについて提案する。基本的な技術思想は、問題を帰納的に解決する点にある：
１．  達成範囲プロフィールＲｍの最大単調領域の生成。
【０１１６】
２．  達成範囲プロフィールＲの最大領域に対して同じでなければならない、このプロフィールの部分を決定することによる問題の低減。
【０１１７】
３．  全プロフィールが決定されない場合、ステップ１に戻る（そして、残りの部分を解決する）。
【０１１８】
ステップ２に対しては、時間ステップｔを選定する必要があり、その際、
Ｒｍ＜Ｒｍ（ｔ＋１）＝＞Ｒｍ（ｔ）＝Ｒ（ｔ）
即ち、達成範囲プロフィールの最大単調領域の強く単調に上昇する部分を決定することができる。更に、プランニング範囲の終わりも決定することができる：
Ｒｍ（ｔ）（ｐｌａｎｎｉｎｇ ｅｎｄ）＝Ｒ（ｐｌａｎｎｉｎｇ ｅｎｄ）
そのために、プランニング窓が少なくとも１だけ低減することができ（場合によっては、もっと多ければ多い程、所定のように決定した場合には、強く単調に上昇する、Ｒｍの部分を低減することができる）。従って、上述のループを高々Ｔステップ繰り返すことができるようになり、その際、
Ｔ＝ｐｌａｎｎｉｎｇ ｅｎｄ−ｐｌａｎｎｉｎｇ ｓｔａｒｔ（プランニング窓内の時間ステップの数）、即ち、時間の複雑性は、Ｔ＊Ｏ（Ｒｍ）によって制限され、その際、Ｏ（Ｒｍ）は、カバレッジプロフィールの最大単調領域用のアルゴリズムの時間的な複雑性である。アルゴリズムの複雑性は、単調プロフィールに較べて有利には高々ファクタＴだけしか上昇せず、従って、膨大な達成範囲プロフィールを、従来の計算機装置でも計算することができる。
【図面の簡単な説明】
【図１】
簡単な配送ネットワークのグラフ図
【図２】
複雑な配送ネットワークのグラフ図
【図３】
双方向グラフの形式で示した、対応関係問題のグラフ図
【図４】
等しい配送のネットワークのグラフ図
【図５】
種々の可能な対応関係の生産及び需要ノードのグラフ図
【図６】
供給及び需要のある生産プラントを示す図
【図７】
複数の輸送形式を有する配送ネットワークのグラフ図
【図８】
複数の輸送形式を有する最適化された配送ネットワークのグラフ図
【図９】
可能であって最適化もされた輸送区間の流れ図
【図１０】
可能且つ最適化された輸送区間の別の例を示す流れ図
【図１１】
許容されない区間が、配送ネットワーク内の可能な輸送オプションに及ぼす影響を示す図
【図１２】
時間値を弧で示した簡単な配送ネットワークのグラフ図
【図１３】
配送ネットワークの生産及び需要プロフィールのグラフ図
【図１４】
可能な対応関係用のグローバルな領域プロフィールのグラフ図
【図１５】
別の可能な対応関係用のグローバルな領域プロフィール用のグラフ図
【図１６】
単調に最適化された輸送プラン用の例を示す図
【図１７】
最大の単調な領域プロフィールの探索を示す図