(57)【要約】  貨物の最適な輸送のための方法および装置が提供される。この方法は、複数の輸送決定項目を最適化するステップと、１組の最適化された輸送決定項目に従って複数のビークルを移動させることによって貨物を機械的に輸送するステップとを含む。決定項目としては、輸送ビークルに関する輸送ルートおよびスケジュール、輸送ビークルによって１つまたは複数の需要地点に輸送すべき貨物の配分、１つまたは複数の供給地点からの輸送ビークルによる荷積みのノミネーション、特殊化された輸送地点の使用、および各輸送ビークルに関するビークル割当てが挙げられる。決定項目の組は、様々な輸送決定項目に関係するデータを収集し、収集されたデータを混合整数線形計画モデルの一部として使用し、１組の最適化された輸送決定項目を見出すためにモデルに対する解を得ることによって最適化される。
2012526326.tif 000002
【特許請求の範囲】
【請求項１】
ばら荷を輸送するための方法であって、
（Ｉ）データセットを受信するステップであって、前記データセットが、
（ａ）複数の供給地点および複数の需要地点の識別と、
（ｂ）各供給地点に関する、その物理的位置およびばら荷の使用可能性に関係する情報と、
（ｃ）各需要地点に関する、その物理的位置およびばら荷の要件に関係する情報と、
（ｄ）前記供給地点から前記需要地点にばら荷を輸送するためのビークルの集団の識別、および各ビークルの使用可能性、コスト、および容量に関係する情報と、
（ｅ）各タイプのばら荷に関する、その潜在的な性質に照らした前記タイプのばら荷の経済的価値に関係する情報と、
（ｆ）前記ばら荷を輸送するコストに関係する情報と、
を含むステップと、
（ＩＩ）純益に関する目的関数と、複数の制約とを含む数学モデルを作成するステップであって、
前記目的関数が、供給ノミネーションパラメータ、前記需要地点での前記要件に対するばら荷の供給の配分、および前記供給地点と前記需要地点の間での前記ビークルの航路に関係する決定変数を含むステップと、
（ＩＩＩ）前記データセットからのデータ、または前記データセットからのデータを用いて計算されたパラメータを数学モデルに投入するステップと、
（ＩＶ）前記数学モデルに対する１つまたは複数の解を得るステップと、
（Ｖ）前記数学モデルに対する解に基づいて前記ばら荷を物理的に輸送するステップと、
を含む方法。
【請求項２】
供給ノミネーションパラメータに関係する前記決定変数が、ノミネートすべきばら荷のタイプ、ノミネートすべきばら荷の体積、および供給地点で前記ばら荷を船積するためのスケジュールに関する前記決定変数を含む請求項１に記載の方法。
【請求項３】
ばら荷の供給の配分に関係する前記決定変数が、各前記需要地点での前記ばら荷の荷揚体積に関係する決定変数を含む請求項１に記載の方法。
【請求項４】
前記ビークルの航路に関係する前記決定変数が、前記航路へのビークルの割当て、ならびに各ビークルに関する供給地点と需要地点への寄港の順序、船積、および荷揚に関係する決定変数を含む請求項１に記載の方法。
【請求項５】
前記供給地点での前記ばら荷の使用可能性に関係する前記情報が、使用可能なばら荷のタイプ、使用可能なばら荷の体積、およびばら荷の時間的な使用可能性に関係する情報を含む請求項１に記載の方法。
【請求項６】
前記需要地点での前記ばら荷の要件に関係する前記情報が、需要地点の隔離区域、各隔離区域に関して許容できるばら荷のタイプ、各隔離区域の在庫容量、各隔離区域の処理速度、必要なばら荷のタイプ、許容値を含む必要なばら荷の体積、およびばら荷配送のための時間的な要件に関係する情報を含む請求項１に記載の方法。
【請求項７】
前記ビークルの使用可能性に関係する前記情報が、前記ビークルの時間的な使用可能性および物理的位置を含む請求項１に記載の方法。
【請求項８】
前記データセットが、
供給地点、需要地点、または航路でのビークル制限に関係する情報と、
ビークルの速度および燃料消費に関係する情報と、
ビークルコストに関係する情報と、
地理的領域への供給地点および需要地点の分類に関係する情報と、
各供給地点および需要地点に関する限度に関係する情報と、
各供給地点および需要地点に関する使用料または関税に関係する情報と、
航路使用料、関税、または通行料に関係する情報と、
運賃に関係する情報と、
走航距離に関係する情報と、
のうちの１つまたは複数をさらに含む請求項１に記載の方法。
【請求項９】
前記データセットが、
スポット用船コストおよび期間用船コストに関係する情報と、
各供給地点および需要地点に関する喫水限度、貨物限度、および錨地限度に関係する情報と、
運河通行料に関係する情報と、
ドロップアンドピックまたは再梱包使用料に関係する情報と、
パイプラインコストに関係する情報と
のうちの１つまたは複数をさらに備える請求項８に記載の方法。
【請求項１０】
前記数学モデルに関する前記制約が、前記需要地点での処理制限に関係する制約を含む請求項１に記載の方法。
【請求項１１】
処理制限に関係する前記制約が、ブレンド仕様またはブレンドダウン比率に関する制約を含む請求項１０に記載の方法。
【請求項１２】
前記数学モデルに関する前記制約が、供給ノミネーションのレータビリティを含む請求項１に記載の方法。
【請求項１３】
前記データセットが、地理的領域への前記需要地点の分類に関係する情報を含み、ＭＩＰモデルに関する前記制約が、各地理的領域に関して、前記ビークルによって配送されるべきまたは前記領域で保持されるべき貨物の最小量または最大量に関係する要件を含む請求項１に記載の方法。
【請求項１４】
前記数学モデルが混合整数計画モデルである請求項１に記載の方法。
【請求項１５】
前記混合整数計画モデルが混合整数線形計画モデルである請求項１に記載の方法。
【請求項１６】
前記数学モデルに対する１つまたは複数の解を得るステップが、
前記数学モデルの制約の１つまたは複数のグループを除去することによって第１の解を得るステップと、
前記数学モデルの下位問題を解くことによって第２の解を得るステップとを含み、前記下位問題において、前記第１の解に基づいて前記数学モデルの１つまたは複数の決定変数が一定に保たれている、または排除されている、
請求項１に記載の方法。
【請求項１７】
前記数学モデルに関する前記制約が、在庫制約およびブレンド制約を含み、前記第１の解が、前記在庫制約、前記ブレンド制約、またはそれら両方を無視することによって得られる請求項１６に記載の方法。
【請求項１８】
前記数学モデルに対する１つまたは複数の解を得るステップが、
初期許容解として前記第２の解を使用して、局所探索発見的技法（ｌｏｃａｌ  ｓｅａｒｃｈ  ｈｅｕｒｉｓｔｉｃ）によって第３の解を得るステップと、
前記数学モデルに関する解探索空間を縮小することによって第４の解を得るステップと
をさらに含む請求項１６に記載の方法。
【請求項１９】
前記第２の解が構成発見的技法によって得られ、前記第３の解が改良発見的技法によって得られ、前記第４の解が解探索空間縮小によって得られる請求項１８に記載の方法。
【請求項２０】
前記第１の解が前記目的関数値に関する上限であり、前記第２の解が前記目的関数値に関する下限である請求項１６に記載の方法。
【請求項２１】
前記第１の解が、選択された１組の航路の決定を含み、前記第２の解が、選択されなかった航路に関係する決定変数が無視された前記数学モデルの下位問題を解くことによって得られる請求項１６に記載の方法。
【請求項２２】
（Ｉ）データファイルを記憶するメモリデバイスであって、前記データファイルが、
（ａ）複数の供給地点および複数の需要地点の識別と、
（ｂ）各供給地点に関する、その物理的位置およびばら荷の使用可能性に関係する情報と、
（ｃ）各需要地点に関する、その物理的位置およびばら荷の要件に関係する情報と、
（ｄ）前記供給地点から前記需要地点にばら荷を輸送するためのビークルの集団の識別、および各ビークルの使用可能性、コスト、および容量に関係する情報と、
（ｅ）各タイプのばら荷に関する、前記タイプのばら荷の経済的価値に関係する情報と、
（ｆ）前記ばら荷を輸送するコストに関係する情報と、
を含むメモリデバイスと、
（ＩＩ）純益に関する目的関数と、複数の制約とを含む数学モデルにデータを投入するためにコンピュータ装置によって実行可能なモデリングアプリケーションであって、
前記目的関数が、供給ノミネーションパラメータ、需要地点での要求に対するばら荷の供給の配分、および前記供給地点と前記需要地点の間の前記ビークルの航路に関係する決定変数を含むモデリングアプリケーションと、
（ＩＩＩ）前記数学モデルに対する１つまたは複数の解を得るために前記コンピュータ装置によって動作可能なソルバと、
を備えるコンピュータ装置。
【請求項２３】
前記数学モデルに対する解に基づいた出力を表示するためのディスプレイをさらに備える請求項２２に記載のコンピュータ装置。
【請求項２４】
ばら荷の輸送を決定するための方法ステップを行うためにコンピュータによって実行可能な命令のプログラムを含む一時的でないコンピュータ可読記憶媒体であって、前記方法ステップが、
（Ｉ）データファイルを読み取るステップであって、前記データファイルが、
（ａ）複数の供給地点および複数の需要地点の識別と、
（ｂ）各供給地点に関する、その物理的位置およびばら荷の使用可能性に関係する情報と、
（ｃ）各需要地点に関する、その物理的位置およびばら荷の要件に関係する情報と、
（ｄ）前記供給地点から前記需要地点にばら荷を輸送するためのビークルの集団の識別、および各ビークルの使用可能性、コスト、および容量に関係する情報と、
（ｅ）各タイプのばら荷に関する、前記タイプのばら荷の経済的価値に関係する情報と、
（ｆ）前記ばら荷を輸送するコストに関係する情報と、
を含むステップと、
（ＩＩ）純益に関する目的関数と、複数の制約とを含む数学モデルにデータを投入するために前記データファイルを使用するステップであって、
前記目的関数が、供給ノミネーションパラメータ、前記需要地点での要求に対するばら荷の供給の配分、および前記供給地点と前記需要地点の間での前記ビークルの航路に関係する決定変数を含むステップと、
（ＩＩＩ）前記数学モデルに対する１つまたは複数の解を得るステップと、
を含む一時的でないコンピュータ可読記憶媒体。
【請求項２５】
前記方法ステップが、前記数学モデルに対する解に基づいて出力を生成するステップをさらに含む請求項２４に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
１．０  発明の背景
１．１  関連出願の相互参照
本出願は、全体を参照により本明細書に援用する米国仮特許出願第６１／１７５７１８号（２００９年５月５日出願）の利益を特許請求するものである。また、本出願は、２００８年１０月１２日出願の「Ｓｙｓｔｅｍ  ｆｏｒ  Ｏｐｔｉｍｉｚｉｎｇ  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｓｃｈｅｄｕｌｉｎｇ」という名称の米国特許出願第１２／２８５６５１号に関連し、この出願はまた、２００７年１１月６日出願の同一名称の米国仮特許出願第６０／９９６１８８号に関連する。また、本出願は、「Ｓｙｓｔｅｍ  ｆｏｒ  Ｏｐｔｉｍｉｚｉｎｇ  Ｂｕｌｋ  Ａｌｌｏｃａｔｉｏｎ，  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  ａｎｄ  Ｂｌｅｎｄｉｎｇ」という名称の２００８年１１月２１日出願の米国特許出願第１２／２９２６００号に関連し、この出願は、２００７年１２月２１日出願の同一名称の米国仮特許出願第６１／００８５８１号に関連する。これらの各出願の全体を参照により本明細書に援用する。
【０００２】
１．２  発明の分野
本発明は、複数の輸送ビークルに関する最適化された輸送方式を決定し、前記方式に従ってビークルを移動させるための方法を対象とする。また、本発明は、最適化された１組の輸送決定項目を求めるための装置を対象とする。より詳細には、本発明は、１つまたは複数のばら荷を含む貨物を輸送するための１組の航路を決定し、所与の計画期間中に航海を行うことができるように使用可能な集団内のビークルを割り当てることによって貨物船積および配送プログラムに関する総純利益を最大にするために、最適解を求めることを対象とする。
【背景技術】
【０００３】
１．３  関連技術の説明
海上輸送は、油およびガス産業を含む多くの産業にとって重要な一態様である。海上輸送は、長距離にわたってばら荷（例えば、原油などのばら積み液体）を搬送するのに経済的に魅力的な手段である。したがって、日々、大容積のばら荷が、供給源地点と仕向先地点の間で多様な船によって海洋を渡って運ばれている。仕向港（例えば製油所敷地）は、地理的に世界中にちらばっていることがあり、必要とされるばら荷（例えば原油）の供給源から遠く離れていることも多い。距離が長いので、輸送費がかなり大きくなる。例えば、２００８年には、ある主要企業の海上活動に、３０，０００の航路が含まれ、運賃が総計で約５０億ドルであった。さらに、運送の選択肢の数が多く、しかも、その選択肢はいかなる時も輸送する必要がある材料の量、輸送に関する時間的制限、使用可能な船および関連の港の物理的制限、船契約条項および条件などに応じて変化するという点で、海上輸送の実務環境は複雑であり動的である。したがって、海上輸送スケジューリング決定も複雑であり動的である。
【０００４】
船輸送決定を下すために従来より商業的に行われているのは、使用可能な選択肢の手動分析の実施である。熟練した人員が、航路制約を計算し、経済的な兼ね合いを推定し、適時に航海イベントを進め、可能性のある意思決定を評価する。また、そのような人員は、許容できる貨物輸送（すなわちリフティング）プログラムを開発するために、発見的技法、事業規則およびガイドライン、さらには直観に頼ることもある。この方法は、時間がかかり、完璧ではなく、選択されたリフティングプログラムが最適なものであるかどうかを知るための現実的な方法はない。実現可能な航路、スケジュール、および船／航路の割当てが典型的には多数あることを前提とすると、１度に１つの航路（または１つの船）を人が考えることによって最適なリフティングプログラムを見つけ出すことは、不可能ではないにせよ非常に難しい。この難しさは、様々な割当て決定の相互作用により、さらに複雑になる（例えば、所与の船が所与の航路に割り当てられた場合、その船は、それと同時並行の１つまたは複数の別の航路には使用可能できない）。相互作用の数、可能性のある決定項目の数、および重要な因子の数は、熟練したスケジュール管理者でさえ、人の手では（特に事業決定を行うのに許容できる時間内では）完全に最適化できないほど複雑である。この問題は、所与の船に割り当てることができる１つまたは複数の航路の順序を考慮することを試みるとき、さらに複雑になる。さらに、人の手で導き出された航路とスケジュールの組が完成した後、日々生じることがある実務環境の変化を反映させるためにスケジューリングプロセスを頻繁に繰り返すことは実用的でなく、また、複数の異なるシナリオを実行して、特定の制約がリフティングプログラム全体に及ぼすことがある影響を試験することも実用的でない。
【０００５】
ＴｕｒｂｏＲｏｕｔｅｒ（登録商標）は、Ｎｅｒｗｅｇｉａｎ  Ｍａｒｉｎｅ  Ｔｅｃｈｎｏｌｏｇｙ  Ｒｅｓｅａｒｃｈ  Ｉｎｓｔｉｔｕｔｅ，ＭＡＲＩＮＴＥＫ  Ｌｏｇｉｓｔｉｃｓによって近年開発されたツールであり、船経路決定およびスケジューリング計算を行う。しかし、このツールは、最適化手法よりは発見的手法に基づいている。さらに、このツールの目的は、用船側や貨物所有者ではなく、運送業者が、運送しなければならない契約貨物の他に任意選択の貨物を運送することによって得られる収益を最大にできるようにすることである。
【０００６】
船舶経路決定およびスケジューリングの分野において多数の刊行物がある。１つの調査記事は、非特許文献１（全体を参照により本明細書に援用する）である。１つの概要的な記事は、非特許文献２（全体を参照により本明細書に援用する）である。
【０００７】
注目すべき１つの刊行物は、非特許文献３（全体を参照によって本明細書に援用する）である。この論文は、原油海上輸送の問題に対処する。しかし、そこに述べられているモデリングの問題は、以下の仮定／単純化を含む。（１）各貨物（すなわち運送すべき原油）が、単一の船積港と単一の荷揚港の間を移動する。（２）運送される貨物は、常に満載でなければならない（すなわち貨物は一定サイズでなければならない）。（３）各船は同じサイズである。さらに、モデルの目的関数は、純利益（すなわち、収益または価格−コスト）を最大にすることではなくコストを最小にすることである。
【０００８】
注目すべき別の刊行物は、非特許文献４（全体を参照により本明細書に援用する）である。この論文も、原油海上輸送モデリング問題に対処する。ここでも、モデリング問題の特徴は、各航路が単一の船積港と単一の荷揚港からならなければならず、各貨物が満載でなければならないというものである。さらに、目的は、純利益を最大にすることではなくコストを最小にすることである。この論文で対処される問題は、船舶が同じサイズである必要はなく、船コンパートメントの明確な取扱いがあるという点で、先の論文とは異なる。
【０００９】
上の文献はどれも、全般的な船経路決定、スケジューリング、および割当ての実務上の問題の特徴および／または制約を表す海上輸送方式を提供しない。例えば、典型的な船スケジューリング問題では、各航路は複数の船積港と複数の荷揚港からなり、吊上げられる貨物は重量および／または体積が異なることがあり、航海を行うのに使用可能な船は、限定はしないが容量および用船タイプ（例えばスポット用船および期間用船）を含めた多くの点で異なることがある。
【００１０】
さらに、上の文献はどれも、単にコストを最小にするのではなく、輸送方式に関する総純利益を最適に最大にする海上輸送プログラムを提供しない。コスト最小化手法だけでは、最適な結果を常には提供できないことがある。なぜなら、そのような手法は、船の割当ての決定の経済的影響を正確には表さず、期間用船の使用とスポット用船の使用との兼ね合いを適切には反映せず、長期および短期の航海を一貫しては評価しないからである。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Ｍ．Ｃｈｒｉｓｔｉａｎｓｅｎ，Ｋ．ＦａｇｅｒｈｏｌｔおよびＤ．Ｒｏｎｅｎ著「Ｓｈｉｐ  ｒｏｕｔｉｎｇ  ａｎｄ  ｓｃｈｅｄｕｌｉｎｇ：ｓｔａｔｕｓ  ａｎｄ  ｐｅｒｓｐｅｃｔｉｖｅｓ」Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｓｃｉｅｎｃｅ，３８（１）：１〜１８，（２００４年）
【非特許文献２】Ｍ．Ｃｈｒｉｓｔｉａｎｓｅｎ，Ｋ．Ｆａｇｅｒｈｏｌｔ，Ｂ．Ｎｙｇｒｅｅｎ，Ｄ．Ｒｏｎｅｎ著、Ｃ．ＢａｒｎｈａｒｔおよびＧ．Ｌａｐｏｒｔｅ編「Ｍａｒｉｎｅ  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ」Ｈａｎｄｂｏｏｋｓ  ｉｎ  Ｏｐｅｒａｔｉｏｎｓ  Ｒｅｓｅａｒｃｈ  ａｎｄ  Ｍａｎａｇｅｍｅｎｔ  Ｓｃｉｅｎｃｅ：Ｔｒａｎｓｐｏｒｔａｔｉｏｎ，（２００５年）
【非特許文献３】Ｇ．Ｇ．Ｂｒｏｗｎ，Ｇ．Ｗ．Ｇｒａｖｅｓ，Ｄ．Ｒｏｎｅｎ著「Ｓｃｈｅｄｕｌｉｎｇ  Ｏｃｅａｎ  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  ｏｆ  Ｃｒｕｄｅ  Ｏｉｌ」Ｍａｎａｇｅｍｅｎｔ  Ｓｃｉｅｎｃｅ，３３（３）：３３５−３４６（１９８７年）
【非特許文献４】Ｈ．Ｄ．Ｓｈｅｒａｌｉ，Ｓ．Ｍ．Ａｌ−Ｙａｋｏｏｂ，Ｍ．Ｍ．Ｈａｓｓａｎ著「Ｆｌｅｅｔ  ｍａｎａｇｅｍｅｎｔ  ｍｏｄｅｌｓ  ａｎｄ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ａｎ  ｏｉｌ  ｔａｎｋｅｒ  ｒｏｕｔｉｎｇ  ａｎｄ  ｓｃｈｅｄｕｌｉｎｇ  ｐｒｏｂｌｅｍ」ＩＩＥ  Ｔｒａｎｓ．３１：３９５−４０６（１９９９年）
【発明の概要】
【課題を解決するための手段】
【００１２】
したがって、以下に記載するように、新規の方法は、最適な輸送経路決定、貨物配分、スケジューリング、および割当て決定を求め、それらの決定に従ってビークル集団を移動させるために開発された。この方法は、一般的なスケジューリング問題の特徴および制約を反映しながら、１つまたは複数のばら荷を含む貨物を輸送するための１組の航路を決定し、航海を行うために使用可能な集団内のビークルを割り当てることによって、貨物船積および配送プログラムに関する総純利益を最大にするために最適解を求めることである。そのような最適化法は、単に海上運送業の域を超えて意味を持っており、陸上輸送（例えばトラック業）および航空輸送にも同様に適用可能である。
【００１３】
２．０  図面の簡単な説明
本発明は、以下に与える詳細な説明および添付図面からより完全に理解される。図面は単に例示として与えるものである。したがって、これらの図面は本発明を限定するものではない。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施形態における、様々なインターフェースおよび計算エンジンを有するユーザとモデリングアプリケーションの間の対話の例示的な図である。
【図２】本発明の特定の実施形態による装置の機能の一部を示す図である。
【図３】本発明の特定の実施形態による１組の最適化された輸送決定項目に従って貨物を移動させるための方法に関連するステップを示す図である。
【発明を実施するための形態】
【００１５】
詳細な図面は例示の目的でのみ示す。様々な例示的なスプレッドシートに記載される特定のデータは、仮定に基づいているが代表的なスケジューリング問題に関する仮定に基づいているが代表的なデータである。したがって、そこから導き出される結果も同様に仮定に基づいているが代表的な結果である。
【００１６】
３．０  発明の概要
本発明は、様々な地点に、および様々な地点から貨物を輸送する複数の輸送ビークルに関する輸送スケジュールに関連する様々な決定項目を最適化し、最適化された決定項目に従って複数の輸送ビークルを移動させるための方法を提供する。より特定的には、決定項目として、輸送ルート（すなわち航路）、輸送ルートが実行されるタイミングおよび順序、スケジュールに従って各ルートを取るように割り当てられた船舶、設定されたパラメータ範囲内での荷積みおよび配送のタイプおよび量が挙げられる。この最適化法を実施することができる装置も提供される。この方法は、海上輸送の分野で特に有益であるが、陸上輸送または航空輸送での貨物の運搬に関する分野など任意の既知の輸送分野に適用することができる。船舶を使用するばら貨物の輸送に関係する特定の実施形態では、最適化すべき様々な決定項目として、供給ノミネーション（供給体積、ばら荷の等級、および日付を含む）、隔離要件を満たすための使用可能な供給の配分、複数のビークルにおける各船に関する輸送ルート（すなわち航路）、ならびに再梱包、ドロップアンドピック、および必要に応じてパイプラインの考慮を組み込む様々な運河（スエズ運河など）の使用が挙げられる。
【００１７】
この方法は、輸送決定項目を最適化することを含み、輸送決定項目としては、複数のビークルに関する輸送ルート、貨物に関する需要配分、貨物の供給ノミネーション、および特殊化された輸送選択肢の考慮が挙げられる。さらに、この方法は、最適化された輸送決定項目に従って複数のビークルを移動させることを含む。最適化は、ビークルで貨物を輸送する総純利益を最大にするように、ビークルを輸送するコストを最小にするように、またはなんらかの他の目的関数を最適化するように行うことができる。輸送決定項目を最適化する方法は、（１）複数の供給地点、複数の需要地点、複数の輸送ビークル、輸送すべき貨物、輸送情報、および他のユーザ定義された制約に関係するデータを収集するステップと、（２）純利益を最大にするため（または発生コストを最小にするため）の目的関数と、データに基づく複数の制約とを備える混合整数線形計画モデルの一部としてデータを使用するステップと、（３）混合整数線形計画モデルに対する１つまたは複数の解を得るステップとを含む。さらに、方法は、最適化された輸送の解に従って複数のビークルを移動させるステップを含む。
【００１８】
この方法は、取るべき最適なルートを決定し、また、最適化された各輸送ルートに関して、各ビークルがルート内で取る停泊地（例えば、供給／需要地点、運河、給油地など）、各供給停泊地で船積される貨物の量およびタイプ、各需要停泊地で荷揚される貨物の量およびタイプ、貨物の船積／荷揚に関するスケジュール、推定される運賃、航路に割り当てられる特定のビークルを決定する。さらに、この方法は、各需要地点での貨物の各グループに関して、配送時の在庫プロファイルおよび他の制限する制約（例えば、提案されたばら貨物のブレンド比率が挙げられる）を決定することがある。特定の実施形態では、上の決定は、コンピュータアプリケーションを使用して行われ、例えばグラフィカルユーザインターフェース（ＧＵＩ）やスプレッドシートを介してユーザに表示される。
【００１９】
また、この方法は、実行されるべき１組の航路の決定、および航海を行うための使用可能な集団内のビークルの割当てに関する総純利益を最大にするために最適解を求めることができる。あるいは、最適解は、発生コストの最小化に基づいて決定することができる。１組の航路における各航路は、計画期間中に開始され、様々なビークルが１つまたは複数の供給地点（例えば船積港）から１つまたは複数の需要地点（例えば荷揚港）に貨物を輸送する方法を正確に表す。一実施形態では、各ビークルは、サイズ、形状、容量、コスト、および用船タイプ（例えば期間用船かスポット用船か）が異なることがある。
【００２０】
この方法は、実現可能な選択肢、ならびに最適な輸送経路決定、スケジュール、およびビークル／航路の割当てを決定する際に、予測される最高の総純利益を生み出す（あるいはその代わりに最小の総計の発生コストを生み出す）ように複数の入力パラメータを考慮する。考慮することができる典型的な決定項目としては、限定はしないが以下のものが挙げられる。（１）供給地点および（２）需要地点（例えば港）。これらは、様々な物理的制限（例えば最大喫水、最大船長および幅など）、コスト（例えば港使用料）、物理的位置、レータビリティ（ｒａｔａｂｉｌｉｔｙ）要件、荷積み／配送タイミング窓（例えばリフティングキャンセル期限）、貨物の処理／消費速度、貨物タイプ要件／使用可能性（例えば原油等級および／またはブレンド比率の制限）、および最小／最大在庫制限を含むことがある。（３）使用可能な集団内の各ビークルの特定の特徴（例えば喫水、船積／バラスト速度、燃料消費速度、ビークル地点、積載容量、および他のパラメータ）。これらは、航路中の供給地点および需要地点の制約をビークルが満たすことができるかどうかを決定する。（４）運搬される貨物の様々なタイプ（例えば様々な等級の原油）、およびそれらの体積、密度、または他の特性。（５）様々な輸送特性、例えば、様々な地点間の距離、特別なルートの使用可能性（例えばドロップアンドピックおよび再梱包能力を備えることがある運河）、通行料、フラットレート、および燃料費。好ましくは、純利益または発生コストにそれなりの影響を与える全ての問題の特徴（例えば入力パラメータ）が考慮される。
【００２１】
この方法は、入力データの感度、仮定、および割当ての制約を調べるために複数回実行することができる。例えば、ユーザは、所与の航路への所与のビークルの割当てをモデルに行わせて、得られた割当てを使用してビークルスケジュールを最適化し直すことができる。これは、既に下されている決定を表すのに、またはビークルの割当てを行う影響を分析するのに有利であることがある。
【００２２】
アプリケーションは、動的な実務環境での機会を評価するのに十分に迅速に、かつ仮説シナリオ（ｗｈａｔ−ｉｆ  ｓｃｅｎａｒｉｏｓ）をサポートするのに十分に迅速に動作する。一実施形態では、アプリケーションは、妨害されない３ＧＨｚのデュアルコアパーソナルコンピュータ上で動作し、典型的な問題に関する計算を約３０〜４５分間で行う。
【００２３】
４．０  詳細な説明
４．１  定義
本明細書における全ての用語は、それらの最も広い従来の意味合いを有するものと意図される。さらに明解にするために、本明細書で使用するいくつかの用語の従来の意味を以下に記載する。
【００２４】
「配分」は、既存の制約および制限を満たしながら、なんらかの嗜好（例えば経済的なもの）に基づいて仕向先の要件を満たすように、使用可能な貨物を様々な需要地点に割り当てることを意味する。
【００２５】
「ブレンド比率」は、単一のビークルで配送されるときに需要地点の隔離区域（例えば港の隔離区域）が許容できる、ばら荷（例えば原油）のいくつかの供給等級の混合（またはブレンド）を制限する１組の制約を表す。
【００２６】
「ばら荷」は、船積されたときに拘束されていない、実質的には流体の任意の材料を意味する。すなわち、これは、ばらの梱包されていない状態である。ばら荷の例は、石炭、穀物、および石油生成物である。
【００２７】
「貨物」は、ビークルによって輸送される任意の製品または材料を意味する。好ましい一実施形態では、貨物は、原油などのばら荷である。
【００２８】
「コード」は、ソースコードとオブジェクトコードの両方を包含する。
【００２９】
「規定ストック義務（ＣＳＯ）」は、典型的には、指定される地理的領域内で維持すべき貨物（および／または等価の製品）の特定の最小体積を命じる法律を指す。例えば、法定義務体積（ＬＯＶ）が日本でのＣＳＯであり、これは、陸上での、または日本の領海内でのばら荷の総体積に基づいて計算される。類似の法律または規制上の義務は、海上、陸上、航空での運送における他の輸送点についても存在することがある。本明細書で使用するとき、ＣＳＯは、これらの類似のプロセスも包含するものとする。
【００３０】
「需要地点」は、輸送された貨物が受け取られる場所を意味する。「荷揚」、「需要」、「受取り」、および「仕向先」地点または場所（港など）が、本明細書では交換可能に使用される。
【００３１】
「荷揚プログラム」は、荷揚活動（すなわち、需要地点への貨物の配送）に関するスケジュールを表し、所与の期間（例えば１か月）にわたって計画される多くの荷揚活動に関する一連のビークル、需要地点、荷揚仕向先、貨物のタイプ、貨物の荷揚体積、荷揚日を含む。特定の実施形態では、「荷揚仕向先」は、各需要地点でのばら荷の隔離区域である。
【００３２】
「ドロップアンドピック」は、本発明の海上輸送用途の文脈で生じる。特定のクラスの船舶（例えば、超大型原油タンカー（ＶＬＣＣ））などの船舶）は、貨物を満杯に船積した状態では、特定の運河（例えばスエズ運河）を通って進むことができない。ドロップアンドピック（Ｄ＆Ｐ）は、船舶が運河を通過できるように、運河に入る前に（例えば紅海ではアイン・スクナ（Ａｉｎ  Ｓｕｋｈｎａ）で）十分な貨物を積み卸ろすことからなる。運河を通過した後、船舶は、ドロップポイントで荷揚した量と同じ（またはそれよりも多い）量を船積する。同様のプロセスは、海上運搬用に使用される他の運河、または他の陸上または航空での運送に関する輸送点でもありえる。本明細書で使用するとき、Ｄ＆Ｐは、これらの類似のプロセスも包含するものとする。
【００３３】
「外部供給」は、船積プログラムに含まれていなかった（例えば需要地点での）荷揚の在庫の影響を表して含めることができる能力を意味する。この手法は、地域的な、または局地での貨物供給を表すために使用することができるが、そのような使用だけに制限されるものではない。
【００３４】
「集団」は、２つ以上のビークルのグループを意味する。集団は、同種（すなわちただ１つのビークルタイプを含む）でも異種（すなわち２つ以上の異なるビークルタイプを含む）でもよい。
【００３５】
「等級交換（Ｇｒａｄｅ  Ｓｗａｐ）」は、需要地点（例えば需要港）での何らかの隔離に関する要件を満たすように、要求された等級ではなく、代用の等級の原油を配送することに関わる。サブステーションが、元々必要とされていたのとは異なる体積または重量を必要とすることがあること、およびそれに従って、代用の原油等級に関する収益または価格が、何らかのペナルティまたはインセンティブによって調整されることがあることが予想される。
【００３６】
「船積プログラム」は、船積活動（すなわち供給地点での貨物の船積）に関するスケジュールを表し、所与の期間（例えば１か月）にわたって計画される複数の船積活動に関する一連のビークル、供給地点、貨物タイプ、貨物の船積体積、および船積日を含む。
【００３７】
「純利益」は、収益から発生コストを引いた値である。
【００３８】
「ノミネーションプログラム」は、需要地点への配送のために様々な輸送ビークルに貨物を供給するためのスケジュールを表す。ノミネーションプログラムは、所与の期間（例えば１か月）にわたる多くの供給船積活動に関する供給地点、貨物のタイプ、貨物の船積積、および船積日を含む。
【００３９】
「最適」およびその派生語およびそれらの別の語形および言語的に関連のある語句は、本明細書で使用するとき、本発明が最適解を見出すことまたは最適決定を行うことが必要であるという意味合いの中で、限定する意図のものではない。実際には、数学的に最適な解が、全ての数学的に取り得る可能性の中で最良のものとなり得るが、完璧な解を実際に実現していなくても、最適化ルーチン、方法、モデル、およびプロセスの実世界での実施形態はそのような目標に向かうことがある。したがって、本開示の利益を享受する当業者は、これらの用語が、本発明の文脈ではより大まかなものであることを理解されたい。これらの用語は、使用可能な最良の解、好ましい解、もしくはある制約の範囲の中で特定の利益を提供する解であることがある１つまたは複数の解を求める（例えば２つ以上の解を比較し、少なくとも１つの解の少なくとも一部を選択する）、または継続的に改良する、または洗練する、または目的に対する高い点または最大値を探索する、またはペナルティ関数を減少させるように処理することなどを表すことができる。
【００４０】
「レータビリティ（Ｒａｔａｂｉｌｉｔｙ）」は、１つまたは複数のタイプの貨物の供給がある期間にわたって一定のレートで使用可能であることを表す。海上輸送用途に関するレータビリティ船積プログラムの一例は、（所与の原油等級のばら荷に関して）全期間にわたる１日当たりの平均体積を、期間中に毎日船積するものである。実践上は、レータビリティのより粗い定義が好ましいことが多く、例えば、船積期間の各四半期中に、船積するべき全貨物のほぼ４分の１を船積する。
【００４１】
「再梱包」は、積替え地点（例えばアイン・スクナでのＳＵＭＥＤパイプライン）に貨物の全てまたは一部を積み卸ろし、その地点で、貨物を同じビークル上または別のビークル上に再び船積することができるプロセスを表す。再梱包は、ある構成（例えば体積またはタイプ）の貨物が、ビークルから荷卸された構成とは異なる構成でビークル上に再び船積されるときに行われるものである。海上輸送の文脈での再梱包の非限定的な一例は、以下のようなものである。原油等級Ａのみを搬送する船舶１と、原油等級Ｂのみを搬送する船舶２が、共にアイン・スクナで、それらの貨物の一部を荷揚する。次いで、それらの船舶がスエズ運河を通り、シディ・クリール（Ｓｉｄｉ  Ｋｅｒｉｒ）で貨物を再び船積みし、それにより、両方の船舶が原油等級Ａと等級Ｂの両方を搬送するようになる。第２の例は、以下のようなものである。船舶３が原油等級Ｃを搬送しており、船舶４が原油等級Ｄを搬送している。両方の船舶が、アイン・スクナで（完全に）荷揚する。船舶５が、船舶３からの貨物の一部と船舶４からの貨物の一部をシディ・クリールで再び船積する。船舶６が原油等級Ｅを搬送しており、アイン・スクナで貨物を荷揚する。船舶７および船舶８（より小さい船舶）が、シディ・クリールで船舶６からの貨物を再び船積する。類似のプロセスは、海上運送に関して使用される他の積替え地点で、または陸上または航空での運送に関する他の輸送地点でもあり得る。再梱包は、本明細書で使用するとき、これらの類似のプロセスも包含するものとする。このプロセスは、以下のような点でドロップアンドピック（上述）とは異なる。同じビークルが、（例えばスエズ運河を通過できるように）荷揚したのと同じ貨物を船積するとき、これは、再梱包なしのドラップアンドピックである。しかし、ビークルから荷揚した貨物と異なる貨物の組合せがビークル上に船積されるとき、これを再梱包と呼ぶ。類似のタイプのプロセスは、海上運送のために使用される他のパイプライン、運河、もしくは他の積替え地点で、または他の運送業に関する他の特別な輸送地点であり得る。
【００４２】
「要件」は、需要地点での特定の隔離区域に対して指定された時間窓（または計画期間中の任意の時間）中に配送しなければならない所与の下限および／または上限許容値を伴う、１つまたは複数のタイプ（例えば、ばら荷の等級）および関連の量（例えば体積）の仕様を意味する。一般に、要件は、需要地点に関するものであることがあり、または（より具体的に、かつ好ましくは）需要地点での特定の隔離区域に関するものであることがある。
【００４３】
「スポット用船」は、典型的には１つの航路に関して用船される船である。特定の実施形態では、語句「スポット用船」はまた、同様の短期の使用可能性がある任意の船を包含することもある。
【００４４】
「供給地点」は、輸送のために貨物が得られる場所を意味する。「船積」、「供給」、および「出発」地点または場所（例えば港）が、本明細書では交換可能に使用される。
【００４５】
「期間用船」は、規定の期間にわたって用船される船である。特定の実施形態では、語句「期間用船」はまた、同様の長期の使用可能性がある任意の船を包含することもある（例えば、完全にまたは一部所有されている船、定期用船、裸用船など）。
【００４６】
「輸送方式」は、１つまたは複数の供給地点から１つまたは複数の需要地点に貨物を輸送するための詳細な全般的な計画を表す。この方式は、貨物の荷積みおよび荷下しのタイミング、荷積みまたは荷下しすべき貨物の量およびタイプ、特別な輸送地点の使用（例えばスエズ運河などの運河）、および特定の荷積みおよび荷下し作業へのビークルの割当てなどの情報を含む。本発明の１つの目的は、最適な輸送方式を見出すために、これらおよび他の輸送決定項目を最適化することである。
【００４７】
「タイプ」は、貨物のタイプの文脈では、貨物内に含まれる製品または材料など、貨物の性質または構成を定義する。例えば、ばら荷の輸送では、タイプは原油の等級を表すことがある。
【００４８】
「ビークル」は、任意の船舶、バージ船、航空機、電車、トラック、または任意の他の機械的な輸送手段を意味する。
【００４９】
「船」は、任意の船舶、バージ船、または他の水上ビークル（ｗａｔｅｒ−ｆａｒｉｎｇ  ｖｅｈｉｃｌｅ）を意味する。
【００５０】
「航路」は、陸、海、空に関わらず、２つ以上の点間の任意の進行経路または通過経路を意味する。用語「航路」、「ルート」、および「輸送ルート」が、本明細書で交換可能に使用される。
【００５１】
４．２  モデルの目的、入力、および出力
本発明による方法は、最適解またはほぼ最適な解を得るために複数の輸送決定項目を最適化するステップと、１組の最適化された輸送決定項目に従って複数の輸送ビークルを移動させることによって貨物を機械的に輸送するステップとを含む。最適化すべき複数の輸送決定項目は、複数の輸送ビークルに関する輸送ルートと、設定パラメータ範囲内での、複数の輸送ビークルによって１つまたは複数の需要地点に輸送すべき貨物の配分と、設定パラメータ範囲内での、複数の輸送ビークルによる１つまたは複数の供給地点からの荷積みのノミネーションと、特別な輸送地点の使用と、複数のビークルそれぞれに関するビークル割当てとを含む。
【００５２】
最適化ステップは、データを収集するステップと、収集されたデータを混合整数線形計画モデルの一部として使用するステップと、１組の最適化された輸送決定項目を見出すために混合整数線形計画モデルに対する解を得るステップとを含む。収集ステップは、供給地点、需要地点、輸送ビークル、輸送すべき貨物に関する情報、様々な輸送情報、および追加の制限または制約を収集する。
【００５３】
混合整数線形計画モデルは、目的関数と複数の制約とを含む。目的関数は、計画期間内に特定の輸送方式の純利益を最大にするためのものでよい。あるいは、特定の実施形態では、目的関数は、計画期間内に特定の輸送方式に関して発生コストを最小にすることができる。また、経済的または財務的な問題に関係する他の目的関数を採用することもできる。さらに、混合整数線形計画モデルの制約は、収集ステップから収集されたデータから定式化される。
【００５４】
本明細書では、海上輸送の例（本明細書では「海上実施形態」と呼ぶ）を使用して本発明をより詳細に説明するが、例えば、陸、空、および陸／空／海の組合せでの輸送など、本発明の他の用途もあり得ることは明白である。海上輸送の例の使用は、本発明の範囲または用途を制限するものと解釈すべきではない。当業者には理解されるように、本明細書に記載する方法が、陸上輸送または航空輸送の問題にも適用可能であることは明白である。
【００５５】
４．２．１  例示的実施形態の全般的な目的
本発明の一実施形態（海上実施形態）において、本発明は、海上輸送方式の輸送決定項目を最適化するための方法であり、そのような決定項目は、例えば、供給ノミネーション、使用可能な供給の配分、輸送ルート（すなわち航路）、特殊化された輸送地点の使用（例えばドロップアンドピックまたは再梱包能力のあるスエズ運河または他の地点）、および様々な船積／荷卸作業へのビークルの割当てである。特定の実施形態では、この方法は、コンピュータアプリケーションを使用して複数の海上ビークル（すなわち船）に関する海上航路を最適化する。このアプリケーションは、実行時に、計画期間中に貨物を移動させるために、使用可能な集団内のビークルの経路決定、スケジューリング、および割当てに関する総純利益を最大にするための最適解を求めるコードを備える。次いで、各航海が、貨物を輸送するために計画期間中に開始される。
【００５６】
この実施形態では、複数の輸送ビークルが、船舶の集団からなることがある。船の集団は異種型でよい。例えば、集団内の各船は、サイズ、形状、貨物搬送容量などが異なることがある。より特定的には、各ビークルの積載容量は、最大載貨体積および最大載貨重量が異なることがある。これは、超大型原油タンカー（ＶＬＣＣ）船など、同じクラス内のビークルに関してさえ当てはまる。さらに、集団は、経済的コストが異なることがある。例えば、集団は、期間用船、所有船、裸用船、スポット用船などの任意の組合せを含むことがある。好ましくは、集団は、期間用船とスポット用船の両方を含む。一実施形態では、集団内の各船は、その用船契約の経済的基礎に関係なく、期間用船またはスポット用船に分類される。この例では、複数の割当てに使用可能な船（例えば、完全所有または一部所有船、定期用船、裸用船など）は、典型的には期間用船に分類され、ただ１つの割当てのために使用可能な船は、典型的にはスポット用船に分類される。あるいは、集団は同種型でよい。
【００５７】
また、この実施形態では、１つまたは複数の供給地点の少なくとも１つが海港（すなわち供給港）である。同様に、１つまたは複数の需要地点の少なくとも１つが海港（すなわち需要港）である。また、この実施形態では、貨物の少なくとも一部が、原油などばら荷である。ばら荷は、様々な等級の原油を含むことがある。
【００５８】
各航路定義（すなわち輸送ルート）が、問題に関連する属性および／または制約を指定する。これらの属性および制約は、限定はしないが以下のものを含むことがある。（１）寄港する必要がある供給／需要地点。（２）各地点で船積または荷揚する必要がある特定の貨物の体積の識別、タイプ、および範囲。（３）各地点で船積または荷揚すべき貨物の量に関する上限および下限許容値。（４）各地点で船積または荷揚を行うための許可された時間窓。（５）様々な時点に各供給地点で使用可能にされる貨物のレータビリティ。および（６）特定の需要地点で配送すべき各タイプの貨物の体積に関する上限／下限。各航路定義は、複数の供給地点および複数の需要地点への寄港を含むことができ、また複数のタイプ（例えば異なる等級の原油）を含む貨物を有することができる。したがって、一実施形態では、各航路が船積区分を含み、１つまたは複数のタイプの貨物（例えば３つの異なる等級の原油）が、地点特有の量範囲内および地点特有の船積期間内で、１つまたは複数の供給地点から船積される。この実施形態では、各航路はさらに荷揚区分を含み、１つまたは複数のタイプの貨物が、地点特有の量範囲内および地点特有の荷揚期間内で、１つまたは複数の需要地点で荷揚される。
【００５９】
好ましくは、船積される貨物の総量は、各航路で荷揚される貨物の総量に等しい。したがって、一実施形態では、船積区分において船積される各タイプの貨物の総量が、荷揚区分で荷揚される各タイプの貨物の総量に等しい。しかし、貨物が、航海前に既にビークル上にある、または航海の最後にビークル上に残っているシナリオを考慮することもできる。
【００６０】
１組の所与の入力（以下で説明する）に基づいて、この方法は、１組の最適化された輸送決定項目を見出す。次いで、これらの最適化されたパラメータに基づいて、輸送ビークルのグループによって貨物が機械的に輸送される。貨物の輸送は、１つの地点から別の地点に材料を機械的に移動させるための任意の手段を使用して実行することができる。例えば、海上適用例では、輸送手段は、船舶または他の船を含むことがある。陸上用途では、手段は、トラックおよび他の自動車を含むことがある。
【００６１】
４．２．２  モデルへの入力
この方法は、最適な配分スケジュール、ノミネーションスケジュール、輸送ルート、特殊化された輸送地点の使用、およびビークルの割当てを決定する際に、最高の総純利益を生成する（あるいはその代わりに正味の発生コストを最小にする）ようにいくつかの入力パラメータおよび変数を考慮する。これらの入力のいくつかの例を以下に説明する。しかし、ここで提示する、および本明細書にわたって提示する例は限定的なものではない。当業者は、以下の列挙する例示的な入力が包括的なものではなく、本明細書の精神に沿った他の関連の入力も本発明に含むことができることを理解されよう。好ましくは、純利益または発生コストに対してそれなりの影響を与える全ての入力パラメータおよび変数が考慮される。さらに、混合整数線形計画モデルでの様々な制約に関係する全ての変数が考慮される。
【００６２】
本発明による方法では、収集ステップは、１つまたは複数の供給地点に関係するデータを収集することを含む。この情報は、地域または他の地理的区域への様々な供給地点の分類を含めた、供給場所の物理的位置を含むことができる。また、この情報は、（タイプおよび量を含めた）貨物の使用可能性、および使用可能性のタイミング（すなわち窓）に関するデータを含むこともできる。また、この情報は、特定の供給地点に関する任意のビークル制限または制約を含むこともある。例えば、特定の供給港が、入港する船の喫水、重量、錨地、または積載容量に対する限度を設けることがある。また、この情報は、港使用料、または供給地点に関連する他の通行料を含むこともある。
【００６３】
海上実施形態では、この方法の収集ステップは、海港で典型的に見られる情報または制限など海上特有の供給地点データを含むことがある。この情報は、例えば、特定の等級の原油の使用可能性に関連することがある。さらに、この情報は、小口または貨物サイズ規則または制限を含むことがある。さらに、この情報は、貨物の目標量よりも多い量または少ない量を積むための許容値を含むこともある。また、この情報は、レータビリティに関連するデータを含むこともある（すなわち、１つのビークルが一度に全ての船荷を積み込むのとは対照的に、ある量の供給貨物を時間にわたってビークルに配分して供給する）。
【００６４】
本発明による方法では、収集ステップは、１つまたは複数の需要地点に関係するデータを収集することを含む。この情報は、需要場所の物理的位置を含むことがある。また、これは、需要地点での貨物に関する在庫および消費スケジュールなどの因子を含むこともあり、それにより、より多くの貨物供給が求められることがある時を決定できるようにする。また、この情報は、特定の需要地点に関する１組の要件を含むこともあり、そのような要件は、例えば貨物のタイプおよび量、配送される貨物の経済的単位価格、配送時間窓、およびグループ分けまたは隔離要件である。
【００６５】
海上実施形態では、この方法の収集ステップは、海港で典型的に見られる情報または制限など海上特有の需要地点データを収集することを含むことがある。この情報は、隔離における様々な原油等級の構成比率またはブレンド比率を含むことがある。また、この情報は、特定の需要地点に関する任意のビークル制限または制約を含むこともある。例えば、特定の需要港が、入港する船の喫水、重量、錨地、または積載容量に対する限度を設けることがある。また、この情報は、港使用料、または需要地点に関連する他の通行料を含むこともある。さらに、この情報は、指定された荷揚量よりも多い量または少ない量を荷揚するための許容値を含むこともある。いくつかの例では、これらの許容値は、貨物量に関する「ソフト」または「相対」リミットとなることがある。いくつかの例では、あるコストでこれらのソフトリミットを超えることがある（例えばソフトリミットを上回るまたは下回る原油１バレル当たりのドル建て価格）。さらに、いくつかの需要地点は、いわゆるハードまたは絶対リミットを有することがある。ソフトリミットとは異なり、これらの許容値は超えられることはない。また、この情報は、需要地点で必要とされる特定の隔離に関する情報を含むこともあり、そのような情報としては、現在の隔離区域在庫、隔離区域消費レートまたはスケジュール、隔離ブレンドダウン比率（例えばブレンド要件、限度、および比率）、配送される貨物量の経済的単位価格、およびコストまたはペナルティに関して在庫限度を超えられる融通性がある。また、この情報は、外部供給または船外要件に関する構成上の制約に関することもある。
【００６６】
特定の実施形態では、データ収集ステップはまた、指定された地理的領域に関係するデータを収集することもある。需要および／または供給地点は、様々な地理的領域にグループ分けすることができる（例えば、アラビア湾、紅海、日本、ヨーロッパ、米国など）。海上輸送実施形態では、供給港および／または需要港を、特定の供給および／または需要領域にグループ分けすることができる。これらの領域はそれぞれ、本明細書で挙げた特性の任意のものを含めた、各領域に関連付けられる１組の特性を有することがある。さらに、これらの領域は、ＣＳＯ（または例えば日本の場合にはＬＯＶ）など、特別な特性を有することがある。
【００６７】
本発明による方法では、収集ステップは、複数の輸送ビークルに関係するデータを収集することをさらに含む。データ収集ステップは、このグループ内の各ビークルから、サイズ、重量、積載容量限度、速度（船積とバラストの両方）、出発地点、および燃料消費速度を含むデータを収集する。出発地点の情報は、推定到着時間（ＥＴＡ）、推定出発時間（ＥＴＤ）、または最新情報での位置の形態でよい。ビークルの容量限度に関する情報は、体積、重量、または任意の他の関連の測定単位で表すことができる。
【００６８】
一実施形態では、方法の収集ステップは、複数の船舶を考慮する。この実施形態では、船容量、ばら荷密度、および供給／需要地点の制約間の相互作用、ならびにビークルサイズ、形状、速度、および燃料消費速度に関する情報が収集される。さらに、貨物が異なるばら荷（例えば、異なる等級の原油）を含む特定の実施形態では、これらのばら荷は典型的には異なる密度を有し、これは、搬送することができる貨物の量に影響を与える。供給および需要地点（例えば港）は、その地点を使用するビークルに対する様々な物理的な制限（例えば最大喫水、最大船長および幅など）を有する。各ビークルの特有の物理的特性（例えば喫水および他のパラメータ）が、特定のルート（すなわち航路）に関してビークルが地点制約を満たすことができるかどうかを決定する。また、各ビークルの船積速度、バラスト速度、および燃料消費速度も、純利益および発生コストに影響を及ぼし、収集ステップで収集される。さらに、スポット用船と期間用船の両方に関するコストデータが考慮される。スポット用船に関しては、滞船料、船齢料、半端貨物最小値などの因子が考慮される。期間用船に関しては、燃料費、港課金、他の使用料、および他のペナルティなどの因子が考慮される。
【００６９】
特定の航路が十分に短く、所与の計画期間（例えば１か月）以内に開始される一連の連続する航海をビークルが行うことができる場合、集団内の任意の長期ビークル（例えば海上用途の場合には期間用船）を、計画期間にわたって複数の連続する航路に割り当てることができる。典型的には、分類「期間用船」は、定期用船、完全所有または一部所有船、裸用船などを含めた、複数の割当てに使用可能な任意の船を包含する。しかし、そのような複数の航路の割当ては、期間用船が、複数の航路割当てにおける各航路に関する（時間的制約や港制約などを含めた）あらゆる制約を満たすことができる場合にのみ行うことができる。短期または個別的なビークル（例えば、海上輸送用途の場合にはスポット用船）は、典型的には複数の航路を取ることは許可されない。なぜなら、それらは通常、ただ１つの航路のために借用されるからである。しかし、いくつかの場合には、スポット用船によるそのような連続する航海が許可される。同様に、同様の短期の使用可能性を規定する用船条項のあるビークル（すなわち、それらの用船の制限された性質により、実質的にスポット用船である船）は、典型的には複数の航路を取ることを許可されない。
【００７０】
本発明による方法では、収集ステップは、輸送すべき貨物に関係するデータを収集することをさらに含む。情報のこのグループにおける因子は、貨物のタイプ、各貨物タイプの物理的性質（例えば、密度や、貨物加熱など特別な取扱い要件）、および各貨物タイプの経済的価値を含む。
【００７１】
海上実施形態では、方法の収集ステップは、海上特有の供給等級データを収集することを含むことがある。この情報は、各供給等級に関して、密度など原油の物理的な特性、および経済的価値を含むことができる。一実施形態では、１つまたは複数のばら荷は、液体のばら荷である。１つまたは複数のばら荷は、１つまたは複数の異なる等級の石油または石油由来製品、例えば原油、ＬＮＧ、ディーゼル、ガソリンなどであることが好ましい。１つまたは複数のばら荷は、１つまたは複数の異なる等級の原油であることがより好ましい。ばら荷が原油である場合、需要地点は、典型的には、精油所、または精油所のある港である。本発明の１つの特定の事業適用例は、供給源地点から精油所地点への原油（または同様の石油液体）の輸送のためにＶＬＣＣなどの原油タンカーを最適化することである。
【００７２】
本発明による方法において、収集ステップは、様々な輸送情報に関係するデータを収集することさらに含む。この輸送情報は、１つの地点から別の地点に貨物を移動させることに関連する一般的な分類の制約を包含する。例えば、この分類での情報は、様々な地点（例えば供給地点および需要地点）間の距離を含むことがある。これらの距離は、長さ（例えば海里）で表すことができ、または所与のビークル速度に基づく時間として表すことができる。また、この分類は、１つの地点から別の地点に貨物を輸送するためのフラットレート使用料に関する情報を包含することがある。また、この分類は、用船主または貨物所有者アカウントに対する通行料（例えば運河通行料）または他の課金を含むこともある（例えば、ワールドスケール当たりの固定レート差、パイプライン関税、または地点間の原油価格の差）。
【００７３】
海上実施形態の場合、輸送情報の分類は、例えば貨物の船積も荷揚も行うことができる運河や港地点など様々な地点でのドロップアンドピック能力に関係する情報を含むことがある。ドロップアンドピック情報は、タイミング、コスト、貨物制限、またはこのプロセスと典型的に関連する他の制約を含むことがある。また、この分類は、ワールドスケールレート、滞船料、および燃料費を含めた運賃を含むこともある。さらに、この分類は、ドロップアンドピックまたは再梱包に関連するパイプラインコストを含むこともある。
【００７４】
また、本発明の特定の実施形態による方法は、決定変数の任意のものに関する強制的な割当てを可能にする。例えば、特定の実施形態では、収集ステップは、あるビークルを特定の作業、供給地点、または需要地点に割り当てることや、体積およびタイミングに関してプログラムに既に固定されている供給ノミネーションを特定することなど、ユーザが課した制限を収集することができる。
【００７５】
本発明のデータ収集ステップで収集された上の情報は、混合整数線形計画モデルを構成する際に使用される。上の情報を使用して、モデルの目的関数または制約を構成することができる。特定の実施形態では、コスト（例えば運賃、通行料、特定のルートに関する燃料費など）に関連する情報、または収益（例えばある貨物の経済的価値）が目的関数の一部になり、この目的関数は、総純利益を最大にするか、または総計の発生コストを最小にする。これらの実施形態では、データ収集ステップで収集された情報の残りを使用して、モデルの制約が生成される。
【００７６】
４．２．３  モデルの出力
本発明の方法は、総純利益を最大にする、または発生コストを最小にする最適化された１組の輸送決定項目を求める。したがって、輸送スケジュール管理者は、この方法を、１組の所与のデータに基づいて最適な輸送ルート、供給ノミネーション、需要配分、特別な輸送地点の使用、およびビークル割当てを決定するためのツールとして使用することができる。一実施形態では、ノミネーションプログラムの決定後、この方法は、以下の情報を輸送スケジュール管理者に提供する。（１）複数の使用可能なビークルから選択される、（タイミングや容量などに基づいて）各割当てに関して実現可能なビークル。（２）ビークル／航路の割当てに関する推奨。（３）航路割当ての各走航中に船積および荷揚すべき貨物の体積、タイプ、および重量。（４）各推奨された航路における、各地点の寄港に関するタイミング、ならびに船積および荷揚イベント。（５）各航路に関する純利益。（６）全ての航路割当てに関する総純利益。（７）期間用船舶の集団スケジュールおよび前方位置。追加の出力は、ビークル／航路の各対に関する推定される運賃、各供給および需要地点に関する在庫プロファイル、提案されるブレンドダウン比率、特別な輸送地点でのドロップアンドピックまたは再梱包の使用、ビークル／航路の各対および隔離区域に関する（レータビリティを含めた）ノミネーションスケジュール、およびビークル／航路の各対および隔離区域に関する配分スケジュールを含むことがある。
【００７７】
特定の実施形態では、本発明の方法は、１組の最適化された輸送決定項目を出力する。この組の決定項目としては、複数の輸送ビークルに関する輸送ルート（すなわち航路）（各地点での特定の時間および作業、ならびに所与のビークルに関する航路の総純利益を含む）、需要地点に輸送すべき貨物の配分（タイミング、荷揚すべき貨物のタイプ、および許容値を含む）、供給地点からの荷積みのノミネーション（貨物使用可能性および許容値のスケジュールを含む）、および各航路に関するビークル割当てを挙げることができる。経済的データ、様々な地点の名前、各地点に関連するコストなど他の関連情報も出力することができる。
【００７８】
４．３  モデルを実行する手段
特定の実施形態では、最適化法が、従来のコンピュータプロセッサ（例えば、３ＧＨｚシングルプロセッサパーソナルコンピュータ）上で動作するコンピュータアプリケーションの形態である。プロセッサは、単一の独立型プロセッサでよい。また、プロセッサは、互いに直接接続された対話型プロセッサの集合、またはコンピュータネットワーク（例えばローカルエリアネットワークまたはインターネット）を介して互いに間接的に接続された対話型プロセッサの集合でよい。
【００７９】
また、コンピュータアプリケーションの使用を伴う特定の実施形態は、データ入力および記憶デバイスインターフェースを含むこともある。データ入力・記憶インターフェースは、アプリケーションと一体であるか、またはアプリケーションとインターフェースすることができる。アプリケーションに関するデータ入力および記憶はいくつかの方法で達成することができる。アプリケーションは、データ入力および記憶インターフェースとして、Ｅｘｃｅｌまたは別のタイプのスプレッドシートソフトウェアを使用することができる。あるいは、ＳＡＰ、Ｏｒａｃｌｅ、およびＪＤ  ＥｄｗａｒｄｓなどのＥＲＰ（エンタープライズリソースプランニング）システム、またはビジネスデータウェアハウス（ＢＤＷ）、または他のタイプのビジネスアプリケーションを利用することができる。
【００８０】
アプリケーションは、計算、シミュレーション、および数学モデルを定義するコードを含み、数学モデルを解くように最適化ソルバに要請し、最適化ソルバは、アプリケーションと一体であるか、またはアプリケーションとインターフェースする。好ましくは、コードは、ＡＩＭＭＳ、ＧＡＭＳ、ＩＬＯＧ  ＯＰＬ、ＡＭＰＬ、またはＸｐｒｅｓｓ  Ｍｏｓｅｌなどのモデリングシステムソフトウェアを使用して書かれる。しかし、Ｃ＋＋、ＦＯＲＴＲＡＮ、およびＭＡＴＬＡＢを含めた任意のコンピュータプログラミング言語を使用してコードを書くこともできる。一実施形態では、アプリケーションは、ＡＩＭＭＳを使用して書かれ、ＡＩＭＭＳユーザインターフェースを採用する。好ましくは、ソルバは、線形計画および混合整数線形計画問題を解くことができる。好ましいソルバとしては、ＣＰＬＥＸ、Ｘｐｒｅｓｓ、ＫＮＩＴＲＯ、およびＸＡがある。しかし、当業者に知られている他のソルバを採用することもできる。
【００８１】
これらの実施形態でのアプリケーションによって生成される出力は、使用可能なビークルのグループ内のビークルを１組の航路に割り当て、ノミネーション要件を有する１つまたは複数の供給地点から様々な配分要件を有する１つまたは複数の需要地点に貨物を輸送する際の総純利益を最大にするための最適解である。出力は、上述したデータ入力および記憶アプリケーション（例えばＥｘｃｅｌ、ＥＲＰ、ＢＤＷなど）の任意のものを使用してファイルとしてエクスポートして保存することができる。
【００８２】
一実施形態では、データ入力および記憶は、Ｅｘｃｅｌインターフェースを使用して達成され、プログラムは、ＡＩＭＭＳモデリング言語で書かれ、プログラムでの数学モデリング問題を解くようにＣＰＬＥＸソルバに要請する。この実施形態では、プログラムは、実行および出力のためにＡＩＭＭＳインターフェースを利用する。次いで、結果をＥｘｃｅｌに戻す（例えばエクスポートまたはコピーする）ことができ、Ｅｘｃｅｌファイルとして記憶することができる。
【００８３】
図１は、本発明の特定の実施形態の方法の一部を行うことができるユーザとモデリングアプリケーションの間の可能な対話を示し、様々なインターフェースおよび計算エンジンを図示する。ユーザ（例えば船舶スケジュール管理者）は、在庫位置、生産消費、運賃などに関するデータを含めた事業データを入力する。データは、データ入力インターフェース（例えば、Ｍｉｃｒｏｓｏｆｔ  Ｅｘｃｅｌなどのスプレッドシートプログラムでのスプレッドシート）を使用して入力される。次いで、データが、最適化エンジン（すなわち混合整数線形計画モデル）にエクスポートされ、最適化エンジンは、総純利益を最大にするように（または、特定の実施形態では総計の発生コストを最小にするように）、貨物を輸送するための１組の航路を決定し、使用可能な集団内のビークルを割り当てることによって、貨物船積および配送プログラムの最適化を決定する。このとき記憶することができる結果は、推奨されるビークル／船積／荷卸スケジュール、在庫予想、および他の最適化された輸送決定項目を含む。次いで、これらの結果を、例えばスプレッドシートを使用してユーザに表示することができる。
【００８４】
したがって、本発明の一実施形態は、本明細書で説明する最適化方法を実行することができる装置である。この装置は、単一のプロセッサ、互いに直接接続された複数の対話型プロセッサ、またはコンピュータネットワークを介して互いに間接的に接続された複数の対話型プロセッサから選択される処理デバイスを備える。また、装置は、海上輸送スケジューリングの最適化のためのコンピュータモデリングアプリケーションを含む。さらに、装置は、所望の航路、使用可能なビークル、および最適化すべき計画期間を含めた、しかしそれらに限定されないデータを入力するためのデータ入力および記憶アプリケーションを含み、このアプリケーションは、コンピュータアプリケーションの一部であるか、またはコンピュータアプリケーションに一体に接続される。さらに、装置は、線形計画問題および混合整数線形計画問題を解くことができるソルバを含み、ソルバは、モデリングアプリケーションと一体であるか、またはモデリングアプリケーションとインターフェースする。さらに、装置は、船の船積および荷揚スケジュール、在庫予想、および利益を含めた、しかしそれらに限定されない結果を出力するための出力および報告アプリケーションを含み、このアプリケーションは、コンピュータアプリケーションの一部であるか、またはコンピュータアプリケーションに一体に接続される。出力は、他のシステムで使用するためにスプレッドシートまたは他のフォーマットで表示し、エクスポートすることができる。
【００８５】
一般に、例えば図２に示されるように、特定の実施形態による装置は、入力情報（例えば、地点特有のデータ、使用可能なビークルに関する情報、貨物使用可能性情報、需要要件など）を収集する。この情報は、混合整数線形計画（ＭＩＬＰ）モデルを形成するために使用される。モデルが解かれ、最適化された出力情報Ｏ１、Ｏ２、およびＯ３、すなわち貨物情報（例えば航海ルートや、貨物のタイプおよび量）、供給ノミネーション、およびビークル割当てを生成する。次いで、これらの出力を使用して、最適化された輸送方式に従って貨物を輸送することができる。
【００８６】
また、本発明は、複数の輸送決定項目を最適化するための装置を提供し、輸送項目としては、複数の輸送ビークルに関する輸送ルート、１つまたは複数の需要地点への輸送すべき貨物の配分、および１つまたは複数の供給地点からの荷積みが挙げられる。装置は、１つまたは複数の供給地点、１つまたは複数の需要地点、複数の輸送ビークル、輸送すべき貨物、輸送情報、および追加の制限に関係するデータを収集するためのデータ収集アプリケーションを含む。また、このデータ収集アプリケーションは、混合整数線形計画モデルを生成するモデリングシステムにデータを提供することもできる。モデルは、総純利益を最大にするため（または総計の発生コストを最小にするため）の目的関数と、収集されたデータに基づく複数の制約とを含む。また、装置は、１組の最適化された輸送決定項目を見出すために混合整数線形計画モードに対する解を得るためのソルバを含む。装置は、ソルバの結果をユーザに表示するためのユーザディスプレイと、他のシステムで使用できるようにスプレッドシートまたは他のリンク機能を介して結果をエクスポートすることができる機能とを含む。
【００８７】
４．４  ソリューションエンジン
ソリューションエンジンは、混合整数線形計画モデルを、１つの大きな問題として、または一連のより小さな成分の問題として解くことができる。特定の実施形態では、計算性能を改良するために、全体の最適化問題を下位部分に分割することができる。これらの実施形態では、ネットワーク内の様々なプロセスが、方法全体の異なる部分に対して同時に作用して、処理時間を速めることができる。
【００８８】
ソリューションエンジンは、モデルを１つの大きな問題または一連のより小さな成分の問題として解くことができる。好ましくは、計算性能を改良するために、全体の最適化問題を下位部分に分割することができる。この実施形態では、アプリケーションは、最初に、時間的および物理的なビークル／航路の制約（例えば上に列挙した輸送決定項目におけるものなど）に基づいて、それぞれの実現可能なビークル／航路／船積イベント／荷揚イベントを決定する。第２のステップは、総純利益を最大にするために組み込まれた１つのソリューションステップとして、航路の最適な選択、航路へのビークルの割当て、および選択された航路／ビークルの割当てへの船積イベントおよび荷揚イベントの最適な割当てに関わる。この最適化問題（または上述した第２のステップ）を、混合整数線形計画の少なくとも一部分として解くことも好ましい。２つの明確な選択肢は、１つの混合整数線形計画部分として最適化問題を解くこと、または、一連のより単純な下位問題に問題を分解することによって最適化問題を解くことを含む。また、下位部分のいくつかまたは全てと数学的プログラミング部分とを組み合わせることによってアプリケーションを修正することも可能である。
【００８９】
４．４．１  航路生成
供給入力データと要件（すなわち需要）入力データを使用して、データセット（解決される事業例に関するデータ）内で「アクティブ」である船積地点および荷揚地点（例えば供給港および需要港）の完全な組を求める。このアクティブ地点の組を、地点使用規則（例えば船積限度や許容値など）と共に使用して、１組の候補船積地点（すなわち供給地点）巡回を構成する。これらの巡回は、各巡回において、指定された最大数以下の船積地点を有する。候補船積地点巡回は、一連の１つまたは複数のアクティブ船積地点であり、これは、１つまたは複数の供給地点に関する収集された制約データにおいて提供される地点特有の規則／制限を満たし、また、１回の巡回で各船積地点を最大回数（好ましくは１回）寄港することができるという追加の制限も満たす。候補荷揚（すなわち需要）地点巡回を決定するためにも同様の手順が使用される。
【００９０】
次に、供給（船積地点による）および需要（荷揚地点による）に関する入力データを使用して、公称体積および上限許容値に基づいて入力データ値を加算することによって、各貨物タイプに関して、各船積地点巡回および各荷揚地点巡回での可能な貨物量が求められる。さらに、制約される積載能力が計算され、これは、地点の容量限度の影響（例えば港喫水限度や港等級最高貨物限度など）、および他の船積地点または荷揚地点の制約（例えば荷揚港のブレンドダウン比率）を含み、船積および荷揚巡回に関する可能な貨物量を減少させる（例えば、巡回の最後の船積港で厳しい喫水制約がある船積巡回は、この物理的制約により、積載能力が減少することがある）。これらの計算の結果は、
ＬｏａｄＲｏｔａｔｉｏｎＧｒａｄｅＰｏｔｅｎｔｉａｌ（ｌｒ，ｃ）
ＬｏａｄＲｏｔａｔｉｏｎＣｏｎｓｔｒＧｒａｄｅＰｏｔｅｎｔｉａｌ（ｖ，ｌｒ，ｃ）
ＤｉｓｃｈａｒｇｅＲｏｔａｔｉｏｎＧｒａｄｅＰｏｔｅｎｔｉａｌ（ｄｒ，ｃ）
ＤｉｓｃｈａｒｇｅＲｏｔａｔｉｏｎＣｏｎｓｔｒＧｒａｄｅＰｏｔｅｎｔｉａｌ（ｖ，ｄｒ，ｃ）
であり、ここで、「Ｉｒ」は船積巡回を表し、「ｄｒ」は荷揚巡回を表し、「ｃ」は供給等級を表し、「ｖ」はビークルを表し、計算される積載能力は、最大重量（例えばキロトン単位）を表す。最後に、船積巡回と荷揚巡回の組合せとしての可能な航路が構成される。この計算に関して、各タイプ（例えば原油の等級）に関して航路内で船積される貨物量は、航路中に完全に荷揚されなければならず、各可能な航路での各タイプの貨物（例えば原油の等級）に関する可能な船積量と可能な荷揚量の最小値（より小さいほう）を計算しなければならないと仮定される。この積載能力は、各可能な航路に関する貨物の最大量を表す。上述したように、計算は、（上に列挙したような）制約を伴って、および制約を伴わずに行われ、
ＶｏｙａｇｅＣａｒｇｏＰｏｔｅｎｔｉａｌ（ｖ，ｖｏｙ）
ＶｏｙａｇｅＣｏｎｓｔｒＣａｒｇｏＰｏｔｅｎｔｉａｌ（ｖ，ｖｏｙ）
を生成し、ビークル／航路の対に関する最大重量（例えばキロトン単位）を表す。ＶｏｙａｇｅＣａｒｇｏＰｏｔｅｎｔｉａｌ（ｖ，ｖｏｙ）を、ビークルの容量（例えば、船ＤＷＴ限度（単位キロトン）、あるいはパート貨物最小値（単位キロトン））で割って、各可能な航路／ビークルの対に関して利用することができるビークル容量の最大比率を計算する。
ＲａｔｉｏＶＣＰ（ｖ，ｖｏｙ）
＝ＶｏｙａｇｅＣａｒｇｏＰｏｔｅｎｔｉａｌ（ｖ，ｖｏｙ）／ＶｅｈｉｃｌｅＣａｐｋＴｏｎ（ｖ）
ＲａｔｉｏＶＣｏｎｓｔｒＣＰ（ｖ，ｖｏｙ）
＝ＶｏｙａｇｅＣｏｎｓｔｒＣａｒｇｏＰｏｔｅｎｔｉａｌ（ｖ，ｖｏｙ）／ＶｅｈｉｃｌｅＣａｐｋＴｏｎ（ｖ）
比率ＲａｔｉｏＶＣｏｎｓｔｇｒＣＰ（ｖ，ｖｏｙ）が、ユーザ指定された最小利用値（例えば０．７５、すなわち７５％）よりも大きい場合、可能な航路／ビークルの対は、候補航路／ビークルの対の組に加えられる。この処置が、各船積巡回、荷揚巡回、およびビークルに関して繰り返される。これにより、１組の実現可能な航路／ビークルの対が得られる。実現可能であると決定されたビークル／航路の対に関して、ＲａｔｉｏＶＣＰ（ｖ，ｖｏｙ）を使用して、複数回使用することができる可能性がある航路を識別する。例えば、
ＲａｔｉｏＶＣｏｎｓｔｒＣＰ（“ｖ１”，“ｖｏｙＡＢＣ”）＝１．１
ＲａｔｉｏＶＣＰ（“ｖ１”，“ｖｏｙＡＢＣ”）＝２．３
は、対ｖ１／ｖｏｙＡＢＣが実現可能な対であり、この対を２回使用するのに十分な積載能力が存在することを示唆する。
【００９１】
実現可能な航路／ビークルの対の組の中の航路／ビークルの各対に関して、行うことができる実現可能な船積および荷揚活動（またはイベント、または作業）が決定される。この処置では、可能な合致を識別するために、各航路に関する船積地点および荷揚地点が、供給情報（ノミネーション）および需要要件（配分）と共に考慮される。例えば、特定の船積地点を寄港しないある航路は、その船積地点に関する船積地点活動を満たすことができない。別の航路は、２つの船積地点（例えば港Ａと、それに続く港Ｂ）を寄港することができるが、（収集されたデータ中の開始日および終了日によって与えられる）供給窓が、第２の地点（例えば港Ｂ）での供給に関する船積窓が第１の地点（例えば港Ａ）での供給に関する船積窓が始まる前に終了するようなものである場合には、これらの船積地点で貨物を船積することができないことがある。各候補航路が、規定の順序の寄港（例えばカウント変数ｎによって表され、ここでｎ＝１、２、３、・・・、Ｎ）と、関連の地点（例えば、供給港および需要港）を有するので、この処置の結果が以下の情報セットを生成し、これは例えば以下のアレイによって表されることがある。
ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｌＥｖｅｎｔ（ｖ，ｖｏｙ，ｎ，ｐ，ｌＥｖｅｎｔ）
ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｄＥｖｅｎｔ（ｖ，ｖｏｙ，ｎ，ｐ，ｄＥｖｅｎｔ）
上の表記において、ｖはビークルを表し、ｖｏｙは候補航路を表し、ｎは地点の順序を表し、ｐは地点（例えば港）を表し、ｌＥｖｅｎｔは船積イベントを表し、ｄＥｖｅｎｔは、荷揚イベントを表す。実現可能なｖ−ｖｏｙ−ｎ−ｐ−ｌＥｖｅｎｔの各組合せは、ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｌＥｖｅｎｔ（ｖ，ｖｏｙ，ｎ，ｐ，ｌＥｖｅｎｔ）で値１を割り当てられ、実現可能なｖ−ｖｏｙ−ｎ−ｐ−ｄＥｖｅｎｔの各組合せは、ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｄＥｖｅｎｔ（ｖ，ｖｏｙ，ｎ，ｐ，ｄＥｖｅｎｔ）で値１を割り当てられる。実現可能でない組合せは、デフォルト値０を有する。上の各関数の結果は、多次元アレイまたは他の行列として記憶することができる。
【００９２】
４．４．２  供給ノミネーション最適化モジュール
上の航路生成プロセスは、全ての実現可能な航路選択肢の組Ｖを生じる。各特定の航路選択肢ｖ∈Ｖは、全ての航路／ビークルの対、その地点の順序、地点（例えば港）、および船積イベント／荷揚イベントに関する特定の１組の航路を含む。次いで、混合整数線形計画モデルを使用して、全ての実現可能な航路選択肢のこの組Ｖの中で最適化を行い、最大の純益をもたらす特定の航路選択肢ｖを選択する。したがって、混合整数線形計画モデルは、その項として、各ｖ∈Ｖに関して、生み出される総計の収益から発生コストを引いた値を有する目的関数を備える。線形計画モデルに対する解は、供給ノミネーションスケジュール、配分スケジュール、および総純利益を最大にする運送ルート（すなわち航路）を提供する。
【００９３】
特定の組の各航路選択肢ｖ∈Ｖに関する純利益は、ＮＭｖ＝ＲＥＶｖ−ＩＣｖと表すことができ、ここでＮＭｖは、航路選択肢ｖ∈Ｖに関する純利益を表し、ＲＥＶｖは、航路選択肢の組ｖの中の全ての航路によって生み出される総計の収益であり、ＩＣｖは、航路選択肢の組ｖの中の全ての航路によって発生する総コストである。次いで、最大の純益を提供する特定の航路選択肢ｖに関してモデルが解かれる。
【００９４】
この特定の実施形態では、目的関数は、３つのアレイＦＥＡＳ＿ＳＶ（ビークル／航路の対を定義する）、ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｌＥｖｅｎｔ、およびＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｄＥｖｅｎｔそれぞれに関する決定変数を有する。線形計画モデルに対する解は、ＦＥＡＳ＿ＳＶの中からの選択されたビークル／航路の対を含み、これらのビークル／航路の対に対して、航路／船舶の各対において提供される船積および荷揚イベントを選択する。
【００９５】
４．４．３  航路運賃
ここで、各航路が、既知の地点寄港順序で事前生成されているので、（全体を参照により本明細書に援用する「Ｓｙｓｔｅｍ  ｆｏｒ  Ｏｐｔｉｍｉｚｉｎｇ  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｓｃｈｅｄｕｌｉｎｇ」という名称の米国特許出願第１２／２８５６５１号におけるように）各航路に関するフラットレートを計算することができる。ある航路に関する基準コストは、フラットレート、０．０１、ワールドスケールレート（パーセントで表される）、およびパート貨物最小値の積である。これらの値は全て与えられているか、既知である。追加の運賃（例えば船齢料および滞船料）は最適化ステップ中に計算される。なぜならこれらは、決定変数（例えばビークルのスケジュール、船積および荷揚される貨物の量など）の結果に応じて決まるからである。
【００９６】
４．４．４  生成された航路の最適化モデル内での使用
ＦＥＡＳ＿ＳＶ、ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｌＥｖｅｎｔ、およびＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｄＥｖｅｎｔ（総称して「実現可能性アレイ」と呼ぶ）が、実現可能な航路の場所、および航路の実現可能な利用条件（例えば、特定のビークル／航路の対によって行うことができる船積および荷揚活動）を定義する。最適化モデルは２値決定変数を含み、２値決定変数は、ＦＥＡＳ＿ＳＶ、  ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｌＥｖｅｎｔ、およびＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｄＥｖｅｎｔによって定義される実現可能な選択肢に関して否定または肯定の決定を表すために値０または１を取る。すなわち、航路生成ステップが、可能なアクションの組を定義し、混合整数線形計画が、この可能なアクションの中で最適化を行う。一般に、供給地点および需要地点の可能な組合せの数は非常に大きいことがあるので、生成される可能な航路の数も非常に大きいことがある。本発明の方法が有効になる（すなわち使用可能になる、実施可能になる、実用的になる）ように、ＦＥＡＳ＿ＳＶ、ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｌＥｖｅｎｔ、およびＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｄＥｖｅｎｔを決定するために使用される処置が、最小数の実現可能な組合せのみを生成するのに重要な役割を果たす。しかしまた、この処置は同時に包括的であり、最適なノミネーションプランを生成するために必要とされる全ての選択肢を含まなければならない。
【００９７】
４．４．５  目的関数における項
特定の実施形態では、混合整数線形計画モデルが、総純利益を最大にするノミネーションスケジュール、配分スケジュール、および運送ルート（すなわち航路）を生成するために上述した各制約を考慮する。これらの実施形態では、総純利益が目的関数になる。総純利益は、その最も単純な形態では、輸送方式中のビークル／航路の各対に関する純利益の和として表すことができる。例えば、総純利益は、
ＮＭ＝Ｒｅｖ−ＩＣ＝ΣｉＮＭ＝ΣｉＲｅｖ−ΣｉＩＣ      （式１）
で表すことができ、ここで「ＮＭ」は、輸送方式に関する総純利益を表し、「Ｒｅｖ」は、輸送方式に関する総計の収益を表し、「ＩＣ」は、輸送方式に関する総計の発生コストを表し、「ΣｉＮＭ」は、輸送方式におけるビークル／航路の各対に関する各純利益の和を表し、「ΣｉＲｅｖ」は、輸送方式におけるビークル／航路の各対によって得られる各収益の和であり、ΣｉＩＣは、輸送方式におけるビークル／航路の各対によって発生される各コストの和である。
【００９８】
式１でも示されるように、個々の純利益は、単純に、ビークル／航路の対に関する収益からそのビークル／航路の対の発生コストを引いた値として表すことができる。発生コストは、運賃（例えばスポット用船コストおよび期間用船航路コスト）、在庫ソフトリミットコスト、および在庫保管費を含むことがある。
【００９９】
収益は、以下のように決定することができる。選択された航路／ビークルの各対が、それに関連する、船積および荷揚される貨物の量を有する（選択されない航路／ビークルの対は貨物を輸送してはならない）。したがって、需要地点と隔離の各対に関して、収益は、需要地点／隔離の対で荷揚される貨物の量、および荷揚される貨物の単位価格に基づいて計算することができる。例えば、需要地点／隔離の各対での各タイプの貨物に関する収益は、
ＩｎｄＲｅｖｅｎｕｅＴ，ＤＬ，ＳＥＧ
＝ｕｎｉｔ  ｖａｌｕｅ  ｏｆ  ｃａｒｇｏ＊ｄｉｓｃｈａｒｇｅ  ａｍｏｕｎｔ
（式２）
で表すことができ、ここで、「ＩｎｄＲｅｖｅｎｕｅＴ，ＤＬ，ＳＥＧ」は、特定の地点（ＤＬ）での所与のタイプの貨物（Ｔ）に関する収益であり、（ＳＥＧ）は特定の隔離区域であり、「ｖａｌｕｅ  ｏｆ  ｃａｒｇｏ」は、特定の貨物タイプの経済的単位価格であり（これは、体積当たりの価格、質量当たりの価格、または単位量当たりの価格、例えば原油１バレル当たりのＵＳドル価格などで表すことができる）、「ｄｉｓｃｈａｒｇｅ  ｏｆ  ａｍｏｕｎｔ」は、地点「ＤＬ」での隔離区域「ＳＥＧ」内に荷揚されるタイプ「ｔｙｐｅ」の貨物の量である。荷揚量は、体積、質量、または単位量で表すことができる。好ましくは、「ｄｉｓｃｈａｒｇｅ  ａｍｏｕｎｔ」の単位は、「ｖａｌｕｅ  ｏｆ  ｃｈａｒｇｅ」の単位に対応する。
【０１００】
各需要地点での各タイプの貨物に関する収益が、輸送方式において、全ての貨物タイプＴおよび全ての需要地点ＤＬで全ての適切な隔離区域ＳＥＧにわたって足し合わされる。この和は、輸送方式に関する総計の純収益に等しい。
【０１０１】
上述したように、発生コストは、運賃、在庫ソフトリミット、および在庫保管費を含むことがある。好ましくは、本発明による混合整数線形計画モデルは、その目的関数に少なくとも運賃と在庫ソフトリミットコストを含む。しかし、追加のコストも考慮することができる。
【０１０２】
運賃は、短期ビークル（例えばスポット用船）が使用されるか長期ビークル（例えば期間用船またはチャータ船）が使用されるかに応じて異なることがある。次に、短期ビークルに関する運賃を、スポット用船の例を用いて説明する。しかし、この例に関わらず、同様のプロセスを他のタイプの輸送ビークルに関して使用することができることを理解すべきである。
【０１０３】
スポット用船の文脈で、運賃は、パート貨物最小値、船齢料レート、滞船料レート、または他の船の特徴、例えば容量や載貨重量限度などに応じたものであってよい。これらの考慮因子を用いて、単一のスポット用船に関する運賃は、
ＦＣｏｓｔＳＳＶ，ＶＯＹ
＝ＦＲ＊ＷＳＲａｔｅ＊（ＰＣＭｉｎ＋ＯＴｏｎｎａｇｅ＊ＯＲａｔｅ＊０．０１）
＊０．０１＋ＤＲａｔｅ＊ＤＤａｙｓ      （式３）
で表すことができ、ここで、「ＦＣｏｓｔＳＳＶ，Ｌ」は、航海（ＶＯＹ）を行うための特定のスポット用船（ＳＶ）に関する運賃であり、「ＦＲ」は、航路フラットレート（すなわち航路に関するワールドスケール１００レート）であり、典型的には１トン当たりのＵＳドルの単位であり、ＷＳＲａｔｅは、パーセンテージとして表される市場ワールドスケールレートであり、「ＰＣＭｉｎ」は、パート貨物最小値（典型的にはキロトン単位で表される）であり、「ＯＲａｔｅ」は、ＷＳＲａｔｅのパーセンテージとして表される船齢料レートであり、「ＯＴｏｎｎａｇｅ」は、ＰＣＭｉｎを超える貨物のトン数であり、「ＤＲａｔｅ」は滞船料レート（典型的には、１日当たりの数千ＵＳドルの単位で表される）であり、「ＤＤａｙｓ」は、許容される停泊時間を超える日数（それに対して滞船料課金が査定される）である。
【０１０４】
期間用船の文脈では、運賃は、バンカ燃料消費速度（アイドリング、バラスト、および船積中）、正味の用船費、バンカ燃料費、港使用料、または他の船舶もしくは港パラメータ、例えば船容量、載貨重量コスト、もしくは通行料に応じることがある。これらの考慮因子を使用して、所与の航路または一連の航路中の単一の期間用船に関する運賃は、
ＦＣｏｓｔＴＴＶ，ＶＯＹ
＝ｆｕｅｌ  ｃｏｎｓｕｍｅｄ＊ｆｕｅｌ  ｃｏｓｔ＋ｆｅｅｓ
＋ｔｏｌｌｓ＋ｎｅｔｈｉｒｅｖａｌｕｅ＊ＮＨｄａｙｓ      （式４）
で表すことができ、ここで、「ＦＣｏｓｔＴＴＶ，ＶＯＹ」は、特定の航海（ＶＯＹ）を行うための特定の期間用船（ＴＶ）に関する運賃を表し、「ｆｕｅｌ  ｃｏｎｓｕｍｅｄ」は、通常はメトリックトン単位で表される、期間用船によって消費される燃料の量を表し（これは、進んだ距離、燃料消費速度、および他の関連の因子に応じることがある）、「ｆｕｅｌ  ｃｏｓｔ」は、通常は１メトリックトン当たりのドルの単位で表される、船によって使用される燃料の単位コストを表し、「ｆｅｅｓ」は、港使用料など需要地点によって課金される任意の使用料を含み、「ｔｏｌｌｓ」は、運河通行料など船の航路中に必要な任意の通行料を表し、「ｎｅｔｈｉｒｅｖａｌｕｅ」は、期間契約ビークルに関する正味の用船費（以下参照）を表し、「ＮＨｄａｙｓ」は、期間契約ビークルが休止している日数を表す。
【０１０５】
上に述べた正味の用船費は、特定の貿易ルート内の典型的な航路に割り当てられたときに期間契約ビークルにかかると仮定（または予想）される１日当たりの料金レートから導出することができる。正味の用船費を使用して、ビークルが休止している時間中に失われた機会を表すことができる。さらに、期間契約ビークルに関する休止時間中の追加の燃料消費がありえ、関連のコストが正味の用船費に追加されることがある。滞船時間に関して推定されるスポットビークル滞船料と同様に、以下に式５で示されるように、期間契約ビークルの休止時間に関するコストを計算することができる。この考慮因子は、例えば、目的関数（例えば純利益を求めるための式）において、発生コストの項に以下の式を含むことによって、または（上に示した）式４に同様の項を組み込むことによって考慮することができる。他の実施形態では、モデルは正味の用船費を考慮しない。
ＦＣｏｓｔＴＩｄｌｅＴＶ，ＶＯＹ
＝ｉｄｌｅ＿ｔｉｍｅ＊（ｎｅｔ  ｈｉｒｅ  ｖａｌｕｅ
＋ｉｄｌｅ＿ｆｕｅｌ＿ｃｏｎｓｕｍｐｔｉｏｎ＿ｃｏｓｔ）      （式５）
式５で、「ＦＣｏｓｔＴＩｄｌｅＴＶ，ＶＯＹ」は、航海（ＶＯＹ）を行うための各期間契約ビークル（ＴＶ）に関する休止時間コストを表し、「ｉｄｌｅ＿ｔｉｍｅ」は、（例えば１時間単位または１日単位で表される）特定の期間契約ビークルが休止している時間量を示し、「ｎｅｔ＿ｈｉｒｅ＿ｖａｌｕｅ」は、ある単位時間当たりのビークルの価格を表し、「ｉｄｌｅ＿ｆｕｅｌ＿ｃｏｎｓｕｍｐｔｉｏｎ＿ｃｏｓｔ」は、特定の期間契約ビークルに関するある単位時間当たりの休止燃料消費コストを表す。
【０１０６】
実現可能なビークル／航路の対の組における各スポット用船に関する運賃は、式３を使用して計算することができ、全てのスポット用船ＳＶおよび全ての航路ＶＯＹにわたって足し合わせて総計のスポット用船運賃を求めることができる。同様に、実現可能なビークル／航路の対の組における各期間用船に関する運賃は、式４を使用して計算することができ、全ての期間用船ＴＶおよび全ての航路ＶＯＹにわたって足し合わせて総計の期間用船運賃を求めることができる。次いで、総計のスポット用船運賃と総計の期間用船運賃を足し合わせて総計の運賃を求めることができる。総計の運賃は、目的関数の発生コストの項における一項として使用することができる。
【０１０７】
在庫ソフトリミットコストは以下のように決定することができる。受入れ地点（例えば需要港）は、ソフトリミットとハードリミットの両方を有する隔離区域在庫限度を有することがある。荷揚される貨物が、所与の隔離区域に関する在庫ハードリミット内に残っている限り、値段に関してソフトリミットを超えてもよい。したがって、これらのコストは、目的関数の発生コストの項における重要な因子となりうる。在庫ソフトリミットコストは、ソフトリミットを超えるコスト、これらのリミットを超えて提供される貨物の量、およびソフトリミット自体（すなわち、ベース在庫最小値および最大値）の関数として表すことができる。これらの考慮因子を用いて、特定の需要地点での特定のビークルに関する在庫ソフトリミットコストは、
ＩＳＢＣｏｓｔＤＬＳＥＧ
＝ｅｘｃｅｓｓ  ｃａｒｇｏ＊ｃｏｓｔ  ｔｏ  ｅｘｃｅｅｄ      （式６）
で表すことができ、ここで、「ＩＳＢＣｏｓｔＤＬＳＥＧ」は、特定の需要地点（ＤＬ）での特定の隔離区域に関する在庫ソフトリミットコストを表し、「ｅｘｃｅｓｓ  ｃａｒｇｏ」は、特定の地点に関する最小または最大在庫限度を超える貨物の量を表し（これは、荷揚される貨物の量と、特定の地点のソフトリミットとの関数でよい）、「ｃｏｓｔ  ｔｏ  ｅｘｃｅｅｄ」は、ソフトリミットを超える単位貨物当たりに関連付けられるコストである（例えば単位貨物当たりのＵＳドルの単位で与えることができる）。
【０１０８】
在庫ソフトリミットコストは、輸送方式における全ての需要地点ＤＬおよび隔離区域ＳＥＧにわたって足し合わせることができる。この和は、輸送方式に関する総計の在庫ソフトリミットコストに等しく、これもまた目的関数の発生コストの項に含めることができる。
【０１０９】
在庫保管費は、平均在庫レベルに保管費を乗算した積として決定することができる（例えば、単位貨物当たりのＵＳドルの単位で与えることができる）。これは、例えば、以下の式で表すことができる。
ＩＨＣＣｏｓｔＤＬ，ＳＥＧ
＝ａｖｅｒａｇｅ  ｉｎｖｅｎｔｏｒｙ＊ｈｏｌｄｉｎｇ  ｃｏｓｔ      （式７）
【０１１０】
在庫保管費は、輸送方式において全ての需要地点ＤＬおよび隔離区域ＳＥＧにわたって足し合わせることができる。この和は、輸送方式に関する総計の在庫保管費に等しく、これもまた目的関数の発生コストの項に含めることができる。
【０１１１】
上述した（式３〜７によって表される）各コスト項を足し合わせて、特定の輸送方式に関する総計の発生コスト（ＩＣ）を求めることができる。すなわち、（スポットビークルと期間契約ビークルの両方に関する）総計の運賃、総計の在庫ソフトリミットコスト、および総計の在庫保管費を足し合わせて、総計の発生コストを求めることができる。特定の実施形態は、これらの項の１つまたは複数を除外することができ、他の実施形態は、追加の項を含むことができる（例えば、輸送中の運転資金、貨物または船保険コスト、および油損失コスト）。好ましくは、発生コストは、少なくとも総計の運賃および総計の在庫ソフトリミットコストを含む。
【０１１２】
総純利益を求めるために、（式１に示されるように）総計の発生コストが総計の収益から引かれる。特定の実施形態では、総純利益が目的関数として使用され、この目的関数は、収益と発生コストの両方を考慮に入れる。したがって、ここで述べる制約および入力は、混合整数線形計画モデルの制約および決定変数になる。他の実施形態では、目的関数は総計の発生コストを最小にし、収益は、目的関数における因子でない。
【０１１３】
総純利益の最大値は同時に以下のものをもたらすことが分かり得る。（ａ）収益の項による不積み運賃の減少／最小化。（ｂ）ビークルに関する休止時間の減少／最小化。（ｃ）（例えば航路フラットレートおよび／または航海コストに基づいて）好ましい航路を選択することによる輸送プログラムの効率の最大化。（ｄ）バンカ燃料費（および他の使用料および課金）など航海コストの減少／最小化。（ｅ）比較運賃に基づく期間契約ビークルおよびスポットビークルの利用の最大化。（ｆ）対応する運賃を考慮することによるビークルクラス選択肢の利用の最大化。（ｇ）許容される需要地点および対応する隔離区域（適切であれば）への使用可能な供給の配分の最大化、および（ｈ）ソフトリミットを超えるとき、および／または保管費がかかる場合に生じる在庫管理費の減少／最小化。
【０１１４】
実現可能なビークル／航路の各対に関するそれぞれの純利益は、計算された予測値であることに留意されたい。なぜなら、大抵は、ビークルが実際に航海を完了するまでは確実には分からないことがある発生コストを予測しなければならないからである。
【０１１５】
実現可能な複数のビークル／航路の割当てに関しても、上述した全ての概念がそのまま有効であり、純利益の概念を依然として適用可能である。燃料消費は、各航路の船積部分と、各航路中の在港時と、第１の船積航路の前および連続する航路間のバラスト状態および任意の休止部分と、最後の船積航海が行われた後のバラスト状態および任意の休止部分（主船積領域での基準地点に戻るため）との和に基づいて計算される。他のコストおよび収益の項は、複数航路の組合せに適用されるときに追加される。さらに、混合整数線形計画モデルは、各期間契約ビークルが航路組合せを１つだけ取ることを許されることを保証するための制約を含むことができる（ここで、組合せは、１つまたは複数の連続する航路からなることがある）。
【０１１６】
４．４．６  １つのソリューション手順
一手法は、汎用の混合整数線形計画ソルバを使用してモデルを直接解くものである。ＣＰＬＥＸ、Ｘｐｒｅｓｓ、ＸＡ、ＫＮＩＴＲＯ、または別のＭＩＬＰソルバを使用する適切な混合整数線形計画最適化ルーチンを、混合整数線形計画問題を解くために使用することができる。
【０１１７】
４．４．７  好ましいソリューション手順
効率良くバランスの取れた１組の解を生成するには事前処理が効果的であるが（すなわち、これは、問題サイズを非常に大きくすることがあり得るいくつかの不要な航路選択肢をなくす）、汎用混合整数線形計画ソルバを用いてモデルを直接解くことは、許容できる処理時間量では解を生成しないことがある。そのような場合のために、本発明の方法のいくつかの用途では、最適化の効果を依然として保ちながら、より好ましい処理時間を実現するために、ソリューションプロセスにおいていくつかのステップ中にモデルを一時的に簡略化することが望ましいことがある。したがって、簡略化されたモデルを使用する以下のソリューション方法が開発された。これらのソリューションはそれぞれ、完全なモデルとして独立して使用することができ（すなわち、モデルの結果は、貨物の輸送の基礎になる）、またはそれらは、以下に説明するように互いに構築し合うことができる（すなわち、例えばステップ３がステップ２からの結果をインポートする）。
【０１１８】
ステップ１：問題の選択された複雑な特徴が、より簡単に最適化する（解く）ことができるモデルを生成するために簡略化され、このモデルが解かれる。好ましくは、この解は、元のモデルに対する近似解、および最大（最小）の純利益（コスト）の目的関数に関する上限（下限）目標値を生み出す。モデルの１つのそのような単純化されたバージョンは、需要地点在庫制約が無視されるバージョンである（特定の他の実施形態では、全体のモデルが簡略化されるように、他の仮定がなされることがあり、または他の制約が取り除かれることがあることに留意されたい）。これははるかに単純なモデルとなることがあるので、（デフォルトまたはカスタムのソルバ設定を有する汎用の混合整数線形計画ソルバを使用して）元の「フル」モデルよりもかなり短時間で解くことができる。また、このモデルの結果は、在庫限度を満足する必要はないので、目的関数値はかなり楽観的な結果になり、フルモデルの目的関数値に関する上限（または高い目標値）を提供する。すなわち、この簡略化されたモデルの結果は、「最良の場合」のシナリオを表すことがある。このステップからの解はまた、１組の選択されたビークル／航路の対を含む（例えば、組ＦＥＡＳ＿ＳＶ内からのビークル／航路の割当ての部分集合）。簡便のために、ステップ１で得られる目的関数値をＯＢＪ＿１と呼ぶ。
【０１１９】
ステップ２：ステップ２では、（在庫限度を有する）元のモデルが解かれるが、航路の実現可能な組が縮小されて（例えば一時的に制限されて）、フルセットＦＥＡＳ＿ＳＶの部分集合になる。縮小された組（ＲＥＤ＿ＦＥＡＳ＿ＳＶ）は、ステップ１から導き出される最適な航路のみを含むように定義することができる（例えば、ステップ１に対する解で選択された各航路に関してＲＥＤ＿ＦＥＡＳ＿ＳＶ（ｖ，ｖｏｙ）＝ＦＥＡＳ＿ＳＶ（ｖ，ｖｏｙ）とする）。これは、サイズに関する問題を大幅に緩和するが、ステップ１で簡略化（または無視）された複雑な因子（例えば需要港在庫制約）を考慮する。この問題は、デフォルトまたはカスタムのソルバ設定を使用して汎用の混合整数線形計画ソルバを用いて直接解くことができる。この問題は、実現可能なビークル／航路選択肢のフルセットを含まないので、ここで得られる解は、元の問題に対する最適解ではないことがある。しかし、この解は、依然として元のモデルの全ての制約を満たすので、実現可能な輸送方式を提供する。目的関数値は、元の問題に関する目的関数値に対する下限を提供する（すなわち、実現可能なビークル／航路の選択肢のフルセットが考慮されるときには、より最適な解を得ることができることがある）。このステップは、元の問題に対する許容解を生成するので、「構成発見的技法（Ｃｏｎｓｔｒｕｃｔｉｏｎ  Ｈｅｕｒｉｓｔｉｃ）」と呼ばれる。実際、これが元の問題に対する最適解であることもあるが、保証はされない。ＯＢＪ＿２を、ステップ２で得られる目的関数値とし、ＤｅｌｔａＯＢＪ＿１−２を、ステップ１およびステップ２からの目的関数値の差とする（すなわち、ＤｅｌｔａＯＢＪ＿１−２＝ＯＢＪ＿１−ＯＢＪ＿２）。ＡＢＳ（ＤｅｌｔａＯＢＪ＿１−２）（ここでＡＢＳ（）は絶対値を表す）が許容できるほど小さい場合、問題に対する許容できる解が見つかっている。この場合、この方法は、ステップ６にスキップすることができる。
【０１２０】
ステップ３：元のＦＥＡＳ＿ＳＶアレイが、実現可能な選択肢のフルセットとして回復される。ステップ２からの解は、ステップ３でのソリューション手順に関する開始点（または初期解）として提供される。この問題は、汎用の混合整数線形計画ソルバを使用して解かれる。これは、指定された期間にわたってＳｏｌｕｔｉｏｎ  Ｐｏｌｉｓｈｉｎｇと呼ばれるＣＰＬＥＸでの特定の方法を使用することによって実現することができる。あるいは、問題は、指定された期間にわたってＣＰＬＥＸでデフォルトの方法を使用して解くことができる。ステップ３からの結果は、場合によってはステップ２の解に対する改良となる（しかし、ステップ２に対する解よりも悪くはないことが保証される）。したがって、このステップは、改良発見的技法（Ｉｍｐｒｏｖｅｍｅｎｔ  Ｈｅｕｒｉｓｔｉｃ）ステップと呼ばれる。設定される制限時間、および混合整数線形計画モデルの難易度によっては、ソルバは、制限時間に達する前に実証済みの最適解に収束することがある。その場合、ステップ４は必要ない。ＯＢＪ＿３を、ステップ３で得られる目的関数値とし、ＤｅｌｔａＯＢＪ＿１−３を、ステップ１およびステップ３からの目的関数値の差とする（すなわち、ＤｅｌｔａＯＢＪ＿１−３＝ＯＢＪ＿１−ＯＢＪ＿３）。ＡＢＳ（ＤｅｌｔａＯＢＪ＿１−３）が許容できるほど小さい場合、問題に対する許容できる解が見つかっている。この場合、この方法は、ステップ６にスキップすることができる。
【０１２１】
ステップ４：解探索空間縮小発見的技法が適用される。例えば、以下の条件を適用することができる。すなわち、ステップ３からの解で使用されるユーザ指定された数以下の（例えば２つの）航路を変えることができる。これは、ステップ３からの解の一部分が最適であり、ソルバがこれらの決定項目を固定して保って、航路決定固定の部分集合に対する変化のみを許可しなければならないと仮定される点で、発見的手法である。これは、混合整数線形計画モデル内で値０から値１（すなわち、航路および関連のビークル割当ての選択に関する関連の２値変数）に変えることができるビークル／航路の対の数を制限する制約を加えることによって実現される。このステップの追加された制約は、混合整数線形計画ソルバが許容できる時間量内で実証済みの最適解に収束する可能性をより高める。ＯＢＪ＿４を、ステップ４で得られる目的関数値とし、ＤｅｌｔａＯＢＪ＿１−４を、ステップ１およびステップ４からの目的関数値の差とする（すなわち、ＤｅｌｔａＯＢＪ＿１−４＝ＯＢＪ＿１−ＯＢＪ＿４）。ＡＢＳ（ＤｅｌｔａＯＢＪ＿１−４）が許容できるほど小さい場合、問題に対する許容できる解が見つかっている。この場合、この方法は、ステップ６にスキップすることができる。ステップ４に関する許可された制限時間を超えた場合、ステップ６にスキップする。そうでない場合、ステップ４とステップ３からの目的関数値の差としてＤｅｌｔａＯＢＪ＿４−３を計算する（すなわち、ＤｅｌｔａＯＢＪ＿４−３＝ＯＢＪ＿４−ＯＢＪ＿３）。
【０１２２】
ステップ５：これは、ステップ４からの結果が実際にステップ３からの結果の改良である場合に（複数回）取ることができる任意選択のステップである。ＤｅｌｔａＯＢＪ＿４−３が指定量よりも大きい場合、解探索空間縮小が更新されて、ステップ４で得られた現行の最良解を反映し、ステップ４および５が、制限時間に達するまで、またはステップ４の連続する解からの目的関数値の差が指定量未満になるまで繰り返される。
【０１２３】
ステップ６：最適解またはほぼ最適の解が与えられると、数学モデル解は、供給ノミネーションプログラム、および対応する船積および荷揚スケジュールに変換され、このスケジュールが、取るべき推奨アクションとなる。ユーザは、ステップ１〜５の任意のものから（しかし好ましくはステップ２〜５から）の出力（すなわち目的関数の結果）を、最適化された輸送方式として選択することができる。したがって、例えば、ステップ３からの出力が許容できるものであるとユーザが判断した場合、ユーザは、その点でカスタム法を停止し、輸送方式としてステップ３からの結果を使用することができる。
【０１２４】
次に、表１および２を参照して上述したカスタムソリューション法の非限定的な実施形態に関して例示的な解を説明する。まず、モデルが、上のステップ１に従って、全ての需要港の隔離区域在庫制約を除去する。次いで、総純利益を最大にするようにモデルが解かれる。以下の表１に示されるように、この純利益に関する値は、４９２，０００ドルである。次に、ステップ２におけるように、ステップ１での解で得られたビークル／航路の割当て（例えば、ＲＥＤ＿ＦＥＡＳ＿ＳＶアレイでのビークル／航路の対が航路１５、２２、５５、および１４３を含むように制限される）が使用されて、新規のモデルのための可能なビークル／航路の割当てとして定義される。しかし、この第２のモデルは、需要港の隔離区域在庫制約を考慮する。このモデルが解かれ、総純利益に関する第２の値を生み出す（この場合、表１に示されるように−６０３，０００ドル）。次に、ステップ１に関する総純利益（ＯＢＪ＿１）とステップ２に関する総純利益（ＯＢＪ＿２）の差が求められる。この差の絶対値が小さい（すなわちある許容範囲内にある）場合、解は、許容できるとみなされ、さらなるモデルは実行されない。しかし、（表１における例のように）差が十分には小さくない場合、方法は、ステップ３に進む。このステップでは、可能なビークル／航路の割当ての元のフルアレイが回復されるが、ステップ２からの出力が、初期条件または開始点として使用される。この新規のモデルが解かれ、第３の総純利益（ＯＢＪ＿３）を生み出す。この新規の値がは、ステップ１での総純利益に関する値と比較され、この差の絶対値が十分に小さい場合、この方法が終了し、さらなるモデルは実行されない。しかし、差が十分には小さくない場合、モデルはステップ４に進む。このステップでは、解探索空間発見的技法がモデルに適用され、この新規のモデルが再び解かれる。解は、第４の総純利益（ＯＢＪ＿４）を生み出し、これが、第３の総純利益（ＯＢＪ＿３）または第１の総純利益（ＯＢＪ＿１）と比較される。これらの値の差が小さい場合、この方法は終了し、さらなるモデルは解かれない。しかし、差が十分には小さくない場合、必要であればステップ４を繰り返すことができる。この例では、第４の総純利益と第３の総純利益の差がない。したがって、第４のステップは、改良された解を見出す助けとはならなかった。しかし、最適化プログラムは、妥当な期間内でステップ４のモデルを収束できた。この場合、この方法を終了することができ、ステップ４に対する解を、問題に関する解として使用することができる。
【０１２５】
【表１】
2012526326.tif 000003
【０１２６】
また、ビークル／航路の割当てが、各ステップごとに変わることがあることにも留意されたい。例えば、表２は、上の例での各ステップに関するビークル／航路の割当てを示す。表２は、各ビークルが、上述したカスタムソリューションの各ステップに関して最適に行う航路を示す。各航路は、ビークルが寄港する様々な地点に関する情報を含み、また、供給ノミネーションおよび／または需要配分スケジュール情報も含むことができる。
【０１２７】
【表２】
2012526326.tif 000004
【０１２８】
４．４．８  方法の追加の特徴
特定の実施形態では、方法は、追加の特徴を備えることができる。例えば、モデルは、いくつかのユーザ定義された制約または制限を可能にすることができる。これらのユーザ定義された制約としては、限定はしないが、許容できる供給地点の順序を制限する規則、所与の航路で最大数の供給港および／または需要港を課す規則、および任意の所与の航路で、または船積プログラム全体で各船積地点を寄港することができる総回数に対する制限がある。
【０１２９】
さらに、方法の一部分がコンピュータアプリケーションを使用して実行される特定の実施形態では、アプリケーションは、全体にわたって検証チェックを含むことがある。これらの検証チェックにより、ユーザは、プロセス中の様々な点でアプリケーションの何らかの出力を閲覧して承認することができるようになる。また、ユーザは、出力が妥当でない、または実用的でないように見える、あるいは何らかの他の理由で許容できない場合、いくつかの点でプロセスをキャンセルまたは中断するという選択肢を有することもある。次いで、ユーザは、ある入力情報を再入力するため、および／または他の制約または制限を変更するために、プロセス中の他の点に戻るという選択肢を有する。あるいは、アプリケーション自体が、出力データにエラーがないことを保証するために、プロセス中の様々な点でのチェックを含むことができる。アプリケーションは、エラーが生じていると判断した場合、ユーザに、アプリケーションを再実行させる、またはモデルの入力もしくは他の制約を変えるという選択肢を与える。一般に、できるだけ早く、一致しない入力データを識別して、ユーザにデータ入力エラーの可能性を警告することが望ましい。
【０１３０】
さらに、特定の実施形態では、方法は、ケースマネージメント機能を含む。方法の一部分がコンピュータアプリケーションを使用して行われる特定の実施形態では、コンピュータアプリケーションは、例えば、様々な出力を保存、編成、および記憶することができる能力を有することができる。さらに、これらの実施形態により、ユーザは、より後の時点で出力をリロードすることができるようになり、または様々なモデルと共に使用するための何らかの入力「テンプレート」を有することができるようになることがある。特定の実施形態では、方法は、いくつかの入力パラメータを変えられるようにし、生じた出力を、それらの変更前の結果と比較できるようにする。
【０１３１】
さらに、本発明はまた、輸送方式中に在庫を追跡するための構成要素を含むこともできる。そのような構成要素は、例えば、貨物またはビークルがある地点から別の地点に移動するときに貨物またはビークルを追跡するために全地球測位システム（ＧＰＳ）を使用することを含むことがある。
【０１３２】
輸送方式の最適化、および最適化された方式に従った貨物の機械的な輸送を補助する当業者に知られている他の特徴を本発明に適用することができることは明白である。本明細書で提供する例は、そのようなアプリケーションに関する可能性をまったく制限しない。
【０１３３】
４．５  モデルを使用するワークプロセス
本発明の一実施形態は、様々な輸送決定項目を最適化し、１組の最適化された輸送決定項目に従って貨物を機械的に輸送するために前述した方法を使用する海上輸送スケジューリングに関するワークプロセスである。一実施形態では、方法の収集データステップが、データベースシステムへの入力および／またはモデリング選択肢を含む。データベースシステムは、海上輸送スケジューリングに関するモデリングアプリケーションと一体であり、またはそれとインターフェースする。この実施形態では、別のステップは、データおよび／またはモデリング選択肢が入力された後に、１組の最適化された輸送決定項目を得るために最適化問題ソルバを使用して数学モデルを解くためのアプリケーションを実行するものである。特定の実施形態では、追加（任意選択）のステップは、最適化された輸送決定項目の１つまたは複数の代替の組を得るために、異なるデータおよび／または制約で１回または複数回、先のステップを繰り返すことでよい。特定の実施形態では、最終的なステップは、最適化された１組の輸送決定項目に従って、貨物を機械的に輸送することである。
【０１３４】
アプリケーションは、典型的には、入力データの感度、様々な仮定、および様々な割当て制約を調査するために複数回実行される（例えば、モデルが、所与の航路に所与の船を割り当て、残りを最適化するようにする）。アプリケーションは、これらの種類の仮説シナリオをサポートするのに十分に速く動作する。一実施形態では、アプリケーションは、約３０〜４５分で典型的な問題に関する計算を行い、妨害されない３ＧＨｚデュアルコアパーソナルコンピュータ上で動作する。
【０１３５】
典型的には、供給ノミネーション計画サイクルは１ヶ月であり、１ヶ月の船積期間を考慮する。輸送すべき貨物を含む航路、および使用可能な集団は、サイクルごとに変えることができ、おそらく変わる。また、運賃や燃料費などを含めた経済的因子は、地域的にも全世界的にも日々変化する。計画サイクル中、現行の問題の特徴および考慮事項に基づいて決定が下され、決定は頻繁に更新される。
【０１３６】
本発明の特定の実施形態によるワークプロセスの非限定的な例は、以下のようなものである。まず、最適化モデルが、事業サイクルの開始時に実行される。供給ノミネーション決定が、最大の融通性を有する。得られる（１つまたは複数の）解は、供給スケジュールをノミネートするために使用すべき推奨アクションを提供する。第２に、供給業者が、ノミネートされた供給プログラムの様々な部分を閲覧し、受け入れ、かつ／または計数し、最終的には、確認された供給スケジュールおよび対応する船積量に達する。第３に、プロセスは、追加の供給ノミネーションが確認されたときに繰り返され、それに従って、最適化モデルがノミネーションプログラム全体を再び最適化する。最後に、全ての供給ノミネーションが確認され、総純利益を最大にするように、要件に対する輸送プログラムおよび船の割当てを依然として最適化することができる。さらに、荷揚地点入力データ（予想される初期在庫レベル、処理速度、地点および／または隔離要件、および他の問題データ）は変化し続けることがあり、したがってユーザがノミネーション／輸送プログラムを最適化し続けるようにする。
【０１３７】
４．６  海上輸送以外
本発明を、好ましい実施形態である海上輸送の文脈で説明してきたが、同様に、任意の形態の貨物輸送を最適化するための使用にも適用できる。事実上、海上輸送に関して上述した全ての教示が、任意の他のタイプの集団を使用する輸送を最適化するために同様のアプリケーションを作成するのにも容易に適合され、集団が、電車、トラック、航空機、または他の形態の貨物輸送のいずれの集合体であるかは関係ない。さらに、教示は、電車、トラック、航空機、船、または他の形態の機械的な輸送の任意の組合せと共に採用することができる。
【０１３８】
例えば、（例えばトラックによる）陸上輸送スケジューリング問題を最適化する概念は、海上輸送問題を最適化するのと同様である。どちらの問題でも、集団内のビークルは、サイズ、速度、および船積容量が異なることがある。さらに、どちらの問題でも、集団内のビークルは、異なる用船タイプ（例えば、期間用船またはスポット用船または完全所有用船）であることがある。また、どちらの問題でも、地点特有の時間フレーム内で、特有の貨物量を各供給地点で荷積みして各需要地点に配送する必要がある。航海を行うために集団内の任意の所与のトラックに関する物理的な能力を制限することがある例示的な物理的制限は、トラック重量（委任重量検査所で測定される）、トラックサイズ、およびトレイラーの数に対する任意の当該の連邦、国家、および国の規制を含む。航海を行うために集団内の任意の所与のトラックに関する能力を制限することがある例示的な時間的制約は、航海開始時間および関連の公道での最高速度に鑑みて、最初に使用可能な地点および時間を含む。海上輸送問題での港制限は、陸上輸送問題では、オペレータ国家ライセンスで置き換えることができる。
【０１３９】
同様の例は、航空機および鉄道産業でも見られる。したがって、本発明のより一般的な実施形態は、輸送スケジューリングを最適化するための方法であって、様々なタイプの製品を含む貨物を輸送するために計画期間中に開始すべき１組の航海を行うために、使用可能な輸送ビークルの集団内のビークルの割当てに関して総純利益を最大にするように最適解を計算する方法であってよい。好ましくは、総純利益は、各ビークル／航路割当てに関する個々の純利益から導出され、より好ましくは、総純利益は、各ビークル／航路割当てに関する個々の純利益の和である。ここでも、輸送ビークル／航路の割当てに関する個々の純利益はそれぞれ、概念的なビークル（ｎｏｔｉｏｎａｌ  ｖｅｈｉｃｌｅ）を使用する航路に関する市場価格、および割り当てられたビークルを使用する航路に関する予測される発生コストから導出される。
【０１４０】
これらの追加の用途では、ビークル集団は異種型でよい。例えば、集団内の各ビークルは、サイズ、形状、貨物搬送容量などが異なることがある。さらに、ビークル集団は、経済的コスト（例えば契約条件）が異なることがある。例えば、集団は、期間契約ビークル、所有ビークル、スポットビークルなどの任意の組合せを含むことができる。好ましくは、集団は、期間契約ビークルとスポットビークルの両方を備える。１つの好ましい実施形態では、集団内の各ビークルは、その契約の経済的基礎に関係なく、期間契約ビークルまたはスポットビークルに分類される。
【０１４１】
４．７  例示的な実施例
一般に、本発明の特定の実施形態による方法は、図３におけるステップに従って行われる。
【０１４２】
次に、本発明による方法の一実施形態の非限定的な例を説明する。第１に、ステップＳ３０１で、入力データが収集される。この入力データは、上述した情報または制約の任意のものでよく、地点特有の情報、供給使用可能性、需要要件、およびビークル使用可能性を含む。次に、ステップＳ３０２で、収集された入力データが、数学モデル（好ましくは混合整数線形計画モデル）に転送される。この点で、ステップＳ３０３において、（ユーザによって、またはコンピュータアプリケーションによって）データ妥当性検査を行うことができ、入力データが適切にインポートされたこと、重要な入力データが省かれていないこと、または何らかのエラーが生じていないことを保証する。この妥当性検査に合格した場合、方法は、ステップＳ３０４での実現可能性アレイの構成に進む。しかし、検査に不合格の場合、方法はステップＳ３０５に進み、そこでユーザは、入力データまたは他の制約を改訂することができる。ステップＳ３０５での改訂後、次いで新規の入力データがモデルに供給される（すなわち、方法がステップＳ３０２に戻る）。データ妥当性検査に合格すると、方法はステップＳ３０４に進む。ここで、上述したように、アレイＦＥＡＳ＿ＳＶ、ＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｌＥｖｅｎｔおよびＦｅａｓｉｂｌｅＶｅｈｉｃｌｅＶｏｙａｇｅｄＥｖｅｎｔなどの実現可能性アレイが構成される。ステップＳ３０６で、数学モデル（好ましくは混合整数線形計画モデル）が、収集されたデータを使用して構成される。このステップでは、特定の実施形態で、目的関数と制約の両方を生成することができる。ステップＳ３０７で、モデルが解かれる（例えば、デフォルトまたはカスタムソルバ設定を有する混合整数線形計画ソルバを使用する）。次いで、このモデルの結果が、ステップＳ３０８で観察される。また、ステップＳ３０８で、ユーザは、何らかの理由でモデルを再実行すべきかどうか判断する。例えば、ユーザは、結果（すなわち１組の最適化された輸送決定項目）が許容できない、または実用的でないと思われる場合には、モデルを再実行することを望むことがある。また、ユーザは、最適化の結果に対する様々な入力データの効果を比較するため、またはそうでなければ様々な結果を比較するために、モデルを再実行することを望むことがある。ユーザは、方法を再実行することを望む場合、ステップＳ３０５でモデルの様々な側面（入力パラメータおよび他の制約など）を改訂することができ、改訂された数学モデルが得られる。次いで、ユーザがもはや追加のモデルを実行することを望まなくなるまでステップＳ３０２〜Ｓ３０８を繰り返すことができる（例えば最適化された輸送決定項目の許容できるセットが決定されている）。モデルを１回または複数回実行した後、ユーザは、１つまたは複数の結果から１組の最適化された輸送決定項目を選択し、輸送方式を生成するためにこの解を使用する。次いで、ステップＳ３０９で、この方式に従って（例えば、船舶、トラック、航空機、またはそれらの任意の組合せによって）貨物が機械的に輸送される。
【０１４３】
特定の実施形態では、２つ以上の混合整数線形計画モデルが解かれ、各モデルが異なる制約、入力データ、または他の制限を有する。ユーザは、これらのモデルそれぞれに関して得られた各解を比較して、この比較に基づいて最適な輸送方式を決定することができる。ユーザは、解の１つ、または２つ以上の解の一部分の組合せを選択することができる。次いで、貨物は、選択された輸送方式に従って機械的に輸送される。
【０１４４】
５．０  結び
様々な実施形態を説明してきたが、他の実施形態もありえる。最適化された輸送方式によって貨物を輸送する方法の様々な例の前述の説明は、限定することは意図しておらず、それらの例の任意の数の修正、組合せ、および代替を採用して、輸送方式を最適化する効果を促進することができることを理解すべきである。
【０１４５】
本明細書で説明した例は単に例示にすぎず、本発明の例示的実施形態の精神および範囲から逸脱することなく、特定の他の実施形態を実施することができる。さらに、本発明のいくつかの特徴を、特定の実施形態または構成にのみ図示する場合があるが、これらの特徴を、本発明の範囲内に留めながら、様々な実施形態または構成から、および様々な実施形態または構成間で交換、追加、および除去することができる。同様に、説明して開示した方法はまた、様々な順序で行うこともでき、開示したステップのいくつかまたは全てが、本発明の精神および範囲内に依然として留まりながら、記載したのとは異なる順序で行われ得る。
【図１】
2012526326.tif 000005
【図２】
2012526326.tif 000006
【図３】
2012526326.tif 000007
【国際調査報告】
2012526326.tif 000008