(57)【特許請求の範囲】
【請求項１】
ビル内任意階床において任意時刻に発生したホール呼びに対し、当該ホール呼びに応答させるエレベータカゴを割当てる群管理制御を実行するエレベータ群管理システムにおいて、
エレベータホールでの既発生の複数個の割当演算対象ホール呼びに対して、少なくともホール呼びの発生階床、発生方向、ホール呼びの種類、発生時刻のいずれか一つに応じて、前記既発生の複数個の割当演算対象ホール呼びをエレベータカゴに割当てる群管理制御を実行する当該ホール呼びの割当実行順序としての計算優先順位を設定する計算優先順位設定手段と、
前記ホール呼びの計算優先順位に応じてホール呼びのカゴ仮割当を行い、このカゴ仮割当がなされた場合のエレベータ状態である複数個のカゴ仮割当結果を保持し、保持している複数のカゴ仮割当結果の中から所定の評価に応じて１つのカゴ割当結果を選定し、選定されたカゴ仮割当結果に未仮割当且つ前記計算優先順位に応じたホール呼びのカゴ仮割当を行う、という一連の動作を探索的手順で繰り返し、複数のホール呼びに対するカゴ仮割当結果を求めることができるカゴ割当演算処理手段と
を具備することを特徴とするエレベータ群管理システム。
【請求項２】
請求項１に記載のエレベータ群管理システムにおいて、
前記カゴ割当演算処理手段において保持した複数個のカゴ仮割当結果の中から、前記所定の評価に応じてカゴ仮割当結果を選定し、選定されたカゴ仮割当結果において前記既発生の複数個の割当演算対象ホール呼びのカゴ仮割当がなされている場合には、前記カゴ仮割当結果に応じてカゴへの割当指令を前記既発生の複数個の割当演算対象ホール呼びについて実行することを特徴とするエレベータ群管理システム。
【請求項３】
請求項１又は請求項２に記載のエレベータ群管理システムにおいて、前記カゴ割当演算処理手段に割当演算制限時間を付加することを特徴とするエレベータ群管理システム。
【請求項４】
請求項３に記載のエレベータ群管理システムにおいて、前記割当演算制限時間を可変時間とすることを特徴とするエレベータ群管理システム。
【請求項５】
請求項１から請求項４のいずれか１項に記載のエレベータ群管理システムにおいて、前記カゴ割当演算処理手段の探索的手段として、Ａ探索アルゴリズムを用いることを特徴とするエレベータ群管理システム。
【請求項６】
ビル内任意階床において任意時刻に発生したホール呼びに対し、当該ホール呼びに応答させるエレベータカゴを割当てる群管理制御を実行するエレベータ群管理方法において、
エレベータホールでの既発生の複数個の割当演算対象ホール呼びに対して、少なくともホール呼びの発生階床、発生方向、ホール呼びの種類、発生時刻のいずれか一つに応じて、前記既発生の複数個の割当演算対象ホール呼びをエレベータカゴに割当てる群管理制御を実行する当該ホール呼びの割当実行順序としての計算優先順位を設定し、
前記ホール呼びの計算優先順位に応じてホール呼びのカゴ仮割当を行い、このカゴ仮割当がなされた場合のエレベータ状態である複数個のカゴ仮割当結果を保持し、保持している複数のカゴ仮割当結果の中から所定の評価に応じて１つのカゴ割当結果を選定し、選定されたカゴ仮割当結果に未仮割当且つ前記計算優先順位に応じたホール呼びのカゴ仮割当を行う、という一連の動作を探索的手順で繰り返し、複数のホール呼びに対するカゴ仮割当結果を求める
ことを特徴とするエレベータ群管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エレベータ群管理のための技術に関する。
【背景技術】
【０００２】
エレベータ群管理は、現在発生している呼びの状況とカゴの現在位置、乗車人数等の情報を加味し、新規に発生したホール呼びに適切なカゴを割り当てることを目的とする。従来、予め用意した単純な割当カゴ決定ロジックの可変パラメータを、状況に応じて最も良いものに切り替える方法が主流であった。可変パラメータを選択する基準として、交通需要などの状況を示す特徴量と可変パラメータの組合せに対し予想されるパフォーマンスを予めニューラルネットモデルで学習しておき、選択の基準とする方式が、特許文献１で提案されている。また、予想されるパフォーマンスをシミュレータで見積もる方式が、特許文献２などで提案されている。
【０００３】
しかし、呼びをカゴに対して適切に割当てるためには、本来は次の全ての要因を考慮する必要がある。  
１．現在の割当が、今まで発生し、未だサービスされていない呼び（未応答呼び）に与える影響  
２．現在の割当が将来の呼びに与える影響  
３．将来の呼び発生が今までに割当した全ての未応答呼びに与える影響  
上記の要因において、１の要因は扱い易いが、他の要因については、特許文献３のような一部の提案を除き、従来方式ではほとんど扱われていない。これは、従来の群管理方式と異なり、将来の仮想的な呼びを含む複数の呼びを同時に考慮する必要が生じるため、複数呼びに対しすべての割当ての組合せの中から準最適な解を見つけ出す、一種の組合せ最適化演算を行わなくてはならないため、方法が複雑になるためである。引用文献３ではＧＡ（遺伝的アルゴリズム）を利用して組合せ最適化演算を行うことが提案されている。
【特許文献１】特願平１−４７１３６号公報
【特許文献２】特願平１１−１２５９７８号公報
【特許文献３】特開平５−３１９７０７号公報
【特許文献４】特開平５−３１９７０６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
エレベータの群管理制御方法として利用するためには、所定の制限時間内に、複数呼びに対し組合せ最適化演算を行う必要がある。しかし、引用文献３で提案されているＧＡ（遺伝的アルゴリズム）や引用文献４で提案されているＳＡ（シミュレーテッドアニーリング）を利用した方式などでは、解として利用可能なまで最適化演算が収束するのに時間を要するため、群管理に必要とされるリアルタイム性を実現することが極めて困難である。
【０００５】
複数呼びに対し組合せ最適化演算を行いつつ群管理に必要とされるリアルタイム性を実現するためには、可能な演算制限時間に応じて、本当に必要な呼びの割当についてはその時点でのベストな割当を得られるようにする必要がある。
【０００６】
本発明は、割当すべきホール呼びが複数個あるような状況において、複数個のホール呼び割当を行うための技術を提供することを目的としている。
【課題を解決するための手段】
【０００７】
本発明の局面に係るエレベータ群管理システムは、ビル内任意階床において任意時刻に発生したホール呼びに対し、当該ホール呼びに応答させるエレベータカゴを割当てる群管理制御を実行するエレベータ群管理システムにおいて、エレベータホールでの既発生の複数個の割当演算対象ホール呼びに対して、ホール呼びの種類に応じて、前記既発生複数個の割当演算対象ホール呼びをエレベータカゴに割当てる群管理制御を実行する当該ホール呼びの割当実行順序としての計算優先順位を設定する手段と、前記計算優先順位に応じて前記ホール呼びのカゴ仮割当計算を行う手段と、を具備すること特徴とする。
【０００８】
本発明は、カゴ割当を行うべき複数個の割当対象ホール呼びに対して、ある１つのホール呼びをあるカゴの割当てた場合にどうなるか？といった仮割当（カゴ仮割当パターン）を行い、これを１つのホール呼びに対して複数種類（例えばカゴ台数分のカゴ仮割当パターン）作成する。作成後、現時点で最も評価値の良いカゴ仮割当パターンを選択し、次の割当対象ホール呼びをこのカゴ仮割当パターンに追加した場合の新たなカゴ仮割当パターンを得る。これを制限時間に達するまで反復するという探索的手順を用いることにより、与えられた演算制限時間内で評価値の高いカゴ仮割当パターンを作成する。この作成されたカゴ仮割当パターンで、割当てるべき複数ホール呼びがそれぞれどのカゴに割当てられたかを調べ、割当対象の複数ホール呼びのカゴ割当を決定する。
【０００９】
ここで割当対象ホール呼びが複数個ある場合には、割当処理待ちホール呼びキュー内に格納されているホール呼びに計算優先順序を設定し、設定された割当計算順序に応じて順次カゴ割当パターンを作成していく。加えて、仮割当の決定していない割当対象ホール呼びの評価には見積もり値を利用するＡ探索と呼ばれる探索方法を利用することにより、制限時間の中でなるべく適切なカゴ割当パターンを作成する。
【００１０】
仮に、割当処理待ちホール呼びキューに格納されている全てのホール呼びのカゴ割当が終わらない場合には、残りのホール呼びについて改めて組み合わせ最適化演算によるカゴ割当演算処理を行うことも考えられる。あるいは、制限時間を延長することで、より多くのキュー内のホール呼びのカゴ割当の決定や、キューに格納されているホール呼び全てのカゴ割当を決定してしまうことも可能である。
【００１１】
以上のように、本発明の一局面に係るエレベータ群管理システムは、ビル内任意階床において、任意時刻に発生したホール呼びに対し、エレベータカゴを割当てる群管理制御を実行するエレベータ群管理システムにおいて、既発生未割当ホール呼びが複数個あるような場合、前記複数個のホール呼びに対してホール呼びの種類に応じた組み合わせ計算順序を設定し、設定した計算順序に応じて組み合わせ最適化計算処理によるカゴ割当処理を実行することで、前記既発生未割当ホール呼びに対するカゴ割当演算処理を複数個纏めて行うことを特徴としている。
【発明の効果】
【００１２】
本発明によれば、割当すべきホール呼びが複数個あるような状況において、複数個のホール呼び割当を同時に行うことができる。
【発明を実施するための最良の形態】
【００１３】
図面を参照して本発明の実施の形態を説明する。  
図１は本発明の一実施形態に係るエレベータ群管理システムの概略構成を示すブロック図である。  
エレベータ群管理部０はエレベータの群管理制御を実行する部分である。エレベータ群管理部０は少なくとも２台以上のエレベータカゴ１１、・・・、１Ｎを有するエレベータの群管理制御を実行する。すなわちエレベータ群管理部０は、ビル内の任意階床において任意時刻に発生したホール呼びに対し、本発明の実施形態に係るエレベータ群管理制御方法を実装したカゴ割当演算処理部０１を備え、カゴ割当演算処理部０１の計算結果に応じて群管理制御を行う。エレベータ群管理部０は他に、各フロアのオール呼びボタン２１、・・・、２Ｍの情報を検知・収集するホール呼び情報収集部０３を備え、ホール呼び情報収集部０３は、既発生未割当ホール呼び情報をバッファリングするためのホール呼び割当待ちキューを有している。エレベータ群管理部０は、その他に、各カゴ内に設置された乗客の行き先指定入力するためのカゴ呼びボタン１1２、・・・、１Ｎ２の情報を収集するカゴ呼び情報収集部０５と、既に割当済みであるがカゴが未応答であるホール呼びへのカゴ割当情報を記憶するホール呼び割当情報記憶部０２を有する。また、各カゴの運行を制御するために、各エレベータカゴ１１、・・・、１Ｎに対してカゴ制御部１1１、・・・、１Ｎ１が設けられている。このカゴ制御部１1１、・・・、１Ｎ１は、運行制御の他にカゴ速度、カゴ位置等のカゴ情報の収集も行う。なお、カゴ割当演算処理部０１は、探索演算処理部０１１と、計算優先順位決定部０１２と、探索演算データ記憶部０１３と、評価モデル部０１４とを具備している。
【００１４】
上記の各構成要素は、コンピュータソフトウェア、またはコンピュータソフトウェアとハードウェアの組み合わせにより実現することができる。コンピュータとエレベータの実機との間は、制御に必要な電気信号を送受信するための制御盤や通信インターフェースを介して接続される。
【００１５】
上記のように構成されたエレベータ群管理システムの概略動作を説明する。  
ビル内滞在中のエレベータ乗車希望の乗客はホール呼びボタン２１、・・・、２Ｍを押下し、エレベータ群管理部０へエレベータカゴ１１、・・・、１Ｎの配車要求を行う。なお、本明細書において、「配車」とは、ホール呼びに応じてエレベータカゴを配することを意味する。このエレベータカゴの配車要求は新規ホール呼びの発生という形でホール呼び情報収集部０３を介して、カゴ割当演算処理部０１へ送信される。この際、新規ホール呼びはホール呼び情報収集部０３内のホール呼び割当待ちキューにバッファリングされる。カゴ割当演算処理部０１は計算可能となるタイミング（例えば計算中に受信した場合には、計算終了後）で、ホール呼び情報収集部０３からホール呼び割当待ちキュー内のホール呼び情報を受信し、ホール呼び割当情報記憶部０２とカゴ情報収集部０４とカゴ呼び情報収集部０５の各構成要素が保持している情報を入力として、当該発生ホール呼びに対するカゴ配車決定のための演算処理を実行する。そして、新規ホール呼びに対して配車するカゴを決定し、カゴ制御部１1１、・・・、１Ｎ１へ指示する。カゴ制御部１1１、・・・、１Ｎ１は、カゴ割当演算処理部０１の指示に従い、カゴに割当られているホール呼びとカゴで発生したカゴ呼び、及び現在のカゴ位置情報やシステムで定義されたカゴ状態（停止中や移動中、ドア開中など）情報からカゴの巡回順序が一意に決定されカゴの運行を行っていく。
【００１６】
ホール呼びの割当情報やカゴ呼びの発生情報は、ホール呼び割当情報記憶部０２により、その発生階、呼び方向、発生時刻等の情報が一時的に記憶され、未応答呼びが処理されるとホール呼び割当情報記憶部０２内の処理された呼びに関する情報は削除される。ただし、群管理処理系の違いによっては、例えばホール呼びに対して本来割当られているカゴ以外がカゴ呼び発生等により先に到着してしまい階床待ち乗客が乗車してしまうような所謂カゴ呼び先着が発生することもある。そのような場合には、その呼び情報については削除しないような場合も考えられる。
【００１７】
以下、カゴ割当演算処理部０１の動作について詳しく説明する。  
先に述べたように、ホール呼びボタンの押下によるホール呼びが発生すると、ホール呼び情報収集部０３内のホール呼び割当待ちキューに割当対象のホール呼び情報が格納される。カゴ割当演算処理部０１は、計算可能となるタイミングでホール呼び情報収集部０３からホール呼び割当待ちキューに格納されている割当対象ホール呼び情報を全て受信する。このとき、ホール呼び割当待ちキュー内に格納されていた割当対象ホール呼びはカゴ割当演算処理部０１の構成要素である計算優先順位決定部０１２で受信される。計算優先順位決定部０１２は、ホール呼び割当待ちキュー内に格納されていたホール呼び情報が複数個あった場合には、そのホール呼びのデータ属性に応じてカゴ割当演算処理部０１内で割当演算していくホール呼びの演算順序を決定する。
【００１８】
ホール呼び割当待ちキューに複数個のホール呼び情報が格納されるような状況について説明する。  
エレベータ群管理システムにおいて、システムがホール呼び割当演算ルーチンでの割当演算中である場合やＯＳ割り込みにより割当計算用のＣＰＵが他の処理を実行中である場合などに発生した新しいホール呼びは割当計算待ちとなる。たとえば、混雑時などホール呼びの発生が多発するような状況がこれにあたる。このような混雑時にはホール呼びのカゴ割当演算処理が追いつかず割当計算処理待ちのホール呼びは、ホール呼び割当待ちキューに相当するバッファにバッファリングされる。また、既発生割当済みのホール呼びであっても、割当後にカゴがホール呼びの応答に時間を要している場合には、時間を要しているホール呼び発生階でカゴの到着を待っている乗客の待ち時間を抑制するために、ホール呼びの再割当計算処理を行うことがある。この場合においても、割当計算処理を実行するために、再割当対象のホール呼びはホール呼び割当待ちキューにバッファリングされる。
【００１９】
このように、既発生の割当対象ホール呼びが複数個バッファリングされるような状況が発生する。
【００２０】
次に、計算優先順位決定部０１２の演算順序決定方法について説明する。  
例えば、エレベータ群管理システムでホール呼びのデータ属性として、「発生時刻」「発生階床」「発生方向」「通常呼び」「ＶＩＰ呼び」「障害者呼び」「地下階行き呼び」「送信回数」（カゴ割当演算処理部への送信回数）といったデータ属性が定義されているものとする。ここで、ホール呼び割当待ちキュー内に、図２に示すようなホール呼びデータが、発生時刻順に、［０］、［１］、・・・、［４］といったように格納されていたとする。この場合において、計算優先順位決定部０１２内における計算優先順位が、図３に示すようなフローで定義されているものとする。図３に示すように、計算優先順位は、次のように決定される。  
（１）  ソート１：送信回数＞障害者呼び＞ＶＩＰ呼び＞通常呼び＞地下階行き呼びの優先順位順でソート。  
（２）  ソート２：ソート１で同一の呼び種類がある場合に、発生時刻順でソート。  
（３）  ソート３：ソート２で同一の発生時刻がある場合に、地上階＞地下階の優先順位順でソート。ただし、地上階の場合は、低階層の優先順位を高くし、地下階の場合は１階に近い階の優先順位を高くする。  
（４）ソート４：ソート３で同一の発生階床がある場合に、ＵＰ＞ＤＯＷＮの優先順位順でソート。  
を行い、この計算によって得られた計算優先順位を出力する。このようにして得られた計算処理順序を図４に示す。図４に示すように、図３に示すように定義されたアルゴリズムに従って、計算の順序が変更されている。  
上記のように、計算優先順位決定部０１２では、ホール呼び情報収集部から受信した割当対象ホール呼びの計算順序を決定する。そして、この計算順序に従って、カゴ割当演算処理部０１でのカゴ割り当て演算が行われる。なお、この計算優先順位決定部０１２における優先順位の順位付けルールは変更可能であって、例えば、「出勤時」「通常時」「昼食時」「退社時」などといった、交通流が変化する時間帯に応じて順位付けルールを変更してもよいし、優先順位付けルールについても、ホール呼びデータ属性同士の組み合わせを用いて、例えば優先順位が最も高いものとして「障害者呼び且つ１Ｆ発生ＵＰホール呼び」といったような優先順位付けルールの構成も可能である。
【００２１】
計算優先順位決定部０１２により決定された優先順位を元に、カゴ割当演算処理部０１でカゴ割当計算が行われるが、その計算方法について説明する。  
カゴ割当演算処理部０１では、計算優先順に並んだホール呼びデータのそれぞれに対するカゴの仮割当パターンの組み合わせの中から準最適解を見つけ出す組み合わせ最適化演算を実施する。そして、最も評価の良い仮割当パターンの割当対象ホール呼びの仮割当状況を実際の割当結果としてカゴ制御部１1１、・・・、１Ｎ１へ指示する。ここで、「仮割当パターン」とは、割当対象ホール呼びそれぞれについて、ホール呼びの仮割当を行った場合の状態を表すものである。
【００２２】
カゴ割当演算処理部０１を構成する探索演算処理部０１１の探索処理は、図示しない演算制御部によって制御されるが、本実施形態では、この演算制御部は演算処理時間のみを制御するものとし、探索演算処理部０１１は、演算制御部で制御される探索制限時間に達するまで反復探索を行う。
【００２３】
探索演算処理部０１１は、計算優先順位決定部により決定された探索演算処理部での演算順序に従って探索演算を行い、次のように、カゴ１１、・・・、１Ｎの仮割当パターンを作成していく。まず、前記演算順序先頭の割当対象ホール呼びについて、カゴ１１、・・・、１Ｎの仮割当パターンを複数種類（少なくとも１種類）作成する。カゴ１１、・・・、１Ｎの仮割当パターンの作成後、作成したカゴ仮割当パターンの中で最も評価値の高いカゴ仮割当パターンを選択する。選択したカゴ仮割当パターンにおいて、カゴ仮割当パターンに現時点で追加されている割当対象ホール呼びの次に優先順位の高いホール呼びを新たにこのカゴ仮割当パターンに追加して、新たなカゴ仮割当パターンを得る。上記のような処理を制限時間に達するまで反復する探索的手順を用いて、与えられた制限時間内で複数個のカゴ仮割当パターンを作成していき、作成されたカゴ仮割当パターンの中で最も良い評価値のカゴ仮割当パターンにおいてカゴ１１、・・・、１Ｎに仮割当されているホール呼びの結果をカゴ割当演算処理部０１の割当演算結果としカゴ制御部１1１、・・・、１Ｎ１へ送信する。  
ここで、作成されるカゴ仮割当パターンは探索演算データ記憶部０１３に記憶される。
【００２４】
また、評価モデル部０１４は、探索演算処理部０１１の探索処理の過程で利用される。評価モデル部０１４は、簡易的なシミュレーション演算により以下で説明するモデルデータの更新演算処理を行う。更に、評価モデル部０１４は、更新結果を元にカゴ仮割当パターンの評価を行う。
【００２５】
まず、主要データ構造である「割当対象ホール呼びリスト」、「モデルデータ」、「探索用リスト」、「保存用リスト」について各々説明する。  
「割当対象ホール呼びリスト」は、カゴへの割当対象となるホール呼び情報を記憶するためのリストである。つまり、先に述べた割当優先順にソートしたホール呼びデータもこの割当対象ホール呼びリストへ格納される。この割当対象ホール呼びリストの単位データは、その属性データとしてホール呼びの「発生階」「方向情報」「発生時刻情報」「呼びタイプ」「送信回数」と、そのホール呼びから発生することが予測される派生カゴ呼び情報（行き先階情報）を含む。このホール呼び情報とそれに派生するカゴ呼び情報を一纏めにして、この単位データの呼称を「呼びセット」とする。尚、１つのホール呼びとセットとなる派生カゴ呼びについては、複数個ある場合もある。割当対象ホール呼びリストのデータ構造を図５に示す。
【００２６】
上記の実施形態の説明では説明しないが、優先順位付けした既発生未割当のホール呼びデータ群に仮想呼び（実際に発生していないが、将来発生しうるホール呼びを仮想的に想定した場合のホール呼びデータ）データ群を発生時刻順に付け加えたものを利用した場合も考えられる。
【００２７】
図５の割当対象ホール呼びリストは、優先順位付けされた図４の結果に、呼びセットＩＤと派生カゴ呼び情報を付加したものである。呼びセットＩＤは割当優先順位、派生カゴ呼び情報はホール呼びから予想される行き先（かご呼び）データである。この派生カゴ呼び情報は、呼びセットＩＤについて１つまたは複数個あっても構わない。
【００２８】
次にモデルデータの説明を行う。  
本実施形態においては、評価モデル部０１４において、動特性を無視した簡易的なシミュレーションにより、それぞれのカゴが巡回で割当対象ホール呼びリストに格納されているホール呼び呼びの発生階に到着する時刻を高速に見積もり、到着時刻とホール呼び呼び発生時刻の差を元に遅れ時間（すなわち未応答時間）を計算して、遅れ時間を元に割当の良さを評価する。この場合に、評価値として計算するものは、ホール呼び階床到着から目的階床到着までの時間（つまりサービス時間）など色々な形態が考えられる。本実施形態では評価値として遅れ時間を用いて説明していく。  
「モデルデータ」は、評価モデル部０１４のシミュレーションの途中結果を、カゴの巡回スケジュール情報として保存するデータである。モデルデータは、ホール呼び割当リスト内の全てのホール呼びがそれぞれどのカゴへ割当されるかのカゴ割当パターン情報と、各階床の巡回時刻に関する情報を少なくとも含んでいる。図６にカゴ１つ分のモデルデータの一例を示す。図６では１階床間の移動に要する時間を５、ドア開閉に要する時間を５と設定している。  
図６の呼び方向で、Ｕは上向きの呼びの発生、Ｄは下向きの呼びの発生、Ｎはカゴ呼び
が発生しかつ全ての乗客が掃けてフリーの状態であることを示す。
【００２９】
探索演算処理部０１１により呼びセットのカゴ割当が仮決めされると、既発生割当済み未応答呼びの割当とそれに伴う巡回順序を崩さぬように、巡回スケジュールにおいて新しい呼びが処理可能な箇所の候補が検索される。挿入可能箇所は、物理的な制約及び、乗客に不快感を与えないために最低限守らなくてはならないカゴの運行規則の制約を満足する箇所、例えば乗客がカゴ乗車中である場合には、カゴ運行上効率が良い（他階床待ち乗客への待ち時間等の縮小が望めるといった）としても、カゴ乗車中の乗客の目的階方向へ進行中のカゴを反転させないといったカゴ運行規則を満足する箇所であり、複数箇所が候補となる場合もある。ホール呼びに関しては、例えば、  
（１）呼び方向と、直前の停止時のカゴ方向が一致、かつ、  
（２）（直前の停止階−呼び発生階）×（直後の停止階−呼び発生階）＜０、かつ  
（３）直前の停止階の出発時刻＋直前の停止階から呼び発生階への移動時間≧新しい呼びの発生時刻  
のような挿入可能条件などを満足する箇所が挿入可能箇所となる。階床間の移動時間は、加減速度などの動特性まで考慮した階床間の移動時間を予めテーブルに記憶しておき、これを参照することで見積もる。  
派生するカゴ呼びについては、ホール呼びの処理する箇所が決まると、ホール呼びの処理箇所以降で、かつ、カゴの移動方向が反転する箇所の手前で処理しなければならないため、一意に決まる。これは、乗客を乗せたままの状態でカゴの移動方向が反転する動作は、エレベータでは原則として禁止されているためである。
【００３０】
モデルデータの巡回スケジュールにおいて新しい呼びセットが処理可能な箇所の候補が仮決めされると、新しい呼びセットを加えた状態にモデルデータが更新される。すなわち、各停止階で処理すべき呼びセットを追加し、呼びセットのホール呼びもしくはカゴ呼びを処理するために新たな停止階を設けた場合は、新しい停止階より後に巡回する予定の停止階への到着時刻と出発時刻をそれぞれ更新する。時刻更新処理の流れを以下に示す。
【００３１】
（１）新停止階の時刻設定  
到着時刻は、「直前の停止階の出発時刻＋呼び発生階への移動時間」で求められ、出発時刻は、「到着時刻＋ドア開閉時間」で求められる。  
（２）新停止階以降の既存の停止階の到着時刻の時刻修正  
到着時刻は、「直前の停止階の出発時刻＋更新対象の停止階への移動時間」で求められる。  
（３）「到着時刻＋ドア開閉時間＞出発時刻」の場合は（４）に進む。そうでない場合は終了する。  
（４）出発時刻を到着時刻＋ドア開閉時間とする。  
（５）次の停止階に時間更新処理対象を移し、（２）に戻る。  
図７は、上記の処理の概略を示した図である。図７の（１）の挿入可能箇所のサーチに示すように、１階において上方向のホール呼びがあり、４階において下方向のホール呼びがあると、各ホール呼びに対して挿入可能箇所を検索する。次に、図７の（２）に示すように、挿入処理は、例えば、２階から４階へ上昇するカゴに対して３階の上呼びが挿入されたものとすれば、３階の上呼び時刻が挿入されて４階への到達予定時刻が更新される。なお、探索途中で複数種類のカゴ割当パターンに応じた複数のモデルデータは、探索用リスト及び保存用リストで一時的に記憶する。
【００３２】
図８及び図９を参照して、探索演算処理部０１１で行う探索処理の概要について説明する。図８は探索処理全体の概略フローを示すフローチャートであり、図９は反復探索演算処理部分の処理を抽出したフローチャートである。  
探索演算処理部０１１においては、エレベータ群管理におけるリアルタイム性を実現するために制限時間を設けておき、割当対象ホール呼びリスト内の全てのホール呼びのカゴ割当が決定していなくても途中で探索を打ち切る。すなわち、当対象となるホール呼びが計算優先順位決定部０１２により決定されたホール呼び割当の優先順位の高いホール呼びから順次仮割当が決定される。従って、可能な演算制限時間に応じて、その時点でのベストな割当結果を得られる可能性が高くなる。以下、各ステップ毎に動作の流れを説明する。
【００３３】
計算優先順位決定部０１２により探索演算処理順にソートされた既発生未割当ホール呼びを割当対象ホール呼びリストへセットする（ステップＡ１）。  
各カゴの現在位置（移動中の場合には減速開始し、停止できる階床位置）と、各カゴの既発生割当済み未応答ホール呼びと、未処理カゴ呼びとに基づき、カゴの現在のカゴ巡回スケジュールを決定し、このスケジュールをモデルデータにセットすることにより、モデルデータを初期化する（ステップＡ２）。ここで、カゴ巡回スケジュールは、一意に決定される。なお、後述する未応答ホール呼びから予想される派生カゴ呼び（ステップＡ４）も、モデルデータにセットする場合もあり得る。この場合においても、カゴ巡回スケジュールは一意に決定される。そして、探索用リスト先頭に初期化したモデルデータをセットする（ステップＡ３）。
【００３４】
カゴ仮割当パターンを探索演算処理部０１１による反復演算により決定する（ステップＡ４）。ここで、図９の探索演算のフローチャートを参照して、反復演算処理による割当対象ホール呼びリスト内のホール呼びのカゴ仮割当パターンの決定方法を説明する。
【００３５】
探索用リスト先頭から、次に調べる対象となるモデルデータを取り出す（ステップＢ１）。ここで、探索用リストが空であれば、探索演算を終了して（ステップＡ５）に進み、そうでなければ、ステップＢ３へ進む（ステップＢ２）。
【００３６】
探索用リスト先頭のモデルデータ（以下、「更新前モデルデータ」と称する）に割当対象ホール呼びリスト内のセット呼び全てを追加処理済みであるかどうか調べる（ステップＢ３）。ステップＢ３においてセット呼びが追加済みであれば、探索用リスト先頭のモデルデータを保存用リストに移し、ステップＢ１の処理に戻る（ステップＢ４）。ステップＢ３において追加処理が終了していない場合は、ステップＢ５へ処理を進める。
【００３７】
セット呼びを割当てた場合のカゴ割当状況に相当するモデルデータを作成するために、割当対象ホール呼びリストから、更新前モデルデータで未処理でありかつ最も計算優先順位の高いホール呼び（ここではセット呼びＮとする）のデータを抽出する（ステップＢ５）。そして、各々カゴにセット呼びＮを割当したと仮定した状況に相当するカゴ台数分の複数種類のモデルデータをそれぞれ作成する。具体的には、以下のとおりである。
【００３８】
更新前モデルデータ（割当対象のカゴ巡回スケジュール）でセット呼びＮの属性データであるホール呼びの挿入可能箇所を検索する（ステップＢ６）。  
セット呼びＮデータの属性データであるの派生カゴ呼びを挿入する箇所を検索する（ステップＢ７）。そして、更新前モデルデータのコピーを生成する（ステップＢ８）。次に、コピーにセット呼びＮを挿入し、コピーを更新演算する（ステップＢ９）。以下、更新演算後のコピーを「更新後モデルデータ」と称する。  
更新後モデルデータの評価値を計算する（ステップ１０）。更新後モデルデータを新たな状況に相当するモデルデータとして探索用リストに追加する（ステップＢ１１）。探索用リストを評価値順にソートする（ステップＢ１２）。
【００３９】
ここで、セット呼びＮが全ての挿入可能箇所について処理が終了すれば（ステップＢ１３）、ステップＢ１５に移行し、そうでなければ次の挿入可能箇所に処理を移行し、ステップＢ７の処理へ戻る（ステップＢ１４）。  
割当可能な全てのカゴについて処理が終了すれば（ステップＢ１５）、ステップＢ１７に進む。そうでなければ次のカゴに処理を移行し、ステップＢ６の処理へ戻る（ステップＢ１６）。  
探索の制限時間に達していなければ（ステップＢ１７）、ステップＢ１の処理へ戻り、制限時間に達していれば、ステップＡ５へ処理を移行する。
【００４０】
以上が探索演算処理部０１１の詳細なフローである。ステップＢ１７において、制限時間に達すると、保存用リストを評価値順にソートする（ステップＡ５）。そして、保存用リストが空かどうかを判定し（ステップＡ６）、空ならばステップＡ７へ移行し、保存用リストの先頭のモデルデータを取得する（ステップＡ７）。ステップＡ６において、保存用リストが空でなければステップＡ８へ移行し、探索用リストの先頭のモデルデータを取得する（ステップＡ８）。なお、ステップＡ６、Ａ７、Ａ８の処理の代わりに、保存用リストの先頭のモデルデータの評価値と探索用リストの先頭のモデルデータの評価値を比較し、評価値の良いモデルデータの方を取得しても良い。
【００４１】
取得したモデルデータのカゴ割当内容に従い、割当対象ホール呼びデータのカゴ割当結果を出力する（ステップＡ９）。そして、割当がなされたホール呼びをホール呼び割当待ちキューから削除するし、探索演算処理部０１１の処理を終了する（ステップＡ１０）。
【００４２】
上記の説明において、評価値を、既発生割当済み未応答ホール呼びと割当対象ホール呼びリストに格納される既発生未割当ホール呼びとを仮割当した場合の未応答時間（呼び発生時刻から当該呼びに対するカゴ到着時刻までの経過時間）の和としている。なお、未応答時間の代わりに、「最大未応答時間」「呼び配車時間（ホール呼びから派生したカゴ呼びを処理するまでの時間）」などを用いることもできる。
【００４３】
ただし評価値のソートにおいて、そのままモデルデータ同士の評価値を比較する処理を行うと、追加したホール呼びの数が少ない方が必ず評価値が良くなるため、いわゆる幅優先探索となる。制限時間内で少しでも多くのホール呼びを考慮するため、追加したホール呼びの数が異なるモデルデータ同士で評価値を比較できるように、各々の呼びセット１つあたりについて評価値がどれだけ増加するかの評価値平均値を記憶しておき、これを探索ノードの評価値の見積もり値として調整に用いる。平均評価値が実際の評価値増分に近い予想値であるほど、効率的に探索が進む。このように、見積もり値を探索ノードの優先度付けに利用する方法は「Ａ探索」と呼ばれており、人工知能分野などで良く利用されている。
【００４４】
Ａ探索の場合、評価値は例えば以下のように定義される。  
呼び当りの評価：Ｐ＝到着予定時刻−呼び発生時刻−基準待ち時間  
モデルデータ全体の評価：ΣＰ＋未処理の呼びセット数×評価見積り値
図１０は探索時の基本反復処理を示す図である。  
探索途中で出現したモデルデータを全て保存し、全ての組合せについて探索を行うことは現実には不可能である。このため、図１０で説明しているように、探索用リストのサイズを溢れた際は、評価値の悪い（ペナルティの大きい）カゴ割当パターン（モデルデータ）はその後に最適なカゴ割当パターンになる可能性は小さいと判断し、このようなモデルデータを破棄することを反復する。
【００４５】
上記のように、本実施形態によれば、既発生未割当ホール呼びが複数個ある場合には、これらを定義した優先順位決定方法に従って、計算優先順位付けを行う。そして、割当対象となる計算優先順位付けされた複数個のホール呼びを優先順位に従い、優先順位の高いホール呼びについてカゴ仮割当パターンを複数種類作成し、最も評価値の良いカゴ仮割当を選択する。さらに、各カゴ仮割当パターンに対し、仮割当されておらず、且つ、優先順位の高い割当対象ホール呼びを１つ追加して新たなカゴ仮割当パターンを複数種類作成し、新たな複数のカゴ仮割当パターンの中から最も評価値の良いカゴ仮割当パターンを次に調べる対象とするカゴ仮割当パターンとして選別する。
【００４６】
以上の処理を制限時間に達するまで反復するという探索的手順を用いることにより、与えられた演算制限時間の中で評価値の良いカゴ仮割当パターンを作成する。割当対象となるホール呼びが仮割当され、さらに優先順位に基づきが順次決定される手順により、優先度の高い呼びから先に順次仮割当が決定され、可能な演算制限時間に応じて、その時点でのベストな割当結果を得られる可能性が高くなるため、かつリアルタイム性のあるエレベータ群管理を実現することが可能となり、且つ、  
・割当処理待ちホール呼びキュー内に複数の既発生未割当ホール呼びがある場合、１つずつカゴ割当演算処理を行うため、キューの最後尾のホール呼びのカゴ割当演算処理が行われるのは数秒後となり、割当結果をホール待ち乗客へ報知するホールランタンの点灯タイミングが大幅に遅れる。また、その間にもホール呼びは発生し、キューに格納されていき、  
・複数個のホール呼びが既発生しているにもかかわらず、ホール呼びを１つずつ割り当てるため、キューから取り出した先頭ホール呼びを割当てる時点での現在停止予定階床への影響度（待ち時間の増減など）はある程度考慮して最適なカゴ割当解を導出できたとしても、キューの最後尾のホール呼びを割り当てる時点では、先頭ホール呼びの割当結果が必ずしも最適なカゴ割当解とは限らない、  
といった問題を解決することができる。
【００４７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００４８】
【図１】本発明の一実施形態に係るエレベータ群管理システムの概略構成を示すブロック図。
【図２】ホール呼びのデータ例を示す図。
【図３】計算優先順位を決定するための流れの一例を示す図。
【図４】図３に示す処理によって得られた計算優先順序を示す図。
【図５】割当対象ホール呼びリストのデータ構造を示す図。
【図６】カゴ１つ分のモデルデータの一例を示す図。
【図７】本発明の一実施形態に係るエレベータ群管理システムにおける挿入処理の概要を示す図。
【図８】探索処理全体の概略フローを示すフローチャート。
【図９】反復探索演算処理部分の処理を抽出したフローチャート。
【図１０】探索時の基本反復処理を示す図。
【符号の説明】
【００４９】
０…エレベータ群管理部
０１…カゴ割当演算処理部
０２…ホール呼び割当情報記憶部
０３…情報収集部
０４…カゴ情報収集部
０５…情報収集部
０１１…探索演算処理部
０１２…計算優先順位決定部
０１３…探索演算データ記憶部
０１４…評価モデル部
０１５…演算制御部
０１５…探索制御部
１１、・・・、１Ｎ…カゴ
２１、・・・、２Ｍ…ホール呼びボタン
１1１、・・・、１Ｎ１…カゴ制御部
１1２、・・・、１Ｎ２…カゴ呼びボタン
【図１】
0004690799.tif 000002
【図２】
0004690799.tif 000003
【図３】
0004690799.tif 000004
【図４】
0004690799.tif 000005
【図５】
0004690799.tif 000006
【図６】
0004690799.tif 000007
【図７】
0004690799.tif 000008
【図８】
0004690799.tif 000009
【図９】
0004690799.tif 000010
【図１０】
0004690799.tif 000011