(57)【要約】【課題】より効率的な走行車の走行を可能とする走行車制御装置、走行車システム、及び走行車制御方法を提供する。【解決手段】コントローラ３は、荷掴み位置への移動の要求を含む搬送要求を複数の走行車２のうちから選択される１つの走行車２に割り付ける走行車制御装置である。コントローラ３は、搬送要求を取得して蓄積する蓄積部３１と、蓄積部３１により蓄積された複数の搬送要求の各々に１つの走行車２を対応付けたペアリング情報を導出する導出部３４と、導出部３４により導出されたペアリング情報に基づく指令情報を出力する出力部３５と、を備える。【選択図】図２
2020030723.tif 000002
【特許請求の範囲】
【請求項１】
目的地への移動の要求を含む走行要求を複数の走行車のうちから選択される１つの走行車に割り付ける走行車制御装置であって、
前記走行要求を取得して蓄積する蓄積部と、
前記蓄積部により蓄積された複数の前記走行要求の各々に１つの前記走行車を対応付けたペアリング情報を導出する導出部と、
前記導出部により導出された前記ペアリング情報に基づく指令情報を出力する出力部と、
を備える、走行車制御装置。
【請求項２】
前記蓄積部が前記走行要求を取得及び蓄積する処理は、前記導出部が前記ペアリング情報を導出する処理とは非同期で実行される、請求項１に記載の走行車制御装置。
【請求項３】
前記走行要求が前記蓄積部により取得及び蓄積される第１制御周期は、前記ペアリング情報が前記導出部により導出される第２制御周期よりも短い、請求項１又は２に記載の走行車制御装置。
【請求項４】
前記走行車が走行可能なエリアに含まれる特定の地点をそれぞれ示す複数のノードと、前記ノード間を接続する複数のリンクと、前記リンク毎に関連付けられた、前記走行車が前記リンクを通過するのにかかる時間に基づく走行コストと、を含むマップ情報を記憶する記憶部と、
前記蓄積部により蓄積された複数の前記走行要求のうちの１つの走行要求と前記複数の走行車のうちの１つの走行車との組み合わせ毎に、前記走行車の現在位置と前記走行要求の前記目的地と前記マップ情報とに基づいて、前記走行車の現在位置から前記目的地までの走行経路を決定すると共に前記走行経路に含まれる前記リンクの前記走行コストの和である経路コストを算出する算出部と、を更に備え、
前記導出部は、前記組み合わせ毎に算出された前記経路コストに基づいて、前記ペアリング情報を導出する、請求項１〜３のいずれか一項に記載の走行車制御装置。
【請求項５】
前記導出部は、前記蓄積部により蓄積された複数の前記走行要求と複数の前記走行車との組み合わせにおける前記経路コストの総和が最小となるように、前記ペアリング情報を導出する、請求項４に記載の走行車制御装置。
【請求項６】
前記組み合わせ毎の前記経路コストが前記算出部により算出される第３制御周期は、前記ペアリング情報が前記導出部により導出される第２制御周期と同期している、請求項４又は５に記載の走行車制御装置。
【請求項７】
前記算出部は、前記走行要求と前記走行車との任意の組み合わせについて、前記走行車の現在位置から前記目的地までの複数の候補経路のうち、前記候補経路に含まれる前記リンクの前記走行コストの和が最小となる候補経路を、前記走行経路として決定する、請求項４〜６のいずれか一項に記載の走行車制御装置。
【請求項８】
前記算出部は、前記エリア内に存在する全ての前記走行車を対象として、前記経路コストを算出する、請求項４〜７のいずれか一項に記載の走行車制御装置。
【請求項９】
前記算出部は、前記エリア内に存在する一部の前記走行車を対象として、前記経路コストを算出する、請求項４〜７のいずれか一項に記載の走行車制御装置。
【請求項１０】
前記導出部は、前記走行要求と前記走行車との任意の組み合わせについて、前記経路コストが第１閾値以上である前記走行車を、前記走行要求の割り付け対象から除外する、請求項４〜９のいずれか一項に記載の走行車制御装置。
【請求項１１】
前記導出部は、第１の走行要求が割り付けられた第１の走行車に対して、前記第１の走行要求の実行完了後に実行すべき予約指令として第２の走行要求を割り付け可能であり、
前記導出部は、前記第１の走行車の現在位置から前記第１の走行要求の実行を経て前記第２の走行要求の前記目的地に到達するまでの前記走行経路の前記経路コストが第２閾値以上である場合、前記第１の走行車を前記第２の走行要求の割り付け対象から除外する、請求項４〜１０のいずれか一項に記載の走行車制御装置。
【請求項１２】
前記走行車は、物品を搬送する無人搬送車であり、
前記走行要求は、前記目的地としての荷掴み位置に配置された前記物品を荷掴みして所定の荷降ろし位置で荷降ろしする要求を示す搬送要求であり、
前記経路コストは、前記走行車の現在位置から前記荷掴み位置までの前記走行経路に含まれる前記リンクの前記走行コストの和を含む、請求項４〜１１のいずれか一項に記載の走行車制御装置。
【請求項１３】
前記導出部は、第１の走行要求が割り付けられた第１の走行車に対して、前記第１の走行要求の実行完了後に実行すべき予約指令として第２の走行要求を割り付け可能であり、
前記第１の走行車の前記第２の走行要求に関する前記経路コストは、前記第１の走行車の現在位置から前記第１の走行要求の前記荷降ろし位置までの前記走行経路に含まれる前記リンクの前記走行コストの和と、前記第１の走行要求の前記荷降ろし位置から前記第２の走行要求の前記荷掴み位置までの前記走行経路に含まれる前記リンクの前記走行コストの和と、を含む、請求項１２に記載の走行車制御装置。
【請求項１４】
請求項１〜１３のいずれか一項に記載の走行車制御装置と、
搬送路と、
前記搬送路に沿って走行可能な複数の前記走行車と、
を含む、走行車システム。
【請求項１５】
目的地への移動の要求を含む走行要求を複数の走行車のうちから選択される１つの走行車に割り付ける走行車制御方法であって、
前記走行要求を取得して蓄積する蓄積ステップと、
蓄積された複数の前記走行要求の各々に１つの前記走行車を対応付けたペアリング情報を導出する導出ステップと、
導出された前記ペアリング情報に基づく指令情報を出力する出力ステップと、
を含む、走行車制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、走行車制御装置、走行車システム、及び走行車制御方法に関する。
【背景技術】
【０００２】
従来、例えば半導体製造工場等において、半導体等の物品を搬送する走行車の走行を制御する無人走行車システムが知られている。このような無人走行車システムでは、新たな走行要求（一例として、搬送対象となる物品、荷掴み位置（Ｆｒｏｍ地点）、及び荷降ろし位置（Ｔｏ地点）の各々を示す情報を含む搬送要求）が発生する毎に、例えば以下のような最適台車優先制御が実行される。まず、荷掴み位置を含むモジュール（ベイ）内に存在する複数の空き走行車（物品搬送中ではない走行車）のうちから、最短経路又は最短時間で荷掴み位置に到達可能な走行車が特定される。そして、特定された走行車に上記搬送要求が割り付けられる。例えば、下記特許文献１には、搬送要求が発生する毎に、当該搬送要求を最短時間で処理可能な無人搬送車に当該搬送要求を割り付ける無人搬送車システムが記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３１８９８８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述したような最適台車優先制御によれば、新たな割り付けの対象とされた搬送要求にとっては最適な割り付け（局所最適な割り付け）となる一方で、無人走行車システム全体にとっては、必ずしも最適な割り付け（全体最適な割り付け）とはならない場合がある。例えば、最適台車優先制御によって第１の搬送要求を走行車Ａに割り付けた後に、第２の搬送要求が発生する場合がある。この場合、既に第１の搬送要求が割り付けられた走行車Ａは、第２の搬送要求の割り付け対象から除外され得る。このため、仮に、第１の搬送要求を走行車Ａとは異なる走行車Ｂに割り付けて第２の搬送要求を走行車Ａに割り付けた方が、システム全体で見た場合により効率的な搬送が実現されるとしても、このような割り付けを実現することができない。
【０００５】
そこで、本発明は、より効率的な走行車の走行を可能とする走行車制御装置、走行車システム、及び走行車制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る走行車制御装置は、目的地への移動の要求を含む走行要求を複数の走行車のうちから選択される１つの走行車に割り付ける走行車制御装置であって、走行要求を取得して蓄積する蓄積部と、蓄積部により蓄積された複数の走行要求の各々に１つの走行車を対応付けたペアリング情報を導出する導出部と、導出部により導出されたペアリング情報に基づく指令情報を出力する出力部と、を備える。
【０００７】
上記走行車制御装置では、複数の走行要求が一旦蓄積された後に、当該複数の走行要求の各々に対して１つの走行車を対応付けたペアリング情報が導出される。これにより、単一の走行要求だけでなく複数の走行要求間の相互の影響を考慮した割り付け（走行要求と走行車との対応付け）を行うことが可能となる。したがって、上記走行車制御装置によれば、１つの走行要求が発生する毎にいずれかの走行車に当該走行要求を割り付ける場合と比較して、無人走行車システム全体としてより効率的な走行車の走行が可能となる。
【０００８】
蓄積部が走行要求を取得及び蓄積する処理は、導出部がペアリング情報を導出する処理とは非同期で実行されてもよい。この場合、蓄積部により走行要求を取得及び蓄積しつつ、既に蓄積された複数の走行要求についてのペアリング情報を導出することが可能となる。
【０００９】
走行要求が蓄積部により取得及び蓄積される第１制御周期は、ペアリング情報が導出部により導出される第２制御周期よりも短くてもよい。この場合、複数の走行要求が蓄積された後にペアリング情報を導出する処理を周期的かつ適切に行うことができる。
【００１０】
上記走行車制御装置は、走行車が走行可能なエリアに含まれる特定の地点をそれぞれ示す複数のノードと、ノード間を接続する複数のリンクと、リンク毎に関連付けられた、走行車がリンクを通過するのにかかる時間に基づく走行コストと、を含むマップ情報を記憶する記憶部と、蓄積部により蓄積された複数の走行要求のうちの１つの走行要求と複数の走行車のうちの１つの走行車との組み合わせ毎に、走行車の現在位置と走行要求の目的地とマップ情報とに基づいて、走行車の現在位置から目的地までの走行経路を決定すると共に走行経路に含まれるリンクの走行コストの和である経路コストを算出する算出部と、を更に備え、導出部は、組み合わせ毎に算出された経路コストに基づいて、ペアリング情報を導出してもよい。この場合、走行要求と走行車との組み合わせ毎に算出された経路コストを指標として、ペアリング情報を適切に導出することが可能となる。
【００１１】
導出部は、蓄積部により蓄積された複数の走行要求と複数の走行車との組み合わせにおける経路コストの総和が最小となるように、ペアリング情報を導出してもよい。この場合、複数の走行要求について、全体最適が図られた割り付けを実現することができる。
【００１２】
組み合わせ毎の経路コストが算出部により算出される第３制御周期は、ペアリング情報が導出部により導出される第２制御周期と同期していてもよい。この場合、ペアリング情報を導出する時点の状況（走行車の現在位置等）に関して算出された経路コストに基づいて、ペアリング情報を適切に導出することが可能となる。
【００１３】
算出部は、走行要求と走行車との任意の組み合わせについて、走行車の現在位置から目的地までの複数の候補経路のうち、候補経路に含まれるリンクの走行コストの和が最小となる候補経路を、走行経路として決定してもよい。この場合、走行車が最短経路で目的地まで移動するという合理的な条件の下で、ペアリング情報を適切に導出することができる。
【００１４】
算出部は、エリア内に存在する全ての走行車を対象として、経路コストを算出してもよい。この場合、一部の走行車を対象とする場合と比較して、より最適なペアリング情報（例えば、経路コストの総和がより小さくなるペアリング情報）を導出できる可能性を高めることができる。
【００１５】
算出部は、エリア内に存在する一部の走行車を対象として、経路コストを算出してもよい。例えば、算出部は、走行要求の目的地が属する区画（ベイ）に存在する走行車に対象を絞って経路コストを算出してもよい。経路コストの算出対象となる走行車を一部の走行車に限定することにより、算出部の処理量を低減し、プロセッサ、メモリ等のコンピュータ資源の節約及び処理の高速化を図ることができる。
【００１６】
導出部は、走行要求と走行車との任意の組み合わせについて、経路コストが第１閾値以上である走行車を、走行要求の割り付け対象から除外してもよい。この場合、ある走行要求の実行に第１閾値以上の時間がかかる走行車を当該走行要求の割り付け対象から予め除外することにより、実行時間が比較的大きくなってしまう走行車に走行要求が割り付けられることを確実に防止することができる。
【００１７】
導出部は、第１の走行要求が割り付けられた第１の走行車に対して、第１の走行要求の実行完了後に実行すべき予約指令として第２の走行要求を割り付け可能であり、導出部は、第１の走行車の現在位置から第１の走行要求の実行を経て第２の走行要求の目的地に到達するまでの走行経路の経路コストが第２閾値以上である場合、第１の走行車を第２の走行要求の割り付け対象から除外してもよい。この場合、ある走行要求の実行に第２閾値以上の時間がかかる走行車を当該走行要求の割り付け対象（予約指令としての割り付け対象）から予め除外することにより、実行時間が比較的大きくなってしまう走行車に走行要求が割り付けられることを確実に防止することができる。
【００１８】
走行車は、物品を搬送する無人搬送車であり、走行要求は、目的地としての荷掴み位置に配置された物品を荷掴みして所定の荷降ろし位置で荷降ろしする要求を示す搬送要求であり、経路コストは、走行車の現在位置から荷掴み位置までの走行経路に含まれるリンクの走行コストの和を含んでもよい。この場合、無人搬送車（走行車）が搬送要求の荷掴み位置に到着するまでの時間に基づいて、無人搬送車に対する搬送要求の割り付けを適切に行うことができる。
【００１９】
導出部は、第１の走行要求が割り付けられた第１の走行車に対して、第１の走行要求の実行完了後に実行すべき予約指令として第２の走行要求を割り付け可能であり、第１の走行車の第２の走行要求に関する経路コストは、第１の走行車の現在位置から第１の走行要求の荷降ろし位置までの走行経路に含まれるリンクの走行コストの和と、第１の走行要求の荷降ろし位置から第２の走行要求の荷掴み位置までの走行経路に含まれるリンクの走行コストの和と、を含んでもよい。この場合、無人搬送車（第１の走行車）が第１の走行要求の実行を経て第２の走行要求の荷掴み位置に到着するまでの時間に基づいて、無人搬送車に対する搬送要求（第２の走行要求）の割り付けを適切に行うことができる。
【００２０】
本発明に係る走行車システムは、上記走行車制御装置と、搬送路と、搬送路に沿って走行可能な複数の走行車と、を含む。上記走行車システムは、上述した走行車制御装置を含んでいる。したがって、上記走行車システムによれば、上述した理由により、より効率的な走行車の走行が可能となる。
【００２１】
本発明に係る走行車制御方法は、目的地への移動の要求を含む走行要求を複数の走行車のうちから選択される１つの走行車に割り付ける走行車制御方法であって、走行要求を取得して蓄積する蓄積ステップと、蓄積された複数の走行要求の各々に１つの走行車を対応付けたペアリング情報を導出する導出ステップと、導出されたペアリング情報に基づく指令情報を出力する出力ステップと、を含む。上記走行車制御方法によれば、上述した走行車制御装置と同様の効果が奏される。
【発明の効果】
【００２２】
本発明によれば、より効率的な走行車の走行を可能とする走行車制御装置、走行車システム、及び走行車制御方法を提供することができる。
【図面の簡単な説明】
【００２３】
【図１】一実施形態に係る走行車システムのレイアウト例を示す図である。
【図２】コントローラのハードウェア構成の一例を示すブロック図である。
【図３】コントローラの機能構成を示すブロック図である。
【図４】算出部の処理の一例を説明するための図である。
【図５】算出部の処理の一例を説明するための図である。
【図６】算出部の処理結果の一例を示す図である。
【図７】図６の処理結果について導出されるペアリング情報を示す図である。
【図８】導出部の処理の第１の例を説明するための図である。
【図９】導出部の処理の第１の例を示すフローチャートである。
【図１０】導出部の処理の第１の例を説明するための図である。
【図１１】導出部の処理の第１の例を説明するための図である。
【図１２】導出部の処理の第１の例を説明するための図である。
【図１３】導出部の処理の第１の例を説明するための図である。
【図１４】導出部の処理の第１の例を説明するための図である。
【図１５】導出部の処理の第１の例を説明するための図である。
【図１６】導出部の処理の第２の例を説明するための図である。
【図１７】導出部の処理の第２の例を示すフローチャートである。
【図１８】導出部の処理の第２の例を説明するための図である。
【図１９】導出部の処理の第２の例を説明するための図である。
【図２０】導出部の処理の第２の例を説明するための図である。
【図２１】第１制御周期、第２制御周期、及び第３制御周期の一例を示す図である。
【図２２】コントローラの動作の一例を示すフローチャートである。
【発明を実施するための形態】
【００２４】
以下、図面を参照して本発明の一実施形態について説明する。なお、図面の説明においては、同一又は同等の要素には同一の符号を付し、重複する説明を省略する場合がある。
【００２５】
図１は、本発明の一実施形態に係る走行車システムのレイアウト例を示す図である。図２は、走行車システムに含まれるコントローラのハードウェア構成の一例を示すブロック図である。図３は、コントローラの機能構成を示すブロック図である。図１に示されるように、本実施形態に係る走行車システム１は、搬送路４と、搬送路４に沿って走行可能な複数の走行車２と、各走行車２の動作を制御するコントローラ（走行車制御装置）３と、を含む。
【００２６】
走行車２は、無人走行車であり、例えば天井走行車、有軌道台車等である。本実施形態では、走行車２は、物品を搬送する無人搬送車である。図１に示されるように、本実施形態では一例として、走行車２は、工場内に敷設されたレール（軌道）等の搬送路４に沿って走行可能に設けられた天井搬送車である。例えば、走行車２は、天井走行式無人搬送車（ＯＨＴ：Overhead  Hoist  Transfer）である。一例として、走行車２によって搬送される物品は、複数枚の半導体ウェハが収容されるカセット（いわゆるＦＯＵＰ（Front  Opening  Unified  Pod））である。
【００２７】
搬送路４は、複数（図１の例では１２個）の区画（ベイ）に分けられている。搬送路４は、ベイ内のルートであるイントラベイルート５と、異なるベイ間を接続するルートであるインターベイルート６と、を含む。搬送路４に沿って、ロードポート７及びバッファ８が設けられている。ロードポート７は、図示しない半導体処理装置と走行車２との間でＦＯＵＰの受け渡しをする地点である。バッファ８は、走行車２がＦＯＵＰを仮置きできる地点である。合流部９は、搬送路４上において、複数の走行車２が同時に進入することを排除する排他制御が必要となる地点である。
【００２８】
コントローラ３は、各走行車２に対して例えば無線通信によって搬送命令を出力することにより、各走行車２の搬送動作を制御する。ここで、搬送動作は、ＦＯＵＰを搬送するために行われる一連の動作であり、例えば、ロードポート７及びバッファ８等においてＦＯＵＰを掴む動作（荷掴み動作）及びＦＯＵＰを降ろす動作（荷降ろし動作）、並びに搬送路４を走行する走行動作等を含む。コントローラ３は、例えば図示しないＭＥＳ（Manufacturing  Execution  System）及びＭＣＳ（Material  Control  System）等の上位コントローラから、ＦＯＵＰの搬送に関する搬送要求（搬送指令）を受け付けて、走行車２に割り付ける。すなわち、コントローラ３は、上位コントローラから搬送要求を受け付けると、当該搬送要求を実行する走行車２を決定し、決定された走行車２に対して当該搬送要求を実行するように命令する。ここで、搬送要求は、搬送対象となる物品、荷掴み位置（Ｆｒｏｍ地点）、及び荷降ろし位置（Ｔｏ地点）等を特定するための情報を含んでいる。すなわち、搬送要求は、目的地としての荷掴み位置（Ｆｒｏｍ地点）に配置されたＦＯＵＰ（物品）を荷掴みして所定の荷降ろし位置（Ｔｏ地点）で荷降ろしすることを要求する指令である。
【００２９】
コントローラ３は、図１に示される制御対象エリア（複数のベイを含むエリア）に存在する走行車２を直接的に制御してもよいし、コントローラ３よりも下位のコントローラを介して走行車２を間接的に制御してもよい。例えば、制御対象エリアが複数のゾーン（例えばベイ単位）に分割され、ゾーン内の走行車２を制御するためのゾーンコントローラ（ベイコントローラ）が、ゾーン毎に設けられてもよい。この場合、コントローラ３は、各ゾーンコントローラに対して制御信号を送信し、各ゾーンコントローラが、各ゾーン内の走行車２に対して制御信号を送信してもよい。すなわち、各ゾーン内の走行車２は、各ゾーンのゾーンコントローラを介して、コントローラ３によって間接的に制御されてもよい。
【００３０】
図２に示されるように、コントローラ３は、一以上のＣＰＵ（Central  Processing  Unit）等のプロセッサ３０１と、主記憶装置である一以上のＲＡＭ（Random  Access  Memory）３０２及び一以上のＲＯＭ（Read  Only  Memory）３０３と、オペレータが操作入力を行うためのキーボード等の入力装置３０４と、オペレータに情報を提示するディスプレイ等の出力装置３０５と、上位コントローラ及び走行車２等との間で有線通信又は無線通信を行うための通信モジュール３０６と、ＨＤＤ及びＳＳＤ等の補助記憶装置３０７と、を含むコンピュータシステムとして構成され得る。コントローラ３は、１台のサーバ装置として構成されてもよいし、互いに協調して動作する複数のサーバ装置として構成されてもよい。後述するコントローラ３の各機能は、例えば、ＲＡＭ３０２等のメモリ上に所定のプログラムを読み込ませ、プロセッサ３０１の制御のもとで入力装置３０４及び出力装置３０５を動作させると共に通信モジュール３０６を動作させ、ＲＡＭ３０２及び補助記憶装置３０７におけるデータの読み出し及び書き込みを行うことで実現される。
【００３１】
図３に示されるように、コントローラ３は、機能的構成要素として、蓄積部３１と、記憶部３２と、算出部３３と、導出部３４と、出力部３５と、を備えている。コントローラ３は、これらの各機能により、所定の目的地までの移動を含む走行要求を複数の走行車２のうちから選択される１つの走行車２に割り付ける処理を実行する。本実施形態では、走行要求は、上述した搬送要求であり、所定の目的地は、搬送要求に含まれる荷掴み位置である。
【００３２】
蓄積部３１は、上位コントローラから出力された搬送要求を取得して蓄積する。蓄積部３１は、上位コントローラから取得した搬送要求を、コントローラ３が備えるメモリ等に一時的に保存する。本実施形態では、蓄積部３１は、所定の周期（第１制御周期）で、上位コントローラから周期的に搬送要求を受け付けるように構成されている。つまり、蓄積部３１は、第１制御周期で繰り返し到来する受付タイミングにおいて、上位コントローラから搬送要求を受け付ける。例えば、蓄積部３１は、前回の受付タイミングから今回の受付タイミングまでの間に上位コントローラにおいて発生した一以上の搬送要求を、今回の受付タイミングにおいて取得する。なお、前回の受付タイミングから今回の受付タイミングまでの間に一つも搬送要求が発生しなかった場合、今回の受付タイミングにおいては、蓄積部３１によって搬送要求は取得されなくてもよい。
【００３３】
記憶部３２は、走行車システム１のレイアウトに関するマップ情報を記憶している。マップ情報は、複数のノードと、複数のリンクと、リンク毎に関連付けられた走行コストと、を含む情報である。マップ情報は、後述する算出部３３によって参照される。
【００３４】
ノードは、走行車２が走行可能なエリア（例えば図１に示される制御対象エリア）に含まれる特定の地点を示す情報である。特定の地点は、搬送路４上において予め登録された任意の地点である。特定の地点は、例えば、ロードポート７、バッファ８等の所定の作業装置が配置された地点や、分岐地点又は合流地点となる合流部９等に対応する地点である。リンクは、ノード間を接続する部分（搬送路４の一部）を示す情報である。各リンクには、走行車２が走行可能な方向が関連付けられている。すなわち、マップ情報に含まれる複数のノードと複数のリンクとは、有向グラフを構成している。
【００３５】
走行コストは、走行車２がリンクを通過するのにかかる時間を示す情報である。走行コストは、静的コストと動的コストとを含み得る。静的コストは、リンクに予め関連付けられたコストであり、他の走行車２による影響を受けないコストである。例えば、静的コストは、一の走行車２が他の走行車２の影響を受けない状況においてリンクを通過可能な最短時間を示すコストである。このような静的コストは、例えば、リンクの長さ（距離）、リンクに関連付けられた制限速度等に基づいて算出され得る。一方、動的コストは、他の走行車２の影響（例えばリンクの混雑状況等）が考慮されたコストである。動的コストは、静的コストを算出するために用いられる指標（リンクの距離、制限速度等）に加えて、リンクの利用状況（リンク内に存在する走行車２の数等）等の動的に変化する指標を加味して算出されたコストである。静的コストは、リンク内に存在する走行車２の数によらずに一定となるが、動的コストは、リンク内に存在する走行車２の数によって変動し得る。具体的には、動的コストは、リンク内に存在する走行車２の数が多い程大きくなる。
【００３６】
動的コストは、例えば、走行計画が確定済みの走行車２（例えば、搬送要求を実行中の走行車２）の走行計画に基づいて、将来時点のリンクの混雑状況（リンク内に流入する走行車２の数等）を予測することにより算出され得る。ここで、走行計画は、走行車２がいつどこに存在するかを示す情報であり、計画された走行車２の走行経路及び走行速度に基づいて予測され得る。例えば、あるリンクの動的コストは、当該リンクへの流入時点（当該リンクの始点に到達する時点であり、例えば現在時点からの経過時間ｔの関数ｆ（ｔ）として表現され得る。一例として、あるリンクの動的コストは、下記式（１）〜（３）のように表現され得る。
ｆ（ｔ）＝４（０≦ｔ≦４）  …（１）
ｆ（ｔ）＝１０（４≦ｔ≦６）  …（２）
ｆ（ｔ）＝２（６≦ｔ≦１０）  …（３）
【００３７】
算出部３３は、蓄積部３１により蓄積された複数の搬送要求のうちの１つの搬送要求（Ｘ）と複数の走行車２のうちの１つの走行車２（Ｙ）との組み合わせ（Ｘ，Ｙ）毎に、走行車２が搬送要求を実行する場合にかかる時間（本実施形態では、走行車２が搬送要求の目的地（Ｆｒｏｍ地点）に到達するまでにかかる時間）を示す経路コストを算出する。具体的には、算出部３３は、搬送要求と走行車２との組み合わせ毎に、走行車２の現在位置と搬送要求の目的地（荷掴み位置であるＦｒｏｍ地点）と記憶部３２に記憶されたマップ情報とに基づいて、走行車２の現在位置から上記目的地までの走行経路を決定すると共に、走行経路に含まれるリンクの走行コストの和を経路コストとして算出する。各走行車２の現在位置は、例えば各走行車２からコントローラ３に対して無線通信によって随時報告される。算出部３３は、このように報告された各走行車２の現在位置を参照することにより、各走行車２の現在位置を把握することができる。
【００３８】
本実施形態では、算出部３３は、搬送要求と走行車２との任意の組み合わせについて、走行車２の現在位置から搬送要求の目的地（Ｆｒｏｍ地点）までの複数の候補経路のうち、候補経路に含まれるリンクの走行コストの和が最小となる候補経路（すなわち最短経路）を、上述した走行経路として決定する。算出部３３は、例えばダイクストラ法、Ａ＊（Ａ−ｓｔａｒ）等の公知の最短経路探索アルゴリズムを用いることにより、搬送要求と走行車２との組み合わせ毎に、走行経路（最短経路）を決定し、その経路コストを算出することができる。
【００３９】
図４を参照して、走行車２と搬送要求とのある組み合わせについての算出部３３の処理について説明する。ここでは一例として、ダイクストラ法を用いた処理について説明する。図４において、「Ｅ」、及び「１」〜「６」が記されたノードＮは、上述したマップ情報に含まれるノードに対応している。「Ｓ」が記されたノードＮ（以下「始点Ｓ」ともいう。）は、ルート探索の出発地（すなわち、走行車２の現在位置）を示している。「Ｅ」が記されたノードＮ（以下「終点Ｅ」ともいう。）は、ルート探索の目的地（すなわち、搬送要求のＦｒｏｍ地点）を示している。「１」〜「６」が記されたノードＮは、出発地でも目的地でもないノードである。これらのノードＮ間を接続するリンクＬは、マップ情報に含まれるリンクに対応している。各リンクＬに関連付けられた「Ｃｏｓｔ」は、マップ情報に含まれる走行コストに対応している。ここでは、説明を簡単にするために、各リンクＬの走行コストは、上述した静的コストである。ただし、各リンクＬの走行コストとして、動的コストが使用されてもよい。この場合、あるリンクＬの走行コストとして、走行車２が当該リンクＬの始点ノードに到達するまでの経過時間ｔに応じた走行コストｆ（ｔ）を用いればよい。各リンクＬの向きは、走行車２が走行可能な方向を示している。なお、始点Ｓがマップ情報に予め登録されたノードと一致しない場合（すなわち、始点Ｓがマップ情報に予め登録された第１ノードと第２ノードとを接続するリンクの途中位置に対応する場合）には、算出部３３は、始点Ｓと第１ノードとを接続する第１リンクと始点Ｓと第２ノードとを接続する第２リンクとを新たに設定することにより、図４に示したようなマップの情報を取得してもよい。この場合、第１リンク及び第２リンクの各々に関連付けられる走行コストは、例えば、第１ノードと第２ノードとを接続するリンクに関連付けられた走行コストと、第１リンク及び第２リンクの距離の比と、に基づいて決定され得る。
【００４０】
算出部３３は、図４に示されるような有向グラフに対して最短経路探索アルゴリズム（ここではダイクストラ法）を実行することにより、始点Ｓから終点Ｅまでの最短経路と、当該最短経路に含まれる一以上のリンクＬの走行コストの和である経路コストと、を導出する。図５は、最短経路探索アルゴリズムの実行結果を示す図である。図５に示されるように、算出部３３は、始点Ｓから終点Ｅまでの最短経路として、「Ｓ」→「１」→「２」→「４」→「６」→「５」→「Ｅ」の順に辿るルートを決定する。また、算出部３３は、当該最短経路の経路コストとして、当該最短経路に含まれるリンクＬの走行コストの和である「１６（＝２＋３＋３＋４＋２＋２）」を算出する。このように、算出部３３は、公知の最短経路探索アルゴリズムを実行することにより、走行車２と搬送要求との１つの組み合わせについて、走行経路（最短経路）とその経路コストとを導出する。算出部３３は、蓄積部３１により蓄積された複数の搬送要求と制御対象エリアに存在する複数の走行車２との間で可能な全ての組み合わせについて、上記最短経路探索アルゴリズムを実行する。これにより、算出部３３は、組み合わせ毎の走行経路とその経路コストとを導出する。
【００４１】
なお、上記例は、走行車２に搬送要求が割り付けられていない場合（走行車２が搬送要求を実行中ではない場合）を想定している。すなわち、割付対象とされた搬送要求を走行車２に割り付けた場合に、当該走行車２が直ちに当該搬送要求のＦｒｏｍ地点に向かって走行することが可能な状況を想定している。一方、第１の搬送要求（第１の走行要求）が割り付けられた走行車２に対して、第１の搬送要求の実行完了後に実行すべき予約指令として第２の搬送要求（第２の走行要求）を割り付けることも可能である。この場合、第１の搬送要求が割り付けられた走行車２の走行経路は、第１の搬送要求を実行完了するまでの経路と、第１の搬送要求を実行完了してから第２の搬送要求のＦｒｏｍ地点に到達するまでの経路と、を含むことになる。したがって、算出部３３は、このような第１の搬送要求が割り付けられた走行車２については、例えば上述した最短経路探索アルゴリズムを以下のように段階的に実行することにより、走行経路（最短経路）及び経路コストを算出することができる。なお、以降の説明においては、搬送要求が割り付けられていない走行車２（空き走行車）に対して搬送要求を割り付けることを「通常割付」ということがある。また、第１の搬送要求が割り付けられた走行車２に対して第２の搬送要求を予約指令として割り付けることを「予約割付」ということがある。
【００４２】
第１の搬送要求が割り付けられた走行車２が、第１の搬送要求のＦｒｏｍ地点に到達する前である場合（すなわち、荷掴み前である場合）、算出部３３は、例えば、以下の第１走行経路、第２走行経路及び第３走行経路の各々を上述した最短経路探索アルゴリズムを用いて決定し、第１走行経路、第２走行経路及び第３走行経路をこの順に接続した経路を走行経路として決定することができる。また、算出部３３は、第１走行経路の経路コスト、第２走行経路の経路コスト及び第３走行経路の経路コストの和を、決定された走行経路の経路コストとして算出することができる。
・第１走行経路：走行車２の現在位置を始点Ｓとし、第１の搬送要求のＦｒｏｍ地点を終点Ｅとした場合に算出される最短経路
・第２走行経路：第１の搬送要求のＦｒｏｍ地点を始点Ｓとし、第１の搬送要求のＴｏ地点を終点Ｅとした場合に算出される最短経路
・第３走行経路：第１の搬送要求のＴｏ地点を始点Ｓとし、第２の搬送要求のＦｒｏｍ地点を終点Ｅとした場合に算出される最短経路
【００４３】
第１の搬送要求が割り付けられた走行車２が、第１の搬送要求のＦｒｏｍ地点から第１の搬送要求のＴｏ地点に向かって搬送中である場合、算出部３３は、例えば、以下の第４走行経路と上述した第３走行経路とを上述した最短経路探索アルゴリズムを用いて決定し、第４走行経路及び第３走行経路をこの順に接続した経路を走行経路として決定することができる。また、算出部３３は、第４走行経路の経路コスト及び第３走行経路の経路コストの和を、決定された走行経路の経路コストとして算出することができる。
・第４走行経路：走行車２の現在位置を始点Ｓとし、第１の搬送要求のＴｏ地点を終点Ｅとした場合に算出される最短経路
【００４４】
上述した算出部３３の処理により、蓄積部３１により蓄積された複数の搬送要求と複数の走行車２との間で可能な各組み合わせについての経路コストが得られる。図６は、複数（ここでは４つ）の搬送要求（搬送要求１〜搬送要求４）と複数（ここでは７つ）の走行車２（Ａ〜Ｇの走行車ＩＤにより識別される走行車２）との組み合わせ毎に算出された経路コストの一例を示す図である。例えば、図６の搬送要求１の表における第１行目は、搬送要求１を走行車ＩＤが「Ａ」である走行車２（以下、走行車ＩＤが「Ｘ」である走行車２のことを、単に「走行車Ｘ」と表記する。）に割り付けた場合に、走行車Ａが走行車Ａの現在位置から搬送要求１のＦｒｏｍ地点に到達するまでにかかる最短時間が「３（秒）」であることを示している。なお、図６の例では、後述する割付制限によって、経路コストが所定の閾値（ここでは３０秒）以上となる走行車２が除外されている。
【００４５】
導出部３４は、蓄積部３１により蓄積された複数の搬送要求の各々に１つの走行車２を対応付けた（割り付けた）ペアリング情報を導出する。導出部３４は、算出部３３によって組み合わせ毎に算出された経路コスト（すなわち、図６に示されるような算出結果）に基づいて、ペアリング情報を導出する。本実施形態では、導出部３４は、蓄積部３１により蓄積された複数の搬送要求と複数の走行車２との組み合わせにおける経路コストの総和が最小となるように、ペアリング情報を導出する。
【００４６】
ここで、導出部３４は、通常割付に関して所定の条件に合致する走行車２に対する割付を行わないようにしてもよい。具体的には、導出部３４は、搬送要求と走行車２との任意の組み合わせについて、通常割付の対象となる走行車２の経路コスト（すなわち、走行車２の現在位置から割付対象の搬送要求のＦｒｏｍ地点までの走行経路の経路コスト）が第１閾値（一例として「３０」）以上である走行車２を、搬送要求の割り付け対象（通常割付対象）から除外してもよい。第１閾値は、例えばオペレータ等によって事前に任意に設定され得る。
【００４７】
同様に、導出部３４は、予約割付に関して所定の条件に合致する走行車２に対する割付を行わないようにしてもよい。具体的には、導出部３４は、搬送要求と走行車２との任意の組み合わせについて、第２の搬送要求の予約割付の対象となる走行車２（第１の搬送要求が割り付けられた第１の走行車）の現在位置から第１の搬送要求の実行を経て第２の搬送要求のＦｒｏｍ地点に到達するまでの走行経路の経路コストが第２閾値（一例として「３０」）以上である場合、当該走行車２を第２の搬送要求の割り付け対象（予約割付対象）から除外してもよい。第２閾値は、例えばオペレータ等によって事前に任意に設定され得る。ここで、「走行車２の現在位置から第１の搬送要求の実行を経て第２の搬送要求のＦｒｏｍ地点に到達するまでの走行経路」は、上述した「第１走行経路＋第２走行経路＋第３走行経路」又は「第４走行経路＋第３走行経路」である。
【００４８】
上述のような通常割付又は予約割付についての割付制限を設けることにより、実行時間（ここでは、割付対象の搬送要求の荷掴みが開始されるまでの時間）が比較的大きくなってしまう走行車２に搬送要求が割り付けられることを確実に防止することができる。また、このような割付制限によれば、各搬送要求の割付候補となる走行車２の範囲を限定することができる。つまり、ある搬送要求について、経路コストが第１閾値（又は第２閾値）以上となる走行車２を当該搬送要求の割付候補から予め除外することができる。その結果、後述する導出部３４のアルゴリズムの実行にかかる計算量を低減でき、コントローラ３のプロセッサ３０１、メモリ（ＲＡＭ３０２，ＲＯＭ３０３等）等のコンピュータ資源の節約及び処理の高速化を図ることができる。
【００４９】
図７は、図６の例について導出されたペアリング情報を示す図である。図７に示されるように、搬送要求１に走行車Ｃを対応付け、搬送要求２に走行車Ｅを対応付け、搬送要求３に走行車Ｂを対応付け、搬送要求４に走行車Ａを対応付けた場合に、経路コストの総和が最小値「２１（＝６＋５＋６＋４）」を取る。したがって、このような対応付けを示すペアリング情報が、導出部３４によって導出される。
【００５０】
ここで、比較例として、搬送要求１〜４がこの順に蓄積部３１によって取得され、各搬送要求２に対して従来の最適台車優先制御が行われた場合には、以下のような割付が実現される。なお、ここでは説明を簡単にするために、予約割付を考慮しないものとする。すなわち、先に搬送要求が割り付けられた走行車２は、後の搬送要求の割付対象から除外されるものとする。まず、搬送要求１に対して、経路コストが最小となる（すなわち、搬送要求１を最短時間で実行可能な）走行車Ａが割り付けられる。続いて、搬送要求２に対して、割付可能な走行車２（既に搬送要求１が割り付けられた走行車Ａを除く走行車２）のうちから経路コストが最小となる走行車Ｂが割り付けられる。続いて、搬送要求３に対して、割付可能な走行車２（既に搬送要求１，２が割り付けられた走行車Ａ，Ｂを除く走行車２）のうちから経路コストが最小となる走行車Ｃが割り付けられる。最後に、搬送要求４に対して、割付可能な走行車２（既に搬送要求１〜３が割り付けられた走行車Ａ，Ｂ，Ｃを除く走行車２）のうちから経路コストが最小となる走行車Ｅが割り付けられる。この場合、搬送要求１〜４の経路コストの総和は、２７（＝３＋３＋１０＋１１）となる。
【００５１】
このように、比較例では、１つの搬送要求が発生する毎に、割付対象となる搬送要求にのみ着目し、その都度最適な走行車２に搬送要求を割り付ける処理が実行される。すなわち、比較例では、複数の搬送要求１〜４間の相互の影響が考慮されない。このため、搬送要求１〜４間の経路コスト（走行車２が荷掴み位置に到着するまでの所要時間）のばらつきが大きくなっている。具体的には、経路コストの最小値「３」と最大値「１１」との差は「８」であり、比較的大きい値となっている。
【００５２】
ここで、搬送要求のＦｒｏｍ地点（荷掴み位置）が、半導体ウェハに各種処理を実行する図示しない半導体処理装置に設けられたロードポート７である場合、経路コストが大きいことは、荷掴み（すなわち、ロードポート７に載置された処理済みのＦＯＵＰの回収）が遅れることを意味する。また、荷掴みが遅れることは、全体的な処理遅延の原因となる。また、搬送要求１〜４間の経路コストのばらつきが大きくなると、搬送要求１〜４間のリードタイムのばらつきもその分大きくなる可能性がある。リードタイムとは、搬送要求が発生してから当該搬送要求が特定の走行車２に割り付けられるまでの時間と、当該走行車２が当該搬送要求の実行（例えば、荷掴み位置への移動、荷掴み、荷降ろし位置への移動、及び荷降ろしの一連の動作）を完了するまでのサイクルタイムとの和である。このようなリードタイムのばらつきが大きくなると、安定した生産計画を立て難くなるという問題がある。
【００５３】
一方、上述した導出部３４によれば、複数の搬送要求１〜４間の相互の影響が考慮されたペアリング情報が得られる。すなわち、経路コストの総和が最小となるように全体最適が図られたペアリング情報（以下「最適ペアリング情報」ともいう。）が得られる。そして、このような全体最適が図られた組み合わせにおいては、搬送要求１〜４間で経路コストのばらつきは抑制される傾向がある。図７の例では、経路コストの最小値「４」と最大値「６」との差は「２」であり、比較的小さい値となっている。これにより、上述のように局所最適な割り付けを行う比較例と比較して、搬送要求１〜４間のリードタイムのばらつきを抑制することができる。その結果、安定した生産計画を立て易くなるという効果が奏される。
【００５４】
［第１の例］
次に、図８〜図１５を参照して、最適ペアリング情報を導出するための導出部３４の処理の第１の例について説明する。第１の例では、導出部３４は、搬送要求と走行車２との対応付け（ペアリング）を最小費用流問題として定式化し、当該最小費用流問題を解くことにより、ペアリング情報を導出する。ここでは、図８に示されるように、２つの搬送要求１，２と３つの走行車Ａ，Ｂ，Ｃとの間で経路コストの総和が最小となるペアリング情報（以下「最適ペアリング情報」）を導出する場合の処理について説明する。図８の（Ａ）は、本例の説明のために用意された算出部３３による算出結果の一例を図６と同様の表形式で表現したものである。図８の（Ｂ）は、図８の（Ａ）に示される関係を無向グラフとして表現したものである。図８の（Ｂ）に示されるグラフは、搬送要求１，２と走行車Ａ，Ｂ，Ｃとをそれぞれノードとして表現すると共に、搬送要求１，２と走行車Ａ，Ｂ，Ｃとの各組み合わせの経路コストを搬送要求と走行車とを結ぶリンクのコストとして表現したものである。
【００５５】
図９は、第１の例に係る処理手順を示すフローチャートである。まず、ステップＳ１１において、導出部３４は、最適ペアリング情報を導出する問題を最小費用流問題として定式化するために、図１０に示されるコスト付きネットワークを作成する。具体的には、図１０に示されるように、導出部３４は、搬送要求１，２を示すノード１，２の各々とコスト「０」のリンクによって接続される始点ｓを設定すると共に、走行車Ａ，Ｂ，Ｃを示すノードＡ，Ｂ，Ｃの各々とコスト「０」のリンクによって接続される終点ｅを設定する。また、導出部３４は、グラフ全体が「始点ｓ→搬送要求ノード（ノード１，２）→走行車ノード（ノードＡ，Ｂ，Ｃ）→終点ｅ」の方向に流れる有向グラフとなるように、各リンクの向きを設定する。ここで、各リンクの容量は１に設定される。以上により、２つの搬送要求１，２と３つの走行車Ａ，Ｂ，Ｃとの間の最適ペアリング情報を導出する問題は、図１０に示されるコスト付きネットワーク（有向グラフ）に対する最小費用流問題に変換される。
【００５６】
続いて、ステップＳ１２において、導出部３４は、図１０に示されるコスト付きネットワークについて、ダイクストラ法等の最短経路探索アルゴリズムを実行することにより、始点ｓから終点ｅまでの最短経路Ｐ１を求めると共に、始点ｓから各ノードへの最短コスト（始点ｓから各ノードへの最短経路を辿った場合に通過するリンクのコストの和）を求める。これにより、図１１に示されるように、太線で示される最短経路Ｐ１（始点ｓ→ノード１→ノードＡ→終点ｅ）と各ノードの最短コストとが求まる。
【００５７】
続いて、ステップＳ１３において、導出部３４は、最短経路Ｐ１について、補助ネットワーク（残余容量ネットワーク）を作成する。具体的には、まず、図１２に示されるように、導出部３４は、最短経路Ｐ１上の各リンクの向きを逆転させると共に、最短経路Ｐ１上の各リンクのコストをマイナスにする（すなわち、各リンクのコストに「−１」を乗算する）。これにより、ノード１とノードＡとを結ぶリンクのコストは、「１」から「−１」に変化する。続いて、図１３に示されるように、導出部３４は、有向グラフの各リンクのコストに、「リンクの始点の最短コスト−リンクの終点の最短コスト」を加える。これにより、図１３に示されるように、各リンクのコストが更新された補助ネットワークＡＮ１が得られる。
【００５８】
続いて、ステップＳ１４において、導出部３４は、補助ネットワークＡＮ１において、始点ｓから終点ｅに向かう経路が存在するか否かを判定する。ここでは、補助ネットワークＡＮ１において、始点ｓから終点ｅに向かう経路が存在し、判定結果は「ＹＥＳ」となるため、導出部３４は、ステップＳ１５の処理へと進む。
【００５９】
ステップＳ１５において、導出部３４は、補助ネットワークＡＮ１に対して、ダイクストラ法等の最短経路探索アルゴリズムを実行することにより、始点ｓから終点ｅまでの最短経路Ｐ２を求めると共に、始点ｓから各ノードへの最短コストを求める。これにより、図１４に示されるように、太線で示される最短経路Ｐ２（始点ｓ→ノード２→ノードＡ→ノード１→ノードＢ→終点ｅ）が求まると共に、各ノードの最短コストが更新される。
【００６０】
続いて、ステップＳ１３に戻って、導出部３４は、最短経路Ｐ１についての処理と同様の手順により、最短経路Ｐ２について、補助ネットワークを求める。これにより、図１５に示されるように、最短経路Ｐ２上の各リンクの向きが逆転させられると共に、各リンクのコストが更新された補助ネットワークＡＮ２が得られる。補助ネットワークＡＮ２が得られた時点で、始点ｓから終点ｅに向かう経路は存在しなくなる。したがって、ステップＳ１４の判定結果は「ＮＯ」となるため、導出部３４は、ステップＳ１６の処理へと進む。なお、本例のように「走行車２の数（ここでは３）＞搬送要求の数（ここでは２）」が成立する場合、反復回数（補助ネットワークの導出回数）は、搬送要求の数と等しくなる。このため、本例では、２つ目の補助ネットワークＡＮ２を導出した段階で、始点ｓから終点ｅに向かう経路が存在しなくなる。
【００６１】
続いて、ステップＳ１６において、導出部３４は、上述した繰り返し処理（最短経路探索及び補助ネットワーク作成）を終了した時点の状態（図１５に示される補助ネットワークＡＮ２）における走行車（ノードＡ〜Ｃ）から搬送要求（ノード１，２）に向かうリンクに基づいて、最適ペアリング情報を導出する。図１５の例では、ノードＡからノード２に向かうリンクとノードＢからノード１に向かうリンクとが、搬送要求と走行車との最適な組み合わせを示している。この場合、導出部３４は、搬送要求１を走行車Ｂに対応付けると共に搬送要求２を走行車Ａに対応付けたペアリング情報を最適ペアリング情報として導出する。
【００６２】
なお、第１の例では、ステップＳ１２又はステップＳ１５において、ダイクストラ法等の最短経路探索アルゴリズムによって得られる最短経路が複数存在する場合（すなわち、始点ｓから終点ｅまでのコストが同一となる複数の最短経路が存在する場合）があり得る。このような場合、導出部３４は、複数の最短経路のうちの任意の１つの最短経路を選択して、引き続きの処理（ステップＳ１３における補助ネットワークの作成）を実行すればよい。このような方策によれば、最終的に、最適ペアリング情報を得ることができる。なお、図８の例では、複数の搬送要求１，２と複数の走行車Ａ，Ｂ，Ｃとの間の全ての組み合わせが可能なケース（すなわち、全ての走行車Ａ，Ｂ，Ｃが全ての搬送要求１，２を実行可能なケース）について説明した。ただし、上述した第１の例の処理は、一部の搬送要求のみを実行可能な走行車が存在する場合、及び一部の走行車のみによって実行されることが可能な搬送要求が存在する場合においても、適用可能である。
【００６３】
［第２の例］
次に、図１６〜図２０を参照して、最適ペアリング情報を導出するための導出部３４の処理の第２の例について説明する。第２の例では、導出部３４は、搬送要求と走行車２との対応付け（ペアリング）を割当問題として定式化し、当該割当問題を解くことにより、ペアリング情報を導出する。ここでは、図１６に示されるように、５つの搬送要求１〜５と５つの走行車Ａ〜Ｅとの間で経路コストの総和が最小となるペアリング情報（最適ペアリング情報）をハンガリー法によって導出する場合の処理について説明する。図１６は、算出部３３による算出結果の一例を図６と同様の表形式で表現したものである。
【００６４】
図１７は、第２の例に係る処理手順を示すフローチャートである。まず、ステップＳ２１において、導出部３４は、図１８の（Ａ）に示されるようなコスト行列を作成する。コスト行列は、搬送要求１〜５を縦方向（列方向）に対応付けると共に走行車Ａ〜Ｅを横方向（行方向）に対応付けた５行５列の行列である。コスト行列の各要素には、搬送要求と走行車との組に対応する経路コストが格納される。なお、導出部３４は、図１８の（Ａ）に示されるコスト行列の行と列を入れ替えた行列をコスト行列として作成してもよい。
【００６５】
続いて、ステップＳ２２において、導出部３４は、各行の最小値を検索し、各行の各要素から最小値を減算する。具体的には、導出部３４は、１行目の最小値である「３」を１行目の各要素から減算し、２行目の最小値である「３」を２行目の各要素から減算し、３行目の最小値である「１」を３行目の各要素から減算し、４行目の最小値である「２」を４行目の各要素から減算し、５行目の最小値である「１」を５行目の各要素から減算する。これにより、図１８の（Ｂ）に示される行列が得られる。
【００６６】
続いて、ステップＳ２３において、導出部３４は、「０」である要素を各行各列から１つずつ選択可能であるか否かを判定する。ここでは、図１８の（Ｂ）に示される行列において、「０」である要素を各行各列から１つずつ選択することはできないため、判定結果は「ＮＯ」となる。よって、導出部３４は、ステップＳ２４の処理へと進む。
【００６７】
続いて、ステップＳ２４において、導出部３４は、全ての「０」をできるだけ少ない縦線又は横線で覆う。これにより、図１９の（Ａ）に示されるように、１つの縦線（第１列）と３つの横線（第１行、第２行及び第５行）が設定される。
【００６８】
続いて、ステップＳ２５において、導出部３４は、ステップＳ２４において設定された縦線又は横線で覆われていない各要素から、縦線又は横線で覆われていない要素の最小値を減算する。ここで、縦線又は横線で覆われていない要素の最小値は、第４行第３列の「３」である。よって、導出部３４は、縦線又は横線で覆われていない８つの要素のそれぞれから「３」を減算する。
【００６９】
また、ステップＳ２６において、導出部３４は、縦線及び横線が重なる要素（ここでは、第１行第１列、第２行第１列、及び第５行第１列の３つの要素）に、縦線又は横線で覆われていない要素の最小値（ここでは「３」）を加算する。これにより、図１９の（Ｂ）に示される行列が得られる。
【００７０】
続いて、ステップＳ２３に戻って、導出部３４は、「０」である要素を各行各列から１つずつ選択可能であるか否かを再度判定する。ここでは、図１９の（Ｂ）に示される行列において、「０」である要素を各行各列から１つずつ選択することはできないため、判定結果は「ＮＯ」となる。よって、導出部３４は、再度ステップＳ２４の処理へと進む。
【００７１】
続いて、２回目のステップＳ２４が実行されることにより、図２０の（Ａ）に示されるように、２つの縦線（第１列及び第３列）と２つの横線（第２行及び第５行）が設定される。
【００７２】
続いて、２回目のステップＳ２５及びＳ２６が実行されることにより、図２０の（Ｂ）に示される行列が得られる。続いて、３回目のステップＳ２３において、導出部３４は、「０」である要素を各行各列から１つずつ選択可能であるか否かを再度判定する。図２０の（Ｂ）に示される行列においては、太線枠で示されるように、「０」である要素を各行各列から１つずつ選択できる組み合わせが存在する。よって、判定結果は「ＹＥＳ」となり、導出部３４は、ステップＳ２７の処理へと進む。
【００７３】
続いて、ステップＳ２７において、導出部３４は、選択された組み合わせ（図２０の（Ｂ）において太線枠で囲まれた組み合わせ）を最適ペアリング情報として導出する。すなわち、この例では、導出部３４は、搬送要求１を走行車Ｃに対応付け、搬送要求２を走行車Ｄに対応付け、搬送要求３を走行車Ａに対応付け、搬送要求４を走行車Ｂに対応付け、搬送要求５を走行車Ｅに対応付けたペアリング情報を、最適ペアリング情報として導出する。
【００７４】
なお、第２の例の処理を実行するためには、ｎ行ｎ列のコスト行列が必要となる。図１６に示したように複数の搬送要求と複数の走行車２との関係がｎ：ｎ（ここでは５：５）である場合には、上記のように処理を行うことができる。一方、複数の搬送要求と複数の走行車２との関係がｎ：ｎでない場合には、ダミー要素を加えてｎ行ｎ列のコスト行列を作成することにより、上記のように処理を行うことができる。
【００７５】
出力部３５は、導出部３４により導出されたペアリング情報（本実施形態では、最適ペアリング情報）に基づく指令情報を出力する。コントローラ３が直接的に走行車２を制御する場合には、出力部３５は、ペアリング情報に基づく指令情報を各走行車２に出力（送信）する。例えば、搬送要求１を走行車Ａに対応付けることを示す情報がペアリング情報に含まれている場合、出力部３５は、走行車Ａに対して、搬送要求１を実行するための搬送動作（走行動作、荷掴み動作、荷降ろし動作等）の実行を指示する指令情報を出力する。指令情報は、算出部３３により決定された走行経路（最短経路）の情報を含んでもよい。これにより、走行車Ａは、出力部３５から受け取った指令情報に基づいて、搬送要求１を実行するための搬送動作を行うことが可能となる。
【００７６】
一方、コントローラ３が上述したゾーンコントローラ等の下位コントローラを介して走行車２を制御する場合には、出力部３５は、各走行車２についての指令情報を各走行車２に対応する下位コントローラに出力してもよい。この場合、下位コントローラを介して、出力部３５から各走行車２へと指令情報が伝達される。ただし、コントローラ３から下位コントローラへと送信される指令情報と、下位コントローラから走行車２へと送信される指令情報とは、完全に一致していなくてもよい。例えば、コントローラ３から下位コントローラへと送信された指令情報は、下位コントローラにおいて、走行車２が実行可能な形式へと書き換えられた上で、走行車２へと送信されてもよい。
【００７７】
次に、図２１を参照して、一以上の搬送要求が蓄積部３１により取得及び蓄積される第１制御周期、ペアリング情報が導出部３４により導出される第２制御周期、及び搬送要求と走行車２との組み合わせ毎の経路コストが算出部３３により算出される第３制御周期の関係の一例について説明する。上述したように、本実施形態では、蓄積部３１は、所定の周期（第１制御周期Ｔ１）で、上位コントローラから周期的に搬送要求を取得するように構成されている。第１制御周期Ｔ１で繰り返し到来する受付タイミング（時点ｔ１、ｔ２、ｔ４、ｔ５、ｔ７、ｔ８）のそれぞれにおいて、蓄積部３１は、前回の受付タイミングから今回の受付タイミングの間に発生した一以上の搬送要求を上位コントローラから取得する。
【００７８】
蓄積部３１が搬送要求を取得及び蓄積する受付タイミングは、導出部３４がペアリング情報を導出するための処理を実行するタイミング（時点ｔ３、ｔ６、ｔ９）とずれている。すなわち、蓄積部３１が搬送要求を取得及び蓄積する処理は、導出部３４がペアリング情報を導出する処理とは非同期で実行される。これにより、蓄積部３１により搬送要求を取得及び蓄積しつつ、既に蓄積された複数の搬送要求についてのペアリング情報を導出することが可能とされている。
【００７９】
また、第１制御周期Ｔ１は、第２制御周期Ｔ２よりも短くなるように設定されている。ここでは、第２制御周期Ｔ２は、第１制御周期Ｔ１の２倍となっている。これにより、第２制御周期Ｔ２で繰り返し到来するペアリング情報の導出タイミング（時点ｔ３、ｔ６、ｔ９）のそれぞれにおいて、直近２回の受付タイミングによって取得された複数の搬送要求についてのペアリング情報が導出される。このように、第１制御周期Ｔ１が第２制御周期Ｔ２よりも短く設定されていることにより、複数の搬送要求が蓄積された後に当該複数の搬送要求についてのペアリング情報を導出する処理を周期的かつ適切に行うことができる。
【００８０】
また、組み合わせ毎の経路コストが算出部３３により算出される第３制御周期は、ペアリング情報が導出部３４により導出される第２制御周期Ｔ２と同期している。すなわち、第３制御周期は第２制御周期Ｔ２と略等しく、算出部３３による経路コストの算出は、導出部３４によるペアリング情報の導出の直前（ほぼ同時）に行われる。これにより、ペアリング情報を導出する時点の状況（各走行車２の現在位置等）に関して算出された経路コストに基づいて、ペアリング情報を適切に導出することが可能となる。すなわち、鮮度の高いデータ（経路コスト）を用いることにより、精度の高いペアリング情報を導出することが可能となる。
【００８１】
次に、図２２を参照して、コントローラ３の動作（一実施形態に係る走行車制御方法を含む）の一例について説明する。
【００８２】
ステップＳ３１において、蓄積部３１は、上位コントローラから一以上の搬送要求を取得して蓄積する（蓄積ステップ）。このような搬送要求の蓄積及び取得は、例えば上述したような第１制御周期Ｔ１で繰り返し実行される。
【００８３】
ステップＳ３２〜Ｓ３５において、算出部３３は、蓄積された複数の搬送要求の各々と走行車２との組み合わせ毎の経路コストを算出する（算出ステップ）。まず、ステップＳ３２において、算出部３３は、蓄積された複数の搬送要求（例えば、図６に示される搬送要求１〜４）のうちから１つの搬送要求（例えば、搬送要求１）を選択する。ステップＳ３３において、算出部３３は、搬送要求１と制御対象エリア内に存在する複数の走行車２との各組み合わせについての経路コストを算出する。具体的には、算出部３３は、上述したダイクストラ法等の最短経路探索アルゴリズムを用いることにより、組み合わせ毎の最短経路とその経路コストとを算出する。ステップＳ３４において、算出部３３は、経路コストが閾値（上述した第１閾値又は第２閾値）以上である走行車２を搬送要求１の割り付け対象から除外する。これにより、図６に示される搬送要求１の表に示されるような処理結果が得られる。また、搬送要求１と各走行車２との組み合わせ毎の走行経路（最短経路）の情報も併せて得られる。ステップＳ３５において、算出部３３は、全ての搬送要求（ここでは、搬送要求１〜４）について、ステップＳ３３及びステップＳ３４の処理を完了したか否かを判定する。未実行の搬送要求が残っている場合（ステップＳ３５：ＮＯ）には、算出部３３は、ステップＳ３２に戻り、未実行の搬送要求のうちから１つの搬送要求を選択してステップＳ３３及びステップＳ３４の処理を実行する。一方、全ての搬送要求について処理が完了した場合（ステップＳ３５：ＹＥＳ）には、コントローラ３は、ステップＳ３６に進む。
【００８４】
ステップＳ３６において、導出部３４は、複数の搬送要求（搬送要求１〜４）の各々に１つの走行車２を対応付けたペアリング情報を導出する（導出ステップ）。例えば、導出部３４は、算出部３３の算出結果（例えば図６に示される処理結果）に対して上述した第１の例又は第２の例の処理を実行することにより、図７に示されるような最適ペアリング情報を導出する。
【００８５】
ステップＳ３７において、出力部３５は、導出部３４により導出されたペアリング情報に基づく指令情報を出力する（出力ステップ）。上述したように、出力部３５は、走行車２に対して直接指令情報を出力してもよいし、走行車２を直接制御するゾーンコントローラ等の下位コントローラに対して指令情報を出力してもよい。また、出力部３５は、最適ペアリング情報をディスプレイ、プリンタ等の出力装置３０５に出力することにより、オペレータに最適ペアリング情報を提示してもよい。
【００８６】
次に、本実施形態の作用効果について説明する。コントローラ３では、複数の搬送要求が一旦蓄積された後に、当該複数の搬送要求の各々に対して１つの走行車２を対応付けたペアリング情報が導出される。これにより、単一の搬送要求だけでなく複数の搬送要求間の相互の影響を考慮した割り付け（搬送要求と走行車２との対応付け）を行うことが可能となる。したがって、コントローラ３によれば、１つの搬送要求が発生する毎にいずれかの走行車２に当該搬送要求を割り付ける場合と比較して、無人走行車システム（走行車システム１）全体としてより効率的な走行車２の走行が可能となる。
【００８７】
また、コントローラ３は、マップ情報を記憶する記憶部３２と、算出部３３とを備えている。算出部３３は、蓄積部３１により蓄積された複数の搬送要求のうちの１つの搬送要求と複数の走行車２のうちの１つの走行車２との組み合わせ毎に、走行車２の現在位置と搬送要求の目的地（Ｆｒｏｍ地点）とマップ情報とに基づいて、走行車２の現在位置から目的地までの走行経路を決定すると共に走行経路に含まれるリンクの走行コストの和である経路コストを算出する。そして、導出部３４は、算出部３３によって組み合わせ毎に算出された経路コストに基づいて、ペアリング情報を導出する。これにより、導出部３４において、搬送要求と走行車２との組み合わせ毎に算出された経路コストを指標として、ペアリング情報を適切に導出することが可能となる。
【００８８】
また、導出部３４は、蓄積部３１により蓄積された複数の搬送要求と複数の走行車２との組み合わせにおける経路コストの総和が最小となるように、ペアリング情報を導出する。これにより、複数の搬送要求について、全体最適が図られた割り付けを実現することができる。
【００８９】
また、算出部３３は、搬送要求と走行車２との任意の組み合わせについて、走行車２の現在位置から目的地までの複数の候補経路のうち、候補経路に含まれるリンクの走行コストの和が最小となる候補経路（すなわち最短経路）を、走行経路として決定する。すなわち、算出部３３は、ある搬送要求とある走行車２との組み合わせについて、上述したダイクストラ法、Ａ＊等の最短経路探索アルゴリズムにより得られる最短経路を、当該搬送要求を当該走行車２に割り付けた場合の走行車２の走行経路として決定する。これにより、走行車２が最短経路で目的地まで移動するという合理的な条件の下で、ペアリング情報を適切に導出することができる。
【００９０】
また、算出部３３は、制御対象エリア（本実施形態では一例として、図１に示される複数のベイを含むエリア）内に存在する全ての走行車２を対象として、経路コストを算出する。この場合、制御対象エリア内に存在する一部の走行車２を対象とする場合と比較して、より最適なペアリング情報（例えば、経路コストの総和がより小さくなるペアリング情報）を導出できる可能性を高めることができる。
【００９１】
ただし、算出部３３は、制御対象エリア内に存在する一部の走行車２を対象として、経路コストを算出してもよい。例えば、算出部３３は、搬送要求の目的地が属する区画（ベイ）に存在する走行車２に対象を絞って経路コストを算出してもよい。このように経路コストの算出対象となる走行車２を一部の走行車２に限定することにより、算出部３３の処理量を低減し、プロセッサ、メモリ等のコンピュータ資源の節約及び処理の高速化を図ることができる。また、このように区画（ベイ）毎に独立した割り付け制御がされる場合、上述したコントローラ３は、区画毎に設けられてもよい。すなわち、コントローラ３は、区画毎に設けられたゾーンコントローラであってもよい。つまり、区画毎に設けられたゾーンコントローラが、それぞれ上述したコントローラ３として機能してもよい。具体的には、ある区画に設けられたゾーンコントローラは、Ｆｒｏｍ地点が当該区画内に含まれる複数の搬送要求を蓄積し、当該区画内に存在する走行車２を当該複数の搬送要求の各々の割り付け先の候補として、上述したコントローラ３の処理を実行してもよい。
【００９２】
また、導出部３４は、搬送要求と走行車２との任意の組み合わせについて、経路コストが第１閾値以上である走行車２を、搬送要求の割り付け対象から除外する。このように、ある搬送要求の実行に第１閾値以上の時間がかかる走行車２を当該搬送要求の割り付け対象から予め除外することにより、実行時間が比較的大きくなってしまう走行車２に対して、搬送要求が通常割付として割り付けられることを確実に防止することができる。
【００９３】
また、導出部３４は、第１の搬送要求が割り付けられた第１の走行車２に対して、第１の搬送要求の実行完了後に実行すべき予約指令として第２の搬送要求を割り付け可能であり、導出部３４は、第１の走行車２の現在位置から第１の搬送要求の実行を経て第２の搬送要求の目的地に到達するまでの走行経路の経路コストが第２閾値以上である場合、第１の走行車２を第２の搬送要求の割り付け対象から除外する。このように、ある搬送要求の実行に第２閾値以上の時間がかかる走行車２を当該搬送要求の割り付け対象（予約割付の対象）から予め除外することにより、実行時間が比較的大きくなってしまう走行車２に対して、搬送要求が予約割付として割り付けられることを確実に防止することができる。
【００９４】
また、本実施形態では、走行車２は、物品（例えばＦＯＵＰ）を搬送する無人搬送車である。走行要求は、目的地としての荷掴み位置（Ｆｒｏｍ地点）に配置された物品を荷掴みして所定の荷降ろし位置で荷降ろしする要求を示す搬送要求である。経路コストは、走行車２の現在位置から荷掴み位置までの走行経路に含まれるリンクの走行コストの和を含む。この場合、無人搬送車（走行車２）が搬送要求の荷掴み位置に到着するまでの時間に基づいて、無人搬送車に対する搬送要求の割り付けを適切に行うことができる。
【００９５】
また、第１の搬送要求が割り付けられた第１の走行車２の第２の搬送要求に関する経路コスト（すなわち、予約割付を行う場合の経路コスト）は、第１の走行車２の現在位置から第１の搬送要求の荷降ろし位置までの走行経路に含まれるリンクの走行コストの和と、第１の搬送要求の荷降ろし位置から第２の搬送要求の荷掴み位置までの走行経路に含まれるリンクの走行コストの和と、を含む。この場合、無人搬送車（第１の走行車２）が第１の搬送要求の実行を経て第２の搬送要求の荷掴み位置に到着するまでの時間に基づいて、無人搬送車に対する搬送要求（第２の搬送要求）の割り付けを適切に行うことができる。
【００９６】
また、走行車システム１は、コントローラ３と、搬送路４と、搬送路４に沿って走行可能な複数の走行車２と、を含む。上述したコントローラ３を含む走行車システム１によれば、上述した理由により、より効率的な走行車２の走行が可能となる。
【００９７】
また、一実施形態に係る走行車制御方法によれば、上述した蓄積ステップ、導出ステップ、及び出力ステップを含むことにより、上述したコントローラ３と同様の効果が奏される。
【００９８】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限定されるものではなく、その要旨を逸脱しない範囲で様々な変更が可能である。
【００９９】
上記実施形態では、図２１に示されるように、搬送要求の取得及び蓄積、経路コストの算出、並びにペアリング情報の導出の各処理が所定の制御周期（第１〜第３制御周期）で繰り返し実行されたが、これらの各処理は、周期的に実行されなくともよい。例えば、蓄積部３１は、上位コントローラから搬送要求を不定期に取得してもよい。また、経路コストの算出及びペアリング情報の導出は、所定数の搬送要求が蓄積されたことをトリガとして実行されてもよい。
【０１００】
また、算出部３３は、ある搬送要求と複数の走行車２との複数の組み合わせの各々の経路コストを算出する際に、以下のようにダイクストラ法を用いた２段階の処理を実行してもよい。すなわち、まず、算出部３３は、搬送要求のＦｒｏｍ地点を始点Ｓとした最短経路探索（逆引きルート探索）を開始する。そして、算出部３３は、逆引きルート探索によって走行車２が発見される毎に（すなわち、始点Ｓから走行車２までの最短経路が確定する毎に）、当該走行車２の現在位置を始点Ｓとすると共に搬送要求のＦｒｏｍ地点を終点Ｅとした最短経路探索（通常ルート探索）を実行する。例えば、算出部３３は、逆引きルート探索をメインスレッドにおいて実行し、走行車２が発見される毎に子スレッドを生成し、当該子スレッドにおいて当該走行車２についての通常ルート探索を実行する。これにより、算出部３３は、メインスレッドにおいて逆引きルート探索を実行しつつ、子スレッドにおいて走行車２毎の通常ルート探索を実行することができる。
【０１０１】
ここで、算出部３３は、メインスレッドにおいて、所定の打ち切り条件を満たした場合に、メインスレッドの処理を終了してもよい。所定の打ち切り条件は、例えば、始点Ｓ（搬送要求のＦｒｏｍ地点）から所定の閾値時間（例えば上述した第１閾値）内で到達可能な全てのノードについて探索が完了したこと、所定の閾値数以上の走行車２が発見されたこと等である。このような打ち切り条件を用いて逆引きルート探索を実行することにより、経路コストの算出対象（すなわち、子スレッドにおいて通常ルート探索が実行される対象）となる走行車２を絞ることができる。すなわち、搬送要求のＦｒｏｍ地点から一定以上遠い位置に存在する走行車２（搬送要求の割り付け対象から除外されるべき走行車２）についての経路コストを算出したり、必要数以上の走行車２についての経路コストを算出したりすることを回避することができる。つまり、無駄な経路コストの算出処理を防止できる。これにより、算出部３３の処理量を低減し、プロセッサ、メモリ等のコンピュータ資源の節約及び処理の高速化を図ることができる。なお、上述した逆引きルート探索及び通常ルート探索のいずれについても、ダイクストラ法以外の最短経路探索アルゴリズムが用いられてもよい。逆引きルート探索を実行するためには、終点Ｅを設定せず始点Ｓのみを設定した場合に実行可能な最短経路探索アルゴリズムが用いられればよい。通常ルート探索を実行するためには、始点Ｓ及び終点Ｅの両方を設定した場合に実行可能な最短経路探索アルゴリズムが用いられればよい。
【０１０２】
また、上記実施形態では、搬送要求と走行車２との組み合わせについての走行経路として、最短経路探索アルゴリズムによって得られた最短経路が用いられたが、搬送要求と走行車２との組み合わせについての走行経路は、必ずしも最短経路でなくてもよい。例えば、算出部３３は、ある組み合わせについて、予め設定された計算時間内で探索された複数の候補経路のうち最短となる経路を走行経路としてもよい。これによれば、求められる処理時間内で厳密な最短経路を求めることが困難な場合であっても、算出部３３の処理時間を短縮しつつ、なるべく最短経路に近い経路を走行経路として決定することが可能となる。
【０１０３】
また、導出部３４は、必ずしも最適ペアリング情報を導出しなくてもよい。例えば、導出部３４は、予め設定された計算時間内で探索された複数の組み合わせのうち経路コストの総和が最小となる組み合わせを、ペアリング情報として導出してもよい。これによれば、求められる処理時間内で最適ペアリング情報を求めることが困難な場合であっても、導出部３４の処理時間を短縮しつつ、なるべく最適ペアリング情報に近いペアリング情報を導出することが可能となる。
【０１０４】
また、上記実施形態では、走行車２によって搬送される物品（被搬送物）として、複数の半導体ウェハが収容されたＦＯＵＰを例示したが、物品はこれに限定されず、例えば、ガラスウェハ、レチクル等が収容されたその他の容器であってもよい。また、走行車システム１は、半導体製造工場に限定されず、その他の施設にも適用可能である。
【符号の説明】
【０１０５】
１…走行車システム、２…走行車、３…コントローラ（走行車制御装置）、４…搬送路、３１…蓄積部、３２…記憶部、３３…算出部、３４…導出部、３５…出力部。
【図１】
2020030723.tif 000003
【図２】
2020030723.tif 000004
【図３】
2020030723.tif 000005
【図４】
2020030723.tif 000006
【図５】
2020030723.tif 000007
【図６】
2020030723.tif 000008
【図７】
2020030723.tif 000009
【図８】
2020030723.tif 000010
【図９】
2020030723.tif 000011
【図１０】
2020030723.tif 000012
【図１１】
2020030723.tif 000013
【図１２】
2020030723.tif 000014
【図１３】
2020030723.tif 000015
【図１４】
2020030723.tif 000016
【図１５】
2020030723.tif 000017
【図１６】
2020030723.tif 000018
【図１７】
2020030723.tif 000019
【図１８】
2020030723.tif 000020
【図１９】
2020030723.tif 000021
【図２０】
2020030723.tif 000022
【図２１】
2020030723.tif 000023
【図２２】
2020030723.tif 000024