(57)【要約】【課題】物資の配送コストおよび調達コストを最小化する配送計画を、これまでより効率的に作成する。【解決手段】物資の調達・配送計画を作成するシステムを提供する。このシステムは、それぞれの配送スケジュールにより物資を配送する配送手段の数と、それぞれの供給者から物資を調達する量とを変数とし、配送・調達コストの期待値を算出する第１の目的関数の値を最小化する混合整数計画問題について、これの線形緩和問題の限定問題の双対解を算出する。そして、線形緩和問題の双対問題の制約式に基づく第２の目的関数の値の変化を、配送状態の変化によって表した再帰方程式を有する動的計画問題を解くことで、限定問題の双対解が違反する制約を示す配送スケジュールを探索する。探索された場合に、探索された配送スケジュールを限定問題に追加した新たな限定問題の双対解を算出させ、探索されない場合に、限定問題の解に基づき混合整数計画問題を解く。【選択図】図４
2007210699.tif 000002
【特許請求の範囲】
【請求項１】
物資を供給者から調達して需要者に配送する計画を作成するシステムであって、
それぞれの配送スケジュールによって前記物資を配送する配送手段の数と、それぞれの前記供給者から前記物資を調達する量とを変数とし、配送コストおよび調達コストの期待値を算出する第１の目的関数の値を最小化する混合整数計画問題について、
前記混合整数計画問題の線形緩和問題において、前記物資の配送に用いることができる配送スケジュールを、予め設定した少なくとも１つの配送スケジュールに限定した限定問題を生成し、前記限定問題の双対解を算出する双対解算出部と、
前記線形緩和問題の双対問題の制約式のうち双対解を配送スケジュールによって制約する制約式に基づいて第２の目的関数を生成し、配送状態の変化に対する前記第２の目的関数の値の変化を示す再帰方程式を有する動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索するスケジュール探索部と、
前記配送スケジュールが探索されたことを条件に、探索された前記配送スケジュールを前記限定問題に追加して設定することにより新たな限定問題を生成し、前記双対解算出部により当該新たな限定問題の双対解を算出させるスケジュール追加部と、
前記配送スケジュールが探索されないことを条件に、前記限定問題の解に基づいて前記混合整数計画問題を解くことにより、前記配送手段の数および前記物資を調達すべき量を算出して出力する整数解算出部と
を備えるシステム。
【請求項２】
前記混合整数計画問題は、それぞれの期間に調達した前記物資のうち前記需要者に販売する物資の量と、配送が完了したものの前記需要者に販売していない前記物資の在庫量とを更に変数とし、
更に、複数の期間のそれぞれにおいて、当該期間内に前記配送手段により配送が完了した前記物資の量から前記需要者に販売した前記物資の量を差し引いた差分値が、当該期間における前記物資の在庫量の増分に等しい旨を示す在庫推移制約を含み、
それぞれの配送スケジュールは、前記複数の期間のそれぞれにおいて、当該期間内に前記物資の配送が完了するか否かを示し、
前記双対解算出部は、前記限定問題における期間毎の前記在庫推移制約に対応する双対解を算出し、
前記スケジュール探索部は、期間毎に算出された前記双対解を配送スケジュールに基づいて制約する式を前記第２の目的関数とした動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索する
請求項１に記載のシステム。
【請求項３】
前記混合整数計画問題は、前記複数の期間のそれぞれにおける前記物資の需要を定めた複数の需要シナリオのそれぞれに対応する前記在庫推移制約を含み、
それぞれの配送スケジュールは、前記複数の期間のそれぞれ、および、前記複数の需要シナリオのそれぞれに対応して、当該期間内かつ当該需要シナリオにおいて前記物資の配送が完了するか否かを示し、
前記双対解算出部は、前記限定問題の前記在庫推移制約に対応する双対解を更に前記需要シナリオ毎に算出し、
前記スケジュール探索部は、期間毎かつ需要シナリオ毎に算出された前記双対解を配送スケジュールに基づいて制約する式を前記第２の目的関数とした動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索する
請求項２に記載のシステム。
【請求項４】
前記混合整数計画問題は、前記配送手段の種類毎に、それぞれの配送スケジュールに用いられる当該配送手段の総数が、予め定められた当該配送手段の上限数以下である旨を示す配送手段総数制約を更に含み、
それぞれの配送スケジュールは、当該配送スケジュールによって前記物資を配送する配送手段の種類を示し、
前記双対解算出部は、前記限定問題の前記配送手段総数制約に対応する双対解を前記配送手段の種類毎に算出し、
前記スケジュール探索部は、前記在庫推移制約に対応する双対解と共に前記配送手段総数制約に対応する双対解を制約する式を前記第２の目的関数とした動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索する
請求項２に記載のシステム。
【請求項５】
前記混合整数計画問題は、それぞれの前記供給者から前記物資を調達する量が、それぞれの配送スケジュールによって１つの配送手段によって前記物資が配送される量に当該配送スケジュールによって前記物資を配送する前記配送手段の数を乗じた量と等しくなる旨を示す調達量制約を更に含み、
前記双対解算出部は、前記限定問題の前記調達量制約に対応する双対解を前記物資の供給者毎に算出し、
前記スケジュール探索部は、前記在庫推移制約に対応する双対解と共に前記調達量制約に対応する双対解を制約する式を前記第２の目的関数とした動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索する
請求項２に記載のシステム。
【請求項６】
前記スケジュール探索部は、配送スケジュールに基づく双対解の制約を、関数の値を定数値以上とする不等式として表し、当該関数に前記限定問題の双対解を代入した式を前記第２の目的関数として当該関数の値を最小化する配送スケジュールを動的計画法によって探索する
請求項２に記載のシステム。
【請求項７】
前記スケジュール探索部は、
前記複数の期間の中の最後の期間Ｔにおける配送手段の配送状態に基づき計算される前記第２の目的関数の値を算出する初期値算出部と、
前記再帰方程式に基づき、前記複数の期間の中のある期間ｔから最後の期間Ｔまでの配送状態に基づき計算される前記第２の目的関数の最小値を、前記期間ｔの次の期間ｔ＋１から期間Ｔまでの配送状態に基づき計算される前記第２の目的関数の最小値に基づいて算出する再帰式算出部と、
それぞれの配送状態における前記第２の目的関数の値を前記初期値算出部に算出させ、それぞれの期間において前記配送手段にそれぞれの配送状態を設定した場合における前記第２の目的関数の値を、前記期間Ｔから前記複数の期間の始期に向けて前記再帰式算出部によって順次算出させる算出制御部と、
前記複数の期間の始期における前記第２の目的関数の値を最小化するためにそれぞれの期間において設定された配送状態の組を、探索すべき配送スケジュールとして選択するスケジュール選択部と
を有する請求項６に記載のシステム。
【請求項８】
それぞれの配送スケジュールは、配送コストの料金体系が異なる複数種類の配送手段の何れかによって前記物資を配送するスケジュールを示し、
前記線形緩和問題の双対問題は、前記配送スケジュールに基づく双対解の制約として、配送コストによる前記双対解の制約を含み、
前記初期値算出部は、複数の種類の配送手段のそれぞれについて前記第２の目的関数の値を算出し、
前記再帰式算出部は、複数の種類の配送手段のそれぞれについて、前記期間ｔから期間Ｔまでの配送に基づき計算される前記第２の目的関数の値を、前記期間ｔ＋１から期間Ｔまでの配送に基づき計算される前記第２の目的関数の値に基づいて算出し、
前記算出制御部は、複数の種類の配送手段のそれぞれについて、それぞれの期間において前記配送手段にそれぞれの配送状態を設定した場合における前記第２の目的関数の値を算出させ、
前記スケジュール選択部は、複数の種類の配送手段のそれぞれについて算出させた、前記複数の期間の始期における前記第２の目的関数の値の中から最も小さい値を選択し、当該値を算出させるために設定した配送状態の組を、探索すべき配送スケジュールとして選択する
請求項７に記載のシステム。
【請求項９】
前記混合整数計画問題は、前記複数の期間のそれぞれにおける前記物資の需要を定めた複数の需要シナリオのそれぞれに対応する前記在庫推移制約を含み、
それぞれの配送スケジュールは、前記複数の期間のそれぞれ、および、前記複数の需要シナリオのそれぞれに対応して、当該期間内かつ当該需要シナリオにおいて前記物資の配送が完了するか否かを示す情報を含み、
前記再帰式算出部は、前記期間ｔから前記期間Ｔまでの配送状態に基づく前記第２の目的関数の値を、前記期間ｔ＋１から前記期間Ｔまでの配送状態に基づく前記第２の目的関数の値の、前記複数の期間の始期から前記期間ｔまでの需要からは区別できない複数の需要シナリオについての期待値に基づいて算出する
請求項７に記載のシステム。
【請求項１０】
複数の前記供給者から在庫地までの前記物資の配送に要する期間は供給者毎に異なり、
前記再帰式算出部は、前記期間ｔ＋１から前記期間Ｔまでの配送に基づき計算される前記第２の目的関数の最小値に基づいて、前記期間ｔから前記期間Ｔまでの配送に基づき計算される前記第２の目的関数の値を最小化するためには何れの供給者に対して調達に向かうべきかを選択し、選択した当該供給者に対して調達に向かう場合における前記第２の目的関数の値の最小値を算出する
請求項７に記載のシステム。
【請求項１１】
物資を供給者から調達して需要者に配送する計画を作成する方法であって、
それぞれの配送スケジュールによって前記物資を配送する配送手段の数と、それぞれの前記供給者から前記物資を調達する量とを変数とし、配送コストおよび調達コストの期待値を算出する第１の目的関数の値を最小化する混合整数計画問題について、
前記混合整数計画問題の線形緩和問題において、前記物資の配送に用いることができる配送スケジュールを、予め設定した少なくとも１つの配送スケジュールに限定した限定問題を生成し、前記限定問題の双対解を算出するステップと、
前記線形緩和問題の双対問題の制約式のうち双対解を配送スケジュールによって制約する制約式に基づいて第２の目的関数を生成し、配送状態の変化に対する前記第２の目的関数の値の変化を示す再帰方程式を有する動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索するステップと、
前記配送スケジュールが探索されたことを条件に、探索された前記配送スケジュールを前記限定問題に追加して設定することにより新たな限定問題を生成し、当該新たな限定問題の双対解を算出させるステップと、
前記配送スケジュールが探索されないことを条件に、前記限定問題の解に基づいて前記混合整数計画問題を解くことにより、前記配送手段の数および前記物資を調達すべき量を算出して出力するステップと
を備える方法。
【請求項１２】
物資を供給者から調達して需要者に配送する計画を作成するシステムとして、情報処理装置を機能させるプログラムであって、
それぞれの配送スケジュールによって前記物資を配送する配送手段の数と、それぞれの前記供給者から前記物資を調達する量とを変数とし、配送コストおよび調達コストの期待値を算出する第１の目的関数の値を最小化する混合整数計画問題について、
前記情報処理装置を、
前記混合整数計画問題の線形緩和問題において、前記物資の配送に用いることができる配送スケジュールを、予め設定した少なくとも１つの配送スケジュールに限定した限定問題を生成し、前記限定問題の双対解を算出する双対解算出部と、
前記線形緩和問題の双対問題の制約式のうち双対解を配送スケジュールによって制約する制約式に基づいて第２の目的関数を生成し、配送状態の変化に対する前記第２の目的関数の値の変化を示す再帰方程式を有する動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索するスケジュール探索部と、
前記配送スケジュールが探索されたことを条件に、探索された前記配送スケジュールを前記限定問題に追加して設定することにより新たな限定問題を生成し、前記双対解算出部により当該新たな限定問題の双対解を算出させるスケジュール追加部と、
前記配送スケジュールが探索されないことを条件に、前記限定問題の解に基づいて前記混合整数計画問題を解くことにより、前記配送手段の数および前記物資を調達すべき量を算出して出力する整数解算出部と
して機能させるプログラム。
【請求項１３】
物資を供給者から調達して需要者に配送する計画を作成するサービスの提供方法であって、
それぞれの配送スケジュールによって前記物資を配送する配送手段の数と、それぞれの前記供給者から前記物資を調達する量とを変数とし、配送コストおよび調達コストの期待値を算出する第１の目的関数の値を最小化する混合整数計画問題について、
前記混合整数計画問題の線形緩和問題において、前記物資の配送に用いることができる配送スケジュールを、予め設定した少なくとも１つの配送スケジュールに限定した限定問題を生成し、前記限定問題の双対解を算出するステップと、
前記線形緩和問題の双対問題の制約式のうち双対解を配送スケジュールによって制約する制約式に基づいて第２の目的関数を生成し、配送状態の変化に対する前記第２の目的関数の値の変化を示す再帰方程式を有する動的計画問題を解くことにより、前記限定問題の双対解が違反する制約を示す配送スケジュールを探索するステップと、
前記配送スケジュールが探索されたことを条件に、探索された前記配送スケジュールを前記限定問題に追加して設定することにより新たな限定問題を生成し、当該新たな限定問題の双対解を算出させるステップと、
前記配送スケジュールが探索されないことを条件に、前記限定問題の解に基づいて前記混合整数計画問題を解くことにより、前記配送手段の数および前記物資を調達すべき量を算出して出力するステップと
を備えるサービスの提供方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物資を供給者から調達して需要者に配送する計画を作成するシステムに関する。特に、本発明は、当該計画を作成するための混合整数計画問題を解くシステムに関する。
【背景技術】
【０００２】
従来、事業者は、石油や天然ガスなどの物資を調達する場合に、船舶などの配送手段を用いた調達計画を作成する。調達計画は、物資供給者との調達契約、船舶業者との間の船舶の賃貸契約、および、当該事業者が保有する自社船舶の運用計画を含む。また、運用計画は、物資の調達コストおよび配送コストをできるだけ低減するように作成されることが望ましい。このような調達計画を作成する問題は、調達契約、賃貸計画、および、運用計画のそれぞれを並行に作成しようとすると複雑となり、情報処理装置を用いて計算しても現実的な時間で終了しない場合があった。このため、従来は、調達契約、賃貸契約、および、運用計画を例えばこの順に逐次に作成していた。
【０００３】
なお、ある制約の下コストを最小化する問題は、線形計画問題や混合整数計画問題としてモデル化できる場合がある。線形計画問題の一般的な解法については非特許文献１を参照されたい。
【非特許文献１】最適化ハンドブック  Ｎｅｍｈａｕｓｅｒ，Ｇ．Ｌ．  Ｒｉｎｎｏｏｙ  Ｋａｎ，Ａ．Ｈ．Ｇ．  Ｔｏｄｄ，Ｍ．Ｊ．編  朝倉書店  １９９５
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、調達契約、賃貸契約、および、運用計画は相互に関連しており、その何れかを先に決定してしまうと、調達契約全体として調達コストおよび配送コストを最小化できない場合があった。また、物資の需要が計画期間の途中で変更する場合には、調達計画をその変更に適合させることが望ましい。しかしながら、そのような需要の変更の影響を考慮して調達計画を作成しようとすると、当該作成のために情報処理装置を用いて計算する時間は更に長くなってしまう。このように、従来は、コストを最小化する調達計画を、現実的な計算時間で作成することはできなかった。
【０００５】
そこで本発明は、上記の課題を解決することのできるシステム、方法、および、プログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明の第１の形態においては、物資を供給者から調達して需要者に配送する計画を作成するシステムであって、それぞれの配送スケジュールによって物資を配送する配送手段の数と、それぞれの供給者から物資を調達する量とを変数とし、配送コストおよび調達コストの期待値を算出する第１の目的関数の値を最小化する混合整数計画問題について、混合整数計画問題の線形緩和問題において、物資の配送に用いることができる配送スケジュールを、予め設定した少なくとも１つの配送スケジュールに限定した限定問題を生成し、限定問題の双対解を算出する双対解算出部と、線形緩和問題の双対問題の制約式のうち双対解を配送スケジュールによって制約する制約式に基づいて第２の目的関数を生成し、配送状態の変化に対する第２の目的関数の値の変化を示す再帰方程式を有する動的計画問題を解くことにより、限定問題の双対解が違反する制約を示す配送スケジュールを探索するスケジュール探索部と、配送スケジュールが探索されたことを条件に、探索された配送スケジュールを限定問題に追加して設定することにより新たな限定問題を生成し、双対解算出部により当該新たな限定問題の双対解を算出させるスケジュール追加部と、配送スケジュールが探索されないことを条件に、限定問題の解に基づいて混合整数計画問題を解くことにより、配送手段の数および物資を調達すべき量を算出して出力する整数解算出部とを備えるシステム、当該システムを用いて配送計画を作成する方法、および、当該システムとして情報処理装置を機能させるプログラムを提供する。
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【０００７】
本発明によれば、物資の配送コストおよび調達コストを最小化する配送計画を、これまでより効率的に作成することができる。
【発明を実施するための最良の形態】
【０００８】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００９】
図１は、物資を調達して需要地１０に配送し、需要者１００に販売する作業の概念図である。図１を用いて、物資の配送コストおよび調達コストの期待値を示す第１の目的関数を最小化するための混合整数計画問題を定義する。図中で、下線を付したパラメータは、混合整数計画問題の変数であり、下線を付していないパラメータは、予め与えられる定数である。
【００１０】
物資の需要地１０には、需要者１００および配送業者１１０が存在している。配送業者１１０は、需要地１０とは異なる地点に設けられた複数の供給者のそれぞれから物資を調達し、調達した物資を需要地１０まで配送する。そして、配送業者１１０は、需要地１０において物資を備蓄し、または、需要者１００に販売する。調達した物資が需要に満たない場合には、配送業者１１０は、需要地１０に存在する他の業者から物資を調達し、需要者１００に転売する。
【００１１】
需要地１０とは異なる地点に位置する複数の供給者を供給者１からＪとし、それぞれの供給者から在庫地までの物資の配送に要する期間は供給者毎に異なるものとする。以下、これらの供給者を代表して供給者ｊについて説明する。配送業者１１０と供給者ｊとの間の契約の種類は、ターム契約およびスポット契約の２種類とする。ターム契約は、計画期間（たとえば年間）全体の総調達量ｘｊと価格ξｊとを予め定める契約をいう。スポット契約は、計画期間の途中で、計画期間に含まれる複数の期間のうちある期間における調達量とその期間の価格ｓｐ（ｊ，ｔ）とを定める契約をいう。ここで、ｔは期間を表し、計画期間に含まれる複数の期間（１〜Ｔ）までの中の任意の期間とする。また、配送手段が供給者ｊに到着する毎に物資を調達することのできる、配送手段１つあたりの調達量をＡｊとする。但し、物資が石油や天然ガスなど揮発性を有する場合には、Ａｊはその揮発分を差し引いた需要地１０での量とする。また、計画期間全体で供給者ｊとの契約によって調達できる物資の総量の範囲を、下限値ＭＩＮｊおよび上限値ＭＡＸｊにより定める。
【００１２】
また、配送手段による配送スケジュールの種類を、配送スケジュール１からＫとする。実際には、配送スケジュールとは、期間の経過に応じた配送手段の状態変化の組み合わせとして定義される。具体的には、配送手段（例えば船舶、航空機またはトラックなど）が、指定された何れかの供給先に向かい、物資を調達して需要地１０に帰還する一連の動作が、配送スケジュールとなる。このため、想定し得る配送スケジュールの数は膨大であり、それら全てを計算の対象とするのは現実的ではない。但し、図１では、説明の便宜上、全ての配送スケジュールが判明していると仮定した場合の配送スケジュールを、配送スケジュール１からＫとする。
【００１３】
任意の配送スケジュールｋについて説明する。配送スケジュールｋによって物資を配送する配送手段の数をｚｋとする。例えば、配送手段が船舶の場合に、ｚｋは船舶の隻数を示す。また、配送スケジュールｋに要する配送手段１つあたりの配送コストをηｋとする。また、配送スケジュールｋによる配送手段の種類をΓｇ，ｋによって表す。配送手段の種類ｇは、定期運行、チャーター運行、および、自社運行の３種類とする。配送手段が船舶の場合、その種類は、定期船、チャーター船、および、自社船の３種類である。定期船は、ターム契約により供給される物資のみを配送する。また、定期船は、需要シナリオに関わらず予め定められた配送状態を採るものとする。即ち、定期船の配送スケジュールは、計画期間の途中で需要動向に応じて変更することができないものとする。また、これらの種類の配送手段は、配送コストについて異なる料金体系を有する。即ち、定期運行の配送コストは計画期間全体について予め定められ、それぞれの期間の配送状態に関わらず一定である。一方で、チャーター船および定期船には、稼動期間あたりの配送コストが定められているものとする。
【００１４】
チャーター船および自社船のそれぞれは、ターム契約およびスポット契約の何れによって供給される物資も配送するものとする。即ち例えば、チャーター船および自社船のそれぞれは、ある期間においてはターム契約の物資を配送し、他の期間においてはスポット契約の物資を配送してよい。この場合も、需要シナリオに関わらず予め定められた配送状態を採るものとする。また、チャーター船および自社船のそれぞれは、スポット契約によって供給される物資のみを配送してもよい。この場合には、需要シナリオに応じて計画期間の途中で動作を変更できるものとする。なお、パラメータΓｇ，ｋは、配送スケジュールｋの配送手段がｇである場合に１を採り、ｇで無い場合に０を採る。
【００１５】
配送業者１１０における計画期間の初期の在庫量をｈ０とする。また、期間ｔおよび需要シナリオがｓにおいて、供給者から配送業者への配送が完了したものの需要者１００に販売していない物資の在庫量をｈｓ，ｔとする。また、需要地１０に存在する他の業者から配送業者１１０が購入する物資の購入量をｖｓ，ｔとし、その購入価格をσｔとする。また、配送業者１１０がある期間ｔにおいてそれぞれの供給者から調達した物資のうち需要者１００に販売する販売量を変数ｗｓ，ｔとする。更に、配送業者１１０が他の業者から購入して需要者１００に転売する物資の量は、購入量と同じｖｓ，ｔとする。また、予め予測された複数の需要シナリオを１からＳとし、任意の需要シナリオｓの生起確率をｐｓとする。また、任意の需要シナリオｓの期間ｔにおいて予想される需要をｄｓ，ｔとする。
【００１６】
また、配送業者１１０には、計画作成システム４０と、環境データベース３０とが設けられている。計画作成システム４０は、配送業者１１０が供給者から物資を調達して需要者１００に配送する計画を作成する。また、環境データベース３０は、計画の作成に用いられる各種のパラメータ、具体的には、下線の付されていないパラメータが記録されている。但し、配送スケジュールｋに関するパラメータについては、想定しうる全ての配送スケジュールのうち一部のみの配送スケジュールに関するものに限られる。
【００１７】
図２は、配送スケジュールｋの具体例を示す。配送スケジュールｋは、計画期間に含まれる複数の期間のそれぞれに対応する、配送手段の配送状態の組み合わせを示す。それぞれの期間における配送状態は、当該期間内に物資の配送が完了するか否かを示す。例えば、計画期間（年間）の第１週において、配送手段は需要地１０を出発して配送中の状態となる。第３週において、配送手段は供給者１に到着して物資を積み込む。そして、第５週において、配送手段は需要地１０に期間して物資を積み下ろし、配送を完了する。更に、配送手段は、第６週において需要地１０を再度出発して、第８週に供給者２に到着する。配送手段は、そこで物資を積み込み、第１０週に需要地１０に帰還して配送を完了する。
【００１８】
パラメータβは、配送スケジュールｋに従う配送手段の配送状態を示す。具体的には、βｋ、ｊ、ｓ、ｔは、需要シナリオｓにおける期間ｔにおいて、配送スケジュールｋに従う配送手段によって供給者ｊからの調達が完了する場合に１を採り、当該調達が完了しない場合に０を採る。したがって、図２の例ではβｋ、１、ｓ、５＝１となり、βｋ、２、ｓ、１０＝１となる。第１週から第４週までや、第６週から第９週までについては、βｋ、ｊ、ｓ、ｔ＝０である。
【００１９】
また、パラメータδは、配送スケジュールｋに従う配送手段による物資の配送量を示す。具体的には、δｊ，ｋは、配送スケジュールｋに従う１つの配送手段によって、計画期間全体において供給者ｊから調達する物資の総量を示す。供給者１から１度しか調達しない場合には、第５週におけるその１度の調達量（例えば５０トン）がδ１，ｋとなる。同様に、供給者２から１度しか調達しない場合には、第１０週におけるその１度の調達量がδ２，ｋとなる。
【００２０】
図３は、環境データベース３０のデータ構造の一例を示す。環境データベース３０は、図１および図２を参照して説明した定数のパラメータに加えて、複数の需要シナリオを記録している。複数の需要シナリオのそれぞれは、計画期間に含まれる複数の期間のそれぞれにおける物資の需要を定めるものである。図３の例において、環境データベース３０は、４つの需要シナリオを記録している。それぞれの需要シナリオは、第１の期間から第５の期間のそれぞれにおける需要者１００の需要を示している。
【００２１】
例えば、第１の需要シナリオにおいて、第１の期間から第５の期間までのそれぞれの期間の需要は、この順に、５、５、１０、１０、および、５である。また、第２の需要シナリオにおいて、第１の期間から第５の期間までのそれぞれの期間の需要は、この順に、５、５、１０、１０、および、１０である。また，第３の需要シナリオにおいて、第１の期間から第５の期間までのそれぞれの期間の需要は、この順に、５、５、５、５、および、５である。また、第４の需要シナリオにおいて、第１の期間から第５の期間までのそれぞれの期間の需要は、この順に、５、５、５、５、および、１０である。
【００２２】
この例において、第１の期間の時点では、第１の需要シナリオおよび第２の需要シナリオのそれぞれにおける需要は共に５で同一であり、配送業者は、第１の需要シナリオおよび第２の需要シナリオを区別できない。本実施形態の混合整数計画問題では、このような需要シナリオの区別の可否を示す定数パラメータＢを導入する。Ｂ（ｓ，ｓ´，ｔ）は、ある需要シナリオｓと他の需要シナリオｓ´が期間ｔにおいて区別される場合に０を、区別されない場合に１を採る。例えば、Ｂ（１，２，１）＝１である。また、第３の期間において第３の需要シナリオおよび第４の需要シナリオは区別されないため、Ｂ（３，４，３）＝１である。また、第５の期間において第３の需要シナリオおよび第４の需要シナリオは区別されるため、Ｂ（３，４，５）＝０である。
【００２３】
混合整数計画問題は、以上の図１から図３を参照して説明したパラメータについて、以下の式（１）に示す第１の目的関数の値を最小化する問題となる。
【数１】
2007210699.tif 000003
但し、混合整数計画問題は、物資の配送に関し以下の制約を有する。
【００２４】
１．需要と供給の一致制約
この制約は、それぞれの期間について、他の業者から物資を購入して転売した量に、供給者から調達した物資を需要者に販売した量を加えると、その期間の需要に等しくなる旨を示す。この制約は、以下の式（２）のように表される。
【数２】
2007210699.tif 000004
【００２５】
２．在庫推移制約
この制約は、複数の期間のそれぞれ、および、複数の需要シナリオのそれぞれにおいて、当該期間内に配送手段により配送が完了した物資の量から需要者に販売した物資の量を差し引いた差分値が、当該期間における物資の在庫量の増分に等しい旨を示す。この制約は、以下の式（３）のように表される。
【数３】
2007210699.tif 000005
但し、配送する物資が石油や天然ガスなど揮発性を有する場合には、配送中や在庫中であっても期間の経過に応じて物資が減少する。１期間あたりの減少率をＥとする。
【００２６】
３．配送手段総数制約
配送手段の種類毎に、それぞれの配送スケジュールに用いられる配送手段の総数の上限数が予め定められているものとする。この上限数をＮｇとする。ｇは、既に述べたように、配送手段の種類を示す。配送手段総数制約は、配送手段の種類毎に、それぞれの配送スケジュールに用いられる当該配送手段の総数が、この上限数Ｎｇ以下である旨を示す。この制約は、以下の式（４）のように表される。
【数４】
2007210699.tif 000006
【００２７】
４．ターム契約量の一致制約
この制約は、それぞれの供給者から物資を調達する量が、それぞれの配送スケジュールによって１つの配送手段によって物資が配送される量に当該配送スケジュールによって前記物資を配送する配送手段の数を乗じた量と等しくなる旨を示す。この制約は、以下の式（５）のように表される。
【数５】
2007210699.tif 000007
５．調達量制約
また、それぞれの供給者からターム契約によって供給される物資の総量には、範囲が設けられている。この範囲に基づく制約は、以下の式（６）および式（７）のように表される。
【数６】
2007210699.tif 000008
【数７】
2007210699.tif 000009
【００２８】
６．予測不可能制約
また、需要シナリオは予測不可能であるものとする。即ち、期間ｔの時点で区別できない複数の需要シナリオのそれぞれについて、期間１から期間ｔまでは何れの需要シナリオにおいても同一の配送を行うものとする。このことから、以下の式（８）および式（９）の制約が導かれる。
【数８】
2007210699.tif 000010
【数９】
2007210699.tif 000011
【００２９】
７．変数の値域
それぞれの変数の値域を、以下のように定める。
【数１０】
2007210699.tif 000012
【００３０】
図４は、計画作成システム４０の機能構成を示す。計画作成システム４０は、双対解算出部４００と、スケジュール探索部４１０と、スケジュール追加部４２０と、整数解算出部４３０とを有する。以下、図４を参照して混合整数計画問題の解法を説明するが、その基本アイデアは概ね以下の通りである。既に述べたように、配送スケジュールは配送状態の組み合わせであるので、その種類は膨大である。このため、本実施形態においては、物資の配送に用いることができる配送スケジュールを、予め設定した少なくとも１つの配送スケジュールに限定した限定問題を解く。そして、その限定問題に追加すると解を改善する他の配送スケジュールを探索し、それが探索された場合にはそれを限定問題に追加して再度その限定問題を解く。解を改善する配送スケジュールが探索されなくなるまでこれを繰り返す。
【００３１】
最適解が算出できたか否かの判断は、双対定理を利用することで、迅速な処理として実現できる。具体的には、双対定理より、「限定問題の双対解が、もとの線形緩和問題の双対問題の実行可能解となっている」場合には、限定問題の解がもとの線形緩和問題の解と等しくなる。即ち、限定問題の双対解を求め、その双対解がもとの線形緩和問題の何れの制約をも満たすことを確かめることによって判断できる。この判断は、動的計画法を利用した迅速な処理として実現できる。以下、これらの処理機能について具体的に述べる。
【００３２】
双対解算出部４００は、混合整数計画問題の線形緩和問題において、物資の配送に用いることができる配送スケジュールを、予め設定した少なくとも１つの配送スケジュールに限定した限定問題を生成し、その限定問題の双対解を算出する。つまり、上述の問題設定において可能な全ての配送スケジュールを予め設定する必要はなく、少数の配送スケジュールを予め設定すればよい。このため、双対解算出部４００による算出処理は、極めて迅速に完了する。
【００３３】
双対解算出部４００によって算出される双対解を以下のように表す。需要と供給の一致制約に対応する双対解を変数μｓ，ｔと表し、在庫推移制約に対応する双対解をπｓ，ｔとする。これらの双対解は、期間毎かつ需要シナリオ毎に算出される。また、配送手段総数制約に対応する双対解を変数λｇと表す。また、ターム契約量の一致制約に対応する双対解を変数θｊと表し、ターム契約量の上限を定める制約に対応する双対解を変数φｊと表し、ターム契約量の下限を定める制約に対応する双対解を変数Φｊと表す。これらの双対解は、供給者ｊ毎に算出される。また、他の業者から購入する物資の量が予測不可能である旨を示す制約に対応する双対解を変数χｓ，ｓ´，ｔと表し、供給者から調達した物資のうち需要者に販売する量が予測不可能である旨を示す制約に対応する双対解を変数ψｓ，ｓ´，ｔと表す。
【００３４】
もとの線形緩和問題の双対問題の目的関数を以下の式（１１）に示し、もとの線形緩和問題の双対問題に含まれる制約式を、以下の式（１２）から式（１６）に示す。
【数１１】
2007210699.tif 000013
【数１２】
2007210699.tif 000014
【数１３】
2007210699.tif 000015
【数１４】
2007210699.tif 000016
【数１５】
2007210699.tif 000017
【数１６】
2007210699.tif 000018
【００３５】
なお、双対解を示す変数の値域は式（１７）の通りである。
【数１７】
2007210699.tif 000019
【００３６】
ここで、限定問題の双対問題は、全ての配送スケジュールを処理の対象としない点で、もとの線形緩和問題の双対問題とは異なる。具体的には、上述の式（１３）において、配送スケジュールを示す変数ｋの値域は、１からＫではなく、それより狭い所定の範囲となる。即ち、限定問題の双対問題に含まれる制約は、線形緩和問題の双対問題に含まれる制約よりも少ない。このため、限定問題の双対解は、式（１３）に示す制約に違反している可能性がある。スケジュール探索部４１０は、限定問題の双対解を、この式（１３）の制約に違反させるような配送スケジュールを探索することによって、限定問題の解が線形緩和問題の解となっているかを確かめる。
【００３７】
具体的には、まず、スケジュール探索部４１０は、式（１３）に基づいて第２の目的関数を生成する。なお、式（１３）は、双対解を配送スケジュールによって制約する。即ち、β、δ、Γおよび配送コストηは、配送スケジュールによって定まる値であり、式（１３）は、これらのパラメータを用いて双対解を制約する不等式を構成する。スケジュール探索部４１０は、この制約を、関数の値を定数値以上とする不等式として表し、この関数に限定問題の双対解を代入した式を第２の目的関数とする。具体的には、スケジュール探索部４１０は、式（１３）の右辺式から左辺式を引いた式を第２の目的関数として生成してもよい。
【００３８】
この第２の目的関数は、期間毎かつ需要シナリオ毎に算出された双対解πｓ，ｔを配送スケジュールに基づいて制約する式を第１項に含む。また、この目的関数は、在庫推移制約に対応する双対解πｓ，ｔを制約する第１項のみならず、配送手段総数制約に対応する双対解λｇを制約する第２項と、ターム契約量の一致制約に対応する双対解θｊを制約する第３項とを更に含む。
【００３９】
次に、スケジュール探索部４１０は、配送状態の変化に対する第２の目的関数の値の変化を示す再帰方程式を有する動的計画問題を解くことにより、限定問題の双対解が違反する制約を示す配送スケジュールを探索する。探索方法の詳細は後述するが、概ね以下の通りである。ある期間ｔから計画期間の最終期であるＴまでの配送状態に基づく第２の目的関数の値を、当該期間ｔの次の期間ｔ＋１から期間Ｔまでの配送状態に基づく第２の目的関数の値によって定義する。この定義を動的計画問題の再帰方程式とする。そして、スケジュール探索部４１０は、それぞれの期間において第２の目的関数の値を最小とする配送状態を、期間Ｔから期間１に遡って順次計算する。そして、期間１において第２の目的関数の値が最も小さい配送状態の組み合わせを選択し、それを探索すべき配送スケジュールとする。
【００４０】
スケジュール追加部４２０は、配送スケジュールが探索されたことを条件に、探索されたその配送スケジュールを限定問題に追加して設定することにより新たな限定問題を生成する。そして、スケジュール追加部４２０は、双対解算出部４００により当該新たな限定問題の双対解を算出させる。整数解算出部４３０は、配送スケジュールが探索されないことを条件に、限定問題の解に基づいて混合整数計画問題を解くことにより、配送手段の数および物資を調達すべき量を算出して出力する。
【００４１】
図５は、スケジュール探索部４１０の機能構成を示す。スケジュール探索部４１０は、初期値算出部５００と、再帰式算出部５１０と、算出制御部５２０と、スケジュール選択部５３０とを有する。初期値算出部５００は、計画期間に含まれる複数の期間の中の最後の期間Ｔにおける配送手段の配送状態に基づき計算される第２の目的関数の値を算出する。再帰式算出部５１０は、再帰方程式に基づき、計画期間の中のある期間ｔから最後の期間Ｔまでの配送状態に基づき計算される第２の目的関数の最小値を、この期間ｔの次の期間ｔ＋１から期間Ｔまでの配送状態に基づき計算される第２の目的関数の最小値に基づいて算出する。
【００４２】
算出制御部５２０は、それぞれの配送状態における第２の目的関数の値を初期値算出部５００に算出させ、それぞれの期間において配送手段にそれぞれの配送状態を設定した場合における第２の目的関数の値を、期間Ｔから計画期間の始期に向けて再帰式算出部５１０によって順次算出させる。スケジュール選択部５３０は、計画期間の始期における第２の目的関数の値を最小化するためにそれぞれの期間において設定された配送状態の組を、探索すべき配送スケジュールとして選択する。
【００４３】
図６は、混合整数計画問題を解くことにより調達・配送計画を作成する処理のフローチャートを示す。双対解算出部４００は、線形緩和問題の限定問題の双対解を算出する（Ｓ６００）。スケジュール探索部４１０は、配送スケジュールに基づき双対解を制約する式に基づいて動的計画問題の目的関数を生成し、この動的計画問題を解くことにより、限定問題が違反する制約を示す配送スケジュールを探索する（Ｓ６１０）。配送スケジュールが探索されたことを条件に（Ｓ６２０：ＹＥＳ）、スケジュール追加部４２０は、探索されたこの配送スケジュールを限定問題に追加して設定することにより新たな限定問題を生成する（Ｓ６３０）。そして、スケジュール追加部４２０は、Ｓ６００に処理を戻して、当該新たな限定問題の双対解を算出させる。
【００４４】
一方で、配送スケジュールが探索されなかったことを条件に（Ｓ６２０：ＮＯ）、整数解算出部４３０は、限定問題の解に基づいて混合整数計画問題を解くことにより、配送手段の数および物資を調達すべき量を算出して出力する（Ｓ６４０）。この混合整数計画問題は、全ての配送スケジュールに基づく制約を含むのではなく、スケジュール追加部４２０によって順次追加された配送スケジュールのみに基づく制約を含む。このため、混合整数計画問題の規模を小さくすることができ、処理を効率化することができる。また、限定問題の実数解を収束判定などに用いることで、混合整数計画問題を解く処理を一層効率化できる。
【００４５】
図７は、配送状態の状態遷移の一例を示す。図７を参照して、配送手段が採りうる配送状態について説明する。配送状態は、以下の２種類に分類される。
１．ｓｔａｔｅ（１，ｊ）：供給者ｊから物資の調達が完了する状態
２．ｓｔａｔｅ（２，ｔ）：配送手段が配送中または非稼動の状態。変数ｔは、出発してから経過した期間の数を示す。但し、ｔ＝１の場合は非稼動の状態を含む。また、１≦ｔ≦ｍａｘｊｌｔ（ｊ）−１であり、ｌｔ（ｊ）は供給者ｊから物資を調達するために要する期間の数を示す。
【００４６】
配送状態の遷移には、以下の４種類がある。
１．ｓｔａｔｅ（２，ｔ−１）→ｓｔａｔｅ（２，ｔ）：配送が進行している状態
２．ｓｔａｔｅ（２，ｌｔ（ｊ）−１）→ｓｔａｔｅ（１，ｊ）：配送中から調達完了への遷移
３．ｓｔａｔｅ（１，ｊ）→ｓｔａｔｅ（２，１）：次の調達、または、非稼動状態への遷移
４．ｓｔａｔｅ（２，１）→ｓｔａｔｅ（２，１）：次の配送がすぐには行われない状態の継続
【００４７】
図７では具体例として、供給者１および供給者２の何れかに対して物資を調達する場合の配送状態の遷移を示す。図７では供給者１から物資を調達するために要する期間を３とし、供給者２から物資を調達するために要する期間を４とする。図中の斜線を付した状態は、配送中を示し、斜線を付していない状態は、配送が完了した状態を示す。供給者１に調達に向かう場合には、ｓｔａｔｅ（２，１）を初期状態とし、期間の経過によりｓｔａｔｅ（２，２）に状態変化する。そして、ｓｔａｔｅ（１，１）に状態変化して配送を完了し、ｓｔａｔｅ（２，１）に戻る。一方、供給者２に調達に向かう場合には、ｓｔａｔｅ（２，１）を初期状態とし、期間の経過によりｓｔａｔｅ（２，２）およびｓｔａｔｅ（２，３）に状態変化する。そして、ｓｔａｔｅ（１，２）に状態変化して配送を完了し、ｓｔａｔｅ（２，１）に戻る。
【００４８】
図８は、Ｓ６１０における処理の詳細を示す。算出制御部５２０は、図８に示すように、複数の種類の配送手段のそれぞれについて、当該配送手段によって物資を配送した場合の第２の目的関数の最小値を算出する。具体的には、まず、スケジュール探索部４１０は、定期運行によってターム契約の物資を配送する配送スケジュールのうち、第２の目的関数を最小化する配送スケジュールを動的計画法によって探索する（Ｓ７００）。この探索に用いる再帰方程式は以下の通りである。但し、期間ｔから期間Ｔまでの配送状態に基づく第２の目的関数の値をｃｏｓｔ（ｓｔａｔｅ，ｔ）とする。
【数１８】
2007210699.tif 000020
【００４９】
計画期間全体について生じるコストは、計画期間の最終期である期間Ｔに生じるものとする。したがって、式（１８）の第１式に示すように、定期運行に伴う配送コストは期間Ｔにおいてのみ発生する。その大きさは予め定められた定数であるものとし、式では（定期船の賃貸価格）と表す。これは、式（１３）の右辺式のηｋに対応する。また、配送状態の組み合わせ関わらず目的関数の値に寄与する値も、期間Ｔにおいてのみ目的関数に寄与するものとみなす。即ち、双対解λｇ＝定期運行の値は、期間Ｔにおいてのみ目的関数に寄与する。これは、式（１３）の左辺式の第２項に対応する。その他、配送状態の組み合わせに基づく値は、１回の配送毎に目的関数に寄与するものとする。即ち、配送状態が配送完了状態から配送中の状態に遷移する毎に、１回の配送に基づく値を目的関数に寄与させる。
【００５０】
また、式（１８）の第４式に示すように、スケジュール探索部４１０は、期間ｔから期間Ｔまでの配送に基づき計算される第２の目的関数の値を最小化するためには何れの供給者に対して調達に向かうべきかを選択し、選択した当該供給者に調達に向かう場合における第２の目的関数の値の最小値を算出する。式（１８）の数４式では、ｓｔａｔｅ（２，ｕ）からｓｔａｔｅ（１，ｊ）への状態遷移が、調達の所要期間をｕ−１とする何れかの供給者からの調達を示す。また、ｓｔａｔｅ（２，ｕ）からｓｔａｔｅ（２，ｕ＋１）への状態遷移が、それよりも多くの所要期間を要する他の供給者からの調達を示す。
【００５１】
次に、スケジュール探索部４１０は、チャーター運行または自社運行によってターム契約およびスポット契約の双方の物資を配送する配送スケジュールのうち、第２の目的関数を最小化する配送スケジュールを探索する（Ｓ７１０）。この探索に用いる再帰方程式は以下の通りである。
【数１９】
2007210699.tif 000021
【００５２】
式（１９）は式（１８）と比較して、ηｋに対応する値の算出方法が異なっている。即ち、式（１９）の第５式および第６式は、新たな調達に向かう期間ｔにおいて、ターム契約およびスポット契約の何れによる調達の方が目的関数の値を小さくできるかを判断することを示している。ターム契約の方が少ない場合には、式（１３）におけるδの項に対応する値を第２の目的関数に寄与させる。即ち、−（１回の調達量）・θｊが第２の目的関数に加えられる。一方で、スポット契約の方が少ない場合には、式（１３）における右辺式に対応する値を第２の目的関数に寄与させる。即ち、スポット調達のコストｓｐ（ｊ，ｔ）が第２の目的関数に加えられる。
【００５３】
次に、スケジュール探索部４１０は、チャーター運行または自社運行によってスポット契約の物資を配送する配送スケジュールのうち、第２の目的関数を最小化する配送スケジュールを探索する（Ｓ７２０）。この探索に用いる再帰方程式は以下の通りである。
【数２０】
2007210699.tif 000022
【００５４】
但し、この式（２０）において、期間ｔにおいて需要シナリオｓとの区別ができない需要シナリオの集合をＳ（ｓ，ｔ）とする。即ち、Ｓ（ｓ，ｔ）は、計画期間の始期から期間ｔまでの間の需要が需要シナリオｓと同一の需要シナリオの集合である。また、期間ｔにおいて需要シナリオｓとの区別ができない需要シナリオの集合を、期間ｔ＋１でも区別ができない需要シナリオの集合に分割したときのｍ番目の集合をＳ（ｓ，ｔ，ｍ）とする。
【００５５】
式（２０）は式（１８）と比較して、ηｋに対応する値の算出方法が異なっている。即ち、式（２０）の第１式、第２式、第５式、および、第６式では、配送が完了する毎に、スポット契約による調達コストｓｐ（ｊ，Ｔ）が第２の目的関数に加えられる。また、式（２０）の第５から第７式は、需要シナリオの予測不可能制約に基づく。即ち、再帰式算出部５１０は、期間ｔから期間Ｔまでの配送状態に基づく第２の目的関数の値を、期間ｔ＋１から期間Ｔまでの配送状態に基づく第２の目的関数の値の、複数の需要シナリオについての期待値に基づいて算出する。算出に用いられる需要シナリオは、計画期間の始期から期間ｔまでの需要からは区別できないもののみであり、その他の需要シナリオは用いられない。
【００５６】
そして、スケジュール選択部５３０は、これら複数の種類の配送手段のそれぞれについて算出させた、複数の期間の始期における第２の目的関数の値の中から最も小さい値を選択し、当該値を算出させるために設定した配送状態の組を、探索すべき配送スケジュールとして選択する（Ｓ７３０）。
【００５７】
図９は、Ｓ７００、Ｓ７１０、および、Ｓ７２０における処理の詳細を示す。また、図１０は、Ｓ８２０における処理の概念図を示す。計画作成システム４０は、図９に示す順序に従い処理を進め、その結果を図１０のような構造の表に記録していく。Ｓ７００およびＳ７１０において用いられる表を図１０の上側に例示する。Ｓ７２０において用いられる表を図１０の下側に例示する。図９および図１０を参照して、配送スケジュールを探索する処理の詳細を述べる。
【００５８】
初期値算出部５００は、複数の配送手段のそれぞれについて、期間Ｔにおける配送手段の配送状態に基づき計算される第２の目的関数の値を算出する（Ｓ８００）。即ち、初期値算出部５００は、Ｓ７００においては定期運行の配送手段のみについて、その配送状態に基づき計算される第２の目的関数の値を算出する。また、初期値算出部５００は、Ｓ７１０においてはチャーター運行および自社運行の配送手段のみについて、その配送手段に基づき計算される第２の目的関数の値を算出する。また、初期値算出部５００は、Ｓ７２０においてはチャーター運行および自社運行の配送手段のみについて、その配送手段に基づき計算される第２の目的関数の値を算出する。
【００５９】
例えば図１０に示すように、初期値算出部５００は、期間Ｔにおけるｓｔａｔｅ（１，１）からｓｔａｔｅ（１，Ｊ）までのそれぞれについて、その配送状態によって生じる第２の目的関数の値を算出する。図１０の例では、期間Ｔにおいて供給者１から物資を調達する場合の第２の目的関数の値は１００である。また、期間Ｔにおいて供給者２から物資を調達する場合の第２の目的関数の値は８０である。また、期間Ｔにおいて供給者ｊから物資を調達する場合の第２の目的関数の値は５０である。また、期間Ｔにおいて供給者Ｊから物資を調達する場合の第２の目的関数の値は４０である。この値の算出には、Ｓ７００においては式（１８）の第１式が用いられ、Ｓ７１０においては式（１９）の第１および第２式が用いられ、Ｓ７２０においては式（２０）の第１および第２式が用いられる。
【００６０】
また、初期値算出部５００は、期間Ｔにおけるｓｔａｔｅ（２，１）からｓｔａｔｅ（２，Ｕ）までのそれぞれについて、その配送状態によって生じる第２の目的関数の値を算出する。例えば定期運行の場合、配送中や非稼動の状態で計画期間を終えた場合には、期間Ｔのみに注目すると配送コストは生じない。このため、期間Ｔのみの配送状態によっては第２の目的関数の値は０となる。但し、本実施形態では、計画期間全体を通して計上されるコストを期間Ｔの目的関数の値に寄与させているので、図１０の例では目的関数の値が１０となっている。この値の算出には、Ｓ７００においては式（１８）の第２式が用いられ、Ｓ７１０においては式（１９）の第３および第４式が用いられる。
【００６１】
なお、Ｓ７２０において、初期値算出部５００は、それぞれの供給先に加えて、それぞれの需要シナリオについても、期間Ｔの配送状態によって生じる第２の目的関数の値を算出する。即ち、初期値算出部５００は、需要シナリオｓ（１≦ｓ≦Ｓ）のそれぞれについて、配送状態がｓｔａｔｅ（１，ｊ）（１≦ｊ≦Ｊ）の場合の第２の目的関数の値を算出する。また、初期値算出部５００は、需要シナリオｓ（１≦ｓ≦Ｓ）のそれぞれについて、配送状態がｓｔａｔｅ（２，ｕ）（１≦ｕ≦Ｕ）の場合の第２の目的関数の値を算出する。この値の算出には、式（２０）の第１〜４式が用いられる。この計算結果は、例えば、図１０の下側の表に記録される。
【００６２】
図９に戻る。次に、算出制御部５２０は、期間Ｔの直前の期間（Ｔ−１）から期間１に向けて遡ったそれぞれの期間（期間ｔとする）について、以下の処理を繰り返す（Ｓ８１０）。再帰式算出部５１０は、複数の種類の配送手段のそれぞれについて、期間ｔから期間Ｔまでの配送に基づき計算される第２の目的関数の値を、期間ｔ＋１から期間Ｔまでの配送に基づき計算される第２の目的関数の値に基づいて算出する（Ｓ８２０）。
【００６３】
例えば、図１０に示すように、Ｓ８００において計算された目的関数の値は、図１０の表の最右列に記録されている。このため、期間（Ｔ−１）から期間Ｔまでに基づき計算される目的関数の値を求めるためには、期間Ｔにおいて生じる目的関数の値に、期間（Ｔ−１）において生じる目的関数の値を加えればよい。再帰式算出部５１０は、期間（Ｔ−１）において採りうる全ての配送状態のそれぞれについて、当該配送状態から期間Ｔのそれぞれの配送状態への状態遷移によって生じる目的関数の値を算出する。そして、再帰式算出部５１０は、その値を最も小さくする期間Ｔにおける配送状態を選択し、その配送状態への遷移によって生じる目的関数の値を記録する。更に、再帰式算出部５１０は、目的関数をその値とするには期間Ｔにおいてどの配送状態に遷移すべきかを記録してもよい。この値の算出には、Ｓ７００においては式（１８）の第３および第４式が用いられ、Ｓ７１０においては式（１９）の第５〜第７式が用いられる。なお、Ｓ７２０においては、更に複数の需要シナリオのそれぞれについても目的関数の値が算出される。この値の算出には、式（２０）の第５〜第７式が用いられる。
【００６４】
図９に戻る。算出制御部５２０は、以上の処理をそれぞれの期間ｔについて繰り返す（Ｓ８３０）。スケジュール選択部５３０は、期間１から期間Ｔまでの配送状態に基づく第２の目的関数の値を最小とする配送スケジュールを選択する（Ｓ８４０）。具体的には、スケジュール選択部５３０は、図１０に例示する表の最左列を走査し、最も小さい値を選択する。そして、スケジュール選択部５３０は、その値を算出するために配送手段が採るべき配送状態の組み合わせを配送スケジュールとして選択する。
【００６５】
図１１は、計画作成システム４０として機能する情報処理装置９００のハードウェア構成の一例を示す。情報処理装置９００は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＢＩＯＳ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００６６】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＢＩＯＳ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００６７】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、情報処理装置９００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０又はハードディスクドライブ１０４０に提供する。
【００６８】
また、入出力コントローラ１０８４には、ＢＩＯＳ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ１０１０は、情報処理装置９００の起動時にＣＰＵ１０００が実行するブートプログラムや、情報処理装置９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、入出力チップ１０７０を介してＲＡＭ１０２０またはハードディスクドライブ１０４０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００６９】
情報処理装置９００に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び/又は入出力コントローラ１０８４を介して、記録媒体から読み出され情報処理装置９００にインストールされて実行される。プログラムが情報処理装置９００等に働きかけて行わせる動作は、図１から図１０において説明した計画作成システム４０における動作と同一であるから、説明を省略する。
【００７０】
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムを情報処理装置９００に提供してもよい。
【００７１】
以上、図１から図１１を参照して説明したように、計画作成システム４０によれば、小さい限定問題を徐々に拡大して線形緩和問題の最適解を探索することにより、最適解の探索に要する計算時間を低減できる。また、最適解の探索は、動的計画法を用いて迅速な処理によって実現される。これにより、物資の調達契約および配送契約を含み、かつ、複数の需要シナリオを考慮した計画を、これまでより効率的に作成することができる。
【００７２】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００７３】
【図１】図１は、物資を調達して需要地１０に配送し、需要者１００に販売する作業の概念図である。
【図２】図２は、配送スケジュールｋの具体例を示す。
【図３】図３は、環境データベース３０のデータ構造の一例を示す。
【図４】図４は、計画作成システム４０の機能構成を示す。
【図５】図５は、スケジュール探索部４１０の機能構成を示す。
【図６】図６は、混合整数計画問題を解くことにより調達・配送計画を作成する処理のフローチャートを示す。
【図７】図７は、配送状態の状態遷移の一例を示す。
【図８】図８は、Ｓ６１０における処理の詳細を示す。
【図９】図９は、Ｓ７００、Ｓ７１０、および、Ｓ７２０における処理の詳細を示す。
【図１０】図１０は、Ｓ８２０における処理の概念図を示す。
【図１１】図１１は、計画作成システム４０として機能する情報処理装置９００のハードウェア構成の一例を示す。
【符号の説明】
【００７４】
１０  需要地
３０  環境データベース
４０  計画作成システム
１００  需要者
１１０  配送業者
４００  双対解算出部
４１０  スケジュール探索部
４２０  スケジュール追加部
４３０  整数解算出部
５００  初期値算出部
５１０  再帰式算出部
５２０  算出制御部
５３０  スケジュール選択部
【図１】
2007210699.tif 000023
【図２】
2007210699.tif 000024
【図３】
2007210699.tif 000025
【図４】
2007210699.tif 000026
【図５】
2007210699.tif 000027
【図６】
2007210699.tif 000028
【図７】
2007210699.tif 000029
【図８】
2007210699.tif 000030
【図９】
2007210699.tif 000031
【図１０】
2007210699.tif 000032
【図１１】
2007210699.tif 000033