"物体が1つずつ配置され得るブロックが1以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成する物体再配置計画装置であって、前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する移動要素抽出部と、前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を探索する順序制約探索部と、抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する、有向グラフ作成部とを備える、物体再配置計画装置。前記順序制約探索部は、或ブロックに関わる1以上の物体の移動が、当該ブロックから出発する移動、当該ブロックを通過する移動、当該ブロックへ到着する移動の順となるように、前記複数の移動要素間の順序の制約を探索する、請求項1に記載の物体再配置計画装置。前記有向グラフにおいて、前記節点および前記有向矢印により形成されるループを深さ優先探索法により抽出する、ループ抽出部を備える、請求項1又は2に記載の物体再配置計画装置。前記ループ抽出部により前記ループが抽出されたときに、当該ループ内に含まれる1節点を、当該節点に対応する物体の前記出発位置から当該物体を一時的に待避させる待避位置までの移動から成る移動要素を表す第1の節点と、その物体の前記待避位置から前記目標位置までの移動から成る移動要素を表す第2の節点とに置き換えて前記ループを解消する、ループ解消部を備える、請求項3に記載の物体再配置計画装置。前記ループ抽出部により複数の前記ループが抽出され、抽出された複数の前記ループに前記節点の数が2のループが含まれるときに、前記ループ解消部は、前記節点の数が2のループを構成している節点のうちその移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して前記第1および第2の節点に置き換える、請求項4に記載の物体再配置計画装置。前記有向矢印が表す前記複数の移動要素間の順序の制約に基づいて、前記複数の移動要素の順序を決定する、順序決定部を備える、請求項1~5のいずれか一項に記載の物体再配置計画装置。前記順序決定部は、各移動要素に乱数を与え、前記複数の移動要素間の順序の制約の下で前記乱数に基づいて優先順位を定めることにより、前記複数の移動要素の順序を決定し、決定した前記複数の移動要素の順序で前記複数の物体の再配置に要する作業時間を算出し、前記各移動要素に与えた乱数の数値配列を遺伝子とし、前記作業時間の算出過程を評価関数とし、遺伝的アルゴリズムを用いて前記作業時間が最短となる遺伝子が残るように交叉を繰り返して解を探索し、前記複数の移動要素の順序を決定する、請求項6に記載の物体再配置計画装置。物体が1つずつ配置され得るブロックが1以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画方法であって、前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出するステップと、前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求めるステップと、抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成するステップとを含む、物体再配置計画方法。物体が1つずつ配置され得るブロックが1以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成するコンピュータで実行される物体再配置計画プログラムであって、前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する処理と、前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求める処理と、抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する処理とを、前記コンピュータに実行させる物体再配置計画プログラム。上記特許文献1において、キャリッジは、横方向および縦方向に配置された複数の収納棚から制約なく収納物を取り出して、空いている任意の収納棚位置にその収納物を移動することができる。このように特許文献1では、比較的自由に収納物の入れ換えができるため、再配置案の作成について記載されているものの、収納物の移動順序や移動経路の決定方法については詳細に記載されていない。また、上記特許文献2に記載の技術は、同一のレーン上を移動する複数の搬送機械で、輸入コンテナをバッファからヤードへ、輸出コンテナをヤードからバッファへそれぞれ配置換えする場合を想定しており、この複数の搬送機械が衝突したり追い越したりすることなくコンテナの受渡しをするように計画される。この特許文献2に記載の技術は上記のような単純な移動に適用することができるが、移動が複雑となったときに、遺伝的アルゴリズムの評価関数が失敗する可能性が高くなり、適切な解が得られない事態が生じうる。そこで、本発明は、物体の移動に制約がある条件下で複数の物体を移動前のレイアウトから移動後のレイアウトへ再配置するために、デッドロックが生じない物体再配置計画すなわち、物体の移動順序および移動経路をパーソナルコンピュータ等の演算手段を用いて自動的に作成することを可能とする技術を提供することを目的とする。加えて、物体の再配置に要する作業時間が最短時間となる最適な物体再配置計画を作成する技術を提供することを目的とする。本発明に係る物体再配置計画装置は、物体が1つずつ配置され得るブロックが1以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成する物体再配置計画装置であって、前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する移動要素抽出部と、前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を探索する順序制約探索部と、抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する、有向グラフ作成部とを備えるものである。なお、上記においてレイアウトとは、ステージ上の物体の全体的な配列を意味する。同様に、本発明に係る物体再配置計画方法は、物体が1つずつ配置され得るブロックが1以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画方法であって、前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出するステップと、前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求めるステップと、抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成するステップとを含むものである。なお、上記においてレイアウトとは、ステージ上の物体の全体的な配列を意味する。同様に、本発明に係る物体再配置計画プログラムは、物体が1つずつ配置され得るブロックが1以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成するコンピュータで実行されるプログラムであって、前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する処理と、前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求める処理と、抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する処理とを、前記コンピュータに実行させるものである。なお、上記においてレイアウトとは、ステージ上の物体の全体的な配列を意味する。上記物体再配置計画装置、物体再配置計画方法、物体再配置計画プログラムによれば、作成された有向グラフには、節点により物体の移動が示され、有向矢印により物体の移動順序が示される。この有向グラフおいて、節点および有向矢印から成るループの有無により、複数の物体の再配置の作業の間に生じるデッドロックが発生するか否かを知ることができる。よって、物体の移動に制約がある条件下で、ステージ上の複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、デッドロックが生じない物体再配置計画すなわち、物体の移動順序および移動経路をパーソナルコンピュータ等の演算手段を用いて自動的に作成することが可能となる。前記物体再配置計画装置において、前記順序制約探索部は、或ブロックに関わる1以上の物体の移動が、当該ブロックから出発する移動、当該ブロックを通過する移動、当該ブロックへ到着する移動の順となるように、前記複数の移動要素間の順序の制約を探索することができる。上記のように前記複数の移動要素間の順序の制約を探索すれば、単純な演算で、もれなく前記複数の移動要素間の順序の制約を求めることができる。前記物体再配置計画装置において、前記有向グラフにおいて、前記節点および前記有向矢印により形成されるループを深さ優先探索法により抽出する、ループ抽出部を備えることがよい。上記物体再配置計画装置によれば、有向グラフ上に存在する複数の物体の再配置の作業の間に生じるデッドロックを意味するループを全て抽出することができる。前記物体再配置計画装置において、前記ループ抽出部により前記ループが抽出されたときに、当該ループ内に含まれる1節点を、当該節点に対応する物体の前記出発位置から当該物体を一時的に待避させる待避位置までの移動から成る移動要素を表す第1の節点と、その物体の前記待避位置から前記目標位置までの移動から成る移動要素を表す第2の節点とに置き換えて前記ループを解消する、ループ解消部を備えることがよい。ここで、前記ループ抽出部により複数の前記ループが抽出され、抽出された複数の前記ループに前記節点の数が2のループが含まれるときに、前記ループ解消部は、前記節点の数が2のループを構成している節点のうちその移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して前記第1および第2の節点に置き換えることがよい。上記物体再配置計画方法または物体再配置計画装置によれば、有向グラフ上に存在していたループが解消されるため、複数の物体の再配置の作業の間にデッドロックを生じさせないように複数の移動要素の順序を定めることが可能となる。前記物体再配置計画装置において、前記有向矢印が表す前記複数の移動要素間の順序の制約に基づいて、前記複数の移動要素の順序を決定する、順序決定部を備えることがよい。上記物体再配置計画装置によれば、ステージ上の複数の物体の再配置の作業の間にデッドロックを生じさせないような物体再配置計画すなわち、各物体の移動順序と移動経路を作成することができる。前記物体再配置計画装置において、前記順序決定部は、各移動要素に乱数を与え、前記複数の移動要素間の順序の制約の下で前記乱数に基づいて優先順位を定めることにより、前記複数の移動要素の順序を決定し、決定した前記複数の移動要素の順序で前記複数の物体の再配置に要する作業時間を算出し、前記各移動要素に与えた乱数の数値配列を遺伝子とし、前記作業時間の算出過程を評価関数とし、遺伝的アルゴリズムを用いて前記作業時間が最短となる遺伝子が残るように交叉を繰り返して解を探索し、前記複数の移動要素の順序を決定することがよい。上記物体再配置計画装置によれば、決定された複数の移動要素の順序は、ステージ上の物体の再配置に要する作業時間が最短となるものである。よって、ステージ上の物体の再配置の作業の間にデッドロックを生じず、且つ、物体の再配置に要する作業時間が最短時間となる最適な物体再配置計画を作成することができる。さらに、複数の移動要素の順序の半順序集合を予め決定し、この半順序集合を全順序集合に変換するために遺伝的アルゴリズムを利用するので、遺伝的アルゴリズムの評価関数が失敗する可能性を抑えることができ、適切な解を短時間で得ることが可能となる。本発明によれば、物体の移動に制約がある条件下でステージ上の複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、デッドロックが生じない物体再配置計画すなわち、物体の移動順序および移動経路をパーソナルコンピュータ等の演算手段を用いて自動的に作成することが可能となる。以下、本発明を実施するための形態について、図面を参照しながら、詳細に説明する。なお、以下では全ての図を通じて同一又は相当する要素には同一の参照符号を付して、その重複説明を省略する。まず、本実施の形態に係る物体再配置計画装置について説明する。図1は本発明の実施の形態に係る物体再配置計画装置の概略構成を示すブロック図である。同図に示すように、物体再配置計画装置1は、主に1又は複数のコンピュータ2からなり、各コンピュータ2はCPU中央処理装置、CPUが実行する物体再配置計画プログラムやこのプログラムで使用されるデータを書き替え可能に記憶する主記憶装置、CPUがプログラム実行時にデータを一時的に記憶する副記憶装置、CPUと外部機器を接続するためのインターフェース、並びにこれらを接続する内部経路等を備えている何れも不図示。物体再配置計画プログラムは、フレキシブルディスク、CD-ROM、メモリカード等の各種記憶媒体に保存されており、これらの記憶媒体からコンピュータ2にインストールされる。そして、この物体再配置計画プログラムがコンピュータ2のCPUで実行されることにより、物体再配置計画装置1としての機能が実現される。物体再配置計画プログラムは、移動要素抽出ルーチン、順序制約探索ルーチン、有向グラフ作成ルーチン、ループ抽出ルーチン、ループ解消ルーチン、および順序決定ルーチンを少なくとも含んでいる。これらは物体再配置計画装置1において、移動要素抽出部61、順序制約探索部62、有向グラフ作成部63、ループ抽出部64、ループ解消部65、および順序決定部66としてそれぞれ機能する。物体再配置計画装置1のこれらの機能部の機能については後ほど詳細に説明する。コンピュータ2は、インターフェースを介してマウスポインタやキーボード等の入力装置3と接続されている。ユーザが入力装置3に対して入力操作を行った場合には、その操作内容を示す信号がコンピュータ2へ入力され、コンピュータ2は入力信号に基づいて処理を行う。また、コンピュータ2は、インターフェースを介してディスプレイやプリンタ等の出力装置4と接続されている。コンピュータ2が、動作上ユーザに提供する各種の情報は出力装置4において文字や記号により適宜表示される。さらに、コンピュータ2は、インターフェースを介して記憶装置5と接続されている。記憶装置5には、物体が配置されるステージ10に係る情報と、複数の物体の移動前レイアウトと移動後レイアウトに係る情報とが少なくとも記憶されている。なお、これらの情報は、記憶装置5に代えてコンピュータ2が備える記憶装置に記憶されていてもよい。次に、物体が配置されるステージおよびこのステージでの物体の移動の制約について説明する。図2abは複数の物体が配置されたステージの一例を示している。図2aは物体の移動前レイアウトを示し、図2bは物体の移動後レイアウトを示している。ステージ10において、1以上のブロック13が一方向図2の紙面左右方向に並んで1本のレーンLが形成されている。そして、複数のレーンLがレーンと交わる方向図2の紙面上下方向に互いに略平行に並んで、1つのエリア12が形成されている。図2abに示す例では、ステージ10に第1のエリア12aと第2のエリア12bとの、行方向に並ぶ2つのエリアが形成されている。第1のエリア12aにはL11,L12,L13の3本のレーンLが形成され、第2のエリア12bにはL21,L22,L23の3本のレーンLが形成されている。レーンL11には、座標が1,bと1,cでそれぞれ表される2つのブロック13が設けられている。レーンL12には、座標が2,aと2,bと2,cでそれぞれ表される3つのブロック13が設けられている。レーンL13には、座標が3,aと3,bと3,cでそれぞれ表される3つのブロック13が設けられている。以下同様に、レーンL21,レーンL22,レーンL23に複数のブロック13が設けられている。ステージ10には合計15個のブロック13が設けられており、このうち7個のブロック13にA~Gまでの7個の物体20がそれぞれ配置されている。以下では、図2aに示される物体A~Gの配置されているブロック13を出発位置ということがあり、図2bに示される物体A~Gの配置されているブロック13を目標位置ということがある。ステージ10の第1のエリア12aと第2のエリア12bの2つのエリアの間には、レーンと交わる方向に移動可能なトラバーサ11が設けられている。トラバーサ11は物体20を1つずつレーンと交わる方向へ運ぶことができる。或レーンLに存在する物体20が他のレーンLへ移動するとき、つまり、物体20がレーンLを跨いで移動するときには、トラバーサ11を介することとなる。上記構成のステージ10において、物体20には次に示す<1>~<3>の移動の制約が課せられる。<1>物体が配置されるステージ10には物体20が1つずつ配置され得るブロック13が1以上並んだレーンLが複数存在しており、物体20はレーンLに沿って移動することができる。<2>物体20は他の物体が存在しているブロック13へ移動したり、他の物体20を追い越して移動したりすることができない。<3>物体20は他のレーンLへ移動することができるが、必ずトラバーサ11を介さねばならない。これは、各レーンLには出入口に相当するブロック図2abに示す例ではトラバーサ11に隣接しているブロックが決まっており、この出入口に相当するブロックを通らねば物体20は他のレーンLへ移動することができないことを意味している。上記のような移動の制約から、次のような移動の順序制約が生じる。図3は、ブロック2,eに関する移動の順序制約を説明する図である。以下では、ブロック座標で、その座標のブロックを示すこととする。例えば、図2abに示す移動前後の配置からブロック2,eに関係する物体20の移動を抽出すると、図3に示すように、物体Eがブロック2,eから出発してブロック2,cへ到着する移動、物体Aがブロック1,bを出発してブロック2,eを通過してブロック2,fへ到着する移動、物体Dがブロック1,cを出発してブロック2,eへ到着する移動の、3つの移動がある。ブロック2,eの立場で見れば、出発する移動、通過する移動、到着する移動の順でなければ移動は成立せず、これが移動の順序制約を生じさせる。よって、ブロック2,eについて物体A,D,Eの移動の順序制約は、物体E→物体A→物体Dの順となる。以上、ブロック2,eに関係する物体の移動の順序制約について説明したが、他のブロックでも同様に物体の移動の順序制約が生じる。続いて、図4を参照しつつ、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための物体再配置計画、すなわち、物体の移動順序と移動経路を決定する処理の手順を、図2abに示す実施例を用いて説明する。図4は、物体再配置計画処理の流れを説明するフローチャートである。物体再配置計画装置1のコンピュータ2のCPUは、物体再配置計画プログラムを実行し、記憶装置5に記憶された情報を適宜読み出しながら次に示す手順で所定の演算を行うことにより、物体再配置計画を作成することができる。物体再配置計画装置1の有向グラフ作成部は、まず、複数の物体20が配置されるステージ10に係る情報と、複数の物体20の移動前レイアウトと移動後レイアウトに係る情報とを取得するステップS0。ここで、コンピュータ2のCPUは、記憶装置5から複数の物体20が配置されるステージ10に係る情報と複数の物体20の移動前レイアウトと移動後レイアウトに係る情報とを読み出す。但し、これらの情報は予め記憶装置5に格納されているものに限られない。例えば、コンピュータ2は、出力装置4で複数の物体20の移動前レイアウトと移動後レイアウトに係る情報の入力をユーザに促し、ユーザにより入力装置3を介して入力された複数の物体20の移動前レイアウトと移動後レイアウトに係る情報を取得することもできる。物体再配置計画装置1が取得した複数の物体20が配置されるステージ10に係る情報と複数の物体20の移動前レイアウトと移動後レイアウトに係る情報には、ステージ10の構成、ステージ10での物体20の移動の制約、複数の物体20の移動前レイアウト各物体の出発位置の座標、および複数20の物体の移動後レイアウト各物体の目標位置の座標が少なくとも含まれている。次に、物体再配置計画装置1の移動要素抽出部61は、各物体20について出発位置から目標位置までの移動を移動要素として抽出するステップS1。なお、移動要素には、出発位置と目標位置が同じであって物体が結果的に移動しないものも含まれる。物体再配置計画装置1の有向グラフ作成部63は、抽出された各移動要素が節点ノードとして表されたグラフを作成するステップS2。物体20の総数がn個の場合は、n個の移動要素が抽出されて、グラフ上にn個の節点N1~Nnが作成される。図5に示すように、図2abに示す例では、物体A~GのそれぞれについてN1~N7の合計7個の節点がグラフ上に作成される。物体Aの節点N1は、出発位置1,bから目標位置2,fまでの移動要素で成り、その移動要素がA:1b→2fと表されている。同様に、物体Bの節点N2は、出発位置2,dから目標位置2,aまでの移動要素で成り、その移動要素がB:2d→2aと表されている。物体Cの節点N3は、出発位置2,bから目標位置1,cまでの移動要素で成り、その移動要素がC:2b→1cと表されている。物体Dの節点N4は、出発位置1,cから目標位置2,eまでの移動要素で成り、その移動要素がD:1c→2eと表されている。物体Eの節点N5は、出発位置2,eから目標位置2,cまでの移動要素から成り、その移動要素がE:2e→2cと表されている。物体Fの節点N6は、出発位置1,dから目標位置3,aまでの移動要素で成り、その移動要素がF:1d→3aと表されている。物体Gの節点N7は、出発位置3,bから目標位置3,bまでの移動要素で成り、その移動要素がG:3b→3bと表されている。ここで注意すべきは、再配置の前後で移動しない物体物体Gについては、出発位置から当該出発位置と同一の目標位置への移動要素を有するものとして、節点が作成されることである。続いて、物体再配置計画装置1の順序制約探索部62は、全ての物体20について出発位置から目標位置までの移動経路を算出しステップS3、算出された移動経路に基づいてグラフ上に作成された節点N1~Nn同士の移動の順序制約を探索するステップS4。節点同士の移動の順序制約は、つまり、移動要素同士の移動の順序制約である。節点同士の移動の順序制約は、或ブロックに関する物体の移動の制約が、出発する移動、通過する移動、到着する移動の順であることに基づいて定められる。例えば、図3に示すように、ブロック2,eに関する移動の順序制約は、このブロックを出発する物体Eの移動、このブロックを通過する物体Aの移動、このブロックへ到着する物体Dの移動の順である。ここから、節点N5が先で節点N1が後、節点N1が先で節点N4が後という節点同士の移動の順序制約を定めることができる。上記のように定められた節点同士の移動の順序制約に基づき、物体再配置計画装置1の有向グラフ作成部63は、グラフ上に作成された節点N1~Nnを結ぶ辺エッジを有向矢印で作成するステップS5。この有向矢印は節点同士の移動の順序制約を表し、有向矢印の根元が先、矢印の向かう方が後である。このようにして、移動要素を表す各節点が移動要素の順序制約を表す有向矢印で結ばれた有向グラフが作成される。図6に示すように、ブロック2,eに関する移動の順序制約により、節点N5から節点N1へ向かう矢印と、節点N1から節点N4へ向かう矢印が作成される。同様に、ブロック3,bに関する移動の順序制約により、節点N7から節点N6へ向かう矢印と、節点N6から節点N7へ向かう矢印が作成される。ブロック2,cに関する移動の順序制約により、節点N3から節点N5へ向かう矢印と、節点N2から節点N5へ向かう矢印が作成される。ブロック1,cに関する移動の順序制約により、節点N4から節点N1へ向かう矢印と、節点N1から節点N3へ向かう矢印が作成される。ブロック2,bに関する移動の順序制約により、節点N3から節点N2へ向かう矢印が作成される。ブロック2,dに関する移動の順序制約により、節点N2から節点N1へ向かう矢印と、節点N2から節点N5へ向かう矢印と、節点N2から節点N4へ向かう矢印が作成される。上述のように作成された有向グラフにおいて、節点と有向矢印により形成される閉じられたループが存在することがある。有向グラフ上のループは、移動要素の順序制約のループであり、このループはデッドロックを意味している。ステージ10において、物体20は他の物体20を追い越したり他の物体20と同じブロック13へ同時に移動したりすることができないためデッドロックが生じることがあり、このデッドロックは移動の順序制約のループとして有向グラフに表れる。よって、物体再配置計画装置1の有向グラフ作成部により作成された有向グラフに存在するループの有無により、複数の物体の再配置の作業の間に生じるデッドロックが発生するか否かを知ることができる。物体再配置計画装置1のループ抽出部64は、上述のように作成された有向グラフにおいて、有向矢印により形成される閉じられたループを抽出するステップS6。有向グラフ中の全てのループを抽出するために、グラフ理論の深さ優先探索が用いられる。なお、複数の物体の再配置が比較的単純な場合には、有向グラフ上にループが存在しない、つまり、デッドロックが生じない場合もあり、このような場合は、ループは抽出されない。図6に示す有向グラフには、6つのループ節点N1,N4のループ、節点N1,N3,N2のループ、節点N1,N3,N5のループ、節点N1,N3,N2,N5のループ、節点N2,N4,N1,N3のループおよび節点N6,N7のループが存在し、これら全てのループが抽出される。グラフ上にループが存在する状態では、前述の通り、デッドロックが生じるために移動が成立しない。そこで、物体再配置計画装置1のループ解消部65は、ループ抽出部によりループが抽出された場合に、抽出された全てのループについて節点の分解を行い、全てのループを解消するステップS7。上記において節点の分解とは、ループを構成している節点のなかから1つを選択し、この1つの節点を仮に定めた待避位置を経由する2つの移動を表す節点に置き換えることを意味する。換言すれば、節点の分解とは、1つの移動要素を、出発位置から待避位置までの移動要素と、待避位置から出発位置までの移動要素とに置き換えることを意味する。例えば、図6に示すように、グラフ上に節点N6,N7のループが存在する。このループについて節点の分解を行う場合には、図7に示すように、ループを構成している節点N6,N7のなかから1つここでは、節点N7を選択し、この節点N7を出発位置3,bから待避位置W3までの移動を表す節点N71と、待避位置W3から目標位置3,bまでの移動を表す節点N72とに分解する。なお、待避位置W3は、出発位置および目標位置と異なる位置でなければならない。このように、節点N7が節点N71と節点N72とに分解されることによって、節点N6,N7のループが解消される。節点の分解を行うに当たって、ループを構成している節点のうち分解可能な節点は1つに限られない。但し、複数の節点が分解可能である場合に、分解する節点の選定にルールが定められている。第1のルールは、2つの節点と2本の矢印から成る長さ2のループでは、その移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して選択するというものである。このルールに則れば、ループに出発位置と目標位置が同じ節点が含まれる場合には、必ずこの節点が分解される。第2のルールは、分解することによりループがより多く解消される節点を優先して選択するというものである。節点の分解により節点すなわち、移動要素の数が増加することは、再配置を完了するまでの時間の増加に繋がる。よって、グラフ上の節点の数をなるべく少なくするために、ループがより多く解消される節点が優先して選択されねばならない。図6に示すグラフにおいて、上記ルールに則って分解される節点N3,N4,N7が選択され、これらの節点を分解することにより全てのループを解消することができる。図6に示すグラフ上には、長さ2のループが2つ存在する。第1のルールに則り、節点N1,N4のループでは、節点N4の物体Dの移動要素の経路は、物体Aの移動要素の経路の一部に含まれることから、分解する節点として節点N4が選択される。また、第1のルールに則り、節点N6,N7のループでは、節点N7は出発位置と目標位置が同一であるから、分解する節点として節点N7が選択される。そして、長さ2のループを分解した後に残る長さ2以外のループには、節点N1,N3,N2のループ、節点N1,N3,N5のループおよび節点N1,N3,N2,N5のループが存在する。ここで、第2のルールに則り、分解する節点として節点N1または節点N3が優先的に選択される。図7に示す例では、節点N3が選択され、この節点N3が出発位置2,bから待避位置W1までの移動要素を表す節点N31と、待避位置W1から目標位置1,cまでの移動要素を表す節点N32とに分解されている。上記節点の分解によりグラフ上の全てのループを解消した結果、グラフ上の節点は7個から10個に増加している。上述のように節点の分解を繰り返すことによりグラフ上の全てのループが解消されると、節点の半順序集合、すなわち、移動要素の半順序集合が完成する。移動要素の半順序集合では、或移動要素の移動を行った後、次に行うべき移動を表す移動要素を一意に選択することができない。そこで、物体再配置計画装置1は、前述のように完成した移動要素の半順序集合を基にして、物体の再配置を最短時間で完了する移動要素の順序を探索する。つまり、移動要素の半順序集合を全順序集合に変換する。移動要素の半順序集合を全順序集合に変換する方法は幾つか存在するが、ここでは、遺伝的アルゴリズムGA:GeneticAlgorithmが用いられる。具体的には、物体再配置計画装置1の順序決定部66は、移動要素を表す各節点N1~Nnに乱数を与えステップS8、節点同士の移動の順序制約を守るという条件の下で、節点N1~Nnの全順序を決定するステップS9。節点の全順序が決まれば、物体再配置計画装置1の順序決定部66は、仮に定めた待避位置に空きブロックを割り当てるステップS10。待避位置に実際のブロックが割り当てられれば、全ての物体の移動順序と移動経路が決定し、物体の再配置に要する作業時間を計算することができる。物体再配置計画装置1の順序決定部66は、決定した節点の全順序で物体の再配置に要する作業時間を求めるステップS11。そして、物体再配置計画装置1の順序決定部66は、各節点に与えた乱数の数値配列を遺伝子とし、物体の再配置に要する作業時間を求める過程を評価関数として、遺伝的アルゴリズムGAを適用させて前記作業時間が最短となる遺伝子が残るように交叉を行い、ステップS8~S11の処理を繰り返して解を探索するステップS12。最後に、物体再配置計画装置1の順序決定部66は、物体の再配置に要する作業時間が最短となる遺伝子に対応する移動要素の全順序を、最適な物体再配置計画と決定するステップS13。なお、遺伝的アルゴリズムGAは、一般に、評価関数が失敗する可能性が高すぎると良好に機能しないことがある。これに対し、以上説明した物体再配置計画の処理の流れでは、遺伝的アルゴリズムGAを適用させる前に半順序集合を求めることにより、遺伝的アルゴリズムGAの役割が自由度解決だけに絞られている。これにより、不正な移動順序の生成可能性が大きく排除される結果、物体の再配置に要する作業時間が最短となる移動要素の全順序を容易に求めることが可能となっている。ここで、物体再配置計画装置1が遺伝的アルゴリズムGAを用いて、図7に示す移動要素節点N1~N72の半順序集合を全順序集合に変換する流れを説明する。物体再配置計画装置1は、まず、図7に示すグラフ上の全ての節点N1~N72に、次の表1に示すように[0、1の乱数を与えるステップS8。次に、物体再配置計画装置1は、与えられた乱数の数値配列を遺伝子として、節点同士の移動の順序制約を守るという条件の下で最大又は最小の遺伝子要素が与えられた節点を選択することで、節点N1~N72の全順序を決定するステップS9。図8に示すように、最初に、節点同士の移動の順序制約を守るという条件の下で有向矢印の源となる節点N31,N41,N71が抽出され、これらの節点N31,N41,N71に与えられた遺伝子要素0.4,0.5,0.0が比較される。これらのうち最大の遺伝子要素が与えられた節点N41が選択され、節点N41の順序は1番目とされる。次に、図9に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点N31,N71が抽出され、これらの節点N31,N71に与えられた遺伝子要素0.4,0.0が比較される。このうち最大の遺伝子要素が与えられた節点N31が選択され、節点N31の順序は2番目とされる。続いて、図10に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点N2,N71が抽出され、これらの節点N2,N71に与えられた遺伝子要素0.1,0.0が比較される。このうち最大の遺伝子要素が与えられた節点N2が選択され、節点N2の順序は3番目とされる。続いて、図11に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点N5,N71が抽出され、これらの節点N5,N71に与えられた遺伝子要素0.8,0.0が比較される。このうち最大の遺伝子要素が与えられた節点N5が選択され、節点N5の順序は4番目とされる。続いて、図12に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点N1,N71が抽出され、これらの節点N1,N71に与えられた遺伝子要素0.2,0.0が比較される。このうち最大の遺伝子要素が与えられた節点N1が選択され、節点N1の順序は5番目とされる。続いて、図13に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点N32,N42,N71が抽出され、これらの節点N32,N42,N71に与えられた遺伝子要素0.6,0.3,0.0が比較される。これらのうち最大の遺伝子要素が与えられた節点N32が選択され、節点N32の順序は6番目とされる。そして、節点N42,N71に与えられた遺伝子要素0.3,0.0が比較され、このうち最大の遺伝子要素が与えられた節点N42の順序は7番目とされる。最後に、図14に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で、節点N71の順序は8番目とされ、節点N6の順序は9番目とされ、節点N72の順序は10番目とされる。以上により、次の表2に示すように、節点N1~N72の全順序が決定する。節点の全順序が決定すると、物体再配置計画装置1は、物体が待避位置に滞在している期間に空いているブロックを探索し、この空きブロックを待避位置に割り当てるステップS10。表2に示すように、第1の待避位置W1には、物体Cが順序2番目から6番目の間に滞在している。この滞在期間に空いているブロック3,dが第1の待避位置W1に割り当てられる。第2の待避位置W2には、物体Dが順序1番目から7番目の間に滞在している。この滞在期間に空いているブロック3,cが第2の待避位置W2に割り当てられる。第3の待避位置W3には、物体Gが順序8番目から10番目の間に滞在している。この滞在期間に空いているブロック3,dが第3の待避位置W3に割り当てられる。なお、待避位置に割り当てることの可能な空きブロックが複数存在する場合には、遺伝的アルゴリズムGAを用いて物体の再配置に要する作業時間が最も短くなるような1つの空きブロックが選択される。なお、本実施の形態では、各待避位置に空きブロックを割り当てているが、待避位置は必ずしもステージ10上のブロック13に限定されない。例えば、ステージ10上にトラバーサ11が複数設けられている場合には、そのうち1以上のトラバーサ11をいずれかの待避位置に割り当てることも可能である。また、ステージ10上にブロック13とは異なる1又は複数の待避位置を設けてもよい。物体再配置計画装置1は、以上のようにして決められた移動順序に対して、物体の再配置に要する作業時間、換言すれば、全ての物体を出発位置から目標位置へ移動させるために必要な作業時間をシミュレーションにより計算するステップS11。物体再配置計画装置1のコンピュータ2にはシミュレーションモデルが予め構築されており、物体再配置計画装置1はこのシミュレーションモデルを用いて物体の再配置に要する作業時間を算出する。算出された物体の再配置に要する作業時間には、物体のレーンL上の移動時間、物体がトラバーサ11で搬送される時間およびトラバーサ11が物体を乗せずに移動する時間等が加味されている。そして、物体再配置計画装置1は、物体の再配置に要する作業時間を遺伝子の評価値とし、遺伝的アルゴリズムGAにより物体の再配置に要する作業時間が最短となる遺伝子が残るように遺伝子すなわち、各節点に付与される乱数の数値配列を交叉しながら、ステップS8~ステップS11の処理を繰り返すステップS12。なお、遺伝的アルゴリズムGAの交叉組み換え方法は、一様交叉が用いられてよい。例えば、下記表3に示すように、各節点に与えられた乱数の数値配列である親遺伝子1と親遺伝子2とを一様交叉で組み換え、遺伝子の要素ごとに1/2の確率で親遺伝子1,2の要素を引き継いで子遺伝子を生成する。表3では、親遺伝子1および親遺伝子2の太枠で囲まれた遺伝子要素を組み合わせて子遺伝子を生成している。そして、この子遺伝子を用いてステップS8~ステップS13の処理が行われる。最後に、物体再配置計画装置1は、評価値が最小となる遺伝子、換言すれば、物体の再配置に要する作業時間が最短となる遺伝子に対応する移動順序を遺伝的アルゴリズムGAの解とし、物体再配置計画を決定するステップS13。このように決定された物体再配置計画は、物体の移動順序と移動経路とを含み、デッドロックが生じず、且つ、物体の再配置に要する作業時間が最短となっている。以上説明した物体再配置計画の処理の流れでは、各物体の出発位置から目標位置までの移動を移動要素とし、移動要素を表す各節点が移動要素の順序制約を表す有向矢印で結ばれた有向グラフを表すことにより、移動要素の移動順序の制約関係が整理された状態となる。そして、この有向グラフにグラフ理論が適用されることにより、移動要素を表す各節点の半順序集合が作成される。さらに、この節点の半順序集合に遺伝的アルゴリズムGAが適用されることにより、節点の半順序集合が全順序集合に変換され、節点の全順序集合のうち最適なものが物体再配置計画として決定される。この物体再配置計画の処理の流れによれば、熟練の作業者の経験に頼らず物体再配置計画を作成することができる。しかも、作成された物体再配置計画の最適性は遺伝的アルゴリズムGAにより評価されており、作成された物体再配置計画はデッドロックが生じず、且つ、最短時間で物体の再配置を完了できるものとなる。このように、本発明によれば、パーソナルコンピュータ等の演算手段を用いて最適な物体再配置計画を自動的に作成することができ、物体再配置計画の作成にかかる労力と時間を削減することができる。物体再配置計画の作成にかかる時間の削減を達成した一実施例を紹介すると、100個のブロック13が設けられたステージにおいて80個の物体20の再配置計画を作成するための所要時間は、作業者では数時間であったが、本発明に係る物体再配置計画装置1では数分であった。以上、本発明の好適な一実施形態について説明したが、本発明は上述の実施の形態に限られるものではなく、特許請求の範囲に記載した限りにおいて、様々な設計変更を行うことが可能である。例えば、物体20が再配置されるステージ10の形態は上述の実施の形態に限定されない。各レーンLに含まれるブロック13の数や各エリア12に含まれるレーンLの数は適宜変更することができる。また、ステージ10は平面であっても、立体であってもよい。ステージ10が平面の場合は、複数のレーンLが水平方向に並んで1つのエリア12が形成され、トラバーサ11は水平方向へ往復移動することとなる。ステージ10が立体の場合は、複数のレーンLが上下方向に並んで1つのエリア12が形成され、トラバーサ11は上下方向へ往復移動することとなる。さらに、ステージ10に設けられるエリア12の数やトラバーサ11の数も、上述の実施の形態に限定されない。例えば、図15に示すように、ステージ10に3以上のエリア12が設けられ、2以上のトラバーサ11が設けられても良い。トラバーサ11の配置はエリア12間に限定されず、エリア12間ではないレーンの端に設けられてもよい。また、トラバーサ11はレーンL間で物体20を渡すことができる物であればその移動方向は限定されず、トラバーサ11はステージ10上を自在に移動できるものであってもよい。また、例えば、上述の実施形態において、遺伝的アルゴリズムGAの遺伝子要素を数値[0、1とし、交叉組み換え方法を一様交叉としているが、遺伝的アルゴリズムGAの遺伝子要素の数値配列や交叉方法はこれに限定されない。なお、本発明に係る物体再配置計画方法および装置は、鉄道車両の艤装工場において車両の再配置計画を作成するために利用できるが、本発明の利用範囲はこれにとどまらない。物体の移動に制約がある条件下で、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための再配置計画を作成するために、広く利用することができる。"