(57)【要約】【課題】  搬送物を目的地まで搬送するのに適したＡＧＶを自動的に割り付けるようにする。【解決手段】  ＡＧＶの走行をペトリネットモデルで構築し、ＡＧＶ状態と搬送命令に応じて設定された目標状態量Ｍrを目標として、ペトリネットの状態方程式から操作ベクトルｕ(k)を決定する。制御手段２１３はこの操作ベクトルに基づき各コイルと各ＡＧＶの移動操作を行うことにより最適制御理論を用いて配車問題の解を求める。一方、コスト関数設定手段２０８でＡＧＶの総空車走行時間とコイルの総搬送待ち時間との線型和となる関数を設定し、配車組み合わせ計算手段２０９で、このコスト関数が最小となる解を求める。シミュレーション手段２０３は、以上の配車問題の解を用いて各々シミュレーションを行い、コスト関数比較手段２１１にて最もコスト関数が小さくなる解を求め、その解を上位プロコン１０１へ返す。【選択図】  図２
2006107121.tif 000002
【特許請求の範囲】
【請求項１】
搬送プロセスをペトリネットモデルで表し、上記ペトリネットモデルから搬送命令の搬送車に対する割り付けを決定する配車計画作成装置であって、
上記搬送プロセスのペトリネットモデルとして、上記搬送車の走行路をプレースと移動操作端とで表すとともに、搬送物及び搬送車をトークンで表したペトリネットモデルを構築するモデル構築手段と、
上記モデル構築手段により構築されたペトリネットモデルの状態方程式を求めるとともに、上記求めた状態方程式と、設定した評価行列及び目標状態量によって表される評価関数とからフィードバックゲイン行列を求めるゲイン行列算出手段と、
上記搬送プロセスにおけるトークンの仕掛状態を表す状態ベクトルを取得する状態ベクトル入力手段と、
上記ゲイン行列算出手段により求められたフィードバックゲイン行列と、上記状態ベクトル入力手段により取得された仕掛状態を表す状態ベクトルと、上記搬送車の状態及び与えられる搬送命令に応じて設定される目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求める操作ベクトル算出手段と、
上記操作ベクトル算出手段により求められた操作ベクトルに基づいて、各移動操作端に対して、上記操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び各搬送車を移動可能な数だけ移動させる操作を行うことにより、その操作後の状態ベクトルを求め、求めた操作後の状態ベクトルを用いて、上記各搬送車に対して各搬送物を割付ける配車問題の解を求める制御手段とを備え、
上記制御手段は、上記求めた操作後の状態ベクトルを、上記搬送プロセスにおけるトークンの仕掛状態を表す新たな状態ベクトルとして上記状態ベクトル入力手段にフィードバックさせることを特徴とする配車計画作成装置。
【請求項２】
上記モデル構築手段は、上記搬送車が作業を行う場所であるスキッド用のペトリネットモデルモジュールと、上記搬送車が通信を行う場所である中継用ペトリネットモデルモジュールとを組み合わせてペトリネットモデルを構築することを特徴とする請求項１に記載の配車計画作成装置。
【請求項３】
上記モデル構築手段によって上記ペトリネットモデルを上記搬送車ごとに構築し、上記搬送命令が割り付け済みの搬送車については個々にペトリネットモデルを用い、上記搬送命令が未割り付けの搬送車については１つのペトリネットモデルをまとめて用いるようにし、
上記搬送命令を上記未割り付けの搬送車に対して割り付けるようにしたことを特徴とする請求項１又は２に記載の配車計画作成装置。
【請求項４】
上記制御手段は、上記操作ベクトル算出手段によって上記搬送車ごとに算出された操作ベクトルを統合した操作ベクトルに基づいて、各移動操作端に対して、上記統合した操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び搬送車を移動可能な数だけ移動させるようにする操作を行うことを特徴とする請求項３に記載の配車計画作成装置。
【請求項５】
上記搬送車の状態遷移を上記移動操作端の発火に応じて制御し管理する状態管理手段を備えることを特徴とする請求項１〜４の何れか１項に記載の配車計画作成装置。
【請求項６】
上記各搬送車の位置及び作業状態と、上記各搬送車に割り付いた各搬送物の搬送元及び搬送先とにより定義されるコスト関数を設定するコスト関数設定手段と、
上記目標状態量を、上記コスト関数の係数比の関数として変更する目標値変更手段と、
上記コスト関数の値ができるだけ小さくなるように、上記各搬送車に対して各搬送物を割付ける配車問題の解を、組み合わせ最適化手法を用いて複数求める配車組合わせ計算手段と、
上記制御手段より得られた配車問題の解と、上記配車組み合わせ計算手段により得られた配車問題の解とに対して、各々シミュレーションを行い、上記コスト関数の値を計算するシミュレーション手段と、
上記シミュレーション手段で計算された全てのコスト関数の値を比較し、最も小さい値に対応した配車問題の解を出力するコスト関数比較手段とを備え、
上記操作ベクトル算出手段は、上記ゲイン行列算出手段により求められたフィードバックゲイン行列と、上記状態ベクトル入力手段により取得された仕掛状態を表す状態ベクトルと、上記目標値変更手段により変更された目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求めることを特徴とする請求項１〜５の何れか１項に記載の配車計画作成装置。
【請求項７】
上記コスト関数設定手段は、各搬送車の空車走行時間の単調増加関数と各搬送物の搬送待ち時間の単調増加関数との線型和をコスト関数として用いることを特徴とする請求項６に記載の配車計画作成装置。
【請求項８】
上記コスト関数設定手段は、各搬送車の空車走行時間の単調増加関数と各搬送物の搬送待ち時間の単調増加関数と、特定のゾーン付近に搬送車が集中することによって値が大きくなる関数との線型和をコスト関数として用いることを特徴とする請求項６に記載の配車計画作成装置。
【請求項９】
上記配車組合わせ計算手段は、上記各搬送車のバッテリ残量が指定された値を下回らないように、上記各搬送車が最寄りのバッテリ場に到着するまでに走行する時間及び上記最寄りのバッテリ場における上記各搬送車の充電時間を加味して、上記配車問題の解を求めることを特徴とする請求項６〜８の何れか１項に記載の配車計画作成装置。
【請求項１０】
上記配車組合わせ計算手段は、上記搬送車の走行路を複数のエリアに分割して、そのエリアで空車と荷卸し中の搬送車とが、指定された台数以上になった場合には、上記指定された台数以下になるよう上記搬送車を別エリアに退避させるように、上記配車問題の解を求めることを特徴とする請求項６〜９の何れか１項に記載の配車計画作成装置。
【請求項１１】
搬送プロセスをペトリネットモデルで表し、上記ペトリネットモデルから搬送命令の搬送車に対する割り付けを決定する配車計画作成方法であって、
上記搬送プロセスのペトリネットモデルとして、上記搬送車の走行路をプレースと移動操作端とで表すとともに、搬送物及び搬送車をトークンで表したペトリネットモデルを構築するモデル構築ステップと、
上記モデル構築ステップにより構築されたペトリネットモデルの状態方程式を求めるとともに、上記求めた状態方程式と、設定した評価行列及び目標状態量によって表される評価関数とからフィードバックゲイン行列を求めるゲイン行列算出ステップと、
上記搬送プロセスにおけるトークンの仕掛状態を表す状態ベクトルを取得する状態ベクトル入力ステップと、
上記ゲイン行列算出ステップにより求められたフィードバックゲイン行列と、上記状態ベクトル入力ステップにより取得された仕掛状態を表す状態ベクトルと、上記搬送車の状態及び与えられる搬送命令に応じて設定される目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求める操作ベクトル算出ステップと、
上記操作ベクトル算出ステップにより求められた操作ベクトルに基づいて、各移動操作端に対して、上記操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び各搬送車を移動可能な数だけ移動させる操作を行うことにより、その操作後の状態ベクトルを求め、求めた操作後の状態ベクトルを用いて、上記各搬送車に対して各搬送物を割付ける配車問題の解を求める制御ステップとを備え、
上記状態ベクトル入力ステップは、上記制御ステップにより求められた上記操作後の状態ベクトルを、上記搬送プロセスにおけるトークンの仕掛状態を表す新たな状態ベクトルとして取得することを特徴とする配車計画作成方法。
【請求項１２】
搬送プロセスをペトリネットモデルで表し、上記ペトリネットモデルから搬送命令の搬送車に対する割り付けを決定することをコンピュータに実行させるためのコンピュータプログラムであって、
上記搬送プロセスのペトリネットモデルとして、上記搬送車の走行路をプレースと移動操作端とで表すとともに、搬送物及び搬送車をトークンで表したペトリネットモデルを構築するモデル構築ステップと、
上記モデル構築ステップにより構築されたペトリネットモデルの状態方程式を求めるとともに、上記求めた状態方程式と、設定した評価行列及び目標状態量によって表される評価関数とからフィードバックゲイン行列を求めるゲイン行列算出ステップと、
上記搬送プロセスにおけるトークンの仕掛状態を表す状態ベクトルを取得する状態ベクトル入力ステップと、
上記ゲイン行列算出ステップにより求められたフィードバックゲイン行列と、上記状態ベクトル入力ステップにより取得された仕掛状態を表す状態ベクトルと、上記搬送車の状態及び与えられる搬送命令に応じて設定される目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求める操作ベクトル算出ステップと、
上記操作ベクトル算出ステップにより求められた操作ベクトルに基づいて、各移動操作端に対して、上記操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び各搬送車を移動可能な数だけ移動させる操作を行うことにより、その操作後の状態ベクトルを求め、求めた操作後の状態ベクトルを用いて、上記各搬送車に対して各搬送物を割付ける配車問題の解を求める制御ステップとをコンピュータに実行させ、
上記状態ベクトル入力ステップは、上記制御ステップにより求められた上記操作後の状態ベクトルを、上記搬送プロセスにおけるトークンの仕掛状態を表す新たな状態ベクトルとして取得することを特徴とするコンピュータプログラム。
【請求項１３】
上記請求項１２に記載のコンピュータプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配車計画作成装置、配車計画作成方法、コンピュータプログラム、及びコンピュータ読み取り可能な記録媒体に関し、特に、無人搬送台車の配車計画（搬送命令の割り付け）を行うための装置に用いて好適なものである。
【背景技術】
【０００２】
鉄鋼を始めとする多くの産業における製造プロセスでは、複数の製品を異なる複数の工程で処理して製造している。そのため、各製造ライン間で材料や製品を搬送することが必要となる。従来、物を搬送するための物流システムとして、例えば複数の無人搬送台車（ＡＧＶ＝Automatic Guided Vehicle）を用いたシステムが利用されている。
【０００３】
このＡＧＶを用いたシステムでは、ＡＧＶと上位のプロセスコンピュータ（以下、プロコンと言う）とで通信をしながら、上位プロコンから与えられる搬送命令をＡＧＶに割り付けることによって各ＡＧＶに走行ルートデータを設定し、あらかじめ設定した走行路上を無人で走行することにより、複数のＡＧＶスキッド（物を蓄えておくバッファのようなもの）間で物を搬送するようになっている。
【０００４】
このとき、複数の光空間伝送装置（ＯＣＤ）がＡＧＶの走行ルートに沿って設置されており、このＯＣＤを介して、ＡＧＶと上位プロコン本体との間で通信が行われる。これにより、上述したように上位プロコンからの搬送命令を各ＡＧＶに割り付けることができるとともに、どのＡＧＶによりどういう物をどこへ搬送しているのかが上位プロコンで把握可能なようになっている。
【０００５】
上述のようなＡＧＶを用いた搬送システムにおいては、材料や製品を各ＡＧＶスキッド間で搬送する際に、複数個あるＡＧＶのうちどのＡＧＶを使って搬送させるか、つまり、上位プロコンから出力される１つ以上の搬送命令をどのＡＧＶに割り付けるかを決める必要がある。そして、この決定方式に関して従来は、搬送が終わるなどして空車となったＡＧＶのうち、現在の位置から搬送命令中に示されている荷受け位置までの距離が短い順に割り付けを行うようにしていた（特許文献１を参照）。
【０００６】
【特許文献１】特開平１１−３２７６４４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、上述したような搬送システムでは、例えば、ＡＧＶの走行路の状態によっては、荷受け位置までの距離は近くても、荷受け位置までの走行時間が長くなる場合がある。しかしながら、上述した従来の手法では、このような場合であっても、荷受け位置までの距離が近いＡＧＶに搬送命令を割り付けてしまう。すなわち、上述した従来の技術では、荷受け位置までの距離は近いが必ずしも荷受け位置までの走行時間がより短くなるＡＧＶに搬送命令の割り付けが行われるとは限らないという問題があった。
【０００８】
一般にＡＧＶが走行する走行路は、設備コストや工場内の物理的スペースの問題などから単線で設計され、双方向にＡＧＶが走行することが多い。このため、複数のＡＧＶが走行中に衝突（干渉）を起こすことがある。ＡＧＶが干渉を起こすと、停止したり退避走行や逆走をしたりする必要があるので、結果として長い時間がかかってしまうことになる。
【０００９】
また、このような干渉が起こらなくても、走行路の状態（例えば、走行路が直線であるか曲線であるかによって走行速度は異なる）やその他の要因により、他のＡＧＶより距離が短くても走行時間が上記他のＡＧＶより短くならないことがあった。
【００１０】
本発明は、このような問題を解決するために成されたものであり、搬送物を目的地まで搬送するのに適したＡＧＶなどの搬送車を自動的に割り付けることを第１の目的とする。
また、このような搬送命令の割り付けにより、搬送車の走行時間を短くしたり、搬送物が運び出されるまでの搬送待ち時間を短くしたり、搬送車の空車走行時間と搬送待ち時間両者のトレードオフとを最適に調整したりすることができるようにすることを第２の目的とする。
【課題を解決するための手段】
【００１１】
本発明の配車計画作成装置は、搬送プロセスをペトリネットモデルで表し、上記ペトリネットモデルから搬送命令の搬送車に対する割り付けを決定する配車計画作成装置であって、上記搬送プロセスのペトリネットモデルとして、上記搬送車の走行路をプレースと移動操作端とで表すとともに、搬送物及び搬送車をトークンで表したペトリネットモデルを構築するモデル構築手段と、上記モデル構築手段により構築されたペトリネットモデルの状態方程式を求めるとともに、上記求めた状態方程式と、設定した評価行列及び目標状態量によって表される評価関数とからフィードバックゲイン行列を求めるゲイン行列算出手段と、上記搬送プロセスにおけるトークンの仕掛状態を表す状態ベクトルを取得する状態ベクトル入力手段と、上記ゲイン行列算出手段により求められたフィードバックゲイン行列と、上記状態ベクトル入力手段により取得された仕掛状態を表す状態ベクトルと、上記搬送車の状態及び与えられる搬送命令に応じて設定される目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求める操作ベクトル算出手段と、上記操作ベクトル算出手段により求められた操作ベクトルに基づいて、各移動操作端に対して、上記操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び各搬送車を移動可能な数だけ移動させる操作を行うことにより、その操作後の状態ベクトルを求め、求めた操作後の状態ベクトルを用いて、上記各搬送車に対して各搬送物を割付ける配車問題の解を求める制御手段とを備え、上記制御手段は、上記求めた操作後の状態ベクトルを、上記搬送プロセスにおけるトークンの仕掛状態を表す新たな状態ベクトルとして上記状態ベクトル入力手段にフィードバックさせることを特徴とする。
また、本発明の他の特徴とするところは、上記モデル構築手段は、上記搬送車が作業を行う場所であるスキッド用のペトリネットモデルモジュールと、上記搬送車が通信を行う場所である中継用ペトリネットモデルモジュールとを組み合わせてペトリネットモデルを構築することにある。
また、本発明のその他の特徴とするところは、上記モデル構築手段によって上記ペトリネットモデルを上記搬送車ごとに構築し、上記搬送命令が割り付け済みの搬送車については個々にペトリネットモデルを用い、上記搬送命令が未割り付けの搬送車については１つのペトリネットモデルをまとめて用いるようにし、上記搬送命令を上記未割り付けの搬送車に対して割り付けるようにしたことにある。
また、本発明のその他の特徴とするところは、上記制御手段は、上記操作ベクトル算出手段によって上記搬送車ごとに算出された操作ベクトルを統合した操作ベクトルに基づいて、各移動操作端に対して、上記統合した操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び搬送車を移動可能な数だけ移動させるようにする操作を行うことにある。
また、本発明のその他の特徴とするところは、上記搬送車の状態遷移を上記移動操作端の発火に応じて制御し管理する状態管理手段を備えることにある。
また、本発明のその他の特徴とするところは、上記各搬送車の位置及び作業状態と、上記各搬送車に割り付いた各搬送物の搬送元及び搬送先とにより定義されるコスト関数を設定するコスト関数設定手段と、上記目標状態量を、上記コスト関数の係数比の関数として変更する目標値変更手段と、上記コスト関数の値ができるだけ小さくなるように、上記各搬送車に対して各搬送物を割付ける配車問題の解を、組み合わせ最適化手法を用いて複数求める配車組合わせ計算手段と、上記制御手段より得られた配車問題の解と、上記配車組み合わせ計算手段により得られた配車問題の解とに対して、各々シミュレーションを行い、上記コスト関数の値を計算するシミュレーション手段と、上記シミュレーション手段で計算された全てのコスト関数の値を比較し、最も小さい値に対応した配車問題の解を出力するコスト関数比較手段とを備え、上記操作ベクトル算出手段は、上記ゲイン行列算出手段により求められたフィードバックゲイン行列と、上記状態ベクトル入力手段により取得された仕掛状態を表す状態ベクトルと、上記目標値変更手段により変更された目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求めることにある。
また、本発明のその他の特徴とするところは、上記コスト関数設定手段は、各搬送車の空車走行時間の単調増加関数と各搬送物の搬送待ち時間の単調増加関数との線型和をコスト関数として用いることにある。
また、本発明のその他の特徴とするところは、上記コスト関数設定手段は、各搬送車の空車走行時間の単調増加関数と各搬送物の搬送待ち時間の単調増加関数と、特定のゾーン付近に搬送車が集中することによって値が大きくなる関数との線型和をコスト関数として用いることにある。
また、本発明のその他の特徴とするところは、上記配車組合わせ計算手段は、上記各搬送車のバッテリ残量が指定された値を下回らないように、上記各搬送車が最寄りのバッテリ場に到着するまでに走行する時間及び上記最寄りのバッテリ場における上記各搬送車の充電時間を加味して、上記配車問題の解を求めることにある。
また、本発明のその他の特徴とするところは、上記配車組合わせ計算手段は、上記搬送車の走行路を複数のエリアに分割して、そのエリアで空車と荷卸し中の搬送車とが、指定された台数以上になった場合には、上記指定された台数以下になるよう上記搬送車を別エリアに退避させるように、上記配車問題の解を求めることにある。
【００１２】
本発明の配車計画作成方法は、搬送プロセスをペトリネットモデルで表し、上記ペトリネットモデルから搬送命令の搬送車に対する割り付けを決定する配車計画作成方法であって、上記搬送プロセスのペトリネットモデルとして、上記搬送車の走行路をプレースと移動操作端とで表すとともに、搬送物及び搬送車をトークンで表したペトリネットモデルを構築するモデル構築ステップと、上記モデル構築ステップにより構築されたペトリネットモデルの状態方程式を求めるとともに、上記求めた状態方程式と、設定した評価行列及び目標状態量によって表される評価関数とからフィードバックゲイン行列を求めるゲイン行列算出ステップと、上記搬送プロセスにおけるトークンの仕掛状態を表す状態ベクトルを取得する状態ベクトル入力ステップと、上記ゲイン行列算出ステップにより求められたフィードバックゲイン行列と、上記状態ベクトル入力ステップにより取得された仕掛状態を表す状態ベクトルと、上記搬送車の状態及び与えられる搬送命令に応じて設定される目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求める操作ベクトル算出ステップと、上記操作ベクトル算出ステップにより求められた操作ベクトルに基づいて、各移動操作端に対して、上記操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び各搬送車を移動可能な数だけ移動させる操作を行うことにより、その操作後の状態ベクトルを求め、求めた操作後の状態ベクトルを用いて、上記各搬送車に対して各搬送物を割付ける配車問題の解を求める制御ステップとを備え、上記状態ベクトル入力ステップは、上記制御ステップにより求められた上記操作後の状態ベクトルを、上記搬送プロセスにおけるトークンの仕掛状態を表す新たな状態ベクトルとして取得することを特徴とする。
【００１３】
本発明のコンピュータプログラムは、搬送プロセスをペトリネットモデルで表し、上記ペトリネットモデルから搬送命令の搬送車に対する割り付けを決定することをコンピュータに実行させるためのコンピュータプログラムであって、上記搬送プロセスのペトリネットモデルとして、上記搬送車の走行路をプレースと移動操作端とで表すとともに、搬送物及び搬送車をトークンで表したペトリネットモデルを構築するモデル構築ステップと、上記モデル構築ステップにより構築されたペトリネットモデルの状態方程式を求めるとともに、上記求めた状態方程式と、設定した評価行列及び目標状態量によって表される評価関数とからフィードバックゲイン行列を求めるゲイン行列算出ステップと、上記搬送プロセスにおけるトークンの仕掛状態を表す状態ベクトルを取得する状態ベクトル入力ステップと、上記ゲイン行列算出ステップにより求められたフィードバックゲイン行列と、上記状態ベクトル入力ステップにより取得された仕掛状態を表す状態ベクトルと、上記搬送車の状態及び与えられる搬送命令に応じて設定される目標状態量とを用いて、上記搬送物及び搬送車の移動操作端に対する操作ベクトルを求める操作ベクトル算出ステップと、上記操作ベクトル算出ステップにより求められた操作ベクトルに基づいて、各移動操作端に対して、上記操作ベクトルの中の正値で大きい操作量が得られた順に各搬送物及び各搬送車を移動可能な数だけ移動させる操作を行うことにより、その操作後の状態ベクトルを求め、求めた操作後の状態ベクトルを用いて、上記各搬送車に対して各搬送物を割付ける配車問題の解を求める制御ステップとをコンピュータに実行させ、上記状態ベクトル入力ステップは、上記制御ステップにより求められた上記操作後の状態ベクトルを、上記搬送プロセスにおけるトークンの仕掛状態を表す新たな状態ベクトルとして取得することを特徴とする。
本発明のコンピュータ読み取り可能な記録媒体は、上記記載のコンピュータプログラムを記録したことを特徴とする。
【発明の効果】
【００１４】
本発明によれば、搬送プロセスをペトリネットモデルで表し、ペトリネットモデルから得られる状態方程式と、設定した評価行列及び目標状態量によって表される評価関数に応じて、各搬送車へ搬送命令を割り付けるようにしたので、距離的に近い搬送車に搬送命令を割り付けていた従来例に対して、搬送車の走行時間を短くすることができるとともに、搬送車間の干渉も格段に少なくすることができ、干渉によって搬送車の走行時間が長くなることを防止することができる。
また、本発明の他の特徴によれば、シミュレーションを行って、搬送車の位置及び作業状態と、搬送車に割り付いた搬送物の搬送元及び搬送先とにより定義されるコスト関数の値が小さくなる解を求め、その解に基づいて搬送車の割り付けを行うようにしたので、搬送車の空車走行時間と搬送物の搬送待ち時間とのトレードオフを考慮した割り付けを行うことができる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施形態を図面に基づいて説明する。
（配車計画作成装置の概要）
図１は、本実施形態の配車計画作成装置の概略構成の一例を説明するブロック図である。
図１において、配車計画作成装置は、配車シミュレータ１ａを備えたシミュレーション制御部１、及び最適化計算装置２等によって構成されている。
【００１６】
本実施形態では、配車シミュレータ１ａは、無人搬送台車（ＡＧＶ）の状態と、無人搬送台車（ＡＧＶ）を配車する際の制約とを表現した搬送プロセスを模擬したシミュレータ、いわばＡＧＶを用いて稼動する工場を模擬した大型のシミュレータである。より具体的に説明すると、例えば、配車シミュレータ１ａは、ペトリネットモデルを用いて構築され、事象（シミュレータ１ａのイベント）毎に物を動かす離散系として構成されている。
【００１７】
また、配車計画作成装置には、配車シミュレータ１ａを数学的に表現した数式モデル３が構成されている。本実施形態においては、搬送プロセスにおけるＡＧＶの状態と、ＡＧＶを配車する際の制約との中から、作成する配車計画に関連する要素を取り込んで、以下の式（イ）に示すような状態方程式を用いて、数式モデル３が作成されている。なお、数式モデル３は、半導体記憶装置等により構成される数式モデル保持手段（図示せず）によって保持されるようにしてもよい。
Ｍ（ｋ＋１）＝Ｍ（ｋ）＋Ｂ・ｕ（ｋ）  ・・・（イ）
すなわち、離散化したある時刻ｋにおいて各プレースに存在するトークンの数を示す状態ベクトル、言い換えれば状態量をＭ（ｋ）で表し、各トランジションの発火の有無を"１"及び"０"で表現した操作ベクトルをｕ（ｋ）で表すと、次の時刻ｋ＋１における状態ベクトルＭ（ｋ＋１）は、接続行列Ｂを用いて上記式（イ）で表すことができる。ここで、接続行列Ｂとは、ｕ（ｋ）のｊ番目に相当するトランジションが発火した際に、Ｍ（ｋ）のｉ番目に相当するプレースに存在するトークンの増減数を（ｉ，ｊ）要素とする整数行列である。
【００１８】
最適化計算装置２では、上記数式モデル３に対して最適化計算処理を行い、フィードバックゲインＫを算出するようにしている。最適化計算装置２によって行われる最適化計算は、線形二次（ＬＱ）制御を利用するものであり、以下の式（ロ）に示すような評価関数Ｓを用いて行われる。
Ｓ＝Σ[Ｍ´（ｋ）ＱＭ（ｋ）＋ｕ´（ｋ）Ｒｕ（ｋ）]  ・・・（ロ）
評価関数Ｓにおいて、Ｑ、Ｒは制御目的にあわせて設定された適当な行列であり、Ｍ´（ｋ），ｕ´（ｋ）は、それぞれ状態ベクトルＭ（ｋ）、操作ベクトルｕ（ｋ）の転置ベクトルである。Σはｋ＝０〜∞までの｛ ｝内の値の合計を表している。そして、この評価関数Ｓが最小となるように制御することを考えれば、
ｕ（ｋ）＝−Ｋ・Ｍ（ｋ）  ・・・（ハ）
とした状態フィードバック制御を行うフィードバックゲインＫを最適制御理論により求めることができる。
【００１９】
シミュレーション制御部１の最適制御方策部１ｂでは、最適化計算装置２で算出されるフィードバックゲインＫと、ＡＧＶの状態（状態ベクトルＭ）とを用いて、配車指示（操作ベクトルｕ）を算出して配車シミュレータ１に与えて、シミュレーションを進め、ＡＧＶの新たな状態を得て、この新たなＡＧＶの状態をもとに新たな配車指示を算出するという処理を繰り返す。そして、このようにして得られたシミュレーション結果４から、搬送プロセスにおける配車スケジュールを作成する。
【００２０】
（第１の実施形態）
図２は、本発明の第１の実施形態を示し、無人搬送台車（ＡＧＶ）の配車計画作成装置を実施したスケジューリングシステムの全体構成の一例を示すブロック図である。なお、以下の実施形態では、製鉄プロセスにおいて複数のＡＧＶスキッド間でコイルを搬送する場合を例にとって説明する。
【００２１】
図２に示すように、本実施形態のスケジューリングシステムは、上位プロコン１００と、ＡＧＶの配車計画作成装置としての機能を有するパソコン１０１とを具備して構成されている。上位プロコン１００は、所定の搬送命令、ＡＧＶ状態やコイル状態及びＡＧＶの現在位置などを表す情報を配車計画作成装置（パソコン）１０１に供給する。搬送命令としては、搬送すべきコイルを識別するためのコイル番号、コイルをどこからどこへ搬送するかを示すＦｒｏｍ／Ｔｏなどの情報が含まれる。
【００２２】
また、ＡＧＶの状態や現在位置は、実プロセスにおいてはＡＧＶの走行ルートに沿って設置されている複数の光空間伝送装置（ＯＣＤ）を介してＡＧＶと上位プロコン１００とが通信を行うことにより上位プロコン１００で把握されるが、配車計画をあらかじめ作成する際には、離散時間毎のシミュレーションの結果より把握される。すなわち、現在どのＡＧＶがどのような作業をしているのかとか、各ＡＧＶが現在存在する位置がどこであるかといったことが、上位プロコン１００で把握される。
【００２３】
本実施形態で扱うＡＧＶの状態とは、空車、要求走行、荷受け、搬送、荷卸し、充電走行、充電、退避走行のようなＡＧＶの作業状態を示すものである。「空車」とは、コイルを積んでおらず、かつ搬送命令も割り付けられていない状態のＡＧＶを言う。すなわち、何ら作業を行っておらず、しかも行うべき作業が決められてもいない状態を言う。例えばコイルの搬送完了によってＡＧＶが空車となったときは、基本的にはそのＡＧＶはその搬送完了位置に居続ける。
【００２４】
また「要求走行」とは、実際にコイルを搬送中ではないが、空車であったＡＧＶが搬送命令を受信し、コイルの荷受け位置（搬送命令中のＦｒｏｍ位置）に向かって走行している状態を言う。「荷受け」とは、要求走行状態のＡＧＶがその後荷受け位置に到着して、コイルをＡＧＶスキッドからＡＧＶに移載している状態を言う。「搬送」とは、荷受けが完了して実際にコイルを積んで荷卸し位置（搬送命令中のＴｏ位置）に向かって搬送している状態を言う。
【００２５】
また「荷卸し」とは、ＡＧＶが荷卸し位置に到着して、コイルをＡＧＶからＡＧＶスキッドへと降ろしている状態を言う。この荷卸しが完了すると、ＡＧＶは再び「空車」の状態に戻る。「充電走行」とは、ＡＧＶのバッテリ交換のために、充電場に向かって走っている状態を言い、「充電」とは実際に充電を行っている状態を言う。「退避走行」とは、ＡＧＶ間の干渉を避けるために、あらかじめ規則等によって決められた退避位置に向かって走行している状態を言う。この退避走行の指令は、空車のＡＧＶに対して行われる。
【００２６】
図２に示したように、上位プロコン１００は、以上のような状態遷移中にその時々の状態を表すデータを配車計画作成装置１０１に送信しており、これが状態管理手段２０５により管理される。状態管理手段２０５は、このような空車、要求走行、搬送のような作業状態だけでなく、各ＡＧＶの現在位置も記憶している。本実施形態の配車計画作成装置は、状態管理手段２０５にてどのＡＧＶが空車になったかの情報を得て、その空車ＡＧＶに対して搬送命令を割り付ける。
【００２７】
具体的に、配車計画作成装置１０１は、図２に示すように、入力手段３０１と、ゲイン行列算出手段３０２と、記憶手段２０１と、操作ベクトル算出手段２０２と、状態ベクトル入力手段２０４と、状態管理手段２０５と、搬送命令管理手段２０６と、処理計画出力手段２０７と、モデル構築手段２１２と、制御手段２１３とを具備しており、以下に述べるような本実施形態によるＡＧＶの配車計画作成方法を実施する。
【００２８】
入力手段３０１は、ＡＧＶによる搬送プロセスを構成する各ＡＧＶスキッドやＯＣＤ、各ＡＧＶスキッド間の走行路やその距離、ペトリネットモデルに関する所定の評価関数を表す評価行列Ｑ，Ｒ、更には各ＡＧＶの目標状態（初期状態に対して達成したい状態）を表す目標状態量Ｍrの各情報をＡＧＶごとに入力するためのものであり、例えばキーボード等により構成される。なお、上記評価行列Ｑ，Ｒは、
Ｑ＝ＱT≧０、Ｒ＝ＲT＞０
を満たすものとする（行列Ｑ，Ｒの肩のＴは転置行列であることを示す）。
【００２９】
モデル構築手段２１２は、入力手段３０１により入力された情報に従って、ＡＧＶの走行路をプレースとトランジションとで表すとともに、ＡＧＶとコイルとをトークンで表したペトリネットモデルをＡＧＶごとに構築する。このとき、そのペトリネットモデルの状態方程式を記述する接続行列Ｂを求める。この接続行列Ｂにより、トークン（ＡＧＶ及びコイル）の移動操作端であるトランジションの発火によるトークンの移動が数式で表される。
【００３０】
ここで、離散化したある時間ｋにおいて各プレースに存在するトークンの数を示す状態ベクトルすなわち状態量をＭ（ｋ）で表し、各トランジション発火の有無を"１"及び"０"で表現した操作ベクトルをｕ（ｋ）で表すとすると、次の時間ｋ＋１における状態ベクトルＭ（ｋ＋１）は、以下の式（１）に示す状態方程式で表すことができる。
Ｍ（ｋ＋１）＝Ｍ（ｋ）＋Ｂ・ｕ（ｋ）  ・・・（１）
【００３１】
図３に、ペトリネットモデルの一例を示す。図３（ａ）は現実の搬送プロセスの簡単な例を示し、図３（ｂ）はこの搬送プロセスに従って作成したペトリネットモデルの例を示している。すなわち、走行路中の各ＡＧＶスキッドやＯＣＤのある位置をゾーンとし、各ゾーン内のＡＧＶスキッドやＯＣＤをプレースで表すとともに、各ゾーンを矢印で接続して走行路を表す。各ゾーン内はモジュール単位のペトリネットモデルになっており（詳しくは後述する）、矢印はペトリネットモデルのアークを示している。なお、ＯＣＤは、各ＡＧＶスキッドの繋がりを表すノードである。
【００３２】
ゲイン行列算出手段３０２は、入力手段３０１により入力された評価行列Ｑ，Ｒ及び目標状態量Ｍrと、モデル構築手段２１２により求められた接続行列Ｂとを用いて、所定の評価関数の値を最小にするようなペトリネットモデルのフィードバックゲイン行列Ｋを求める。このフィードバックゲイン行列Ｋの計算について、以下に詳しく述べる。
【００３３】
上述したように、ペトリネットモデルの状態方程式は上記式（１）で表される。さらに、本実施形態で導入している目標状態量Ｍrを考慮すると、上記式（１）は、以下の式（２）のように書ける。
Ｍ（ｋ＋１）−Ｍr＝（Ｍ（ｋ）−Ｍr）＋Ｂ・ｕ（ｋ）  ・・・（２）
ここで、Ｍ（ｋ）−Ｍrを新たな状態ｘ（ｋ）と見ることができ、式（２）は、次の式（３）のように書ける。
ｘ（ｋ＋１）＝ｘ（ｋ）＋Ｂ・ｕ（ｋ）  ・・・（３）
【００３４】
なお、上記式（１）の状態方程式は、各プレースの状態の目標量が０の場合に相当するものである。これに対して、上記式（２）あるいは上記式（３）の状態方程式のように、目標状態量Ｍrを導入することで、各プレースの状態の目標量を自由に設定することができる。詳しくは後述するが、本実施形態では、入力手段３０１によって入力する初期状態に対する目標状態量Ｍr以外は、シミュレーションの過程で刻々と遷移するＡＧＶの状態（上述した空車、要求走行、搬送、…などの状態）に応じて目標状態量Ｍrの設定内容を変化させる。
【００３５】
本実施形態においては、上記式（２）あるいは上記式（３）上の移動操作端（トランジション）と、実プロセスの移動操作端とは一致している。すなわち、操作ベクトルｕ（ｋ）の信号は、実プロセスの操作信号である。これにより、各プレースに存在するトークンの数から目標状態量を引いた値を並べた状態ベクトルをｘで表し、各トランジションの発火の有無を"１"及び"０"で表した操作ベクトルをｕとすれば、接続行列Ｂを用いて上記式（３）のように、ベクトルｘ（ｋ）からベクトルｘ（ｋ＋１）への状態変化を表現することができる。
【００３６】
このように、ペトリネットモデルを用いて接続行列ＢでＡＧＶの走行路を表すことにより、離散時間ｋが１進むたびに複数の離散きざみ時間を要するプレースをトークンが移動していくことを表現でき、その結果、離散時間系の最適制御理論を適用できる形にすることができる。
【００３７】
このように本実施形態では、ペトリネットモデルを離散時間系の最適制御理論を適用できる形にすることができるので、制御の目的にあわせて適当な評価行列Ｑ，Ｒを設定して、下記の式（５）に示す評価関数Ｊが最小になるように操作ベクトルｕ（ｋ）を制御することを考えれば、
ｕ(k) ＝−Ｋ（Ｍ（ｋ）−Ｍr）＝−Ｋ・ｘ（ｋ）  ・・・（４）
とした状態フィードバック制御を行うフィードバックゲイン行列Ｋを最適制御理論より求めることができる。
【００３８】
【数１】
2006107121.tif 000003
【００３９】
上述の評価行列Ｑ，Ｒは、それぞれプレース数の次元及びトランジション数の次元を有する正方行列で、それぞれ制御の過渡特性とトランジション操作の入力エネルギーとを評価関数として表すためのものであり、制御目的に応じて適宜設定すればよい。例えば、過渡特性を重視する場合は、大きな数値をもつ評価行列Ｑを設定すればよい。また、操作に要する入力エネルギーを小さく抑えたい場合は、大きな数値をもつ評価行列Ｒを設定すればよい。
【００４０】
このようにして接続行列Ｂと所定の評価関数Ｊを定義する評価行列Ｑ，Ｒとが定まれば、離散時間系における最適制御理論によりフィードバックゲイン行列Ｋを求めることができる。なお、フィードバックゲイン行列Ｋの計算法としては、例えば（安藤和昭、他編著「数値解析手法による制御系設計」計測自動制御学会発行、pp.126-130、平成５年初版第２刷）に記載された幾つかの方法がある。
【００４１】
このようにしてゲイン行列算出手段３０２により求められたフィードバックゲイン行列Ｋは、モデル構築手段２１２により求められた接続行列Ｂと共に、操作ベクトル算出手段２０２及び制御手段２１３において実際に制御を行う際に使用するため、記憶手段２０１に記憶されて保存される。
【００４２】
次いで、状態管理手段２０５は、ペトリネットモデルのトークンとして表されるＡＧＶやコイルの状態を上位プロコン１００から受け取り、記憶する。ＡＧＶの状態とは、上述した空車(Empty)、要求走行(Request)、荷受け(Load)、搬送(Carry)、荷卸し(Unload)、充電走行(Battery)、充電(Charge)、退避走行(Escape)の各状態を言う。また、コイルの状態とは、未割り付け(Unassigned)、割り付け済(Assigned)、荷受け(Load)、搬送(Carry)、荷卸し(Unload)、搬送完了(Complete)の各状態を言う。本実施形態では、これらの状態に応じてＡＧＶ及びコイルのトークンに属性（カラー）を持たせる。
【００４３】
搬送命令管理手段２０６は、上位プロコン１００から与えられる１つ以上の搬送命令を管理し、この搬送命令と、状態管理手段２０５によって管理されているＡＧＶ状態とに基づいて、ＡＧＶ及びコイルの各トークンを生成し、それらに属性を設定する。また、与えられたＡＧＶ状態に応じて目標状態量Ｍrを設定する。目標状態量Ｍrの設定の仕方は、例えば所定のルールによってあらかじめ決められている。
【００４４】
一例を挙げると、ＡＧＶ状態が要求走行のとき（属性がRequestのとき）は、その要求走行の目的地、すなわちその搬送命令中のＦｒｏｍ位置（荷受け位置）に目標値を設定する。また、ＡＧＶ状態が搬送のとき（属性がCarryのときは、その搬送の目的地、すなわちその搬送命令中のＴｏ位置（荷卸し位置）に目標値を設定する。
【００４５】
操作ベクトル算出手段２０２は、ゲイン行列算出手段３０２により求められて記憶手段２０１に記憶されたフィードバックゲイン行列Ｋと、状態ベクトル入力手段２０４により入力される仮想的な搬送プロセスの現時点における各ゾーンでのトークンの仕掛状態を表す状態ベクトルＭ（ｋ）と、搬送命令管理手段２０６よりＡＧＶごとに供給される初期状態以降の目標状態量Ｍrとから、トークンの移動操作端（トランジション）に対する発火の有無を表す操作ベクトルｕ（ｋ）を求める。
【００４６】
制御手段２１３は、操作ベクトル算出手段２０２により求められた操作ベクトルｕ（ｋ）に基づいて、操作量（操作ベクトルｕ（ｋ）の要素）の正値で大きい順に発火可能性を調べ、仮想的な搬送プロセス内の各移動操作端に対して発火可能な操作端を全て発火させて、移動可能な数だけ移動操作を順次行うという方法を用いて、全ての搬送命令が何らかのＡＧＶに割り付くまで搬送プロセスのシミュレーションを実行して、配車問題の解Sol(0)を求める。
【００４７】
すなわち、上記計算された操作ベクトルｕ（ｋ）に基づいて、各トランジションに対して、正値で大きい操作量の順に発火可能性を調べ、移動可能な数のトークンに対して操作量を改めて"１"とおき、その他のトークンに対しては操作量を"０"とおいて最終的な操作ベクトルｕ（ｋ）を求める。これにより、操作量が"１"であるトランジションを発火させれば、式（１）に示した値｛Ｍ（ｋ）＋Ｂ・ｕ（ｋ）｝として状態ベクトルＭ（ｋ＋１）を得ることが可能となる。
【００４８】
このとき、ある１つの時刻単位のシミュレーションを行ったら、そのとき記憶手段２０１より入力される接続行列Ｂと、搬送命令管理手段２０６より入力される目標状態量Ｍr等と、状態ベクトル入力手段２０４より入力される現時点での状態ベクトルＭ（ｋ）とを用いて、上記状態方程式から移動操作後の状態ベクトルＭ（ｋ＋１）を求め、それを次の時刻単位におけるシミュレーションに利用するために状態ベクトル入力手段２０４にフィードバックする。そして、１つの移動操作を仮想的に行ったら直ぐに次の移動操作を行うというようにしてシミュレーションを順次行う。
【００４９】
処理計画出力手段２０７は、以上のようにして制御手段２１３により行われたシミュレーションの結果を上位プロコン１００にフィードバックする。その際処理計画出力手段２０７は、どのトークンがいつどこからどこへ移動したかという記録ファイルを解析し、どのＡＧＶにどのように搬送命令が割り付けられ、どのルートを通って搬送したかというデータを上位プロコン１００のフォーマットに従って生成し、出力する。上位プロコン１００では、図示しないディスプレイやプリンタなどの出力装置にそのシミュレーション結果を出力する。
【００５０】
ところで、上記した図３（ｂ）のペトリネットモデルは、ＡＧＶが１台の場合について示したものである。ＡＧＶが複数台ある場合は、この図３（ｂ）に示すようなモデルを１つのモジュールとして、ＡＧＶの台数分だけ同様のモジュールを作成する。このとき、搬送中及び搬送命令割り付け確定済のＡＧＶは、走行先の目的地が１台ごとに決まっている。一方、空車（退避走行中のものを含む）のＡＧＶの目的地は、新たな搬送命令がどのように割り付くかにより異なる。
【００５１】
そこで、搬送中及び搬送命令割り付け確定済のＡＧＶについては、図４の上段（ＡＧＶ１、ＡＧＶ２、ＡＧＶ３、…）のように１台ごとに区別し、空車及び退避走行中のＡＧＶについては図４の下段（ＡＧＶ０）のように区別しないこととする。つまり、図４の上段の各モジュール内にＡＧＶはそれぞれ１台ずつしか入らないが、下段のモジュールには空車のＡＧＶが複数台入り得る。新たな搬送命令の割り付けは、この空車及び退避走行中のＡＧＶに対して行われる。
【００５２】
各モジュールにおいて、対応するゾーン（ＡＧＶスキッドやＯＣＤのある位置）は、物理的には同一の場所を表し、一般に容量が制限されている。例えば、ＡＧＶ１のスキッドＡとＡＧＶ２のスキッドＡは、物理的には同一の場所を表し、ＡＧＶ１がスキッドＡにあるとき、スキッドＡの容量が１ならば、他のＡＧＶはスキッドＡには進入できない。
【００５３】
このような制約をソフトウェア上で実現するためには、ＡＧＶの状態、コイルの状態に加え、容量に関する状態として、各ゾーンのトークンの個数を状態管理手段２０５により管理させれば良い。すなわち、１つの時刻単位のシミュレーションを進めるたびに、各ゾーンの容量（入ることが許されるトークン数の上限値）と、現在の各ゾーンのトークン数とを比較し、各ゾーンの容量を越えるような発火を禁止する。
【００５４】
なお、図４では各ＡＧＶのモジュールを明確に分けた図を示しているが、各モジュールを分けることは本質的ではなく、数式モデル上（ソフトウェア上）で各ＡＧＶを区別することができれば良い。
【００５５】
このようにペトリネットモデルをＡＧＶごとに分けて考えることにより、搬送命令管理手段２０６によってＡＧＶ状態に応じて設定される目標状態量ＭrもＡＧＶごとに設定される。そのため、上記式（５）に示した評価関数ＪもＡＧＶごとに異なることとなる。例えば、４台あるＡＧＶのうち、ＡＧＶ１は搬送中、ＡＧＶ２は要求走行中、ＡＧＶ３とＡＧＶ４が空車であるとすると、それぞれの評価関数Ｊ1、Ｊ2、Ｊ3,4（空車や退避走行の場合はひとまとめにして考える）は、以下の式（６）のようになる。
【００５６】
【数２】
2006107121.tif 000004
【００５７】
この式（６）において、Ｍr1はＡＧＶ１についての目標状態量であり、この場合はコイルの搬送先、すなわち割り付け済搬送命令中のＴｏ位置を目標値として設定したものである。また、Ｍr2はＡＧＶ２についての目標状態量であり、この場合はコイルの搬送元、すなわち割り付け済搬送命令中のＦｒｏｍ位置を目標値として設定したものである。また、Ｍr3,4はＡＧＶ３、ＡＧＶ４についての目標状態量であり、この場合は未割り付けの搬送命令の搬送元（Ｆｒｏｍ位置）を目標値として設定したものである。
【００５８】
目標値の設定の仕方は、例えば、目標状態量Ｍrの行列中で目的地に該当する要素の値を"１"とし、他の要素の値を"０"とする。また、目標値は"１"以外の値、例えばそれ以上の整数値あるいは小数値に設定するようにしても良く、他の要素の値も必ずしも"０"でなくても良い。要は、目的地の要素の値が他の要素の値よりも大きくなるように設定すれば良い。
【００５９】
これらＡＧＶごとの評価関数Ｊ1、Ｊ2、Ｊ3,4を最小化する操作ベクトルｕ（ｋ）は、ＡＧＶごとに上記式（４）により求められる。つまり、この場合は３つの操作ベクトルｕ（ｋ） 1、ｕ（ｋ）2、ｕ（ｋ）3,4が求められる。操作ベクトル算出手段２０２は、各操作ベクトルｕ（ｋ） 1、ｕ（ｋ）2、ｕ（ｋ）3,4を統合したベクトルｕ（ｋ）（＝〔ｕ（ｋ） 1  ｕ（ｋ）2  ｕ（ｋ）3,4〕）を更に生成する。
【００６０】
制御手段２１３は、操作ベクトル算出手段２０２により求められた上記統合した操作ベクトルｕ（ｋ）に基づいて、操作量の正値で大きい順に発火可能性を調べ、仮想的な製造プロセス内の各移動操作端に対して発火可能な操作端を全て発火させて、移動可能な数だけ移動操作を順次行うという方法を用いて、所定期間の搬送プロセスのシミュレーションを実行する。
【００６１】
なお、上述したモデル構築手段２１２、ゲイン行列算出手段３０２、記憶手段２０１、操作ベクトル算出手段２０２、状態ベクトル入力手段２０４、状態管理手段２０５、搬送命令管理手段２０６、処理計画出力手段２０７、及び制御手段２１３は、例えば、ＣＰＵ（中央処理装置）、ＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（リードオンリメモリ）などからなるマイクロコンピュータによって構成されており、ＣＰＵの作業プログラムは、ＲＯＭあるいはＲＡＭに記憶されている。
【００６２】
また、ゲイン行列算出手段３０２が、図１に示した最適化計算装置２に相当し、モデル構築手段２１２から出力される接続行列Ｂを上記式（１）に代入することにより得られる数式モデル（例えば式（２））が、図１に示した数式モデル３に相当する。また、入力手段３０１のユーザによる操作に基づき入力される評価行列Ｑ、Ｒ及び目標状態量Ｍrに基づいて得られる評価関数（式（５）の評価関数Ｊ）が、図１に示した評価関数Ｓに相当する。
【００６３】
さらに、シミュレーション制御部２００が、図１に示したシミュレーション制御部１に相当する。特に、制御手段２１３及び状態ベクトル入力手段２０４が、図１に示した配車シミュレータ１ａに相当し、操作ベクトル算出手段２０２が、図１に示した最適制御方策部１ｂに相当する。
【００６４】
以上に、ＡＧＶ割り付け問題をペトリネットでモデリングする手法、ペトリネットモデルを数式変換する手法、ＡＧＶ状態に応じて目標状態量Ｍrを設定した評価関数により搬送目的を達成できる手法、評価関数を最小化する手法について原理的なことを述べた。
次に、このような原理に基づいて実際に実施するための具体的なペトリネットモデル設定について説明する。
【００６５】
図５及び図６は、図３（ｂ）に示した各ゾーン内のペトリネットモデルを詳細に示した図であり、図５は各ＡＧＶスキッド用ゾーンのペトリネットモデルを示し、図６はＯＣＤ用ゾーンのペトリネットモデルを示している。なお、図５及び図６において、白丸印はプレース、棒印はトランジション、白丸内の黒丸印はトークンを表しており、トークンはトランジションの発火によってプレース間を移動する。
【００６６】
各モジュール中"ＡＧＶ"と書かれたプレースはＡＧＶ用のプレースであり、ＡＧＶスキッド用及びＯＣＤ用のモジュール内にそれぞれ１個ずつ備えられている。また、"Ｆｒｏｍ"及び"Ｔｏ"と書かれたプレースはコイル用のプレースであり、ＡＧＶスキッド用のモジュール内にそれぞれ１個ずつ備えられている。これらのプレースは容量が１個に制限されている。さらに、"Common"、"Complete"、"Request"と書かれたプレースは各モジュールに共通のプレースであり、全体でそれぞれ１つのみ備えられる。この共通プレースには複数のトークンを設定することが可能である。
【００６７】
また、"Load"、"Unload"、"Allocate"、"Reallocate"、"Move"と書かれたものはそれぞれトランジションである。ここで、トランジション"Load"は、プレース"ＡＧＶ"とプレース"Ｆｒｏｍ"にトークンがあるとき発火可能である。また、トランジション"Unload"は、プレース"ＡＧＶ"にトークンがあるとき発火可能である。また、トランジション"Move"は、プレース"ＡＧＶ"にトークンがあるとき発火可能であり、ＡＧＶの移動を制御する。トランジション"Allocate"及び"Reallocate"は、任意に発火可能である。
【００６８】
図７は、図３（ｂ）に示したペトリネットモデルを図５及び図６の具体例に従って書き直したものである。この図７に示したように、プレース"ＡＧＶ"と"Ｆｒｏｍ"と"Ｔｏ"とに通し番号（カッコ内の数字）を付け、トランジション"Load"と"Unload"と"Move"とに通し番号（丸内の数字）を付けることにより、それぞれを区別している。ＡＧＶ及びコイルの各トークンは、状態以外に現在位置、割り付け済みのコイル及びＡＧＶの組があるときはそれらのそれぞれに対応する番号などの属性を持っている。
【００６９】
また、図５〜図７に示したように、本実施形態においてトランジション"Move"は、モジュールの外部に出ていく方向に対してのみ設け、入ってくる方向には設けていない。ＡＧＶスキッド及びＯＣＤの全てのモジュールについてこのように構成することにより、必要に応じて入出力の足の本数を変えて各モジュールを接続するだけで、全体のペトリネットモデルを簡単に作成することができる。したがって、設計変更も容易である。
【００７０】
図８は、上記のように構成した本実施形態による配車計画作成装置１０１のシミュレーション時の動作の一例を示すフローチャートである。以下、この図８のフローチャートに従って動作を説明する。
図８において、最初にステップＳ１では、上位プロコン１００から搬送命令及びＡＧＶ状態の情報を受信する。次に、ステップＳ２で、上記受信した情報をもとに前処理を行う。この前処理では、ＡＧＶ及びコイルの各トークンを生成してそれぞれに属性を設定し、ＡＧＶのトークンはプレース"Common"にセットし、コイルのトークンはプレース"Request"にセットする。
【００７１】
次に、ステップＳ３では、上述した最適制御理論に基づく各トランジションの発火制御を利用してＡＧＶ割り付け処理を行う。例えば、図９に示すようなＡＧＶ及びコイルのトークンがあるとする。本実施形態ではこれだけの情報を状態管理手段２０５や搬送命令管理手段２０６にて管理している。これらの情報に基づいて、コイルのプレース"Request"に置かれた各トークンは、その属性が示す搬送元のプレースに繋がっているトランジションが発火することにより、搬送元にコイルのトークンがセットされる。また、ＡＧＶのプレース"Common"に置かれた各トークンは、各ＡＧＶに繋がっているトランジションが発火することにより、各ＡＧＶの現在位置に各ＡＧＶのトークンが振り分けられる。この際、各ＡＧＶ状態に応じて搬送元または搬送先のプレースに目標値が付けられる。
【００７２】
また、本実施形態では、ＡＧＶ状態のうち、"Empty "と"Escape"を除く各状態は、走行の目的地が確定しているので、ＡＧＶのカラー（属性）として本来のＡＧＶ番号を与える（この例ではＡＧＶ１はカラー１、ＡＧＶ２はカラー２）。また、"Empty"と"Escape"の状態は、搬送命令の割り付けが可能であることを示すカラー（例えば、カラー０）を与える。コイルの状態も同様の考え方に従い、割り付け確定済み（"Unassigned"以外）の場合は割り付いているＡＧＶ番号のカラーを、未割り付けの場合は、未割り付けの番号（例えば、カラー０）を与える。
【００７３】
このようにしてカラー番号を与え、同じ番号同士のトークンが揃ったときに限りトランジション"Load"を発火できるようにすると、割り付いたコイル及びＡＧＶ同士、未割り付き同士の正しい割り付けを実現することができる。
【００７４】
以上の方法で各プレースにセットされたトークンと目標値とに基づいて状態ベクトルＭ（ｋ）と目標状態量Ｍrとが計算できるので、上記式（４）により操作ベクトルｕ（ｋ）が計算できる。この操作ベクトルｕ（ｋ）によってトランジション発火の優先順位が与えられ、この操作ベクトルｕ（ｋ）に基づき上述した方法に従って発火するトランジションを決定する。そして、実際にトランジションを発火すると、次のステップの状態Ｍ（ｋ＋１）が求まり、以下逐次発火するトランジションが決まる。
【００７５】
図１０は、各トランジション発火とそれによる状態（属性）遷移の様子を示したものであり、図１０（ａ）はトランジションの発火を示し、図１０（ｂ）は状態遷移を示している。図１０において、要求走行中（Request）のＡＧＶは、搬送元（Ｆｒｏｍ位置）に到着すると、トランジション"Load"が発火し、ＡＧＶ状態が"Load"に変化する。
【００７６】
また、空車（Empty）または退避走行中（Escape）のＡＧＶは、未割り付けを表すカラーが与えられるが、未割り付けのコイルのトークンをセットする際に搬送元に目標値を付けることにより、空車または退避走行中のＡＧＶを搬送命令（コイル）に割り付けることができる。すなわち、未割り付け同士のＡＧＶ及びコイルは、トランジション"Load"が発火することによってＡＧＶ状態が"Load"に変化し、以下"Request"と同様の動作をする。
【００７７】
次に、トランジション"Reallocate"が発火し、ＡＧＶ状態が"Carry "へと変化する。このとき、この"Carry "の属性を持ったＡＧＶのトークンがプレース"Common"に移動し、搬送中のＡＧＶ及びコイルがセットされたときと同様の働きにより、トランジション"Allocate"の発火により目標値が搬送先にセットされ、搬送が開始される。搬送は、トランジション"Move"の発火によって行われるが、この発火によってＡＧＶ状態は変化しない。
【００７８】
搬送中のＡＧＶが搬送先（Ｔｏ位置）に到着すると、トランジション"Unload"が発火し、ＡＧＶ状態が"Unload"に変化する。これと同時に、"Unload"の属性を持つコイルのトークンも生成される。次に、トランジション"Reallocate"が発火し、次に搬送するコイルがあるときは"Request"に、ないときは"Empty"にＡＧＶ状態がセットされる。
【００７９】
このようなＡＧＶの走行によって搬送先にコイルのトークンが移動すると、そのコイルのトークンはプレース"Complete"に移動する。そして、全てのコイルが搬送されたら、図８のステップＳ３におけるＡＧＶ割り付け処理を終了する。上述したように、このプレース"Complete"は全てのモジュールに共通に１個のみ設けられており、複数のトークンを設定可能なように構成している。したがって、このプレース"Complete"の中を見ると、どのコイルのトークンがどの順番で搬送されてきたのかが分かる。
【００８０】
そして、ステップＳ４で後処理を行う。この後処理では、最終結果として記憶されたトークンの移動を表すファイルから上位プロコン１００に返すべきデータ（未割り付けコイルの割り付きＡＧＶ番号、ＡＧＶ走行経路などのデータ）を抽出する。この際、未割付けコイルに搬送余裕があり、特に緊急に運ばなくても良い場合には、ＡＧＶ同士の干渉を押さえるため、ペトリネットでシミュレーションした際のコイルの搬送時間が、ＡＧＶの干渉が無い場合の搬送時間と比べ、大きく異なっているときには、その未割付けコイルは上位プロコン１００へは返さないようにしても良い。
最後に、ステップＳ５で、抽出したデータを上位プロコン１００のフォーマットに変換して送信する。
【００８１】
以上詳しく説明したように、本実施形態によれば、ＡＧＶの走行路をプレースとトランジションとで表すとともに、コイル及びＡＧＶをトークンで表したペトリネットモデルを構築する。そして、ＡＧＶ状態と搬送命令とに応じて目標状態量Ｍrを可変に設定するようにし、この目標状態量Ｍrを考慮した状態方程式から上記コイル及びＡＧＶのトランジションに対する操作ベクトルｕ（ｋ）を求め、この操作ベクトルｕ（ｋ）に基づいて各コイル及びＡＧＶの移動操作を行うようにしたので、搬送命令のＡＧＶに対する割り付け問題を、ペトリネットモデルを用いた離散時間系の最適制御理論を適用できる形にすることができる。
特に、搬送プロセスの規模が差ほど大きくない場合には、評価行列Ｑ，Ｒの要素数も少ないので、フィードバックゲインＫの再計算も時間が掛からないため、オンラインで評価行列Ｑ，Ｒの調整が可能であり、ＡＧＶの走行時間を短くしたり、搬送物が運び出されるまでの搬送待ち時間を短くしたりすることができる。したがって、搬送プロセスの規模が差ほど大きくない場合には、全体の構成を簡単にしながら、調整員が望む性能を達成することができる。
【００８２】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。なお、以下の説明において、上述した第１の実施形態と同一の部分については、詳細な説明を省略する。
上述したように、第１の実施形態の配車計画作成装置では、配車性能を調整するためには、評価関数Ｑ、Ｒの要素を変更し、フィードバックゲインを再計算する必要が有る。そして、搬送プロセスの規模が大きくなると、フィードバックゲインの計算に時間を要する。このため、このフィードバックゲインの計算をオフラインで行う必要が有る。このように、規模が大きくなると配車性能をオフラインで調整員が簡単に調整することは困難である。また、評価行列Ｑ、Ｒが配車性能に与える影響も調整員に理解しがたいものになってしまう。
【００８３】
そこで、本実施形態では、第１の実施形態におけるこのような問題を解決し、ＡＧＶへの搬送命令の割り付けを効率よく行うことにより、ＡＧＶの走行時間を短くしたり、搬送物が運び出されるまでの搬送待ち時間を短くしたり、両者のトレードオフを最適に調整することができるようにしている。
【００８４】
図１１は、本発明の第２の実施形態を示し、無人搬送台車（ＡＧＶ）の配車計画作成装置を実施したスケジューリングシステムの全体構成の一例を示すブロック図である。
図１１に示すように、本実施形態のスケジューリングシステムは、図２に示した第１の実施形態のスケジューリングシステム（配車計画作成装置１０１）に、シミュレーション手段２０３と、コスト関数設定手段２０８と、配車組合わせ計算手段２０９と、目標値変更手段２１０と、コスト関数比較手段２１１とを加えた構成である。
【００８５】
コスト関数設定手段２０８は、各ＡＧＶの現在位置及び現在状態と、各ＡＧＶに割り付いたコイルの搬送元及び搬送先とから定義されるコスト関数を設定する。例えば、コスト関数は、以下の式（７）のように、各ＡＧＶの空車走行時間の合計と、各コイルの搬送待ち時間の合計とをＫａ、Ｋｂという係数で線型結合した式とする。
【００８６】
【数３】
2006107121.tif 000005
【００８７】
上記式（７）の係数Ｋａ、ＫｂはＡＧＶの配車性能を左右する調整係数である。本実施形態の配車計画作成装置では、上記式（７）のコストＣの値が小さくなるＡＧＶとコイルとの割付け結果が求められる。この際、調整計数Ｋａを大きくすれば、ＡＧＶの空車走行時間が小さくなるとともに、コイルを搬送するためのＡＧＶのエネルギーコストが小さくなるため、単位時間当りの搬送個数は多くなるという長所が有る。ただし、空車走行が長く掛かるような遠くのコイルは搬送されにくくなり、搬送遅れを生じるという欠点も有る。一方、調整計数Ｋｂを大きくすると、コイルの搬送待ち時間が小さくなるため、搬送遅れが生じにくくなるという長所もあるが、ＡＧＶのエネルギーコストは相対的に大きくなってしまい、長時間でみると、単位時間当りの搬送個数が少なくなってしまうという欠点もある。
【００８８】
配車組合わせ計算手段２０９は、状態管理手段２０５より各ＡＧＶの現在位置とＡＧＶ状態（空車、要求走行、荷受け、搬送、荷卸し、充電走行、充電、退避走行）とを入力するとともに、搬送命令管理手段２０６より各コイルの搬送元と搬送先とを入力し、コスト関数設定手段２０８によって設定された、式（７）のコスト関数の値が小さくなる配車問題の解（どのＡＧＶでどのコイルをどの順番で搬送するか）を複数計算する。ここで、上記式（７）のコスト関数の計算の際には、計算時間を短くするため、ＡＧＶ同士の干渉を含まない標準走行時間に基づき計算を行う。また、分枝限定法のような厳密手法を用いると組み合わせの数が多いため、実用的な時間で解くことが出来ない。そこで、タブサーチやＧＡ、シミュレーティッドアニーリング等の組み合わせ最適化手法を用い、繰り返し回数や計算時間に上限を設け、その時間内に求められた上位Ｌ個の解（Sol(1)〜 Sol(L)）を求める。タブサーチを用いて配車問題の解を求める方法を後述する。
【００８９】
最適制御による配車計算の際にも、上記式（７）のコスト関数の値が小さくなる解が求まりやすくするため、目標値変更手段２１０でコスト関数設定手段２０８により設定された調整係数Ｋａ、Ｋｂを用いて、目標値Ｍrを変更する。具体的には、目標値を大きくすることと、ＡＧＶの空車走行時間の合計とコイルの搬送待ち時間の合計との割合（Ｋｂ／Ｋａ）に相関があるため、目標値を以下の式（８）のように変更する。
Ｍr←Ｍr（０．１＋Ｋｂ／Ｋａ）  ・・・（８）
【００９０】
シミュレーション手段２０３は、上記式（７）のコスト関数の値を再計算する。この際、ＡＧＶ同士の干渉を含んでシミュレーションするため、上記式（７）のコスト関数の値は、ＡＧＶ同士の干渉を含んだ実走行に近い厳密な値が算出される。ここで、最適制御による配車計算シミュレーションで求められた（制御手段２１３で求められた）配車問題の解Sol(0)をシミュレーションした際に求められるコスト関数の値をCost(0)とし、タブサーチで求めた配車問題の解Sol(1)〜Sol(L)をそれぞれシミュレーションした際に求められるコスト関数の値をCost(1)〜Cost(L)とする。
【００９１】
コスト関数値比較手段２０８は、上記コスト関数の値Cost(0)〜Cost(L)を単純に比較し、最も小さい値を求め、それに対応した、シミュレーションが出力する記録ファイル（どのトークンがいつどこからどこへ移動したかを記録したファイル）のみを残し、最終的な配車問題の結果とする。
【００９２】
なお、上述したシミュレーション手段２０３、コスト関数設定手段２０８、配車組合わせ計算手段２０９、目標値変更手段２１０、及びコスト関数比較手段２１１は、例えば、ＣＰＵ（中央処理装置）、ＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（リードオンリメモリ）などからなるマイクロコンピュータによって構成されており、ＣＰＵの作業プログラムは、ＲＯＭあるいはＲＡＭに記憶されている。
【００９３】
図１２は、上記のように構成した本実施形態による配車計画作成装置１０１のシミュレーション時の動作の一例を示すフローチャートである。以下、この図１２のフローチャートに従って動作を説明する。
図１２において、ステップＳ１１では、図８のステップＳ１と同様に、上位プロコン１００から搬送命令及びＡＧＶ状態の情報を受信する。次に、ステップＳ１２で、図８のステップＳ２と同様に、上記受信した情報をもとに前処理を行う。
【００９４】
次に、ステップＳ１３では、図８のステップＳ３と同様に、上述した最適制御理論に基づく各トランジションの発火制御を利用してＡＧＶ割り付け処理を行う。ただし、本実施形態では、このＡＧＶ割付け処理と平行して、ステップＳ１４でＡＧＶ組合わせ割付け処理を行う。このＡＧＶ組合わせ割付け処理では、前処理で得られたＡＧＶのトークンとコイルのトークンとから、上記式（７）のコスト関数の値が小さくなる組み合わせを複数算出する。この方法には、タブサーチやＧＡ，シミュレーティッドアニーリングなどの各種手法があるが、ここでは、タブサーチを例として説明する。タブサーチによる配車問題の解法の一例を図１３に示す。
【００９５】
ここでは、コイルとＡＧＶのトークンが図９に示したようになる場合を例に挙げて説明する。ただし、走行路のレイアウトを図１４のようにし、ＡＧＶ１２０１〜１２０４の各格子間における走行時間を空車走行時は６０秒、積載走行時は９０秒掛かると仮定する。また、コイル１２１１〜１２１４の荷受け時間・荷卸し時間を共に１０秒とする。例えば、図１４において、現在、位置Ａ１に空車で存在するＡＧＶが、位置Ｃ１から位置Ｄ１までコイルを搬送して位置Ｄ１で空車になるまでの時間は、８００秒（＝６０×４＋１０＋９０×６＋１０）となる。また、上記式（７）のコスト関数の調整係数Ｋａ、Ｋｂをそれぞれ１０．０、１．０とする。
【００９６】
図１３において、ステップＳ２１では、欲張り法により初期解を求める。欲張り法には様々な方法があるが、ここでは、各未割付けコイルを順番に調べ、最も早く搬送が開始できるＡＧＶにコイルを割付けることとする。つまり、未割付けコイル１００番は３号車に、未割付けコイル１０３番は４号車に割付ける（図９を参照）。このＡＧＶとコイルの組み合わせを表１のように記述することにする。この表１で、括弧が付いているコイル番号は既に実施中を表し、確定済みであるため動かすことが出来ないことを意味している。
【００９７】
【表１】
2006107121.tif 000006
【００９８】
次に、ステップＳ２２では、未割付けコイルの任意の２つを選び交換する。図９に示す例では、コイル番号１００、１０３の組み合わせしか存在しないので、コイル番号１００、１０３を入れ替えると、ＡＧＶとコイルの組み合わせは、表２のようになる。
【００９９】
【表２】
2006107121.tif 000007
【０１００】
そして、未割付けコイルを入れ替えた後の組み合わせのうち、コスト関数の値が最も小さくなる組み合わせＡを求める。この例の場合では、交換する組み合わせは１つしか存在しないので、コスト関数の値が最も小さくなる組み合わせＡは表２のケースとなる。
【０１０１】
次に、ステップＳ２３では、未割付コイルの任意の２つの組み合わせを選択し、片方をもう片方の前に挿入する。この例の場合では、表３と表４の２通りが存在する。
【０１０２】
【表３】
2006107121.tif 000008
【０１０３】
【表４】
2006107121.tif 000009
【０１０４】
そして、これらの組み合わせのうち、コスト関数の値が最も小さくなる組み合わせＢを求める。この例の場合では、コスト関数の値が最も小さくなる組み合わせＢは表３のケースとなる。
【０１０５】
次に、ステップＳ２４では、任意の１つのコイルを選び、任意のＡＧＶの最後に搬送するコイルとする。この例では、表５〜表１０の６通りが存在する。
【０１０６】
【表５】
2006107121.tif 000010
【０１０７】
【表６】
2006107121.tif 000011
【０１０８】
【表７】
2006107121.tif 000012
【０１０９】
【表８】
2006107121.tif 000013
【０１１０】
【表９】
2006107121.tif 000014
【０１１１】
【表１０】
2006107121.tif 000015
【０１１２】
従って、この例では、任意の１つのコイルを選び、任意のＡＧＶの最後に搬送するコイルとする操作を行った後の組み合わせのうち、最もコスト関数が小さくなる組み合わせＣは表５のケースになる。
【０１１３】
次に、ステップＳ２５では、ステップＳ２２〜Ｓ２４で求めた組み合わせＡ〜Ｃの中で、コスト関数の値が最も小さくなる組み合わせを求める。この例では、表５のケースとなる。この解を新しい解とし、更に、この解をタブリストに加える。なお、ステップＳ２２〜Ｓ２４の処理を実行して組み合わせＡ〜Ｃを求める際には、タブリストに存在する解以外で最小となる解を探索する。
【０１１４】
そして、ステップＳ２６で、このような操作を指定回数繰り返したか否かを判定し、上記指定回数の処理で得られた解の中で、小さいものから上位Ｌ個を記憶する。
【０１１５】
以上のようにして、ＡＧＶ組み合わせ割付け処理を行った後、図１２のフローチャートＳ１５において、最適制御で得られた配車問題の解Sol(0)と、タブサーチで得られたＬ個の解Sol(1)〜Sol(L)のシミュレーションを各々行い、各々の解に対応するコスト関数の値Cost(0)〜Cost(L)を計算する。この際には、全てのコイルは何らかのＡＧＶに割り付いているため、未割付けコイルが無い。全て割り付け確定済みコイルとしてシミュレーションを行う。すなわち、ＡＧＶのトークンは、すべて図４の上側の号車番号に対応したモジュールに入り、シミュレーションが行われる。
【０１１６】
具体的に、ステップＳ１５でシミュレーションする際には、式（７）のコスト関数の値をシミュレーションで求める。また、シミュレーションの際には、トークンの移動を表すファイルが作成される。
【０１１７】
そして、ステップＳ１６の比較処理では、最適制御に基づいたシミュレーションと、タブサーチで求めたＬ個の解に基づいたシミュレーションとからそれぞれ計算されたコスト関数値を比較し、最も小さい値を求め、それに対応したトークンの移動を表すファイルを最終結果として記憶する。
【０１１８】
そして、図ステップＳ１７及びステップＳ１８において、それぞれ図８のステップＳ４及びステップＳ５と同様の後処理及び割付け結果送信処理を行う。
【０１１９】
以上のように本実施形態では、ＡＧＶの走行をペトリネットモデルで構築し、ＡＧＶ状態と搬送命令に応じて設定された目標状態量Ｍrを目標として、ペトリネットの状態方程式から操作ベクトルｕ(k)を決定する。制御手段２１３は、この操作ベクトルに基づき各コイルと各ＡＧＶの移動操作を行うことにより最適制御理論を用いて配車問題の解を求める。一方、コスト関数設定手段２０８でＡＧＶの総空車走行時間とコイルの総搬送待ち時間との線型和となる関数を設定し、配車組み合わせ計算手段２０９で、このコスト関数が最小となる配車問題の解をタブサーチで複数求める。そして、シミュレーション手段２０３で、以上の配車問題の解を用いて各々シミュレーションを行い、コスト関数比較手段２１１にて最もコスト関数が小さくなる解を求め、その解を上位プロコン１０１へ返すようにした。これにより、ＡＧＶの走行時間を短くしたり、搬送物が運び出されるまでの搬送待ち時間を短くしたり、ＡＧＶの空車走行時間とコイルの搬送待ち時間とのトレードオフを考慮した最適な割り付けを行ったりすることができるようになる。
【０１２０】
（第３の実施形態）
次に、本発明の第３の実施形態について説明する。なお、以下の説明において、上述した第１の実施形態と同一の部分については、詳細な説明を省略する。
ＡＧＶの運行制御では、ＡＧＶの集中が問題となるケースがある。複数スキッドにまんべんなくコイルが発生する場合は良いが、一個所に集中してコイルが発生すると、そこにＡＧＶが集中して、干渉が非常に大きくなったり、デッドロック発生の一因になったりする。そこで、ＡＧＶはなるべく分散していた方が望ましい。
【０１２１】
これを実現するためには、ＡＧＶが集中することによって値が大きくなる渋滞度関数を考え、以下の式（９）のようにコスト関数を定義し、このコスト関数の値がなるべく小さくなる解を、以上説明した方法で求めれば良い。
【０１２２】
【数４】
2006107121.tif 000016
【０１２３】
渋滞度の定義と計算方法の一例を説明する。まず、走向路上のスキッドを複数のエリアに分割し、エリア毎に在席しているＡＧＶが指定された台数を超えると、渋滞度は大きな値を持つようにする。在席しているＡＧＶとは、空車または荷受け・荷卸し中のＡＧＶを指し、エリアを通過中のＡＧＶは含まないとする。
【０１２４】
渋滞度の計算例を次に説明する。簡単のため、エリア数を３、ＡＧＶの台数を３、エリアの台数制限値を全て２とする。そして、行をエリア、列を時間とした２次元マトリクス（渋滞マトリクスと呼ぶ）を考える。ここで、時間は１分毎に離散化して考え、列数を１０（分）とする。また、渋滞マトリクスの各要素は当該エリアで当該時刻に在席しているＡＧＶの合計台数を表すものとする。例えば、エリア１にあるＡＧＶが在席し、３分後にエリア１のスキッドから離れ、５分後にエリア２のスキッドに到着したとすると、渋滞マトリクスは以下の表１１のようになる。
【０１２５】
【表１１】
2006107121.tif 000017
【０１２６】
エリア１に１台のＡＧＶが、エリア２に２台のＡＧＶが在席し、エリア１からエリア２への搬送命令に、エリア１のＡＧＶが割り付き、３分後にエリア１のスキッドを離れ、５分後にエリア２のスキッドに到着したとすると、渋滞マトリクスは次の表１２のようになる。
【０１２７】
【表１２】
2006107121.tif 000018
【０１２８】
ここで、渋滞度は、以下の式（１０）で定義する。
【０１２９】
【数５】
2006107121.tif 000019
【０１３０】
先のマトリクスの（２，５）〜（２，１０）要素はエリアの最大数２を超えている。従って、渋滞度は６になる。
一方、同じ搬送命令をエリア２のAGVが搬送するときには、エリア２を０分後に離れ、エリア１に２分後に到着し、エリア１を４分後に離れて、エリア２に６分後に戻ってきたとすると、渋滞マトリクスは以下の表１３のようになる。
【０１３１】
【表１３】
2006107121.tif 000020
【０１３２】
この場合は全ての要素がエリアの最大数を超えていないため、渋滞度は０になる。この渋滞度に係数Ｋｃが掛けられ、コスト関数に加えられる。計数Ｋｃを大きな値にすることにより、渋滞度が少ない（ＡＧＶが１個所に集中しにくい）配車が得られる。
【０１３３】
以上は、充電量を考慮しない場合であるが、現実のＡＧＶはバッテリ駆動されている場合が多く、ＡＧＶが作業することによりバッテリを消耗する。この場合、バッテリ残量がある下限値を下回らないように、ＡＧＶを運行させる必要がある。例えば、図１５のように、適当な場所に充電場１３０１を設け、ＡＧＶ１３１１〜１３１４のバッテリが下限に近くなったら、コイル搬送を一時的に中断し、充電場に向かって走行し、充電場にて充電を行ってからコイル１３２１〜１３２４の搬送を再開する。
【０１３４】
本実施形態は、このような充電量を考慮する場合にも適用できる。例えば、１つの搬送が終了すると必ず充電するという方案にした場合には、あるコイルの搬送終了後のスキッドから充電場までの空車走行時間と充電場から次に搬送するコイルの荷受けスキッドまでの空車走行時間を全空車走行時間と考え、また、２番目に搬送するコイルの搬送待ち時間は空車走行時間の増加分と充電時間分を増やせば良い。
【０１３５】
（第４の実施形態）
次に、本発明の第４の実施形態について説明する。なお、以下の説明において、上述した第１〜第３の実施形態と同一の部分については、詳細な説明を省略する。
製鉄所のコイル搬送のように、コイルが発生するスキッドが特定出来ない場合には、ＡＧＶを１個所に集中させず、適度に分散していた方が望ましい。そこで、本実施形態では、スキッドを複数のエリアに分割して、そのエリアで空車と荷卸し中のＡＧＶが指定された個数以上になった場合には、指定個数以下になるよう空車ＡＧＶを別エリアに退避走行させることにより、ＡＧＶを分散化させることができるようにしている。
【０１３６】
例えば、図１６のようにスキッドを４つのエリアに分割する。そして、それぞれの許容台数を表１４のように設定したとすると、エリア１４０２（エリア２）の台数は２台となっており、許容台数を超えているため、空車ＡＧＶである３号車１４１３または４号車１４１４を別エリア１４０１、１４０３、１４０４（エリア１、３、４）に退避走行させる。退避走行先はエリア１４０２から近く、且つ許容台数に余裕があるエリアを探索する。図１６に示す例では、エリア１４０３のＡＧＶ台数は０であるため、退避先はエリア１４０３になる。退避走行させるＡＧＶは、エリア１４０３に近い方のＡＧＶとし、エリア１４０３の退避場所は、そのＡＧＶから最も近いスキッドとする。すなわち４号車１４１４をスキッドＤ１に退避させる。これにより、各エリア１４０１〜１４０４のＡＧＶ台数は全て１となり、ＡＧＶ１４１１〜１４１４を分散させることができる。
【０１３７】
【表１４】
2006107121.tif 000021
【０１３８】
なお、以上の各実施形態では、搬送システムの例として鉄鋼の製造ラインでコイルを搬送する例を挙げたが、本発明はこれに限定されるものではない。
また、以上の各実施形態では、物を搬送するためにＡＧＶを用いたが、自動クレームやキャリアパレット等、他の搬送システムにも本発明を適用することが可能である。
また、上記実施形態では、本発明をシミュレーション装置に適用した場合について説明したが、実プロセスに適用して物流制御装置として用いるようにすることも可能である。
【０１３９】
（本発明の他の実施形態）
上述した実施形態の機能を実現するべく各種のデバイスを動作させるように、該各種デバイスと接続された装置あるいはシステム内のコンピュータに対し、上記実施形態の機能を実現するためのソフトウェアのプログラムコードを供給し、そのシステムあるいは装置のコンピュータ（ＣＰＵあるいはＭＰＵ）に格納されたプログラムに従って上記各種デバイスを動作させることによって実施したものも、本発明の範疇に含まれる。
【０１４０】
また、この場合、上記ソフトウェアのプログラムコード自体が上述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそのプログラムコードをコンピュータに供給するための手段、例えば、かかるプログラムコードを格納した記録媒体は本発明を構成する。かかるプログラムコードを記憶する記録媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【０１４１】
また、コンピュータが供給されたプログラムコードを実行することにより、上述の実施形態の機能が実現されるだけでなく、そのプログラムコードがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）あるいは他のアプリケーションソフト等と共同して上述の実施形態の機能が実現される場合にもかかるプログラムコードは本発明の実施形態に含まれることは言うまでもない。
【０１４２】
さらに、供給されたプログラムコードがコンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後、そのプログラムコードの指示に基づいてその機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって上述した実施形態の機能が実現される場合にも本発明に含まれることは言うまでもない。
【図面の簡単な説明】
【０１４３】
【図１】本発明の実施形態を示し、配車計画作成装置の概略構成の一例を説明するブロック図である。
【図２】本発明の第１の実施形態を示し、無人搬送台車（ＡＧＶ）の配車計画作成装置を実施したスケジューリングシステムの全体構成を示すブロック図である。
【図３】本発明の第１の実施形態を示し、ペトリネットモデルの一例を示す図である。
【図４】本発明の第１の実施形態を示し、各ＡＧＶごとにペトリネットモデルのモジュールを生成する様子を示す図である。
【図５】本発明の第１の実施形態を示し、図３（ｂ）に示した各ＡＧＶスキッド用ゾーン内のペトリネットモデルを詳細に示す図である。
【図６】本発明の第１の実施形態を示し、図３（ｂ）に示したＯＣＤ用ゾーン内のペトリネットモデルを詳細に示す図である。
【図７】本発明の第１の実施形態を示し、図３（ｂ）に示したペトリネットモデルを図４及び図５の具体例に従って書き直した図である。
【図８】本発明の第１の実施形態を示し、ＡＧＶの配車計画作成装置のシミュレーション時の動作の一例を説明するフローチャートである。
【図９】本発明の第１の実施形態を示し、ＡＧＶ及びコイルのトークンの一例を示す図である。
【図１０】本発明の第１の実施形態を示し、各トランジション発火とそれによる状態遷移の様子を示した図である。
【図１１】本発明の第２の実施形態を示し、無人搬送台車（ＡＧＶ）の配車計画作成装置を実施したスケジューリングシステムの全体構成を示すブロック図である。
【図１２】本発明の第２の実施形態を示し、ＡＧＶの配車計画作成装置のシミュレーション時の動作の一例を説明するフローチャートである。
【図１３】本発明の第２の実施形態を示し、タブサーチによる配車組合わせを求める際のＡＧＶの配車計画作成装置の動作の一例を説明するフローチャートである。
【図１４】本発明の第２の実施形態を示し、ＡＧＶの走行路の一例を示す図である。
【図１５】本発明の第３の実施形態を示し、充電場を加えたＡＧＶの走行路の一例を示す図である
【図１６】本発明の第４の実施形態を示し、複数エリアに分割されたＡＧＶの走行路の一例を示す図である。
【符号の説明】
【０１４４】
１、２００  シミュレーション制御部
１ａ  配車シミュレータ
１ｂ  最適制御方策部
２  最適化計算装置
３  数式モデル
４  シミュレーション結果
１００  上位プロコン
１０１  配車計画作成装置
２０１  記憶手段
２０２  操作ベクトル算出手段
２０３  シミュレーション手段
２０４  状態ベクトル入力手段
２０５  状態管理手段
２０６  搬送命令管理手段
２０７  処理計画出力手段
２０８  コスト関数設定手段
２０９  配車組合わせ計算手段
２１０  目標値変更手段
２１１  コスト関数値比較手段
２１２  モデル構築手段
２１３  制御手段
３０１  入力手段
３０２  ゲイン行列算出手段
【図１】
2006107121.tif 000022
【図２】
2006107121.tif 000023
【図３】
2006107121.tif 000024
【図４】
2006107121.tif 000025
【図５】
2006107121.tif 000026
【図６】
2006107121.tif 000027
【図７】
2006107121.tif 000028
【図８】
2006107121.tif 000029
【図９】
2006107121.tif 000030
【図１０】
2006107121.tif 000031
【図１１】
2006107121.tif 000032
【図１２】
2006107121.tif 000033
【図１３】
2006107121.tif 000034
【図１４】
2006107121.tif 000035
【図１５】
2006107121.tif 000036
【図１６】
2006107121.tif 000037