物体再配置計画装置、方法およびプログラム
【課題】物体の移動に制約がある条件下で複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための物体再配置計画を、パーソナルコンピュータ等の演算手段を用いて自動的に作成する。
【解決手段】各物体について移動前レイアウト上の出発位置から移動後レイアウト上の目標位置までの移動を移動要素として抽出し、複数の移動要素間の順序の制約を探索する。そして、複数の移動要素を節点とし、複数の移動要素間の順序の制約を節点間を結ぶ有向矢印とする有向グラフを作成する。有向グラフ上に節点と有向矢印で形成されたループがある場合には、ループに含まれる節点を分解することによりループを解消する。さらに、移動要素間の順序の制約の下で移動要素の半順序を決定し、遺伝的アルゴリズムを用いて移動要素の半順序を物体の再配置に要する作業時間が最短となる全順序に変換する。
【解決手段】各物体について移動前レイアウト上の出発位置から移動後レイアウト上の目標位置までの移動を移動要素として抽出し、複数の移動要素間の順序の制約を探索する。そして、複数の移動要素を節点とし、複数の移動要素間の順序の制約を節点間を結ぶ有向矢印とする有向グラフを作成する。有向グラフ上に節点と有向矢印で形成されたループがある場合には、ループに含まれる節点を分解することによりループを解消する。さらに、移動要素間の順序の制約の下で移動要素の半順序を決定し、遺伝的アルゴリズムを用いて移動要素の半順序を物体の再配置に要する作業時間が最短となる全順序に変換する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の物体を次なる目的地へ再配置するための物体の移動手順を計画する技術に関する。
【背景技術】
【０００２】
従来、鉄道車両の組立や塗装等の作業が行われる車両の艤装工場では、作業毎に工区が決まっており、車両は作業工程に応じた工区へ移動させる必要がある。艤装工場では、敷設されたレール上に複数の工区がレールと平行な方向に並んで工区レーンを形成している。そして、複数の工区レーンがレールと交わる方向に並んで１つのエリアを形成している。エリアはレールと平行な方向に複数設けられており、エリア間にトラバーサが設けられている。トラバーサはレールと交わる方向に車両を移動させるものであり、トラバーサを介して車両を他の工区レーンへ移動させることができる。
【０００３】
上記のような艤装工場では、車両は自己が存在している工区が属する工区レーンを移動可能であるが、他の車両を追い越したり、他の車両が存在する工区へ移動したりすることができない。さらに、車両は工区レーンを跨って移動可能であるが、この場合トラバーサを経由する必要がある。艤装工場の車両の移動にはこのような制約があるため、無計画に車両を移動させたのではデッドロック（行き詰まり）が生じることがある。そこで、デッドロックが生じず、且つ、できるだけ時間を掛けずに移動前の車両の配置から移動後の車両の配置へ各車両を移動させるための車両再配置計画が作成され、この車両再配置計画に則って各車両を順次移動させている。車両再配置計画は、車両を現レイアウトから次レイアウトへ再配置するための車両の移動順序及び移動経路等の、再配置の過程を定めたものである。現状では、熟練の作業者が経験に基づき車両再配置計画を作成している。このように車両再配置計画の作成が作業者の経験に基づくために、車両再配置計画を作成できる人員の確保が困難となる事態が生じうる。また、車両再配置計画を評価するすべがなく、作成された車両再配置計画が最適であること、すなわち、デッドロックが生じず、且つ、最短時間で車両の移動を完了できるものであることを保証することができない。
【０００４】
上記課題は、鉄道車両の艤装工場における車両の再配置に限らず、物体の移動の制約がある条件下で複数の物体を移動前レイアウトから移動後レイアウトへ再配置する場合にも生じる。よって、鉄道車両の艤装工場に限らず、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、物体の移動順序および移動経路を定めた物体再配置計画を自動的に作成するシステムの開発が望まれている。
【０００５】
ところで、前述の艤装工場と異なる移動制約の下で物体の再配置の手順を計画するための手法は、例えば、特許文献１，２に示すように従来から提案されている。特許文献１には、横方向および縦方向に配置された複数の収納棚と、これらの収納棚に対し収納物の入れ換え作業を行うための昇降キャリッジを備えた自動倉庫において、収納物を再配置するための手法が示されている。特許文献１に記載された手法では、まず、入出庫要求の頻度の高い収納物がランクの高い収納棚位置（すなわち、キャリッジのホームポジションからより近い収納棚位置）に収納されるように収納物の再配置案を作成する。次に、入れ換え効果（すなわち、全体的な運転コストとアクセスタイムの改善率）の大きい収納物の組み合わせから順に入れ換えを実行するように、再配置案を最適化する。
【０００６】
また、特許文献２には、同一レーン上に複数台の搬送機械を有するコンテナヤードにおいて、コンテナ搬出を円滑且つ迅速に行うために搬送機械間の干渉を排除し配置換えの総作業時間をできる限り短縮できるようなコンテナの配置替え計画を作成する手法が示されている。特許文献２に記載された手法では、各搬送機械が処理するコンテナ処理順序を遺伝子表現とする個体群に遺伝的アルゴリズムを適用し、交叉および突然変異を行って、所定の適応度関数に基づいた淘汰によって世代更新を繰り返しながら最適計画を得る。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開昭６１−２９５９０２号公報
【特許文献２】特開平８−２７２７６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記特許文献１において、キャリッジは、横方向および縦方向に配置された複数の収納棚から制約なく収納物を取り出して、空いている任意の収納棚位置にその収納物を移動することができる。このように特許文献１では、比較的自由に収納物の入れ換えができるため、再配置案の作成について記載されているものの、収納物の移動順序や移動経路の決定方法については詳細に記載されていない。
【０００９】
また、上記特許文献２に記載の技術は、同一のレーン上を移動する複数の搬送機械で、輸入コンテナをバッファからヤードへ、輸出コンテナをヤードからバッファへそれぞれ配置換えする場合を想定しており、この複数の搬送機械が衝突したり追い越したりすることなくコンテナの受渡しをするように計画される。この特許文献２に記載の技術は上記のような単純な移動に適用することができるが、移動が複雑となったときに、遺伝的アルゴリズムの評価関数が失敗する可能性が高くなり、適切な解が得られない事態が生じうる。
【００１０】
そこで、本発明は、物体の移動に制約がある条件下で複数の物体を移動前のレイアウトから移動後のレイアウトへ再配置するために、デッドロックが生じない物体再配置計画（すなわち、物体の移動順序および移動経路）をパーソナルコンピュータ等の演算手段を用いて自動的に作成することを可能とする技術を提供することを目的とする。加えて、物体の再配置に要する作業時間が最短時間となる最適な物体再配置計画を作成する技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明に係る物体再配置計画装置は、物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成する物体再配置計画装置であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する移動要素抽出部と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を探索する順序制約探索部と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する、有向グラフ作成部とを備えるものである。なお、上記において「レイアウト」とは、ステージ上の物体の全体的な配列を意味する。
【００１２】
同様に、本発明に係る物体再配置計画方法は、物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画方法であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出するステップと、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求めるステップと、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成するステップとを含むものである。なお、上記において「レイアウト」とは、ステージ上の物体の全体的な配列を意味する。
【００１３】
同様に、本発明に係る物体再配置計画プログラムは、物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成するコンピュータで実行されるプログラムであって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する処理と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求める処理と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する処理とを、前記コンピュータに実行させるものである。なお、上記において「レイアウト」とは、ステージ上の物体の全体的な配列を意味する。
【００１４】
上記物体再配置計画装置、物体再配置計画方法、物体再配置計画プログラムによれば、作成された有向グラフには、節点により物体の移動が示され、有向矢印により物体の移動順序が示される。この有向グラフおいて、節点および有向矢印から成るループの有無により、複数の物体の再配置の作業の間に生じるデッドロックが発生するか否かを知ることができる。よって、物体の移動に制約がある条件下で、ステージ上の複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、デッドロックが生じない物体再配置計画（すなわち、物体の移動順序および移動経路）をパーソナルコンピュータ等の演算手段を用いて自動的に作成することが可能となる。
【００１５】
前記物体再配置計画装置において、前記順序制約探索部は、或ブロックに関わる１以上の物体の移動が、当該ブロックから出発する移動、当該ブロックを通過する移動、当該ブロックへ到着する移動の順となるように、前記複数の移動要素間の順序の制約を探索することができる。
【００１６】
上記のように前記複数の移動要素間の順序の制約を探索すれば、単純な演算で、もれなく前記複数の移動要素間の順序の制約を求めることができる。
【００１７】
前記物体再配置計画装置において、前記有向グラフにおいて、前記節点および前記有向矢印により形成されるループを深さ優先探索法により抽出する、ループ抽出部を備えることがよい。
【００１８】
上記物体再配置計画装置によれば、有向グラフ上に存在する複数の物体の再配置の作業の間に生じるデッドロックを意味するループを全て抽出することができる。
【００１９】
前記物体再配置計画装置において、前記ループ抽出部により前記ループが抽出されたときに、当該ループ内に含まれる１節点を、当該節点に対応する物体の前記出発位置から当該物体を一時的に待避させる待避位置までの移動から成る移動要素を表す第１の節点と、その物体の前記待避位置から前記目標位置までの移動から成る移動要素を表す第２の節点とに置き換えて前記ループを解消する、ループ解消部を備えることがよい。ここで、前記ループ抽出部により複数の前記ループが抽出され、抽出された複数の前記ループに前記節点の数が２のループが含まれるときに、前記ループ解消部は、前記節点の数が２のループを構成している節点のうちその移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して前記第１および第２の節点に置き換えることがよい。
【００２０】
上記物体再配置計画方法または物体再配置計画装置によれば、有向グラフ上に存在していたループが解消されるため、複数の物体の再配置の作業の間にデッドロックを生じさせないように複数の移動要素の順序を定めることが可能となる。
【００２１】
前記物体再配置計画装置において、前記有向矢印が表す前記複数の移動要素間の順序の制約に基づいて、前記複数の移動要素の順序を決定する、順序決定部を備えることがよい。
【００２２】
上記物体再配置計画装置によれば、ステージ上の複数の物体の再配置の作業の間にデッドロックを生じさせないような物体再配置計画（すなわち、各物体の移動順序と移動経路）を作成することができる。
【００２３】
前記物体再配置計画装置において、前記順序決定部は、各移動要素に乱数を与え、前記複数の移動要素間の順序の制約の下で前記乱数に基づいて優先順位を定めることにより、前記複数の移動要素の順序を決定し、決定した前記複数の移動要素の順序で前記複数の物体の再配置に要する作業時間を算出し、前記各移動要素に与えた乱数の数値配列を遺伝子とし、前記作業時間の算出過程を評価関数とし、遺伝的アルゴリズムを用いて前記作業時間が最短となる遺伝子が残るように交叉を繰り返して解を探索し、前記複数の移動要素の順序を決定することがよい。
【００２４】
上記物体再配置計画装置によれば、決定された複数の移動要素の順序は、ステージ上の物体の再配置に要する作業時間が最短となるものである。よって、ステージ上の物体の再配置の作業の間にデッドロックを生じず、且つ、物体の再配置に要する作業時間が最短時間となる最適な物体再配置計画を作成することができる。さらに、複数の移動要素の順序の半順序集合を予め決定し、この半順序集合を全順序集合に変換するために遺伝的アルゴリズムを利用するので、遺伝的アルゴリズムの評価関数が失敗する可能性を抑えることができ、適切な解を短時間で得ることが可能となる。
【発明の効果】
【００２５】
本発明によれば、物体の移動に制約がある条件下でステージ上の複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、デッドロックが生じない物体再配置計画（すなわち、物体の移動順序および移動経路）をパーソナルコンピュータ等の演算手段を用いて自動的に作成することが可能となる。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施の形態に係る物体再配置計画装置の概略構成を示すブロック図である。
【図２】複数の物体が配置されたステージの再配置の前後の状況の一例を示す図であり、（ａ）は移動前レイアウトを示し、（ｂ）は移動後レイアウトを示している。
【図３】ブロック（２，ｅ）に関する移動の順序制約を説明する図である。
【図４】物体再配置計画処理の流れを説明するフローチャートである。
【図５】物体の移動を節点とするグラフの一例である。
【図６】節点を結ぶ有向矢印が加えられたグラフの一例である。
【図７】節点の分解によりループが解消されたグラフの一例である。
【図８】遺伝子として与えられた乱数により節点の順序を決定する手法を説明する図（１）である。
【図９】与えられた乱数により節点の順序を決定する手法を説明する図（２）である。
【図１０】与えられた乱数により節点の順序を決定する手法を説明する図（３）である。
【図１１】与えられた乱数により節点の順序を決定する手法を説明する図（４）である。
【図１２】与えられた乱数により節点の順序を決定する手法を説明する図（５）である。
【図１３】与えられた乱数により節点の順序を決定する手法を説明する図（６）である。
【図１４】与えられた乱数により節点の順序を決定する手法を説明する図（７）である。
【図１５】複数の物体が配置されたステージの変形例を示す図である。
【発明を実施するための形態】
【００２７】
以下、本発明を実施するための形態について、図面を参照しながら、詳細に説明する。なお、以下では全ての図を通じて同一又は相当する要素には同一の参照符号を付して、その重複説明を省略する。
【００２８】
まず、本実施の形態に係る物体再配置計画装置について説明する。図１は本発明の実施の形態に係る物体再配置計画装置の概略構成を示すブロック図である。同図に示すように、物体再配置計画装置１は、主に１又は複数のコンピュータ２からなり、各コンピュータ２はＣＰＵ（中央処理装置）、ＣＰＵが実行する物体再配置計画プログラムやこのプログラムで使用されるデータを書き替え可能に記憶する主記憶装置、ＣＰＵがプログラム実行時にデータを一時的に記憶する副記憶装置、ＣＰＵと外部機器を接続するためのインターフェース、並びにこれらを接続する内部経路等を備えている（何れも不図示）。物体再配置計画プログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、メモリカード等の各種記憶媒体に保存されており、これらの記憶媒体からコンピュータ２にインストールされる。そして、この物体再配置計画プログラムがコンピュータ２のＣＰＵで実行されることにより、物体再配置計画装置１としての機能が実現される。物体再配置計画プログラムは、移動要素抽出ルーチン、順序制約探索ルーチン、有向グラフ作成ルーチン、ループ抽出ルーチン、ループ解消ルーチン、および順序決定ルーチンを少なくとも含んでいる。これらは物体再配置計画装置１において、移動要素抽出部６１、順序制約探索部６２、有向グラフ作成部６３、ループ抽出部６４、ループ解消部６５、および順序決定部６６としてそれぞれ機能する。物体再配置計画装置１のこれらの機能部の機能については後ほど詳細に説明する。
【００２９】
コンピュータ２は、インターフェースを介してマウスポインタやキーボード等の入力装置３と接続されている。ユーザが入力装置３に対して入力操作を行った場合には、その操作内容を示す信号がコンピュータ２へ入力され、コンピュータ２は入力信号に基づいて処理を行う。また、コンピュータ２は、インターフェースを介してディスプレイやプリンタ等の出力装置４と接続されている。コンピュータ２が、動作上ユーザに提供する各種の情報は出力装置４において文字や記号により適宜表示される。さらに、コンピュータ２は、インターフェースを介して記憶装置５と接続されている。記憶装置５には、物体が配置されるステージ１０に係る情報と、複数の物体の移動前レイアウトと移動後レイアウトに係る情報とが少なくとも記憶されている。なお、これらの情報は、記憶装置５に代えてコンピュータ２が備える記憶装置に記憶されていてもよい。
【００３０】
次に、物体が配置されるステージおよびこのステージでの物体の移動の制約について説明する。図２（ａ）（ｂ）は複数の物体が配置されたステージの一例を示している。図２（ａ）は物体の移動前レイアウトを示し、図２（ｂ）は物体の移動後レイアウトを示している。ステージ１０において、１以上のブロック１３が一方向（図２の紙面左右方向）に並んで１本のレーンＬが形成されている。そして、複数のレーンＬがレーンと交わる方向（図２の紙面上下方向）に互いに略平行に並んで、１つのエリア１２が形成されている。
【００３１】
図２（ａ）（ｂ）に示す例では、ステージ１０に第１のエリア１２ａと第２のエリア１２ｂとの、行方向に並ぶ２つのエリアが形成されている。第１のエリア１２ａにはＬ11，Ｌ12，Ｌ13の３本のレーンＬが形成され、第２のエリア１２ｂにはＬ21，Ｌ22，Ｌ23の３本のレーンＬが形成されている。レーンＬ11には、座標が（１，ｂ）と（１，ｃ）でそれぞれ表される２つのブロック１３が設けられている。レーンＬ12には、座標が（２，ａ）と（２，ｂ）と（２，ｃ）でそれぞれ表される３つのブロック１３が設けられている。レーンＬ13には、座標が（３，ａ）と（３，ｂ）と（３，ｃ）でそれぞれ表される３つのブロック１３が設けられている。以下同様に、レーンＬ21，レーンＬ22，レーンＬ23に複数のブロック１３が設けられている。ステージ１０には合計１５個のブロック１３が設けられており、このうち７個のブロック１３にＡ〜Ｇまでの７個の物体２０がそれぞれ配置されている。以下では、図２（ａ）に示される物体Ａ〜Ｇの配置されているブロック１３を「出発位置」ということがあり、図２（ｂ）に示される物体Ａ〜Ｇの配置されているブロック１３を「目標位置」ということがある。
【００３２】
ステージ１０の第１のエリア１２ａと第２のエリア１２ｂの２つのエリアの間には、レーンと交わる方向に移動可能なトラバーサ１１が設けられている。トラバーサ１１は物体２０を１つずつレーンと交わる方向へ運ぶことができる。或レーンＬに存在する物体２０が他のレーンＬへ移動するとき、つまり、物体２０がレーンＬを跨いで移動するときには、トラバーサ１１を介することとなる。
【００３３】
上記構成のステージ１０において、物体２０には次に示す＜１＞〜＜３＞の移動の制約が課せられる。＜１＞物体が配置されるステージ１０には物体２０が１つずつ配置され得るブロック１３が１以上並んだレーンＬが複数存在しており、物体２０はレーンＬに沿って移動することができる。＜２＞物体２０は他の物体が存在しているブロック１３へ移動したり、他の物体２０を追い越して移動したりすることができない。＜３＞物体２０は他のレーンＬへ移動することができるが、必ずトラバーサ１１を介さねばならない。これは、各レーンＬには出入口に相当するブロック（図２（ａ）（ｂ）に示す例ではトラバーサ１１に隣接しているブロック）が決まっており、この出入口に相当するブロックを通らねば物体２０は他のレーンＬへ移動することができないことを意味している。
【００３４】
上記のような移動の制約から、次のような移動の順序制約が生じる。図３は、ブロック（２，ｅ）に関する移動の順序制約を説明する図である。以下では、「ブロック（座標）」で、その座標のブロックを示すこととする。例えば、図２（ａ）（ｂ）に示す移動前後の配置からブロック（２，ｅ）に関係する物体２０の移動を抽出すると、図３に示すように、物体Ｅがブロック（２，ｅ）から出発してブロック（２，ｃ）へ到着する移動、物体Ａがブロック（１，ｂ）を出発してブロック（２，ｅ）を通過してブロック（２，ｆ）へ到着する移動、物体Ｄがブロック（１，ｃ）を出発してブロック（２，ｅ）へ到着する移動の、３つの移動がある。ブロック（２，ｅ）の立場で見れば、出発する移動、通過する移動、到着する移動の順でなければ移動は成立せず、これが移動の順序制約を生じさせる。よって、ブロック（２，ｅ）について物体Ａ，Ｄ，Ｅの移動の順序制約は、物体Ｅ→物体Ａ→物体Ｄの順となる。以上、ブロック（２，ｅ）に関係する物体の移動の順序制約について説明したが、他のブロックでも同様に物体の移動の順序制約が生じる。
【００３５】
続いて、図４を参照しつつ、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための物体再配置計画、すなわち、物体の移動順序と移動経路を決定する処理の手順を、図２（ａ）（ｂ）に示す実施例を用いて説明する。図４は、物体再配置計画処理の流れを説明するフローチャートである。物体再配置計画装置１のコンピュータ２のＣＰＵは、物体再配置計画プログラムを実行し、記憶装置５に記憶された情報を適宜読み出しながら次に示す手順で所定の演算を行うことにより、物体再配置計画を作成することができる。
【００３６】
物体再配置計画装置１の有向グラフ作成部は、まず、複数の物体２０が配置されるステージ１０に係る情報と、複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報とを取得する（ステップＳ０）。ここで、コンピュータ２のＣＰＵは、記憶装置５から複数の物体２０が配置されるステージ１０に係る情報と複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報とを読み出す。但し、これらの情報は予め記憶装置５に格納されているものに限られない。例えば、コンピュータ２は、出力装置４で複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報の入力をユーザに促し、ユーザにより入力装置３を介して入力された複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報を取得することもできる。
【００３７】
物体再配置計画装置１が取得した複数の物体２０が配置されるステージ１０に係る情報と複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報には、ステージ１０の構成、ステージ１０での物体２０の移動の制約、複数の物体２０の移動前レイアウト（各物体の出発位置の座標）、および複数２０の物体の移動後レイアウト（各物体の目標位置の座標）が少なくとも含まれている。
【００３８】
次に、物体再配置計画装置１の移動要素抽出部６１は、各物体２０について出発位置から目標位置までの移動を移動要素として抽出する（ステップＳ１）。なお、移動要素には、出発位置と目標位置が同じであって物体が結果的に移動しないものも含まれる。物体再配置計画装置１の有向グラフ作成部６３は、抽出された各移動要素が節点（ノード）として表されたグラフを作成する（ステップＳ２）。物体２０の総数がｎ個の場合は、ｎ個の移動要素が抽出されて、グラフ上にｎ個の節点Ｎ1〜Ｎnが作成される。
【００３９】
図５に示すように、図２（ａ）（ｂ）に示す例では、物体Ａ〜ＧのそれぞれについてＮ1〜Ｎ7の合計７個の節点がグラフ上に作成される。物体Ａの節点Ｎ1は、出発位置（１，ｂ）から目標位置（２，ｆ）までの移動要素で成り、その移動要素が「Ａ：１ｂ→２ｆ」と表されている。同様に、物体Ｂの節点Ｎ2は、出発位置（２，ｄ）から目標位置（２，ａ）までの移動要素で成り、その移動要素が「Ｂ：２ｄ→２ａ」と表されている。物体Ｃの節点Ｎ3は、出発位置（２，ｂ）から目標位置（１，ｃ）までの移動要素で成り、その移動要素が「Ｃ：２ｂ→１ｃ」と表されている。物体Ｄの節点Ｎ4は、出発位置（１，ｃ）から目標位置（２，ｅ）までの移動要素で成り、その移動要素が「Ｄ：１ｃ→２ｅ」と表されている。物体Ｅの節点Ｎ5は、出発位置（２，ｅ）から目標位置（２，ｃ）までの移動要素から成り、その移動要素が「Ｅ：２ｅ→２ｃ」と表されている。物体Ｆの節点Ｎ6は、出発位置（１，ｄ）から目標位置（３，ａ）までの移動要素で成り、その移動要素が「Ｆ：１ｄ→３ａ」と表されている。物体Ｇの節点Ｎ７は、出発位置（３，ｂ）から目標位置（３，ｂ）までの移動要素で成り、その移動要素が「Ｇ：３ｂ→３ｂ」と表されている。ここで注意すべきは、再配置の前後で移動しない物体（物体Ｇ）については、出発位置から当該出発位置と同一の目標位置への移動要素を有するものとして、節点が作成されることである。
【００４０】
続いて、物体再配置計画装置１の順序制約探索部６２は、全ての物体２０について出発位置から目標位置までの移動経路を算出し（ステップＳ３）、算出された移動経路に基づいてグラフ上に作成された節点Ｎ1〜Ｎｎ同士の移動の順序制約を探索する（ステップＳ４）。節点同士の移動の順序制約は、つまり、移動要素同士の移動の順序制約である。
【００４１】
節点同士の移動の順序制約は、或ブロックに関する物体の移動の制約が、出発する移動、通過する移動、到着する移動の順であることに基づいて定められる。例えば、図３に示すように、ブロック（２，ｅ）に関する移動の順序制約は、このブロックを出発する物体Ｅの移動、このブロックを通過する物体Ａの移動、このブロックへ到着する物体Ｄの移動の順である。ここから、節点Ｎ5が先で節点Ｎ1が後、節点Ｎ1が先で節点Ｎ4が後という節点同士の移動の順序制約を定めることができる。
【００４２】
上記のように定められた節点同士の移動の順序制約に基づき、物体再配置計画装置１の有向グラフ作成部６３は、グラフ上に作成された節点Ｎ1〜Ｎｎを結ぶ辺（エッジ）を有向矢印で作成する（ステップＳ５）。この有向矢印は節点同士の移動の順序制約を表し、有向矢印の根元が先、矢印の向かう方が後である。このようにして、移動要素を表す各節点が移動要素の順序制約を表す有向矢印で結ばれた有向グラフが作成される。
【００４３】
図６に示すように、ブロック（２，ｅ）に関する移動の順序制約により、節点Ｎ5から節点Ｎ1へ向かう矢印と、節点Ｎ1から節点Ｎ4へ向かう矢印が作成される。同様に、ブロック（３，ｂ）に関する移動の順序制約により、節点Ｎ7から節点Ｎ6へ向かう矢印と、節点Ｎ6から節点Ｎ7へ向かう矢印が作成される。ブロック（２，ｃ）に関する移動の順序制約により、節点Ｎ3から節点Ｎ5へ向かう矢印と、節点Ｎ2から節点Ｎ5へ向かう矢印が作成される。ブロック（１，ｃ）に関する移動の順序制約により、節点Ｎ4から節点Ｎ1へ向かう矢印と、節点Ｎ1から節点Ｎ3へ向かう矢印が作成される。ブロック（２，ｂ）に関する移動の順序制約により、節点Ｎ3から節点Ｎ2へ向かう矢印が作成される。ブロック（２，ｄ）に関する移動の順序制約により、節点Ｎ2から節点Ｎ1へ向かう矢印と、節点Ｎ2から節点Ｎ5へ向かう矢印と、節点Ｎ2から節点Ｎ4へ向かう矢印が作成される。
【００４４】
上述のように作成された有向グラフにおいて、節点と有向矢印により形成される閉じられたループが存在することがある。有向グラフ上のループは、移動要素の順序制約のループであり、このループはデッドロックを意味している。ステージ１０において、物体２０は他の物体２０を追い越したり他の物体２０と同じブロック１３へ同時に移動したりすることができないためデッドロックが生じることがあり、このデッドロックは移動の順序制約のループとして有向グラフに表れる。よって、物体再配置計画装置１の有向グラフ作成部により作成された有向グラフに存在するループの有無により、複数の物体の再配置の作業の間に生じるデッドロックが発生するか否かを知ることができる。
【００４５】
物体再配置計画装置１のループ抽出部６４は、上述のように作成された有向グラフにおいて、有向矢印により形成される閉じられたループを抽出する（ステップＳ６）。有向グラフ中の全てのループを抽出するために、グラフ理論の深さ優先探索が用いられる。なお、複数の物体の再配置が比較的単純な場合には、有向グラフ上にループが存在しない、つまり、デッドロックが生じない場合もあり、このような場合は、ループは抽出されない。
【００４６】
図６に示す有向グラフには、６つのループ（節点Ｎ1，Ｎ4のループ、節点Ｎ1，Ｎ3，Ｎ2のループ、節点Ｎ1，Ｎ3，Ｎ5のループ、節点Ｎ1，Ｎ3，Ｎ2，Ｎ5のループ、節点Ｎ2，Ｎ4，Ｎ1，Ｎ3のループおよび節点Ｎ6，Ｎ7のループ）が存在し、これら全てのループが抽出される。
【００４７】
グラフ上にループが存在する状態では、前述の通り、デッドロックが生じるために移動が成立しない。そこで、物体再配置計画装置１のループ解消部６５は、ループ抽出部によりループが抽出された場合に、抽出された全てのループについて節点の分解を行い、全てのループを解消する（ステップＳ７）。
【００４８】
上記において「節点の分解」とは、ループを構成している節点のなかから１つを選択し、この１つの節点を仮に定めた待避位置を経由する２つの移動を表す節点に置き換えることを意味する。換言すれば、「節点の分解」とは、１つの移動要素を、出発位置から待避位置までの移動要素と、待避位置から出発位置までの移動要素とに置き換えることを意味する。
【００４９】
例えば、図６に示すように、グラフ上に節点Ｎ6，Ｎ7のループが存在する。このループについて節点の分解を行う場合には、図７に示すように、ループを構成している節点Ｎ6，Ｎ7のなかから１つ（ここでは、節点Ｎ7）を選択し、この節点Ｎ7を出発位置（３，ｂ）から待避位置Ｗ３までの移動を表す節点Ｎ71と、待避位置Ｗ３から目標位置（３，ｂ）までの移動を表す節点Ｎ72とに分解する。なお、待避位置Ｗ３は、出発位置および目標位置と異なる位置でなければならない。このように、節点Ｎ7が節点Ｎ71と節点Ｎ72とに分解されることによって、節点Ｎ6，Ｎ7のループが解消される。
【００５０】
節点の分解を行うに当たって、ループを構成している節点のうち分解可能な節点は１つに限られない。但し、複数の節点が分解可能である場合に、分解する節点の選定にルールが定められている。第１のルールは、２つの節点と２本の矢印から成る長さ２のループでは、その移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して選択するというものである。このルールに則れば、ループに出発位置と目標位置が同じ節点が含まれる場合には、必ずこの節点が分解される。第２のルールは、分解することによりループがより多く解消される節点を優先して選択するというものである。節点の分解により節点（すなわち、移動要素）の数が増加することは、再配置を完了するまでの時間の増加に繋がる。よって、グラフ上の節点の数をなるべく少なくするために、ループがより多く解消される節点が優先して選択されねばならない。
【００５１】
図６に示すグラフにおいて、上記ルールに則って分解される節点Ｎ3，Ｎ4，Ｎ7が選択され、これらの節点を分解することにより全てのループを解消することができる。図６に示すグラフ上には、長さ２のループが２つ存在する。第１のルールに則り、節点Ｎ1，Ｎ4のループでは、節点Ｎ4の物体Ｄの移動要素の経路は、物体Ａの移動要素の経路の一部に含まれることから、分解する節点として節点Ｎ4が選択される。また、第１のルールに則り、節点Ｎ6，Ｎ7のループでは、節点Ｎ7は出発位置と目標位置が同一であるから、分解する節点として節点Ｎ7が選択される。そして、長さ２のループを分解した後に残る長さ２以外のループには、節点Ｎ1，Ｎ3，Ｎ2のループ、節点Ｎ1，Ｎ3，Ｎ5のループおよび節点Ｎ1，Ｎ3，Ｎ2，Ｎ5のループが存在する。ここで、第２のルールに則り、分解する節点として節点Ｎ1または節点Ｎ3が優先的に選択される。図７に示す例では、節点Ｎ3が選択され、この節点Ｎ3が出発位置（２，ｂ）から待避位置Ｗ１までの移動要素を表す節点Ｎ31と、待避位置Ｗ１から目標位置（１，ｃ）までの移動要素を表す節点Ｎ32とに分解されている。上記節点の分解によりグラフ上の全てのループを解消した結果、グラフ上の節点は７個から１０個に増加している。
【００５２】
上述のように節点の分解を繰り返すことによりグラフ上の全てのループが解消されると、節点の半順序集合、すなわち、移動要素の半順序集合が完成する。移動要素の半順序集合では、或移動要素の移動を行った後、次に行うべき移動を表す移動要素を一意に選択することができない。そこで、物体再配置計画装置１は、前述のように完成した移動要素の半順序集合を基にして、物体の再配置を最短時間で完了する移動要素の順序を探索する。つまり、移動要素の半順序集合を全順序集合に変換する。移動要素の半順序集合を全順序集合に変換する方法は幾つか存在するが、ここでは、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）が用いられる。
【００５３】
具体的には、物体再配置計画装置１の順序決定部６６は、移動要素を表す各節点Ｎ1〜Ｎｎに乱数を与え（ステップＳ８）、節点同士の移動の順序制約を守るという条件の下で、節点Ｎ1〜Ｎｎの全順序を決定する（ステップＳ９）。節点の全順序が決まれば、物体再配置計画装置１の順序決定部６６は、仮に定めた待避位置に空きブロックを割り当てる（ステップＳ１０）。待避位置に実際のブロックが割り当てられれば、全ての物体の移動順序と移動経路が決定し、物体の再配置に要する作業時間を計算することができる。物体再配置計画装置１の順序決定部６６は、決定した節点の全順序で物体の再配置に要する作業時間を求める（ステップＳ１１）。そして、物体再配置計画装置１の順序決定部６６は、各節点に与えた乱数の数値配列を遺伝子とし、物体の再配置に要する作業時間を求める過程を評価関数として、遺伝的アルゴリズムＧＡを適用させて前記作業時間が最短となる遺伝子が残るように交叉を行い、ステップＳ８〜Ｓ１１の処理を繰り返して解を探索する（ステップＳ１２）。最後に、物体再配置計画装置１の順序決定部６６は、物体の再配置に要する作業時間が最短となる遺伝子に対応する移動要素の全順序を、最適な物体再配置計画と決定する（ステップＳ１３）。なお、遺伝的アルゴリズムＧＡは、一般に、評価関数が失敗する可能性が高すぎると良好に機能しないことがある。これに対し、以上説明した物体再配置計画の処理の流れでは、遺伝的アルゴリズムＧＡを適用させる前に半順序集合を求めることにより、遺伝的アルゴリズムＧＡの役割が自由度解決だけに絞られている。これにより、不正な移動順序の生成可能性が大きく排除される結果、物体の再配置に要する作業時間が最短となる移動要素の全順序を容易に求めることが可能となっている。
【００５４】
ここで、物体再配置計画装置１が遺伝的アルゴリズムＧＡを用いて、図７に示す移動要素（節点Ｎ1〜Ｎ72）の半順序集合を全順序集合に変換する流れを説明する。物体再配置計画装置１は、まず、図７に示すグラフ上の全ての節点Ｎ1〜Ｎ72に、次の表１に示すように［０、１）の乱数を与える（ステップＳ８）。
【００５５】
【表１】
【００５６】
次に、物体再配置計画装置１は、与えられた乱数の数値配列を遺伝子として、節点同士の移動の順序制約を守るという条件の下で最大（又は最小）の遺伝子要素が与えられた節点を選択することで、節点Ｎ1〜Ｎ72の全順序を決定する（ステップＳ９）。図８に示すように、最初に、節点同士の移動の順序制約を守るという条件の下で有向矢印の源となる節点Ｎ31，Ｎ41，Ｎ71が抽出され、これらの節点Ｎ31，Ｎ41，Ｎ71に与えられた遺伝子要素（０．４，０．５，０．０）が比較される。これらのうち最大の遺伝子要素が与えられた節点Ｎ41が選択され、節点Ｎ41の順序は１番目とされる。
【００５７】
次に、図９に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ31，Ｎ71が抽出され、これらの節点Ｎ31，Ｎ71に与えられた遺伝子要素（０．４，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ31が選択され、節点Ｎ31の順序は２番目とされる。
【００５８】
続いて、図１０に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ2，Ｎ71が抽出され、これらの節点Ｎ2，Ｎ71に与えられた遺伝子要素（０．１，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ2が選択され、節点Ｎ2の順序は３番目とされる。
【００５９】
続いて、図１１に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ5，Ｎ71が抽出され、これらの節点Ｎ5，Ｎ71に与えられた遺伝子要素（０．８，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ5が選択され、節点Ｎ5の順序は４番目とされる。
【００６０】
続いて、図１２に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ1，Ｎ71が抽出され、これらの節点Ｎ1，Ｎ71に与えられた遺伝子要素（０．２，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ1が選択され、節点Ｎ1の順序は５番目とされる。
【００６１】
続いて、図１３に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ32，Ｎ42，Ｎ71が抽出され、これらの節点Ｎ32，Ｎ42，Ｎ71に与えられた遺伝子要素（０．６，０．３，０．０）が比較される。これらのうち最大の遺伝子要素が与えられた節点Ｎ32が選択され、節点Ｎ32の順序は６番目とされる。そして、節点Ｎ42，Ｎ71に与えられた遺伝子要素（０．３，０．０）が比較され、このうち最大の遺伝子要素が与えられた節点Ｎ42の順序は７番目とされる。
【００６２】
最後に、図１４に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で、節点Ｎ71の順序は８番目とされ、節点Ｎ6の順序は９番目とされ、節点Ｎ72の順序は１０番目とされる。以上により、次の表２に示すように、節点Ｎ1〜Ｎ72の全順序が決定する。
【００６３】
【表２】
【００６４】
節点の全順序が決定すると、物体再配置計画装置１は、物体が待避位置に滞在している期間に空いているブロックを探索し、この空きブロックを待避位置に割り当てる（ステップＳ１０）。
【００６５】
表２に示すように、第１の待避位置Ｗ１には、物体Ｃが順序２番目から６番目の間に滞在している。この滞在期間に空いているブロック（３，ｄ）が第１の待避位置Ｗ１に割り当てられる。第２の待避位置Ｗ２には、物体Ｄが順序１番目から７番目の間に滞在している。この滞在期間に空いているブロック（３，ｃ）が第２の待避位置Ｗ２に割り当てられる。第３の待避位置Ｗ３には、物体Ｇが順序８番目から１０番目の間に滞在している。この滞在期間に空いているブロック（３，ｄ）が第３の待避位置Ｗ３に割り当てられる。なお、待避位置に割り当てることの可能な空きブロックが複数存在する場合には、遺伝的アルゴリズムＧＡを用いて物体の再配置に要する作業時間が最も短くなるような１つの空きブロックが選択される。なお、本実施の形態では、各待避位置に空きブロックを割り当てているが、待避位置は必ずしもステージ１０上のブロック１３に限定されない。例えば、ステージ１０上にトラバーサ１１が複数設けられている場合には、そのうち１以上のトラバーサ１１をいずれかの待避位置に割り当てることも可能である。また、ステージ１０上にブロック１３とは異なる１又は複数の待避位置を設けてもよい。
【００６６】
物体再配置計画装置１は、以上のようにして決められた移動順序に対して、物体の再配置に要する作業時間、換言すれば、全ての物体を出発位置から目標位置へ移動させるために必要な作業時間をシミュレーションにより計算する（ステップＳ１１）。物体再配置計画装置１のコンピュータ２にはシミュレーションモデルが予め構築されており、物体再配置計画装置１はこのシミュレーションモデルを用いて物体の再配置に要する作業時間を算出する。算出された物体の再配置に要する作業時間には、物体のレーンＬ上の移動時間、物体がトラバーサ１１で搬送される時間およびトラバーサ１１が物体を乗せずに移動する時間等が加味されている。
【００６７】
そして、物体再配置計画装置１は、物体の再配置に要する作業時間を遺伝子の評価値とし、遺伝的アルゴリズムＧＡにより物体の再配置に要する作業時間が最短となる遺伝子が残るように遺伝子（すなわち、各節点に付与される乱数の数値配列）を交叉しながら、ステップＳ８〜ステップＳ１１の処理を繰り返す（ステップＳ１２）。なお、遺伝的アルゴリズムＧＡの交叉（組み換え）方法は、一様交叉が用いられてよい。例えば、下記表３に示すように、各節点に与えられた乱数の数値配列である親遺伝子１と親遺伝子２とを一様交叉で組み換え、遺伝子の要素ごとに１／２の確率で親遺伝子１，２の要素を引き継いで子遺伝子を生成する。表３では、親遺伝子１および親遺伝子２の太枠で囲まれた遺伝子要素を組み合わせて子遺伝子を生成している。そして、この子遺伝子を用いてステップＳ８〜ステップＳ１３の処理が行われる。
【００６８】
【表３】
【００６９】
最後に、物体再配置計画装置１は、評価値が最小となる遺伝子、換言すれば、物体の再配置に要する作業時間が最短となる遺伝子に対応する移動順序を遺伝的アルゴリズムＧＡの解とし、物体再配置計画を決定する（ステップＳ１３）。このように決定された物体再配置計画は、物体の移動順序と移動経路とを含み、デッドロックが生じず、且つ、物体の再配置に要する作業時間が最短となっている。
【００７０】
以上説明した物体再配置計画の処理の流れでは、各物体の出発位置から目標位置までの移動を移動要素とし、移動要素を表す各節点が移動要素の順序制約を表す有向矢印で結ばれた有向グラフを表すことにより、移動要素の移動順序の制約関係が整理された状態となる。そして、この有向グラフにグラフ理論が適用されることにより、移動要素を表す各節点の半順序集合が作成される。さらに、この節点の半順序集合に遺伝的アルゴリズムＧＡが適用されることにより、節点の半順序集合が全順序集合に変換され、節点の全順序集合のうち最適なものが物体再配置計画として決定される。この物体再配置計画の処理の流れによれば、熟練の作業者の経験に頼らず物体再配置計画を作成することができる。しかも、作成された物体再配置計画の最適性は遺伝的アルゴリズムＧＡにより評価されており、作成された物体再配置計画はデッドロックが生じず、且つ、最短時間で物体の再配置を完了できるものとなる。このように、本発明によれば、パーソナルコンピュータ等の演算手段を用いて最適な物体再配置計画を自動的に作成することができ、物体再配置計画の作成にかかる労力と時間を削減することができる。物体再配置計画の作成にかかる時間の削減を達成した一実施例を紹介すると、１００個のブロック１３が設けられたステージにおいて８０個の物体２０の再配置計画を作成するための所要時間は、作業者では数時間であったが、本発明に係る物体再配置計画装置１では数分であった。
【００７１】
以上、本発明の好適な一実施形態について説明したが、本発明は上述の実施の形態に限られるものではなく、特許請求の範囲に記載した限りにおいて、様々な設計変更を行うことが可能である。
【００７２】
例えば、物体２０が再配置されるステージ１０の形態は上述の実施の形態に限定されない。各レーンＬに含まれるブロック１３の数や各エリア１２に含まれるレーンＬの数は適宜変更することができる。また、ステージ１０は平面であっても、立体であってもよい。ステージ１０が平面の場合は、複数のレーンＬが水平方向に並んで１つのエリア１２が形成され、トラバーサ１１は水平方向へ往復移動することとなる。ステージ１０が立体の場合は、複数のレーンＬが上下方向に並んで１つのエリア１２が形成され、トラバーサ１１は上下方向へ往復移動することとなる。さらに、ステージ１０に設けられるエリア１２の数やトラバーサ１１の数も、上述の実施の形態に限定されない。例えば、図１５に示すように、ステージ１０に３以上のエリア１２が設けられ、２以上のトラバーサ１１が設けられても良い。トラバーサ１１の配置はエリア１２間に限定されず、エリア１２間ではないレーンの端に設けられてもよい。また、トラバーサ１１はレーンＬ間で物体２０を渡すことができる物であればその移動方向は限定されず、トラバーサ１１はステージ１０上を自在に移動できるものであってもよい。
【００７３】
また、例えば、上述の実施形態において、遺伝的アルゴリズムＧＡの遺伝子要素を数値［０、１）とし、交叉（組み換え）方法を一様交叉としているが、遺伝的アルゴリズムＧＡの遺伝子要素の数値配列や交叉方法はこれに限定されない。
【００７４】
なお、本発明に係る物体再配置計画方法および装置は、鉄道車両の艤装工場において車両の再配置計画を作成するために利用できるが、本発明の利用範囲はこれにとどまらない。物体の移動に制約がある条件下で、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための再配置計画を作成するために、広く利用することができる。
【産業上の利用可能性】
【００７５】
本発明は、物体の移動の制約がある条件下で複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための再配置計画を、コンピュータ等の演算手段を用いて自動的に作成するために利用することができる。
【符号の説明】
【００７６】
Ｌ レーン
１ 物体再配置計画装置
２ コンピュータ
３ 入力装置
４ 出力装置
５ 記憶装置
６１ 移動要素抽出部
６２ 順序制約探索部
６３ 有向グラフ作成部
６４ ループ抽出部
６５ ループ解消部
６６ 順序決定部
１０ ステージ
１１ トラバーサ
１２ エリア
１３ ブロック
２０ 物体
【技術分野】
【０００１】
本発明は、複数の物体を次なる目的地へ再配置するための物体の移動手順を計画する技術に関する。
【背景技術】
【０００２】
従来、鉄道車両の組立や塗装等の作業が行われる車両の艤装工場では、作業毎に工区が決まっており、車両は作業工程に応じた工区へ移動させる必要がある。艤装工場では、敷設されたレール上に複数の工区がレールと平行な方向に並んで工区レーンを形成している。そして、複数の工区レーンがレールと交わる方向に並んで１つのエリアを形成している。エリアはレールと平行な方向に複数設けられており、エリア間にトラバーサが設けられている。トラバーサはレールと交わる方向に車両を移動させるものであり、トラバーサを介して車両を他の工区レーンへ移動させることができる。
【０００３】
上記のような艤装工場では、車両は自己が存在している工区が属する工区レーンを移動可能であるが、他の車両を追い越したり、他の車両が存在する工区へ移動したりすることができない。さらに、車両は工区レーンを跨って移動可能であるが、この場合トラバーサを経由する必要がある。艤装工場の車両の移動にはこのような制約があるため、無計画に車両を移動させたのではデッドロック（行き詰まり）が生じることがある。そこで、デッドロックが生じず、且つ、できるだけ時間を掛けずに移動前の車両の配置から移動後の車両の配置へ各車両を移動させるための車両再配置計画が作成され、この車両再配置計画に則って各車両を順次移動させている。車両再配置計画は、車両を現レイアウトから次レイアウトへ再配置するための車両の移動順序及び移動経路等の、再配置の過程を定めたものである。現状では、熟練の作業者が経験に基づき車両再配置計画を作成している。このように車両再配置計画の作成が作業者の経験に基づくために、車両再配置計画を作成できる人員の確保が困難となる事態が生じうる。また、車両再配置計画を評価するすべがなく、作成された車両再配置計画が最適であること、すなわち、デッドロックが生じず、且つ、最短時間で車両の移動を完了できるものであることを保証することができない。
【０００４】
上記課題は、鉄道車両の艤装工場における車両の再配置に限らず、物体の移動の制約がある条件下で複数の物体を移動前レイアウトから移動後レイアウトへ再配置する場合にも生じる。よって、鉄道車両の艤装工場に限らず、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、物体の移動順序および移動経路を定めた物体再配置計画を自動的に作成するシステムの開発が望まれている。
【０００５】
ところで、前述の艤装工場と異なる移動制約の下で物体の再配置の手順を計画するための手法は、例えば、特許文献１，２に示すように従来から提案されている。特許文献１には、横方向および縦方向に配置された複数の収納棚と、これらの収納棚に対し収納物の入れ換え作業を行うための昇降キャリッジを備えた自動倉庫において、収納物を再配置するための手法が示されている。特許文献１に記載された手法では、まず、入出庫要求の頻度の高い収納物がランクの高い収納棚位置（すなわち、キャリッジのホームポジションからより近い収納棚位置）に収納されるように収納物の再配置案を作成する。次に、入れ換え効果（すなわち、全体的な運転コストとアクセスタイムの改善率）の大きい収納物の組み合わせから順に入れ換えを実行するように、再配置案を最適化する。
【０００６】
また、特許文献２には、同一レーン上に複数台の搬送機械を有するコンテナヤードにおいて、コンテナ搬出を円滑且つ迅速に行うために搬送機械間の干渉を排除し配置換えの総作業時間をできる限り短縮できるようなコンテナの配置替え計画を作成する手法が示されている。特許文献２に記載された手法では、各搬送機械が処理するコンテナ処理順序を遺伝子表現とする個体群に遺伝的アルゴリズムを適用し、交叉および突然変異を行って、所定の適応度関数に基づいた淘汰によって世代更新を繰り返しながら最適計画を得る。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開昭６１−２９５９０２号公報
【特許文献２】特開平８−２７２７６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記特許文献１において、キャリッジは、横方向および縦方向に配置された複数の収納棚から制約なく収納物を取り出して、空いている任意の収納棚位置にその収納物を移動することができる。このように特許文献１では、比較的自由に収納物の入れ換えができるため、再配置案の作成について記載されているものの、収納物の移動順序や移動経路の決定方法については詳細に記載されていない。
【０００９】
また、上記特許文献２に記載の技術は、同一のレーン上を移動する複数の搬送機械で、輸入コンテナをバッファからヤードへ、輸出コンテナをヤードからバッファへそれぞれ配置換えする場合を想定しており、この複数の搬送機械が衝突したり追い越したりすることなくコンテナの受渡しをするように計画される。この特許文献２に記載の技術は上記のような単純な移動に適用することができるが、移動が複雑となったときに、遺伝的アルゴリズムの評価関数が失敗する可能性が高くなり、適切な解が得られない事態が生じうる。
【００１０】
そこで、本発明は、物体の移動に制約がある条件下で複数の物体を移動前のレイアウトから移動後のレイアウトへ再配置するために、デッドロックが生じない物体再配置計画（すなわち、物体の移動順序および移動経路）をパーソナルコンピュータ等の演算手段を用いて自動的に作成することを可能とする技術を提供することを目的とする。加えて、物体の再配置に要する作業時間が最短時間となる最適な物体再配置計画を作成する技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明に係る物体再配置計画装置は、物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成する物体再配置計画装置であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する移動要素抽出部と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を探索する順序制約探索部と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する、有向グラフ作成部とを備えるものである。なお、上記において「レイアウト」とは、ステージ上の物体の全体的な配列を意味する。
【００１２】
同様に、本発明に係る物体再配置計画方法は、物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画方法であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出するステップと、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求めるステップと、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成するステップとを含むものである。なお、上記において「レイアウト」とは、ステージ上の物体の全体的な配列を意味する。
【００１３】
同様に、本発明に係る物体再配置計画プログラムは、物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成するコンピュータで実行されるプログラムであって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する処理と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求める処理と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する処理とを、前記コンピュータに実行させるものである。なお、上記において「レイアウト」とは、ステージ上の物体の全体的な配列を意味する。
【００１４】
上記物体再配置計画装置、物体再配置計画方法、物体再配置計画プログラムによれば、作成された有向グラフには、節点により物体の移動が示され、有向矢印により物体の移動順序が示される。この有向グラフおいて、節点および有向矢印から成るループの有無により、複数の物体の再配置の作業の間に生じるデッドロックが発生するか否かを知ることができる。よって、物体の移動に制約がある条件下で、ステージ上の複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、デッドロックが生じない物体再配置計画（すなわち、物体の移動順序および移動経路）をパーソナルコンピュータ等の演算手段を用いて自動的に作成することが可能となる。
【００１５】
前記物体再配置計画装置において、前記順序制約探索部は、或ブロックに関わる１以上の物体の移動が、当該ブロックから出発する移動、当該ブロックを通過する移動、当該ブロックへ到着する移動の順となるように、前記複数の移動要素間の順序の制約を探索することができる。
【００１６】
上記のように前記複数の移動要素間の順序の制約を探索すれば、単純な演算で、もれなく前記複数の移動要素間の順序の制約を求めることができる。
【００１７】
前記物体再配置計画装置において、前記有向グラフにおいて、前記節点および前記有向矢印により形成されるループを深さ優先探索法により抽出する、ループ抽出部を備えることがよい。
【００１８】
上記物体再配置計画装置によれば、有向グラフ上に存在する複数の物体の再配置の作業の間に生じるデッドロックを意味するループを全て抽出することができる。
【００１９】
前記物体再配置計画装置において、前記ループ抽出部により前記ループが抽出されたときに、当該ループ内に含まれる１節点を、当該節点に対応する物体の前記出発位置から当該物体を一時的に待避させる待避位置までの移動から成る移動要素を表す第１の節点と、その物体の前記待避位置から前記目標位置までの移動から成る移動要素を表す第２の節点とに置き換えて前記ループを解消する、ループ解消部を備えることがよい。ここで、前記ループ抽出部により複数の前記ループが抽出され、抽出された複数の前記ループに前記節点の数が２のループが含まれるときに、前記ループ解消部は、前記節点の数が２のループを構成している節点のうちその移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して前記第１および第２の節点に置き換えることがよい。
【００２０】
上記物体再配置計画方法または物体再配置計画装置によれば、有向グラフ上に存在していたループが解消されるため、複数の物体の再配置の作業の間にデッドロックを生じさせないように複数の移動要素の順序を定めることが可能となる。
【００２１】
前記物体再配置計画装置において、前記有向矢印が表す前記複数の移動要素間の順序の制約に基づいて、前記複数の移動要素の順序を決定する、順序決定部を備えることがよい。
【００２２】
上記物体再配置計画装置によれば、ステージ上の複数の物体の再配置の作業の間にデッドロックを生じさせないような物体再配置計画（すなわち、各物体の移動順序と移動経路）を作成することができる。
【００２３】
前記物体再配置計画装置において、前記順序決定部は、各移動要素に乱数を与え、前記複数の移動要素間の順序の制約の下で前記乱数に基づいて優先順位を定めることにより、前記複数の移動要素の順序を決定し、決定した前記複数の移動要素の順序で前記複数の物体の再配置に要する作業時間を算出し、前記各移動要素に与えた乱数の数値配列を遺伝子とし、前記作業時間の算出過程を評価関数とし、遺伝的アルゴリズムを用いて前記作業時間が最短となる遺伝子が残るように交叉を繰り返して解を探索し、前記複数の移動要素の順序を決定することがよい。
【００２４】
上記物体再配置計画装置によれば、決定された複数の移動要素の順序は、ステージ上の物体の再配置に要する作業時間が最短となるものである。よって、ステージ上の物体の再配置の作業の間にデッドロックを生じず、且つ、物体の再配置に要する作業時間が最短時間となる最適な物体再配置計画を作成することができる。さらに、複数の移動要素の順序の半順序集合を予め決定し、この半順序集合を全順序集合に変換するために遺伝的アルゴリズムを利用するので、遺伝的アルゴリズムの評価関数が失敗する可能性を抑えることができ、適切な解を短時間で得ることが可能となる。
【発明の効果】
【００２５】
本発明によれば、物体の移動に制約がある条件下でステージ上の複数の物体を移動前レイアウトから移動後レイアウトへ再配置するために、デッドロックが生じない物体再配置計画（すなわち、物体の移動順序および移動経路）をパーソナルコンピュータ等の演算手段を用いて自動的に作成することが可能となる。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施の形態に係る物体再配置計画装置の概略構成を示すブロック図である。
【図２】複数の物体が配置されたステージの再配置の前後の状況の一例を示す図であり、（ａ）は移動前レイアウトを示し、（ｂ）は移動後レイアウトを示している。
【図３】ブロック（２，ｅ）に関する移動の順序制約を説明する図である。
【図４】物体再配置計画処理の流れを説明するフローチャートである。
【図５】物体の移動を節点とするグラフの一例である。
【図６】節点を結ぶ有向矢印が加えられたグラフの一例である。
【図７】節点の分解によりループが解消されたグラフの一例である。
【図８】遺伝子として与えられた乱数により節点の順序を決定する手法を説明する図（１）である。
【図９】与えられた乱数により節点の順序を決定する手法を説明する図（２）である。
【図１０】与えられた乱数により節点の順序を決定する手法を説明する図（３）である。
【図１１】与えられた乱数により節点の順序を決定する手法を説明する図（４）である。
【図１２】与えられた乱数により節点の順序を決定する手法を説明する図（５）である。
【図１３】与えられた乱数により節点の順序を決定する手法を説明する図（６）である。
【図１４】与えられた乱数により節点の順序を決定する手法を説明する図（７）である。
【図１５】複数の物体が配置されたステージの変形例を示す図である。
【発明を実施するための形態】
【００２７】
以下、本発明を実施するための形態について、図面を参照しながら、詳細に説明する。なお、以下では全ての図を通じて同一又は相当する要素には同一の参照符号を付して、その重複説明を省略する。
【００２８】
まず、本実施の形態に係る物体再配置計画装置について説明する。図１は本発明の実施の形態に係る物体再配置計画装置の概略構成を示すブロック図である。同図に示すように、物体再配置計画装置１は、主に１又は複数のコンピュータ２からなり、各コンピュータ２はＣＰＵ（中央処理装置）、ＣＰＵが実行する物体再配置計画プログラムやこのプログラムで使用されるデータを書き替え可能に記憶する主記憶装置、ＣＰＵがプログラム実行時にデータを一時的に記憶する副記憶装置、ＣＰＵと外部機器を接続するためのインターフェース、並びにこれらを接続する内部経路等を備えている（何れも不図示）。物体再配置計画プログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、メモリカード等の各種記憶媒体に保存されており、これらの記憶媒体からコンピュータ２にインストールされる。そして、この物体再配置計画プログラムがコンピュータ２のＣＰＵで実行されることにより、物体再配置計画装置１としての機能が実現される。物体再配置計画プログラムは、移動要素抽出ルーチン、順序制約探索ルーチン、有向グラフ作成ルーチン、ループ抽出ルーチン、ループ解消ルーチン、および順序決定ルーチンを少なくとも含んでいる。これらは物体再配置計画装置１において、移動要素抽出部６１、順序制約探索部６２、有向グラフ作成部６３、ループ抽出部６４、ループ解消部６５、および順序決定部６６としてそれぞれ機能する。物体再配置計画装置１のこれらの機能部の機能については後ほど詳細に説明する。
【００２９】
コンピュータ２は、インターフェースを介してマウスポインタやキーボード等の入力装置３と接続されている。ユーザが入力装置３に対して入力操作を行った場合には、その操作内容を示す信号がコンピュータ２へ入力され、コンピュータ２は入力信号に基づいて処理を行う。また、コンピュータ２は、インターフェースを介してディスプレイやプリンタ等の出力装置４と接続されている。コンピュータ２が、動作上ユーザに提供する各種の情報は出力装置４において文字や記号により適宜表示される。さらに、コンピュータ２は、インターフェースを介して記憶装置５と接続されている。記憶装置５には、物体が配置されるステージ１０に係る情報と、複数の物体の移動前レイアウトと移動後レイアウトに係る情報とが少なくとも記憶されている。なお、これらの情報は、記憶装置５に代えてコンピュータ２が備える記憶装置に記憶されていてもよい。
【００３０】
次に、物体が配置されるステージおよびこのステージでの物体の移動の制約について説明する。図２（ａ）（ｂ）は複数の物体が配置されたステージの一例を示している。図２（ａ）は物体の移動前レイアウトを示し、図２（ｂ）は物体の移動後レイアウトを示している。ステージ１０において、１以上のブロック１３が一方向（図２の紙面左右方向）に並んで１本のレーンＬが形成されている。そして、複数のレーンＬがレーンと交わる方向（図２の紙面上下方向）に互いに略平行に並んで、１つのエリア１２が形成されている。
【００３１】
図２（ａ）（ｂ）に示す例では、ステージ１０に第１のエリア１２ａと第２のエリア１２ｂとの、行方向に並ぶ２つのエリアが形成されている。第１のエリア１２ａにはＬ11，Ｌ12，Ｌ13の３本のレーンＬが形成され、第２のエリア１２ｂにはＬ21，Ｌ22，Ｌ23の３本のレーンＬが形成されている。レーンＬ11には、座標が（１，ｂ）と（１，ｃ）でそれぞれ表される２つのブロック１３が設けられている。レーンＬ12には、座標が（２，ａ）と（２，ｂ）と（２，ｃ）でそれぞれ表される３つのブロック１３が設けられている。レーンＬ13には、座標が（３，ａ）と（３，ｂ）と（３，ｃ）でそれぞれ表される３つのブロック１３が設けられている。以下同様に、レーンＬ21，レーンＬ22，レーンＬ23に複数のブロック１３が設けられている。ステージ１０には合計１５個のブロック１３が設けられており、このうち７個のブロック１３にＡ〜Ｇまでの７個の物体２０がそれぞれ配置されている。以下では、図２（ａ）に示される物体Ａ〜Ｇの配置されているブロック１３を「出発位置」ということがあり、図２（ｂ）に示される物体Ａ〜Ｇの配置されているブロック１３を「目標位置」ということがある。
【００３２】
ステージ１０の第１のエリア１２ａと第２のエリア１２ｂの２つのエリアの間には、レーンと交わる方向に移動可能なトラバーサ１１が設けられている。トラバーサ１１は物体２０を１つずつレーンと交わる方向へ運ぶことができる。或レーンＬに存在する物体２０が他のレーンＬへ移動するとき、つまり、物体２０がレーンＬを跨いで移動するときには、トラバーサ１１を介することとなる。
【００３３】
上記構成のステージ１０において、物体２０には次に示す＜１＞〜＜３＞の移動の制約が課せられる。＜１＞物体が配置されるステージ１０には物体２０が１つずつ配置され得るブロック１３が１以上並んだレーンＬが複数存在しており、物体２０はレーンＬに沿って移動することができる。＜２＞物体２０は他の物体が存在しているブロック１３へ移動したり、他の物体２０を追い越して移動したりすることができない。＜３＞物体２０は他のレーンＬへ移動することができるが、必ずトラバーサ１１を介さねばならない。これは、各レーンＬには出入口に相当するブロック（図２（ａ）（ｂ）に示す例ではトラバーサ１１に隣接しているブロック）が決まっており、この出入口に相当するブロックを通らねば物体２０は他のレーンＬへ移動することができないことを意味している。
【００３４】
上記のような移動の制約から、次のような移動の順序制約が生じる。図３は、ブロック（２，ｅ）に関する移動の順序制約を説明する図である。以下では、「ブロック（座標）」で、その座標のブロックを示すこととする。例えば、図２（ａ）（ｂ）に示す移動前後の配置からブロック（２，ｅ）に関係する物体２０の移動を抽出すると、図３に示すように、物体Ｅがブロック（２，ｅ）から出発してブロック（２，ｃ）へ到着する移動、物体Ａがブロック（１，ｂ）を出発してブロック（２，ｅ）を通過してブロック（２，ｆ）へ到着する移動、物体Ｄがブロック（１，ｃ）を出発してブロック（２，ｅ）へ到着する移動の、３つの移動がある。ブロック（２，ｅ）の立場で見れば、出発する移動、通過する移動、到着する移動の順でなければ移動は成立せず、これが移動の順序制約を生じさせる。よって、ブロック（２，ｅ）について物体Ａ，Ｄ，Ｅの移動の順序制約は、物体Ｅ→物体Ａ→物体Ｄの順となる。以上、ブロック（２，ｅ）に関係する物体の移動の順序制約について説明したが、他のブロックでも同様に物体の移動の順序制約が生じる。
【００３５】
続いて、図４を参照しつつ、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための物体再配置計画、すなわち、物体の移動順序と移動経路を決定する処理の手順を、図２（ａ）（ｂ）に示す実施例を用いて説明する。図４は、物体再配置計画処理の流れを説明するフローチャートである。物体再配置計画装置１のコンピュータ２のＣＰＵは、物体再配置計画プログラムを実行し、記憶装置５に記憶された情報を適宜読み出しながら次に示す手順で所定の演算を行うことにより、物体再配置計画を作成することができる。
【００３６】
物体再配置計画装置１の有向グラフ作成部は、まず、複数の物体２０が配置されるステージ１０に係る情報と、複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報とを取得する（ステップＳ０）。ここで、コンピュータ２のＣＰＵは、記憶装置５から複数の物体２０が配置されるステージ１０に係る情報と複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報とを読み出す。但し、これらの情報は予め記憶装置５に格納されているものに限られない。例えば、コンピュータ２は、出力装置４で複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報の入力をユーザに促し、ユーザにより入力装置３を介して入力された複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報を取得することもできる。
【００３７】
物体再配置計画装置１が取得した複数の物体２０が配置されるステージ１０に係る情報と複数の物体２０の移動前レイアウトと移動後レイアウトに係る情報には、ステージ１０の構成、ステージ１０での物体２０の移動の制約、複数の物体２０の移動前レイアウト（各物体の出発位置の座標）、および複数２０の物体の移動後レイアウト（各物体の目標位置の座標）が少なくとも含まれている。
【００３８】
次に、物体再配置計画装置１の移動要素抽出部６１は、各物体２０について出発位置から目標位置までの移動を移動要素として抽出する（ステップＳ１）。なお、移動要素には、出発位置と目標位置が同じであって物体が結果的に移動しないものも含まれる。物体再配置計画装置１の有向グラフ作成部６３は、抽出された各移動要素が節点（ノード）として表されたグラフを作成する（ステップＳ２）。物体２０の総数がｎ個の場合は、ｎ個の移動要素が抽出されて、グラフ上にｎ個の節点Ｎ1〜Ｎnが作成される。
【００３９】
図５に示すように、図２（ａ）（ｂ）に示す例では、物体Ａ〜ＧのそれぞれについてＮ1〜Ｎ7の合計７個の節点がグラフ上に作成される。物体Ａの節点Ｎ1は、出発位置（１，ｂ）から目標位置（２，ｆ）までの移動要素で成り、その移動要素が「Ａ：１ｂ→２ｆ」と表されている。同様に、物体Ｂの節点Ｎ2は、出発位置（２，ｄ）から目標位置（２，ａ）までの移動要素で成り、その移動要素が「Ｂ：２ｄ→２ａ」と表されている。物体Ｃの節点Ｎ3は、出発位置（２，ｂ）から目標位置（１，ｃ）までの移動要素で成り、その移動要素が「Ｃ：２ｂ→１ｃ」と表されている。物体Ｄの節点Ｎ4は、出発位置（１，ｃ）から目標位置（２，ｅ）までの移動要素で成り、その移動要素が「Ｄ：１ｃ→２ｅ」と表されている。物体Ｅの節点Ｎ5は、出発位置（２，ｅ）から目標位置（２，ｃ）までの移動要素から成り、その移動要素が「Ｅ：２ｅ→２ｃ」と表されている。物体Ｆの節点Ｎ6は、出発位置（１，ｄ）から目標位置（３，ａ）までの移動要素で成り、その移動要素が「Ｆ：１ｄ→３ａ」と表されている。物体Ｇの節点Ｎ７は、出発位置（３，ｂ）から目標位置（３，ｂ）までの移動要素で成り、その移動要素が「Ｇ：３ｂ→３ｂ」と表されている。ここで注意すべきは、再配置の前後で移動しない物体（物体Ｇ）については、出発位置から当該出発位置と同一の目標位置への移動要素を有するものとして、節点が作成されることである。
【００４０】
続いて、物体再配置計画装置１の順序制約探索部６２は、全ての物体２０について出発位置から目標位置までの移動経路を算出し（ステップＳ３）、算出された移動経路に基づいてグラフ上に作成された節点Ｎ1〜Ｎｎ同士の移動の順序制約を探索する（ステップＳ４）。節点同士の移動の順序制約は、つまり、移動要素同士の移動の順序制約である。
【００４１】
節点同士の移動の順序制約は、或ブロックに関する物体の移動の制約が、出発する移動、通過する移動、到着する移動の順であることに基づいて定められる。例えば、図３に示すように、ブロック（２，ｅ）に関する移動の順序制約は、このブロックを出発する物体Ｅの移動、このブロックを通過する物体Ａの移動、このブロックへ到着する物体Ｄの移動の順である。ここから、節点Ｎ5が先で節点Ｎ1が後、節点Ｎ1が先で節点Ｎ4が後という節点同士の移動の順序制約を定めることができる。
【００４２】
上記のように定められた節点同士の移動の順序制約に基づき、物体再配置計画装置１の有向グラフ作成部６３は、グラフ上に作成された節点Ｎ1〜Ｎｎを結ぶ辺（エッジ）を有向矢印で作成する（ステップＳ５）。この有向矢印は節点同士の移動の順序制約を表し、有向矢印の根元が先、矢印の向かう方が後である。このようにして、移動要素を表す各節点が移動要素の順序制約を表す有向矢印で結ばれた有向グラフが作成される。
【００４３】
図６に示すように、ブロック（２，ｅ）に関する移動の順序制約により、節点Ｎ5から節点Ｎ1へ向かう矢印と、節点Ｎ1から節点Ｎ4へ向かう矢印が作成される。同様に、ブロック（３，ｂ）に関する移動の順序制約により、節点Ｎ7から節点Ｎ6へ向かう矢印と、節点Ｎ6から節点Ｎ7へ向かう矢印が作成される。ブロック（２，ｃ）に関する移動の順序制約により、節点Ｎ3から節点Ｎ5へ向かう矢印と、節点Ｎ2から節点Ｎ5へ向かう矢印が作成される。ブロック（１，ｃ）に関する移動の順序制約により、節点Ｎ4から節点Ｎ1へ向かう矢印と、節点Ｎ1から節点Ｎ3へ向かう矢印が作成される。ブロック（２，ｂ）に関する移動の順序制約により、節点Ｎ3から節点Ｎ2へ向かう矢印が作成される。ブロック（２，ｄ）に関する移動の順序制約により、節点Ｎ2から節点Ｎ1へ向かう矢印と、節点Ｎ2から節点Ｎ5へ向かう矢印と、節点Ｎ2から節点Ｎ4へ向かう矢印が作成される。
【００４４】
上述のように作成された有向グラフにおいて、節点と有向矢印により形成される閉じられたループが存在することがある。有向グラフ上のループは、移動要素の順序制約のループであり、このループはデッドロックを意味している。ステージ１０において、物体２０は他の物体２０を追い越したり他の物体２０と同じブロック１３へ同時に移動したりすることができないためデッドロックが生じることがあり、このデッドロックは移動の順序制約のループとして有向グラフに表れる。よって、物体再配置計画装置１の有向グラフ作成部により作成された有向グラフに存在するループの有無により、複数の物体の再配置の作業の間に生じるデッドロックが発生するか否かを知ることができる。
【００４５】
物体再配置計画装置１のループ抽出部６４は、上述のように作成された有向グラフにおいて、有向矢印により形成される閉じられたループを抽出する（ステップＳ６）。有向グラフ中の全てのループを抽出するために、グラフ理論の深さ優先探索が用いられる。なお、複数の物体の再配置が比較的単純な場合には、有向グラフ上にループが存在しない、つまり、デッドロックが生じない場合もあり、このような場合は、ループは抽出されない。
【００４６】
図６に示す有向グラフには、６つのループ（節点Ｎ1，Ｎ4のループ、節点Ｎ1，Ｎ3，Ｎ2のループ、節点Ｎ1，Ｎ3，Ｎ5のループ、節点Ｎ1，Ｎ3，Ｎ2，Ｎ5のループ、節点Ｎ2，Ｎ4，Ｎ1，Ｎ3のループおよび節点Ｎ6，Ｎ7のループ）が存在し、これら全てのループが抽出される。
【００４７】
グラフ上にループが存在する状態では、前述の通り、デッドロックが生じるために移動が成立しない。そこで、物体再配置計画装置１のループ解消部６５は、ループ抽出部によりループが抽出された場合に、抽出された全てのループについて節点の分解を行い、全てのループを解消する（ステップＳ７）。
【００４８】
上記において「節点の分解」とは、ループを構成している節点のなかから１つを選択し、この１つの節点を仮に定めた待避位置を経由する２つの移動を表す節点に置き換えることを意味する。換言すれば、「節点の分解」とは、１つの移動要素を、出発位置から待避位置までの移動要素と、待避位置から出発位置までの移動要素とに置き換えることを意味する。
【００４９】
例えば、図６に示すように、グラフ上に節点Ｎ6，Ｎ7のループが存在する。このループについて節点の分解を行う場合には、図７に示すように、ループを構成している節点Ｎ6，Ｎ7のなかから１つ（ここでは、節点Ｎ7）を選択し、この節点Ｎ7を出発位置（３，ｂ）から待避位置Ｗ３までの移動を表す節点Ｎ71と、待避位置Ｗ３から目標位置（３，ｂ）までの移動を表す節点Ｎ72とに分解する。なお、待避位置Ｗ３は、出発位置および目標位置と異なる位置でなければならない。このように、節点Ｎ7が節点Ｎ71と節点Ｎ72とに分解されることによって、節点Ｎ6，Ｎ7のループが解消される。
【００５０】
節点の分解を行うに当たって、ループを構成している節点のうち分解可能な節点は１つに限られない。但し、複数の節点が分解可能である場合に、分解する節点の選定にルールが定められている。第１のルールは、２つの節点と２本の矢印から成る長さ２のループでは、その移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して選択するというものである。このルールに則れば、ループに出発位置と目標位置が同じ節点が含まれる場合には、必ずこの節点が分解される。第２のルールは、分解することによりループがより多く解消される節点を優先して選択するというものである。節点の分解により節点（すなわち、移動要素）の数が増加することは、再配置を完了するまでの時間の増加に繋がる。よって、グラフ上の節点の数をなるべく少なくするために、ループがより多く解消される節点が優先して選択されねばならない。
【００５１】
図６に示すグラフにおいて、上記ルールに則って分解される節点Ｎ3，Ｎ4，Ｎ7が選択され、これらの節点を分解することにより全てのループを解消することができる。図６に示すグラフ上には、長さ２のループが２つ存在する。第１のルールに則り、節点Ｎ1，Ｎ4のループでは、節点Ｎ4の物体Ｄの移動要素の経路は、物体Ａの移動要素の経路の一部に含まれることから、分解する節点として節点Ｎ4が選択される。また、第１のルールに則り、節点Ｎ6，Ｎ7のループでは、節点Ｎ7は出発位置と目標位置が同一であるから、分解する節点として節点Ｎ7が選択される。そして、長さ２のループを分解した後に残る長さ２以外のループには、節点Ｎ1，Ｎ3，Ｎ2のループ、節点Ｎ1，Ｎ3，Ｎ5のループおよび節点Ｎ1，Ｎ3，Ｎ2，Ｎ5のループが存在する。ここで、第２のルールに則り、分解する節点として節点Ｎ1または節点Ｎ3が優先的に選択される。図７に示す例では、節点Ｎ3が選択され、この節点Ｎ3が出発位置（２，ｂ）から待避位置Ｗ１までの移動要素を表す節点Ｎ31と、待避位置Ｗ１から目標位置（１，ｃ）までの移動要素を表す節点Ｎ32とに分解されている。上記節点の分解によりグラフ上の全てのループを解消した結果、グラフ上の節点は７個から１０個に増加している。
【００５２】
上述のように節点の分解を繰り返すことによりグラフ上の全てのループが解消されると、節点の半順序集合、すなわち、移動要素の半順序集合が完成する。移動要素の半順序集合では、或移動要素の移動を行った後、次に行うべき移動を表す移動要素を一意に選択することができない。そこで、物体再配置計画装置１は、前述のように完成した移動要素の半順序集合を基にして、物体の再配置を最短時間で完了する移動要素の順序を探索する。つまり、移動要素の半順序集合を全順序集合に変換する。移動要素の半順序集合を全順序集合に変換する方法は幾つか存在するが、ここでは、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）が用いられる。
【００５３】
具体的には、物体再配置計画装置１の順序決定部６６は、移動要素を表す各節点Ｎ1〜Ｎｎに乱数を与え（ステップＳ８）、節点同士の移動の順序制約を守るという条件の下で、節点Ｎ1〜Ｎｎの全順序を決定する（ステップＳ９）。節点の全順序が決まれば、物体再配置計画装置１の順序決定部６６は、仮に定めた待避位置に空きブロックを割り当てる（ステップＳ１０）。待避位置に実際のブロックが割り当てられれば、全ての物体の移動順序と移動経路が決定し、物体の再配置に要する作業時間を計算することができる。物体再配置計画装置１の順序決定部６６は、決定した節点の全順序で物体の再配置に要する作業時間を求める（ステップＳ１１）。そして、物体再配置計画装置１の順序決定部６６は、各節点に与えた乱数の数値配列を遺伝子とし、物体の再配置に要する作業時間を求める過程を評価関数として、遺伝的アルゴリズムＧＡを適用させて前記作業時間が最短となる遺伝子が残るように交叉を行い、ステップＳ８〜Ｓ１１の処理を繰り返して解を探索する（ステップＳ１２）。最後に、物体再配置計画装置１の順序決定部６６は、物体の再配置に要する作業時間が最短となる遺伝子に対応する移動要素の全順序を、最適な物体再配置計画と決定する（ステップＳ１３）。なお、遺伝的アルゴリズムＧＡは、一般に、評価関数が失敗する可能性が高すぎると良好に機能しないことがある。これに対し、以上説明した物体再配置計画の処理の流れでは、遺伝的アルゴリズムＧＡを適用させる前に半順序集合を求めることにより、遺伝的アルゴリズムＧＡの役割が自由度解決だけに絞られている。これにより、不正な移動順序の生成可能性が大きく排除される結果、物体の再配置に要する作業時間が最短となる移動要素の全順序を容易に求めることが可能となっている。
【００５４】
ここで、物体再配置計画装置１が遺伝的アルゴリズムＧＡを用いて、図７に示す移動要素（節点Ｎ1〜Ｎ72）の半順序集合を全順序集合に変換する流れを説明する。物体再配置計画装置１は、まず、図７に示すグラフ上の全ての節点Ｎ1〜Ｎ72に、次の表１に示すように［０、１）の乱数を与える（ステップＳ８）。
【００５５】
【表１】
【００５６】
次に、物体再配置計画装置１は、与えられた乱数の数値配列を遺伝子として、節点同士の移動の順序制約を守るという条件の下で最大（又は最小）の遺伝子要素が与えられた節点を選択することで、節点Ｎ1〜Ｎ72の全順序を決定する（ステップＳ９）。図８に示すように、最初に、節点同士の移動の順序制約を守るという条件の下で有向矢印の源となる節点Ｎ31，Ｎ41，Ｎ71が抽出され、これらの節点Ｎ31，Ｎ41，Ｎ71に与えられた遺伝子要素（０．４，０．５，０．０）が比較される。これらのうち最大の遺伝子要素が与えられた節点Ｎ41が選択され、節点Ｎ41の順序は１番目とされる。
【００５７】
次に、図９に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ31，Ｎ71が抽出され、これらの節点Ｎ31，Ｎ71に与えられた遺伝子要素（０．４，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ31が選択され、節点Ｎ31の順序は２番目とされる。
【００５８】
続いて、図１０に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ2，Ｎ71が抽出され、これらの節点Ｎ2，Ｎ71に与えられた遺伝子要素（０．１，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ2が選択され、節点Ｎ2の順序は３番目とされる。
【００５９】
続いて、図１１に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ5，Ｎ71が抽出され、これらの節点Ｎ5，Ｎ71に与えられた遺伝子要素（０．８，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ5が選択され、節点Ｎ5の順序は４番目とされる。
【００６０】
続いて、図１２に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ1，Ｎ71が抽出され、これらの節点Ｎ1，Ｎ71に与えられた遺伝子要素（０．２，０．０）が比較される。このうち最大の遺伝子要素が与えられた節点Ｎ1が選択され、節点Ｎ1の順序は５番目とされる。
【００６１】
続いて、図１３に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で節点Ｎ32，Ｎ42，Ｎ71が抽出され、これらの節点Ｎ32，Ｎ42，Ｎ71に与えられた遺伝子要素（０．６，０．３，０．０）が比較される。これらのうち最大の遺伝子要素が与えられた節点Ｎ32が選択され、節点Ｎ32の順序は６番目とされる。そして、節点Ｎ42，Ｎ71に与えられた遺伝子要素（０．３，０．０）が比較され、このうち最大の遺伝子要素が与えられた節点Ｎ42の順序は７番目とされる。
【００６２】
最後に、図１４に示すように、順序が未定の節点同士の移動の順序制約を守るという条件の下で、節点Ｎ71の順序は８番目とされ、節点Ｎ6の順序は９番目とされ、節点Ｎ72の順序は１０番目とされる。以上により、次の表２に示すように、節点Ｎ1〜Ｎ72の全順序が決定する。
【００６３】
【表２】
【００６４】
節点の全順序が決定すると、物体再配置計画装置１は、物体が待避位置に滞在している期間に空いているブロックを探索し、この空きブロックを待避位置に割り当てる（ステップＳ１０）。
【００６５】
表２に示すように、第１の待避位置Ｗ１には、物体Ｃが順序２番目から６番目の間に滞在している。この滞在期間に空いているブロック（３，ｄ）が第１の待避位置Ｗ１に割り当てられる。第２の待避位置Ｗ２には、物体Ｄが順序１番目から７番目の間に滞在している。この滞在期間に空いているブロック（３，ｃ）が第２の待避位置Ｗ２に割り当てられる。第３の待避位置Ｗ３には、物体Ｇが順序８番目から１０番目の間に滞在している。この滞在期間に空いているブロック（３，ｄ）が第３の待避位置Ｗ３に割り当てられる。なお、待避位置に割り当てることの可能な空きブロックが複数存在する場合には、遺伝的アルゴリズムＧＡを用いて物体の再配置に要する作業時間が最も短くなるような１つの空きブロックが選択される。なお、本実施の形態では、各待避位置に空きブロックを割り当てているが、待避位置は必ずしもステージ１０上のブロック１３に限定されない。例えば、ステージ１０上にトラバーサ１１が複数設けられている場合には、そのうち１以上のトラバーサ１１をいずれかの待避位置に割り当てることも可能である。また、ステージ１０上にブロック１３とは異なる１又は複数の待避位置を設けてもよい。
【００６６】
物体再配置計画装置１は、以上のようにして決められた移動順序に対して、物体の再配置に要する作業時間、換言すれば、全ての物体を出発位置から目標位置へ移動させるために必要な作業時間をシミュレーションにより計算する（ステップＳ１１）。物体再配置計画装置１のコンピュータ２にはシミュレーションモデルが予め構築されており、物体再配置計画装置１はこのシミュレーションモデルを用いて物体の再配置に要する作業時間を算出する。算出された物体の再配置に要する作業時間には、物体のレーンＬ上の移動時間、物体がトラバーサ１１で搬送される時間およびトラバーサ１１が物体を乗せずに移動する時間等が加味されている。
【００６７】
そして、物体再配置計画装置１は、物体の再配置に要する作業時間を遺伝子の評価値とし、遺伝的アルゴリズムＧＡにより物体の再配置に要する作業時間が最短となる遺伝子が残るように遺伝子（すなわち、各節点に付与される乱数の数値配列）を交叉しながら、ステップＳ８〜ステップＳ１１の処理を繰り返す（ステップＳ１２）。なお、遺伝的アルゴリズムＧＡの交叉（組み換え）方法は、一様交叉が用いられてよい。例えば、下記表３に示すように、各節点に与えられた乱数の数値配列である親遺伝子１と親遺伝子２とを一様交叉で組み換え、遺伝子の要素ごとに１／２の確率で親遺伝子１，２の要素を引き継いで子遺伝子を生成する。表３では、親遺伝子１および親遺伝子２の太枠で囲まれた遺伝子要素を組み合わせて子遺伝子を生成している。そして、この子遺伝子を用いてステップＳ８〜ステップＳ１３の処理が行われる。
【００６８】
【表３】
【００６９】
最後に、物体再配置計画装置１は、評価値が最小となる遺伝子、換言すれば、物体の再配置に要する作業時間が最短となる遺伝子に対応する移動順序を遺伝的アルゴリズムＧＡの解とし、物体再配置計画を決定する（ステップＳ１３）。このように決定された物体再配置計画は、物体の移動順序と移動経路とを含み、デッドロックが生じず、且つ、物体の再配置に要する作業時間が最短となっている。
【００７０】
以上説明した物体再配置計画の処理の流れでは、各物体の出発位置から目標位置までの移動を移動要素とし、移動要素を表す各節点が移動要素の順序制約を表す有向矢印で結ばれた有向グラフを表すことにより、移動要素の移動順序の制約関係が整理された状態となる。そして、この有向グラフにグラフ理論が適用されることにより、移動要素を表す各節点の半順序集合が作成される。さらに、この節点の半順序集合に遺伝的アルゴリズムＧＡが適用されることにより、節点の半順序集合が全順序集合に変換され、節点の全順序集合のうち最適なものが物体再配置計画として決定される。この物体再配置計画の処理の流れによれば、熟練の作業者の経験に頼らず物体再配置計画を作成することができる。しかも、作成された物体再配置計画の最適性は遺伝的アルゴリズムＧＡにより評価されており、作成された物体再配置計画はデッドロックが生じず、且つ、最短時間で物体の再配置を完了できるものとなる。このように、本発明によれば、パーソナルコンピュータ等の演算手段を用いて最適な物体再配置計画を自動的に作成することができ、物体再配置計画の作成にかかる労力と時間を削減することができる。物体再配置計画の作成にかかる時間の削減を達成した一実施例を紹介すると、１００個のブロック１３が設けられたステージにおいて８０個の物体２０の再配置計画を作成するための所要時間は、作業者では数時間であったが、本発明に係る物体再配置計画装置１では数分であった。
【００７１】
以上、本発明の好適な一実施形態について説明したが、本発明は上述の実施の形態に限られるものではなく、特許請求の範囲に記載した限りにおいて、様々な設計変更を行うことが可能である。
【００７２】
例えば、物体２０が再配置されるステージ１０の形態は上述の実施の形態に限定されない。各レーンＬに含まれるブロック１３の数や各エリア１２に含まれるレーンＬの数は適宜変更することができる。また、ステージ１０は平面であっても、立体であってもよい。ステージ１０が平面の場合は、複数のレーンＬが水平方向に並んで１つのエリア１２が形成され、トラバーサ１１は水平方向へ往復移動することとなる。ステージ１０が立体の場合は、複数のレーンＬが上下方向に並んで１つのエリア１２が形成され、トラバーサ１１は上下方向へ往復移動することとなる。さらに、ステージ１０に設けられるエリア１２の数やトラバーサ１１の数も、上述の実施の形態に限定されない。例えば、図１５に示すように、ステージ１０に３以上のエリア１２が設けられ、２以上のトラバーサ１１が設けられても良い。トラバーサ１１の配置はエリア１２間に限定されず、エリア１２間ではないレーンの端に設けられてもよい。また、トラバーサ１１はレーンＬ間で物体２０を渡すことができる物であればその移動方向は限定されず、トラバーサ１１はステージ１０上を自在に移動できるものであってもよい。
【００７３】
また、例えば、上述の実施形態において、遺伝的アルゴリズムＧＡの遺伝子要素を数値［０、１）とし、交叉（組み換え）方法を一様交叉としているが、遺伝的アルゴリズムＧＡの遺伝子要素の数値配列や交叉方法はこれに限定されない。
【００７４】
なお、本発明に係る物体再配置計画方法および装置は、鉄道車両の艤装工場において車両の再配置計画を作成するために利用できるが、本発明の利用範囲はこれにとどまらない。物体の移動に制約がある条件下で、複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための再配置計画を作成するために、広く利用することができる。
【産業上の利用可能性】
【００７５】
本発明は、物体の移動の制約がある条件下で複数の物体を移動前レイアウトから移動後レイアウトへ再配置するための再配置計画を、コンピュータ等の演算手段を用いて自動的に作成するために利用することができる。
【符号の説明】
【００７６】
Ｌ レーン
１ 物体再配置計画装置
２ コンピュータ
３ 入力装置
４ 出力装置
５ 記憶装置
６１ 移動要素抽出部
６２ 順序制約探索部
６３ 有向グラフ作成部
６４ ループ抽出部
６５ ループ解消部
６６ 順序決定部
１０ ステージ
１１ トラバーサ
１２ エリア
１３ ブロック
２０ 物体
【特許請求の範囲】
【請求項１】
物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成する物体再配置計画装置であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する移動要素抽出部と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を探索する順序制約探索部と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する、有向グラフ作成部とを備える、物体再配置計画装置。
【請求項２】
前記順序制約探索部は、或ブロックに関わる１以上の物体の移動が、当該ブロックから出発する移動、当該ブロックを通過する移動、当該ブロックへ到着する移動の順となるように、前記複数の移動要素間の順序の制約を探索する、請求項１に記載の物体再配置計画装置。
【請求項３】
前記有向グラフにおいて、前記節点および前記有向矢印により形成されるループを深さ優先探索法により抽出する、ループ抽出部を備える、請求項１又は２に記載の物体再配置計画装置。
【請求項４】
前記ループ抽出部により前記ループが抽出されたときに、当該ループ内に含まれる１節点を、当該節点に対応する物体の前記出発位置から当該物体を一時的に待避させる待避位置までの移動から成る移動要素を表す第１の節点と、その物体の前記待避位置から前記目標位置までの移動から成る移動要素を表す第２の節点とに置き換えて前記ループを解消する、ループ解消部を備える、請求項３に記載の物体再配置計画装置。
【請求項５】
前記ループ抽出部により複数の前記ループが抽出され、抽出された複数の前記ループに前記節点の数が２のループが含まれるときに、
前記ループ解消部は、前記節点の数が２のループを構成している節点のうちその移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して前記第１および第２の節点に置き換える、
請求項４に記載の物体再配置計画装置。
【請求項６】
前記有向矢印が表す前記複数の移動要素間の順序の制約に基づいて、前記複数の移動要素の順序を決定する、順序決定部を備える、請求項１〜５のいずれか一項に記載の物体再配置計画装置。
【請求項７】
前記順序決定部は、
各移動要素に乱数を与え、前記複数の移動要素間の順序の制約の下で前記乱数に基づいて優先順位を定めることにより、前記複数の移動要素の順序を決定し、
決定した前記複数の移動要素の順序で前記複数の物体の再配置に要する作業時間を算出し、
前記各移動要素に与えた乱数の数値配列を遺伝子とし、前記作業時間の算出過程を評価関数とし、遺伝的アルゴリズムを用いて前記作業時間が最短となる遺伝子が残るように交叉を繰り返して解を探索し、前記複数の移動要素の順序を決定する、請求項６に記載の物体再配置計画装置。
【請求項８】
物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画方法であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出するステップと、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求めるステップと、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成するステップとを含む、物体再配置計画方法。
【請求項９】
物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成するコンピュータで実行される物体再配置計画プログラムであって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する処理と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求める処理と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する処理とを、前記コンピュータに実行させる物体再配置計画プログラム。
【請求項１】
物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成する物体再配置計画装置であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する移動要素抽出部と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を探索する順序制約探索部と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する、有向グラフ作成部とを備える、物体再配置計画装置。
【請求項２】
前記順序制約探索部は、或ブロックに関わる１以上の物体の移動が、当該ブロックから出発する移動、当該ブロックを通過する移動、当該ブロックへ到着する移動の順となるように、前記複数の移動要素間の順序の制約を探索する、請求項１に記載の物体再配置計画装置。
【請求項３】
前記有向グラフにおいて、前記節点および前記有向矢印により形成されるループを深さ優先探索法により抽出する、ループ抽出部を備える、請求項１又は２に記載の物体再配置計画装置。
【請求項４】
前記ループ抽出部により前記ループが抽出されたときに、当該ループ内に含まれる１節点を、当該節点に対応する物体の前記出発位置から当該物体を一時的に待避させる待避位置までの移動から成る移動要素を表す第１の節点と、その物体の前記待避位置から前記目標位置までの移動から成る移動要素を表す第２の節点とに置き換えて前記ループを解消する、ループ解消部を備える、請求項３に記載の物体再配置計画装置。
【請求項５】
前記ループ抽出部により複数の前記ループが抽出され、抽出された複数の前記ループに前記節点の数が２のループが含まれるときに、
前記ループ解消部は、前記節点の数が２のループを構成している節点のうちその移動要素の経路が他の移動要素の経路の一部に含まれる節点を優先して前記第１および第２の節点に置き換える、
請求項４に記載の物体再配置計画装置。
【請求項６】
前記有向矢印が表す前記複数の移動要素間の順序の制約に基づいて、前記複数の移動要素の順序を決定する、順序決定部を備える、請求項１〜５のいずれか一項に記載の物体再配置計画装置。
【請求項７】
前記順序決定部は、
各移動要素に乱数を与え、前記複数の移動要素間の順序の制約の下で前記乱数に基づいて優先順位を定めることにより、前記複数の移動要素の順序を決定し、
決定した前記複数の移動要素の順序で前記複数の物体の再配置に要する作業時間を算出し、
前記各移動要素に与えた乱数の数値配列を遺伝子とし、前記作業時間の算出過程を評価関数とし、遺伝的アルゴリズムを用いて前記作業時間が最短となる遺伝子が残るように交叉を繰り返して解を探索し、前記複数の移動要素の順序を決定する、請求項６に記載の物体再配置計画装置。
【請求項８】
物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、
前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画方法であって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出するステップと、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求めるステップと、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成するステップとを含む、物体再配置計画方法。
【請求項９】
物体が１つずつ配置され得るブロックが１以上並んだレーンが複数存在し、物体が前記レーン上を他の物体を追い越すことなく移動することおよび物体が前記レーン間を移動することが許容されたステージにおいて、前記ステージ上の物体の各々が出発位置にあたるブロックに配置された移動前レイアウトから、前記ステージ上の物体の各々が目標位置にあたるブロックに配置された移動後レイアウトへ、前記ステージ上の物体を再配置するための物体再配置計画を作成するコンピュータで実行される物体再配置計画プログラムであって、
前記移動前レイアウトおよび前記移動後レイアウトに基づいて、各物体について前記出発位置から前記目標位置までの移動を移動要素として抽出する処理と、
前記移動前レイアウト、前記移動後レイアウトおよび前記ステージの構成に基づいて、前記複数の移動要素間の順序の制約を求める処理と、
抽出された複数の移動要素を節点とし、前記複数の移動要素間の順序の制約を前記節点間を結ぶ有向矢印とする有向グラフを作成する処理とを、前記コンピュータに実行させる物体再配置計画プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１２−２４２８８８（Ｐ２０１２−２４２８８８Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１０９３１５（Ｐ２０１１−１０９３１５）
【出願日】平成２３年５月１６日（２０１１．５．１６）
【出願人】（００００００９７４）川崎重工業株式会社 (1,710)
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月１６日（２０１１．５．１６）
【出願人】（００００００９７４）川崎重工業株式会社 (1,710)
[ Back to top ]