(57)【特許請求の範囲】
【請求項１】
複数の階を有する建物におけるエレベータシステムを制御する方法であって、
空のかごの数を変更するイベントの検出に応じて前記エレベータシステムにおける空のかごの数を計数すること、
各階において乗客の到着率を確定すること、
前記複数の階を複数のゾーンに割り当てることであって、各ゾーンの階の数は、前記到着率に従いかつ次に到着する乗客の予測される待ち時間を最小化するように確定されること、
前記次に到着する乗客の前記予測された待ち時間が最小化するように、前記空のかごを前記複数のゾーンに待機させること
を含み、
前記次に到着する乗客の前記予測された待ち時間Ｑ（ｘ）は、
【数１】
0004602086.tif 000018
であり、ここで、ｐｆは、前記到着率から確定されるように前記次に到着する乗客が階ｆに到着する確率であり、ｘｉは、ｉ番目の空のかごの位置であり、Ｔ（ｘｉ，ｆ）は、前記ｉ番目の空のかごが前記次に到着する乗客に対してサービスするために必要な時間であり、
前記予測された待ち時間Ｑ（ｘ）は、
【数２】
0004602086.tif 000019
に従って最小化される
ことを特徴とする複数の階を有する建物におけるエレベータシステムを制御する方法。
【請求項２】
前記計数すること、前記確定すること、前記割り当てること、および前記待機させることは、前記計数すること、前記確定すること、前記割り当てること、および前記空のかごを待機させることが進行中であっても、前記空のかごの数が変化するとすぐに実行される
請求項１に記載の方法。
【請求項３】
前記空のかごは、前記複数のゾーンの中間階に待機する
請求項１に記載の方法。
【請求項４】
特定のゾーンは、最高到着率を有する階から構成され、複数の空のかごは、前記特定のゾーンに待機する
請求項１に記載の方法。
【請求項５】
各階において乗客の行先率を確定すること、
前記到着率および行先率を比較することにより、アップピーク交通パターンとダウンピーク交通パターンとを確定すること
をさらに含む
請求項１に記載の方法。
【請求項６】
前記ゾーンの数は、前記アップピーク交通パターンに対する前記空のかごの数に等しい
請求項５に記載の方法。
【請求項７】
前記交通パターンはダウンピークであり、Ｎ人の次に到着する乗客に対する前記予測された待ち時間は、
【数３】
0004602086.tif 000020
の限界値
【数４】
0004602086.tif 000021
であり、ここで、Ｎ＞１であり、ｓｉは、ｉ番目の次の乗客が到着する時の前記エレベータシステムの状態であり、Ｑ（ｓｓ）は、該ｉ番目の次に到着する乗客の前記予測された待ち時間であり、期待値
【数５】
0004602086.tif 000022
は、前記複数の階において前記Ｎ人の次に到着する乗客の分布に関して取得される
請求項５に記載の方法。
【請求項８】
前記空のかごの数はＣであり、Ｎ＝Ｃである
請求項７に記載の方法。
【請求項９】
前記期待値
【数６】
0004602086.tif 000023
は、
【数７】
0004602086.tif 000024
であり、ここで、期待値
【数８】
0004602086.tif 000025
は、前記Ｎ人の次に到着する乗客に関する
請求項８に記載の方法。
【請求項１０】
前記乗客の前記到着は、
【数９】
0004602086.tif 000026
に従って平均λで時間ｔにわたり指数関数的に分布される
請求項１に記載の方法。
【請求項１１】
前記到着する乗客の前記分布に関する前記予測された待ち時間は、
【数１０】
0004602086.tif 000027
であり、ここで、ｗ（ｔ）は、時刻ｔにおいて到着する特定の乗客に対する、該特定の乗客が到着する前記階において空のかごが待機する前の前記待ち時間である
請求項１０に記載の方法。
【請求項１２】
ｗ（ｔ）は、時間間隔０＜ｔ＜Ｔから線形に低減し、
【数１１】
0004602086.tif 000028
であり、ｗ０は、前記イベントが検出された時に前記次の乗客が到着した場合の前記待ち時間であり、ｗＴは、前記空のかごが前記ゾーンに待機している場合に前記次の乗客が到着した場合の前記待ち時間である
請求項１１に記載の方法。
【請求項１３】
前記間隔０＜ｔ＜Ｔにおける前記予測された待ち時間は、
【数１２】
0004602086.tif 000029
である
請求項１２に記載の方法。
【請求項１４】
複数の階を有する建物におけるエレベータシステムのためのコントローラであって、
空のかごの数を変更するイベントの検出に応じて前記エレベータシステムにおける空のかごの数を計数する手段と、
各階において乗客の到着率を確定する手段と、
前記複数の階を複数のゾーンに割り当て、各ゾーンの階の数は、前記到着率に従いかつ次に到着する乗客の予測される待ち時間を最小化するように確定される手段と、
前記次に到着する乗客の前記予測された待ち時間が最小化するように、前記空のかごを前記複数のゾーンに待機させる手段と
を具備し、
前記次に到着する乗客の前記予測された待ち時間Ｑ（ｘ）は、
【数１３】
0004602086.tif 000030
であり、ここで、ｐｆは、前記到着率から確定されるように前記次に到着する乗客が階ｆに到着する確率であり、ｘｉは、ｉ番目の空のかごの位置であり、Ｔ（ｘｉ，ｆ）は、前記ｉ番目の空のかごが前記次に到着する乗客に対してサービスするために必要な時間であり、
前記予測された待ち時間Ｑ（ｘ）は、
【数１４】
0004602086.tif 000031
に従って最小化される
ことを特徴とする複数の階を有する建物におけるエレベータシステムのためのコントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはエレベータ群制御に関し、特に、群エレベータスケジューリングを最適化することと乗客の待ち時間を最小化することとに関する。
【背景技術】
【０００２】
群エレベータスケジューリングは、非常に実際的な意味で産業制御および運用研究における既知の問題である。Bao他著、「Elevator dispatchers for down-peak traffic」、Technical Report、University of Massachusetts、Department of Electrical and Computer Engineering、Amherst、Massachusetts、1994を参照のこと。複数のエレベータシャフトがある建物の階のうちの１つでホール呼びが発生すると、エレベータ群制御の基本的な目標は、ホール呼びにサービスするためにいずれのかごを使用すべきかを決定することである。
【０００３】
エレベータシステムによっては、コントローラが、ホール呼びの合図がなされるとすぐにその呼びにかごを割り当て、即時にチャイムを鳴らすことによってホール呼びを合図した乗客を対応するシャフトに向かわせる。一方、割り当てられたかごがホール呼びの階に到着するとチャイムを鳴らすシステムもある。
【０００４】
複数のエレベータを備えた建物のエレベータの乗客の交通パターンは、１日のいくつかの期間中に大幅に変化する。オフィスビルでは、朝、乗客のほとんどはロビーから上位階に移動し、一方、１日の終りでは、ほとんどの乗客は上位の階を離れ主にロビーに移動する。高層住宅では、当然ながらパターンはその逆である。これらの交通パターンは、アップピーク（up-peak）とダウンピーク（down-peak）として知られている。
【０００５】
アップピークおよびダウンピークは、エレベータ群に対するスケジューリングプロセスに対し並外れた要求を課す。それは、乗客の到着率が高く、交通パターンが非一様であるためである。同時に、これらのパターンは、標準的な確率構造を有する可能性があり、それを、かごスケジューリングプロセスによって活用することができる。
【０００６】
たとえば、エレベータ群スケジューリングプロセスにおける通常の最適化基準、すなわち、将来到着する乗客の待ち時間を最小化する方法で将来のホール呼びを予期するように、空のかごを階に待機させることができる。将来のホール呼びに関してかごを有利に待機させるという明確な目的で空のかごを移動させる概念は、最適な群エレベータスケジューリングにおいて既知である。しかしながら、これをいかに最適に行うかは、未決問題のままである。
【０００７】
ゾーニングスケジューリングプロセスは、一定の連続した階のセットから発生するすべてのホール呼びにサービスするように空のかごを割り当てる。ホール呼びに先立ってゾーンの中間に空のかごを移動させることは、スケジューリングプロセスに対して明らかに有利である。別の可能性は、かごが必要とされる可能性が最も高い階にかごを配車するために、交通パターンの統計的特性を使用する、というものである。
【０００８】
アップピークパターンの場合、いかなる空のかごも、一般に、到着する次の乗客の一団のためにロビーに待機させる。この洞察は、Pepyne他により、「Optimal dispatching control for elevator systems during uppeak traffic」、IEEE transactions on control systems technology、5(6):629-643、1997において述べられている純粋なアップピークパターンに対して使用されてきた。しかしながら、乗客がロビーにのみ到着し上方にのみ移動する純粋なアップピークトラフィックは、現実の設定ではめったに起こらない。
【０００９】
空のかごに対するいくつかの待機戦略が可能である。最も単純な戦略は、一度に単一のかごのみを、先に割り当てられたホール呼びのすべてにサービスした後に空となったらすぐ、待機させる。別の戦略は、高い到着強度を有する特定の階、たとえばアップピーク移動におけるロビーにおいて、所定数の空のかごを維持しようと試み、そこで空のかごの数が必要な最低数を下回った場合にのみその階に空のかごを待機させる。しかしながら、これはまた、最適には及ばない戦略であることが知られている。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
アップピークとダウンピークとの両方の交通パターンに対するエレベータ群制御において空のエレベータかごの待機を最適化することが望まれる。
【課題を解決するための手段】
【００１１】
本発明は、新たに到着する乗客を予測しかかる乗客に迅速にサービスしかかる乗客の待ち時間を最小化するように、エレベータ群制御において空のかごの最適な待機を提供する。本発明は、ダウンピークとアップピークとの両方の交通パターンに対する解決法を提供する。空のかごの待機を乗客の到着率と一致させることにより、特にダウンピーク交通に対し、８０％までの待ち時間の節約を達成することができる。それよりはるかに困難なアップピーク交通パターンの場合では、本発明は、エレベータシステムを、比較的少ない集約された状態を有するマルコフ決定過程（Markov decision process）（ＭＤＰ）としてモデル化し、そのＭＤＰモデルに対する動的プログラミングにより最適な待機戦略を確定する。
【００１２】
より詳細には、方法は、エレベータシステムにおける空のかごの分布（分配、割当：distribution）を制御する。まず、エレベータシステムの空のかごの数を、この数が変化した時はいつでも計数する。同時に、階の各々における乗客の到着／行先率を確定する。これらの率を用いて、アップピークおよびダウンピーク交通パターンを識別する。そして、建物の階をゾーンに割り当てる。各ゾーンにおける階の数を、到着率に従って確定し、その後、次に到着する乗客の予測される待ち時間を最小化するように、空のかごをゾーンに待機させる。
【発明の効果】
【００１３】
本発明は、異なる乗客交通のパターン下でエレベータかごを最適に待機させる方法およびシステムを提供する。ダウンピーク交通の場合、かごを、次の乗客のみの予測された待ち時間を最小化するように、建物の階にわたって等しく分布させる。これにより、低および中間到着率に対する予測された待ち時間が即時に節約されることになる。かごを、さまざまな階における乗客の到着分布に一致するように待機させる。
【００１４】
最初の乗客のみの予測された待ち時間を最小化することは、主な問題が、階の数と乗客の全到着率とが与えられると、ロビーにいくつの空のかごを維持すべきかである、アップピーク交通の場合には十分でない。アップピーク交通の間のエレベータ群の最適な待機の問題に対する提案された解決法は、候補待機位置に対応するわずかな数の状態を有するマルコフ決定過程としてのシステムの表現と、より長いが依然として制限された時間間隔における将来の乗客の予測された待ち時間を最小化する動的プログラミングプロセスとに基づく。
【００１５】
この解決法は、到着率とロビーに待機させる空のかごの数との間の依存性を捕え、低および中間率に対する非常にすぐれた性能をもたらす。
【発明を実施するための最良の形態】
【００１６】
［概論］
図１に示すように、本発明は、新たに到着する乗客を予測しサービスしかかる乗客の待ち時間を最小化にするように、エレベータ群制御において空のかごを最適に待機させるシステムおよび方法１００を提供する。現在空のかごをすべて待機させることは、すでに待機させている空のかごを異なる階に移動させてもよいことを意味し、空のかごは、移動しない場合、その現在の階で待機し続ける。本発明は、以下の２つのイベント１１１のうちの１つのために空のかごの数が変化するとすぐに、現在空であるすべてのかごを待機させる１００。
【００１７】
第１のイベント１１１では、かごに割り当てられたすべての乗客がサービスされた時、そのかごは空となる。このイベントにより、空のかごの数が１だけ増加する。第２のイベント１１１では、空のかごを、新たなホール呼びにサービスするように割り当てる。このイベントにより、空のかごの数が１だけ減少する。本発明によれば、空のかごの待機は、割り当てられた待機先にまだ到着していない空のかごに対して待機が進行中である場合であっても、これら２つのイベントのうちの一方が検出されるといつでも開始される。換言すると、待機プロセス１００は、イベント１１１が検出されるとすぐに再開する。
【００１８】
本発明は、特定のピーク交通パターン、すなわち、ロビーから上位階へのアップピーク交通パターンと上位階からロビーまでのダウンピーク交通パターンとの両方に対し、空のかごをどこで待機させるべきかに対する最適な戦略を決定する。
【００１９】
本発明は、アップピーク、ダウンピークおよび階間交通の任意の混合を処理する。アップピーク交通の場合を、特別な場合とみなす。それは、特別な最適化を提供しエレベータ制御システムに対する性能係数として経済的重要性を有するためである。
【００２０】
問題を扱い易くするために、アップピーク交通パターンに対する行先の確率が一様である、すなわち、乗客は等しい確率で上位階の各々まで移動するものと想定する。しかしながら、ダウンピーク交通の場合、さまざまな階の到着の確率が一様である、すなわち、ロビーへの新たなホール呼びが上位階の各々において発生する確率が同程度である、とは想定しない。それは、ダウンピーク交通パターン中、乗客のすべてが上位階で一様に発生するわけではなく、この想定は限定的すぎるためである。
【００２１】
ダウンピーク交通パターンに対する非一様な到着確率の場合に対し完全な解決法を提供する。さらに、これらの２つのパターンを、純粋なアップピークまたはダウンピーク交通に限定しない。乗客のほとんどはロビーから上位階に移動しているが、実際のエレベータシステムにおける場合のように、まだ相当量の階間交通も考慮する。
【００２２】
定義、待機ポリシおよびそれらの実行
Ｎｃ個のエレベータかごが備えられたＦ階の建物をモデル化する。ホール呼びは、特定の階において、サービスされる新たに到着した乗客により合図される。一般には、ホール呼びはまた、移動の所望の方向、すなわち上方または下方を通知する。かご呼びは、人が乗っているかごの乗客によって合図される。かご呼びは、その乗客が移動したい特定の階を通知する。任意の特定の時点で、０≦Ｃ≦Ｎｃであるように、Ｎｃ個のうちのＣ個のかごが空であり、すなわち、それらにはいかなるホール呼びもかご呼びも割り当てられていない。
【００２３】
ホール呼びが合図されると、スケジューリングプロセスは、かごをホール呼びに割り当て、その割り当ては変更されない。その結果、空のかごの数Ｃは、新たなホール呼びが空のかごに割り当てられた場合、減少し、あるいは、新たなホール呼びがすでに人が乗っているかごに割り当てられた場合、同じままである。空のかごＣの数が変化する、すなわち、イベント１１１が検出されると、残りの空のかごに対する新たな待機位置が、後述するように確定され、これらの待機位置に空のかごが配車される。同様に、かごが、割り当てられたすべてのホールおよびかご呼びのサービスを完了すると、空のかごＣの数が増加し、空のかごの新たな待機位置が確定される。
【００２４】
待機位置が常に階のうちの１つと一致する、すなわち、かごは決して階の間で待機しないものと想定する。この想定下では、待機ポリシは、空のかごの数ＣとＣ個の待機位置のベクトルｘ（１≦ｘｉ≦Ｆであるように、ｘｉ＝１，・・・，Ｃ）との間のマッピングである。このため、あり得るマッピングの数は、ＦＣである。これらのマッピングポリシのうちのいくつかは、対称なまでに同一であるため、ｉ＞ｊである場合ｘｉ≧ｘｊであるように、マッピングに対して標準的な表現を使用する。かかる対称性を考慮した後でさえ、あり得るマッピングの数は非常に大きいことが明らかである。
【００２５】
待機決定が行われる瞬間、空のかごは、ある階ですでに待機していてもよく、あるいは、先の待機決定の実行により階間で移動してもよい。ｙｉ＝１，・・・，Ｃにより、各空のかごｉがその瞬間にある階を示す。かごｉが移動していない場合、ｙｉは単に、その空のかごが待機している階である。かごｉが移動している場合、ｙｉは、それがその現移動の方向において停止することができる最初の階である。かごが階間でその方向を反転させることは、可能な場合、かかる可能性が待機方法の応答性および効率を向上させ得るとしても、できないと想定する。
【００２６】
空のかごの位置ｙ＝［ｙ１，ｙ２，・・・，ｙＣ］が既知であり、所望の待機位置ｘが確定された後、待機計画は、エレベータ群制御システムにより案出され実行されなければならない。この計画の目的は、空のかごを可能な限り迅速にそれらの現在位置ｙから所望の待機階ｘまで移動させる、ということである。このため、システムは、かごのいずれが待機位置の各々に行くべきかを判断しなければならない。Ｃ個の待機位置とＣ個のかごとの間にＯ（Ｃ！）個のあり得る一致があるため、最適な計画を見つけることは、今までのところ従来技術において取り組まれていない、非常に困難な問題である。
【００２７】
しかしながら、本発明は、待機決定を短時間で効率的に実行することができるようにする発見的方法を提供する。発明された発見的方法は、かごの垂直方向の順序付けを保存する。
【００２８】
この発見的方法を、空の移動しているかごの位置ｙ＝［ｙ１，ｙ２，・・・，ｙＣ］を昇順にソートし、同時にかごの序数ｋ［１，２，・・・，Ｃ］をｙｉのソートに従ってソートすることにより、実施することができる。ソートする前に、ｉ＝１，・・・，Ｃに対しｋｉ＝ｉであるように、序数の配列を初期化する。たとえば、最初にｙ＝［５，３，８，１］でありｋ＝［１，２，３，４］である場合、ソート後、ｙ＝［１，３，５，８］およびｋ＝［４，２，１，３］が得られる。
【００２９】
ポリシｘがすでに標準形であるため、各ｉ＝１，・・・，Ｃに対し、かごｋｉを位置ｘｉに配車することができる。上記例を続けると、ポリシがｘ＝［２，４，６，８］である場合、システムは、かご４を２階へ、かご５を４階へ、かご１を６階へ、かご３を８階に配車する。かご１、２および４が１階しか移動せず、かご３は静止したままであるため、この待機決定は非常に効率的である。
【００３０】
ここで、特定のピーク交通パターンと、階の数Ｆと、かごの数ＮＣと、エレベータかごの速度および加速度と、が与えられた場合の最適な待機位置ｘを見つけるという問題に戻る。
【００３１】
対象となる２つの場合、すなわちダウンピークおよびアップピーク交通における本発明の概略的な戦略は、まず、乗客の流れが空になったかごの最終位置にいかに影響を与えるかを分析し、その後、空のかごの不均一な配置からもたらされる非効率を識別し、最後に、システムの新たなホール呼びに対する応答性が向上するように空のかごをいかに待機させるべきかを判断する、というものである。
【００３２】
図１に示すように、本方法１００は、イベント１１１を検出すること１１０に応じて開始することから実行する。エレベータシステムのその時点での空のかごの数をカウントする１２０。また、各階における乗客の現到着／行先率１３１を確定する１３０。カメラ等のセンサを使用することを含む、交通パターンを確定する任意の数の技法を使用することができる。
【００３３】
率１３１は交通パターンを示すため、それら率を比較する。たとえば、ロビーにおける高到着率は、アップピーク交通パターンを示し、ロビーへの高行先率は、ダウンピーク交通を示す。現パターンにより、空のかごを待機させるために後述する２つの待機ポリシのうちのいずれを使用すべきかが確定する。
【００３４】
到着／行先率１３１と空のかご１２１の数とに基づき、建物のＦ個の階を、ゾーンのセット１４１に割り当て１４０、各ゾーンの階の数を、到着率１３１に従って将来到着する（次の）乗客の予測される待ち時間を最小化するように確定する。一般に、割り当てられるゾーンにおける階は、物理的に隣接している。最後に、将来到着する（次の）乗客の予測される待ち時間が最小化されるように、ゾーンのセット１４１にわたりＣ個の空のかご１２１を待機させまたは再待機させる。
【００３５】
ここで、確定するステップおよび待機させるステップの詳細について、まずダウンピークパターンに対し、次いでアップピーク交通パターンに対し、より詳細に説明する。
【００３６】
ダウンピーク交通パターン中の待機
ダウンピーク交通パターン中、到着する乗客のほとんどの行先はロビーである。その結果、かごが空になると、それは通常ロビーに位置している。空のかごがロビーにあり続ける場合、それは、新たな呼びが発生する可能性が高い階、すなわち上位階にない可能性が高い。空のかごがある位置と空のかごが最も必要とされる位置との間のこの不一致を修正するために、かごが空になるとすぐに、空のかごをロビーから移動させ上位階で待機させる。
【００３７】
これを行うことができる２つのあり得る方法がある。第１の方法は、一度に１つだけの空のかごを、それが空になるとすぐに移動させることである。第２の方法は、空になったばかりのものを含む空のかごのすべてを再度待機させる。先に待機したかごを移動させてもさせなくてもよい。この手法は、到着する乗客の分布に関しかごのより一様な配置をもたらすため、ここでは第２の方法に対する解決法を提供する。さらに、常にすべての空のかごを移動させることは非常に費用がかかると考えられるため、本解決法を、第１の方法に変更することも可能である。
【００３８】
ここでは、すべての到着している乗客の予測される待ち時間を最小化しようと試みるため、最適な解決法は、無限に長い時間間隔で新たなホール呼びの予測された待ち時間を最小化しなければならず、空のかごの状態のみでなく人が乗っているかごの状態にも基づかなければならない。このシナリオに対する最適な解決法を得るためには、非実際的な計算量が必要である。それは、将来新たなホール呼びが発生する時および位置と、それらの将来の呼びがすべてのかごの将来の位置に対していかなる影響を与えるかと、は非常に不確実であるためである。
【００３９】
ダウンピーク交通の場合の問題を扱い易くするために、すぐ次の将来のホール呼び（次の乗客）のみの予測された待ち時間を最小化する。しかしながら、この手法は、アップピーク交通に対しては適当でなく、したがって、後に拡張する。さらに、ここでは、最初の新たなホール呼びが、人が乗っているかごのうちの１つではなく空のかごのうちの１つによってサービスされるものと想定する。この想定を、スケジューリングプロセスが一般に、人が乗っているかごを使用するのではなく空のかごにより新たなホール呼びにサービスする場合、低および中間到着率に対して正当化する。この想定により、残りの空のかごをいかに待機させるかを判断する場合に、すでに人が乗っているかごの状態を無視することができる。
【００４０】
最後に、空のかごの所望の待機位置が獲得された後にのみ新たな呼びが発生するものと想定する。この想定はまた、低および中間到着率の下で正当化される。この場合、空のかごを待機させる時間は、乗客の到着する間の時間間隔に対してごくわずかである。これらの想定に基づき、次のように、次に到着する乗客の予測される待ち時間を空のかごｘの関数として定義することができる。
【００４１】
【数１】
0004602086.tif 000002
【００４２】
ここで、ｐｆは、到着率から確定される、次の乗客が階ｆに到着する確率であり、ｘｉは、ｉ番目の空のエレベータかごの位置であり、Ｔ（ｘｉ，ｆ）は、エレベータかごの一定の物理性能特性、たとえば、加速度、最大速度、最小停止距離等を知った上で、ｉ番目の空のかごが、階ｆにおいて次に到着する乗客にサービスするためにかかる時間である。概して、空のかごが、ホール呼びが発生した階と正確に同じ階で待機している場合であっても、時間Ｔ（ｘｉ，ｆ）≠０である。空のかごのドアのドアがすでに開放されている場合にのみ、待ち時間は０である。
【００４３】
ほとんどの場合、空のかごのドアを閉鎖したままにすることは有利である。これには２つの理由がある。第１に、空のかごは、待機している階における呼びのみでなく近くの階における呼びにも応答する場合がある。空のかごがＦ個の階にサービスしなければならない場合、その空のかごが待機している階から次のホール呼びが合図される確率は、１／Ｆである。第２に、一般に、ドアを閉鎖している時に乗り込んでいる乗客に対して安全性を提供する必要があるため、ドアを開放する時間ｔＯは、ドアを閉鎖する時間ｔＣよりはるかに高速である。ドアが開放している場合、ホール呼びが空のかごと同じ階である場合にドアを開放する時間ｔＯが節約されるが、その確率は低く１／Ｆである。しかしながら、ホール呼びが、かごが待機している階ではない場合、ドアを閉鎖しなければならず、高確率（（１−Ｆ）／Ｆ）で時間ｔＣが無駄になる。ほとんどの場合、ｔＯ／Ｆ＜＜ｔＣ（Ｆ−１）Ｆであるため、空のかごを待機させた後にドアを閉鎖したままにすることは有利であり、時間Ｔ（ｆ，ｆ）≠０である、と理解する。
【００４４】
ここで、Ｑ（ｘ）をさらに最小化するために、空のかごを正確な階にのみではなく隣接する階の対の間にも待機させることが有利であるか否かという問題を考える。これは、待機位置ｘｉ，１，・・・，Ｃを連続変数であると考えることと等価である。
【００４５】
ここでのＱ（ｘ）の定義と選択された最適化基準とに戻ると、Ｑ（ｘ）を最小化する最適な待機ポリシｘ＊は、
【００４６】
【数２】
0004602086.tif 000003
【００４７】
である。
【００４８】
上述したように、あり得るすべての待機位置ｘの数は非常に多く、Ｑ（ｘ）の網羅的な計算は時間がかかる。しかしながら、直観により、最適なポリシは、将来到着する（次の）乗客の分布に関して可能な限り一様であるように空のかごを待機させる、ということが分かる。ｐｆを、階ｆ、ｆ＝１，・・・，Ｆ、
【００４９】
【数３】
0004602086.tif 000004
【００５０】
に対する到着確率とし、ｐｆ＝１とする。この確率に関するかごの均一な分布は、Ｃ個の空のかごを、次のホール呼び（将来到着する乗客）にサービスするそれぞれの確率が（１／Ｃ）に等しいように配置する。
【００５１】
これを達成する１つの近似的な方法は、Ｆ個の階をＣ個のゾーンのセットに割り当て１４０、各ゾーンがＣ個の空のかごのうちの１つによってサービスされるように空のかごをゾーンに待機させる１５０というものである。
【００５２】
【数４】
0004602086.tif 000005
【００５３】
であるように、累積的な到着および行先確率ｐｆ、ｆ＝１，・・・，Ｆのアレイが与えられると、この待機ポリシを、図２に擬似コードを示す固定の待機ポリシ手続きによって確定することができる。
【００５４】
この解決法は、各ゾーンに対し次の乗客に対してサービスする予測された時間が同じである場合の最小化基準に関して最適である。しかしながら、実際には、この時間はゾーンが広いほど長く、そのため、これらのゾーンが１／Ｃより低い確率で乗客の到着をカバーするように相対的に広いゾーンを低減する方向に、補正が必要である。この補正は、エレベータかごの動きの正確な方程式に依存するため、分析的に取得することは困難である。
【００５５】
しかしながら、階が、上述した固定（stationary）ポリシ手続きによって等しい確率のＣ個のゾーンに割り当てられる１４０場合、ゾーンにわたる空のかごの真に最適な待機を見つけるために比較的効率的なプロセスを採用することができる。このプロセスによって確定される待機ポリシを、ｘ（ｏ）で示す。ｘ（ｏ）が真の最適な待機ポリシｘ＊に近接し、さらにＱ（ｘ）がこの近接の凸であるという想定に基づき、ｘ（ｏ）からｘ（ｏ）を最も急峻に低減する方向にわずかに進むことができ、それにより、わずかなステップでｘ＊に達成することができる。離散した数の待機ポリシに対してＱ（ｘ）が定義されるため、強欲な探索（greedy search）戦略で十分である。
【００５６】
まず、ｋ：＝０と設定し、現ポリシｘ（ｋ）のすぐ近傍をすべて生成する。これらは、制約１≦ｘｉ≦Ｆ（ｉ＝１，・・・，Ｃ）を条件に｜ｘｉ−ｘｉ（ｋ）｜≦１（ｉ＝１，・・・，Ｃ）であるようなポリシｘ’である。Ｑ（ｘ（ｋ＋１））がすべてのＱ（ｘ’）の中の最小値であるとし、ｘ（ｋ＋１）は、この最小値が得られるポリシであるとする。Ｑ（ｋ＋１）＝Ｑ（ｋ）である場合、最適なポリシ、すなわちｘ＊＝ｘ（ｋ）が見つかっており、そうでない場合、ｋは１だけ増分し、プロセスは収束するまで繰り返される。
【００５７】
待機している空のかごが将来到着する乗客の分布に一致するように積極的に空のかごを待機させる利益を説明するために、ダウンピーク交通の実験を行った。そこでは、交通の８０％が上位階で発生し行先がロビーであり、１０％がロビーで発生し行先が上位階であり、残りの１０％が上位階間のみの交通であった。
【００５８】
上位階での新たな乗客の到着率は一様、すなわち、ｐｆ＝０．９/（Ｆ−１）であった。この条件下では、Ｃ個の空のかごに対する最適な待機ポリシは、空のかごを各ゾーンの中央に待機させ、階をＣ個のゾーンに均一に割り当てる、というものである。待機位置を、０≦Ｃ≦ＮＣの範囲である、あり得る数の空のかごの各々に対して事前に確定し、上述したように待機ポリシを実行した。
【００５９】
本発明による積極的な待機を、いかなる待機も実行せず、空のかごが単に最後の乗客が運ばれた階に残されている場合と比較した。両方の場合で、その内容をすべて本明細書に援用する、２００２年６月３日にBrand他によって出願された米国特許出願第１０／１６１，３０４号「Method and System for Dynamic Programming of Elevators for Optimal Group Elevator Control」に述べられているように、動的プログラミングに基づくスケジューリングプロセスを使用した。その結果から、ゾーンにわたって均一に分布されるように空のかごを積極的に待機させることが、低到着率で非常に有益であり、時に８０％以上待ち時間が節約されることが分かった。
【００６０】
アップピーク交通パターン中の待機
乗客の到着のパターンに対しエレベータ待機位置のパターンを一致させることに基づく待機解決法は、ダウンピーク交通に対してはうまくいくが、アップピーク交通には十分でない。この理由は、到着率が非常に不均一な分布であるためである。乗客の大多数はロビーに到着し、待ち時間のほとんどはかかる乗客による。このため、このタイプの交通パターンではロビーでの待ち時間を低減することが主に重要である。しかしながら、かかるロビー乗客のみに対して空のかごを待機させることは、それほど十分ではない。すべての空のかごがロビーに即時送られる場合、他の階はカバーされず、上位階に到着した乗客の待ち時間が、予測される待ち時間全体の優位を占め始める。たとえば、そこで乗客が１分間待つことは、６人の乗客が各々ロビーで１０秒間待つことと等価である。
【００６１】
Ｃ個の空のかごがある場合、或る割合の空のかごをロビーに送らなければならず、一方残りの空のかごを上位階に待機させなければならず、再びそこでの到着率に対して均一に分布させなければならない。そのため、問題は、この分布をいかに確定するかということになる。
【００６２】
１つの解決法は、常に、ロビーに一定の数、たとえば２個のかごを提供し、上位階に残りの空のかごを待機させる。しかしながら、この解決法は、実施が容易であるが、最適ではない。ロビーに必要な空のかごの実際の数は、新たな乗客の到着率と階の数とによって決まるためである。ロビーにおける到着率が比較的低い場合、非常にわずかな空のかごをロビーに待機させればよい。
【００６３】
たとえば、到着率が１時間につき１０人の乗客のみである場合、すなわち、予測される到着の間の間隔が６分である場合、ロビーに待機している単一の空のかごで十分である。それは、かごが乗客が乗った状態でロビーから離れるとすぐに、次に到着する乗客の予測される待ち時間がそれほど長くないように、別の空のかごをロビーに送ることができるためである。このように到着率が低い場合、建物をより密にカバーしそのため上位階に到着する乗客の予測された待ち時間を低減するために、１つを除くすべての空のかごを上位階で待機させることができる。
【００６４】
しかしながら、到着率が上昇すると、新たに到着した乗客に対してサービスするために新たなかごがロビーに時間通りに到着する可能性がますます低くなる。たとえば、ロビーにおける到着率が１時間につき１０００人の乗客である、すなわち、ロビーにおける到着の間の予測される間隔が３．６秒であるとする。ロビーに空のかごが１つしか待機しておらず、それが割り当てられた乗客を運ぶために離れると、別の空のかごが、たとえ迅速に配車される場合であっても、次の乗客が到着する前にロビーに到達する可能性は非常に低い。このように到着率が高い場合、ロビーに複数のかごを待機させる方がよい。
【００６５】
ロビーに待機させるかごの最適な数を確定することはまた、階の数によっても決まる。階の数が多い場合、上位階にはより多くの空のかごを待機させるべきである。それは、これらのかごが、相応じてより長い応答時間で比較的広いゾーンにサービスしなければならないためである。しかしながら、これにより、ロビーに待機している空のかごの数が低減し、そこでの予測される待ち時間が増大する。
【００６６】
アップピーク交通パターンに対するマルコフ決定過程
ロビーで待機させる空のかごと上位階で待機させる空のかごとの間の正しい比率を見つけるために、ここでは、待機問題を、マルコフ決定過程（ＭＤＰ）として公式化する。ＭＤＰは、有限数の状態Ｓｉ、ｉ＝１，・・・，Ｎｓと、行為Ａｉ、ｉ＝１，・・・，Ｎａのセットと、行為Ａｋ下での状態ＳｉおよびＳｊの各対の間の遷移の即時待ち時間ｗｉｊｋと、行為Ａｋ下での状態ＳｉおよびＳｊの間の遷移の確率の行列Ｐｉｊｋと、システムが状態Ｓｉで開始する確率を指定する分布π（Ｓｉ）と、を含む。Bertsekas著、「Dynamic Programming and Optimal Control」、Athena Scientific、Belmont、Massachusetts、2000、第１および第２巻を参照のこと。
【００６７】
ダウンピーク交通に使用される最適基準、すなわち、次に到着する乗客のみに対する即時の予測された待ち時間Ｑ（ｘ）は、アップピーク交通の場合には適当でない。Ｑ（ｘ）のみが最小化されると、ロビーにおける空のかごの最適な数は常に１である。それは、ロビーにおいて新たなホール呼びにサービスするために、１個のかごで十分だからである。残りの空のかごは、上位階で、そこに到着する乗客の予測された待ち時間を最小化するためにより利用される。
【００６８】
しかしながら、上述したように、この待機ポリシは、高到着率でのアップピーク交通には効率的ではなく、この場合、ロビーにおける次の到着は、そこに待機する単一の空のかごを使用し、将来のホール呼びに対してロビーはカバーされない。
【００６９】
この交通パターンに対する適当な最適化基準は、より長い時間間隔にわたり、好ましくは無限に長く、予測された待ち時間を最小化する。この場合、最適化基準を連続したＮ人の次の乗客に対する平均値として表すことがより都合がよい。
【００７０】
ここで最適化する正確な基準である、真の長期間の予測された乗客の待ち時間は、Ｎが有限に大きくなると
【００７１】
【数５】
0004602086.tif 000006
【００７２】
の極限値であり、すなわち、次のように時間間隔は無限に長くなる。
【００７３】
【数６】
0004602086.tif 000007
【００７４】
ここで、ｓｉは、ｉ番目の次の乗客が到着した時のエレベータシステムの状態であり、Ｑ（Ｓｓ）は、乗客ｉの予測された待ち時間であり、期待値＜．．．＞は、次のＮ人の到着する乗客の分布に対して取得される。
【００７５】
システムｓのあり得る状態の数は非常に多く、あり得る次の乗客の到着すべてに関して期待値を取ることは、計算上非常に費用がかかるため、この最適化基準を直接最小化することは非常に困難である。
【００７６】
比較的少ない状態のＭＤＰに対し長い時間間隔によってこの基準の最適化を公式化するために、本戦略は、システムのあり得る状態のすべてのうちのわずかなもののみを考慮し、異なる待機ポリシを選択する結果としてこれらの状態の展開の確率構造を簡略化する、というものである。
【００７７】
ＭＤＰにおける状態の数を低減することへの手がかりは、特定の待機ポリシが、システムが乗客の到着がなく空のかごがサービスを完了している状態に収束する、「アトラクタ」状態のセットを導入する、という洞察である。これらの状態は、正確に、待機ポリシによって指定される待機位置である。たとえば、１０階建ての建物の場合の待機ポリシは、４個のかごが空である場合はいつでも、それらのうちの２つをロビーで待機させ、３番目のかごを２階で待機させ、４番目のかごを８階で待機させる、と指定するものとする。再待機プロセスが開始する時に４個のかごの初期位置がどこであっても、最終的な結果は、４個のかごがそれらの割り当てられた待機位置にあり、新たなホール呼びが合図されるまでそこに留まる、と想定する。これにより、人が乗ったかごのうちの１つが再び空になるまで、空のかごの数は低減する。
【００７８】
ここで集約されたＭＤＰの状態として使用するために選択するのは、これらの待機位置である。しかしながら、システムはかかる状態間を即座に飛ばず、それらの間を滑らかに移動するため、ここでは、システムを、その状態を想定した時だけではなくその状態に向かって移動している過程にある時にも、待機位置によって表される特定状態にあるように定義する。
【００７９】
状態の数をさらに低減するために、アップピーク交通の場合の待機位置が、一対の数（Ｌ，Ｕ）によって指定されるものと想定する。ここで、Ｌはロビーで待機しているかごの数であり、Ｕは上位階で待機しているかごの数である。さらに、かごは上位階間で均一に分布されているものと想定する。そうする場合、上位階における新たな到着が均一に分布されると暗に想定する。この想定は、常に真ではないが、比較的小さい比率の到着が上位階で発生するため正当化され、それらの間に存在するいかなる非均一性も、ロビーにおける乗客到着の確率に対してはごくわずかである。
【００８０】
このため、対（Ｌ，Ｕ）が与えられ、階Ｆの数が既知となった後、ロビーにＬ個のかごを待機させ残りのＵ個のかごを建物の上位階間に分布させることにより、対応する詳細な待機位置ｘを生成することができる。したがって、状態（Ｌ，Ｕ）の即時待ち時間Ｑ（Ｌ，Ｕ）を、完全な位置ｘの対応する即時の予測された待ち時間として定義することができる。
【００８１】
【数７】
0004602086.tif 000008
【００８２】
ここでの待機状態に対する表示法では、Ｃ個の空のかごが利用可能である場合に行わなければならない決定は、空のかごのうちのいくつをロビーに送るか（Ｌ）と、上位階にいくつ待機させるか（Ｕ＝Ｃ−Ｌ）と、である。たとえば、３個の空のかごが利用可能である場合、あり得る決定は、（０，３）、（１，２）、（２，１）および（３，０）である。かかるポリシの１つの非常にコンパクトな表現は、値ＬＣ（Ｃ＝１，・・・，Ｎ）の次元ベクトルであり、そのＣ番目の要素は、Ｃ個のかごが空である場合にいくつのかごをロビーに待機させるかを指定する。
【００８３】
Ｎｃ個のかごを有する建物では、あり得るポリシの数はＮＣ！であり、それにより、すべてのポリシを比較し最適な待機ポリシを選択することが実際的でなくなる。かかる選択は、到着プロセスの推測学的性質によりさらに複雑になる。２つ以上のポリシの統計的性能を意義あるように比較するために、ポリシを、多くのあり得るシナリオ、すなわち、連続した乗客到着に対して実行しなければならず、それは、すでに複雑性が指数関数的である計算の計算負荷に対する追加の要因である。
【００８４】
これらのポリシを効率的に評価するために、システムの状態展開の確率構造を記述するＭＤＰモデルに対する動的プログラミングを採用する。上述したように、このモデルの状態は、ＬＣ＋ＵＣ＝Ｃ（Ｃ＝１，・・・，Ｎ）であるような位置の対（ＬＣ，ＵＣ）に対応する集約的「アトラクタ」状態である。ＮＣ個のかごを有する建物に対しかかる状態は（ＮＣ＋２）（ＮＣ＋１）／２個ある。
【００８５】
図３に示すように、動的プログラミング問題において格子（trellis）として知られる標準的な構造３００で状態を編成し、かかる状態間で遷移する確率を特定の待機ポリシの関数として指定する。図３は、１つの特定のポリシ［１，１，２，２］に対する遷移構造とともに、４個のかごを有する建物に対する１５の状態の編成を示す。
【００８６】
格子の各状態に、２つの数をラベル付けする。そのうちの１つ目はＬであり、２つ目はＵである。格子の同じ列における状態の２つの数は、空のかごの数Ｃと同じ数になり、そのためかかる状態は、Ｃ個の空のかごがある場合のあり得る待機決定に対応する。同じ行の状態は、空のかごの数に係りなく、建物の上位階で待機するかごの数と同じ数を有する。状態（０，０）は、待機させる空のかごがないため、この場合いかなる決定も行わないが、同様に格子に存在する。
【００８７】
図３において、ポリシ［１，１，２，２］に対応する状態を、アスタリスク（＊）で示す。このポリシ下では、空のかごが１個利用可能である場合、それをロビーに待機させ、２個のかごが利用可能である場合、一方をロビーに待機させ、他方の空のかごを、建物の上位階を含むゾーン、たとえば、上位階のゾーンの中間階で待機させる。３個のかごが利用可能である場合、２個をロビーで待機させ、１個を上位階で待機させる。４個のかごが利用可能である場合、２個をロビーで待機させ、２個を上位階で待機させる。
【００８８】
選択された待機ポリシは、ＭＤＰモデルがアップピーク乗客交通の影響下で従う遷移と、待機ポリシとは独立して作用し任意であってもよいかごスケジューリングプロセスの動作と、を確定する。
【００８９】
実線は、新たな乗客の到着による遷移を示す。かかるイベントにより空のかごの数が低減し、それら遷移は左から右である。破線は、空になっているかごに対応する遷移を示す。かかるイベントにより空のかごの数が増加し、それら遷移は右から左である。最後に、同じ列内の状態間に遷移がある。これらは、列内の１つの状態のみが安定しているため存在する。かごがその列の他の状態のいずれかで終わる場合、エレベータシステムは、待機位置に向かってかごを移動し始める。ここでは、かかる遷移状態をスライディング状態と呼ぶ。
【００９０】
決定過程の目的は、空のかごのそれぞれに対する待機位置であるべき、列毎に１つの状態を正確に選択することである。かかる選択の数は、以下の待機ポリシの数に等しい。
【００９１】
【数８】
0004602086.tif 000009
【００９２】
かかるポリシのすべての結合推定を回避するため、格子３００の標準的な構造を、後述するモデルをいくつか簡易化した後、最適な待機ポリシを見つけるために動的プログラミングプロセスにより変更することができる。
【００９３】
理論的には、モデルのすべての確率、すなわち、図３に示すものに対してのみではなくすべてのポリシに対する遷移確率が与えられると、上述した最適化基準、すなわち、以下の無限に長い時間間隔にわたるすべての乗客の予測された待ち時間を直接最小化するポリシを効率的に確定するために、ポリシの反復または値の反復を使用することが可能である。
【００９４】
【数９】
0004602086.tif 000010
【００９５】
実際には、図３において破線で示す、かごが空になる確率を見つけることは、非常に困難である。しかしながら、最小化されるべき基準をわずかに修正すると、適当なポリシを確定するために左から右への遷移のみを使用する方法がまだある。図３において、これを実線で示す。
【００９６】
無限に長い時間間隔にわたって予測される待ち時間を最小化する代りに、ここでは、Ｌ＋Ｕ＝Ｃであるようなすべての状態（Ｌ，Ｕ）に対し次のＣ個のホール呼びに対する累積的な予測された待ち時間を最小化することができる。この結果、格子３００の異なる列の状態に対する異なる基準が最小化されるが、待機状態の選択は、最適化基準が同じである同じ列内の状態間のみで実行されるため、これは問題ではない。ここで、列Ｃにおける状態ｓｏに対する最適化基準を次のように定義する。
【００９７】
【数１０】
0004602086.tif 000011
【００９８】
ここで、上述したように、期待値＜．．．＞は、次のＣ個の到着に関し、ｓｉはｉ番目の呼びが発生する時のシステムの状態である。
【００９９】
この最小化基準を使用する利点は、Ｗｃ（ｓ）とＷＣ−１（ｓ’）との間に再帰的定義がある、ということである。ここで、ＷＣ−１（ｓ’）は、格子の次の列、すなわち１つ右側における状態ｓ’の累積的な予測された待ち時間である。
【０１００】
この依存性を見るために、システムが、Ｌ＋Ｕ＝Ｃであるように状態ｓ＝（Ｌ，Ｕ）であり新たな乗客が到着する場合に発生することを考える。ここでは、ｓをＣ個のかごが利用可能である場合の待機状態として選択すべきであるか否かを判断しようとするため、ｓは、この推定下での安定状態であり、空のかごは停止して、それらの待機位置において次のホール呼びを待っている。
【０１０１】
到着率に従って、階の１つにおいて次のホール呼びが発生する。この呼びは、上述したようにＱ（Ｌ，Ｕ）の即時待ち時間を受け、この呼びによってシステムは、空のかごが１個減少する右側の次の列の状態に移動する。
【０１０２】
どこでホール呼びが発生するかにより、２つのシナリオが発生する可能性がある。すなわち、ロビーで待機している空のかごが確率Ｐｌで呼びにサービスするように配車されるか、または、上位階で待機している空のかごが確率Ｐｕ＝１−Ｐｌで使用される。これらの２つの確率を、乗客の到着率１３１が既知である場合に確定することができる。これらの２つのシナリオは、ｓから右の列への２つの遷移をもたらす。図３において、確率Ｐｌの遷移により、ｓと同じ行の状態になり、確率Ｐｕの遷移により、ｓの１つ下の行の状態になる。これらの２つの確率を使用して、ＷＣ（Ｓ）を、
【０１０３】
【数１１】
0004602086.tif 000012
【０１０４】
として分解することができる。ここで、ＷＣ−１（ｌ，ｕ）は、ｕ個の空のかごがロビーで待機しておりｌ個の空のかごが上位階で待機している場合に、最初の乗客到着が発生した場合の、次のＣ−１個の乗客到着のさらなる待ち時間である。
【０１０５】
なお、ＷＣ（ｌ，ｕ）は、Ｃ−１個の待機している空のかごに対する理想的な位置から開始する予測された累積的待ち時間であるため、概して、Ｗ’Ｃ−１（ｌ，ｕ）≠ＷＣ（ｌ，ｕ）である。Ｗ’Ｃ−１（ｌ，ｕ）は、かごがサービスを開始した直後のＣ−１個の空のかごの予測された累積的待ち時間であり、残りのＣ−１個のかごはまだ待機していない。
【０１０６】
両遷移後、次のＣ−１個の呼びに対してシステムによりもたらされるさらなる待ち時間Ｗ’Ｃ−１は、遷移が右側の次の列における最適な状態に対するものであるか、または最適な状態に即時遷移するスライディング状態に対するものであるかによって決まる。これらの２つの状態の相違は、遷移が最適な状態に対するものである場合は、空のかごはすでに最適に待機しているため、次の呼びの前に移動せず、次の呼びに答える時は、それが発生した時に正確には依存しない、という事実からもたらされる。
【０１０７】
対照的に、遷移がスライディング状態に対するものである場合、次の呼びに答える予測された待ち時間は、次の呼びが発生する時に強く依存する。待ち時間（ｗｏ）は、イベント１１１が検出された直後に次の呼びが発生し、空のかごがまだ最適に待機していない場合に最長であり、空のかごがそれらの最適な待機位置であると推定された場合に最短（ｗＴ）である。
【０１０８】
最適な状態への真の即時遷移は、最初の呼びに対しロビーのかごが使用される場合にのみ可能であり、Ｃ−１個の空のかごに対する最適な状態は、（Ｌ−１，Ｕ）である。たとえば、状態（２，０）の待ち時間を計算しており、１個の空のかごに対する最適な状態が（１，０）である場合、ロビーにいる乗客は、最初のロビーのかごを使用し、かごは、１つの空のかごに対して正確に最適な状態のままである。これは、ロビー以外の空のかごが使用される場合には当てはまらない。
【０１０９】
たとえば、状態（２，２）の待ち時間を計算しており、３個のかごに対する最適な状態が（２，１）であるとする。上位階のうちの１つにいる乗客は、そこに待機している空のかごのうちの１個に乗り、２個のかごはロビーに、１個は上位階にあるままである。３個のかごに対する最適な状態であるように、上位階における残りの空のかごは、最適な位置、すなわちゾーンの中間に待機しておらず、呼びにサービスするためにいずれの空のかごが使用されたかにより、ゾーンの高さの１／４または３／４に待機している。
【０１１０】
問題を扱い易くするために、ここでは、システムはこの場合最適な状態に即時遷移する、とさらに簡略化する。到着率がロビーにおける到着率に対して低い場合、最適な待機位置に移動するために必要な時間が、上位階における到着間間隔に対してきわめて小さいと想定されるため、この簡略化の影響は実質的である。
【０１１１】
遷移後の新たな状態が最適ではなくスライディングである場合もまた、同じ簡略化は有効である。同じ理由付けを用いて、ここでは、遷移は瞬時であると想定し、最適状態ではなくスライディング状態であるその状態の結果を別個に扱う。
【０１１２】
ここで、各々、（Ｌ，Ｕ）が最適な待機状態であるという仮定に基づいて計算される、システムにまだ最適に待機していないｌ＋ｕ個の空のかごが残っている場合にＣ−１個の呼びにサービスする、さらなる待ち時間ＷＣ−１（ｌ，ｕ）と、列Ｃにおける状態の推定値ＷＣ−１（Ｌ，Ｕ）と、の間の関係に戻る。この関係は、（ｌ，ｕ）が実際に真に最適な待機状態である場合には簡単である。
【０１１３】
乗客の到着が、時間の経過により平均λ、すなわち、新たな到着がＰ（ｔ｜λ）＝λｅ−λｔ（ｔ≧０）となるまで時刻ｔにおける確率密度で指数関数的に分布されると想定する。システムが次の到着の分布に対し状態（ｌ，ｕ）から最適な状態（Ｌ＊，Ｕ＊）に向かってスライドするための予測された待ち時間Ｗ’Ｃ−１（ｌ，ｕ）は、
【０１１４】
【数１２】
0004602086.tif 000013
【０１１５】
である。ここで、ｗ（ｔ）は、時刻ｔにおいて到着する乗客に対する、その乗客が到着する階において空のかごが待機する前の待ち時間である。
【０１１６】
この積分を計算するためには、すべての瞬間のｗ（ｔ）の正確な形態を知らなければならない。行うことができる最も容易な近似は、次のように、ｗ（ｔ）が時間間隔０＜ｔ＜Ｔにわたり線形に減少すると推定することである。
【０１１７】
【数１３】
0004602086.tif 000014
【０１１８】
ここで、ｗＯは、イベント１１１が検出された時、すなわち待機プロセスの開始時に、次の乗客が到着した場合の待ち時間であり、ｗＴは、すべての空のかごがゾーンにおけるそれらの待機位置に達している、すなわち、待機プロセスの最後における待ち時間であり、時刻ｔはその間にある。
【０１１９】
空のかごがそれらの待機位置に向かって移動を開始した直後の短い時間に、その瞬間、その移動しているかごはそれらの静止した位置から離れてすでにそれらが先に停止していた階で即時に呼びにサービスすることができないため、予測された待ち時間は実際にはｗＯを超過する、ということが留意されるが、これは妥当に作用する近似である。
【０１２０】
時間間隔０＜ｔ＜Ｔに対するｗ（ｔ）の選択された近似に基づき、次の到着の時刻に対する予測された待ち時間を、以下のように２つ以上の間隔にわたり上記積分を分割することにより計算することができる。
【０１２１】
【数１４】
0004602086.tif 000015
【０１２２】
量ｗＯおよびｗＴは、すでに、次の到着の位置と次のＣ−２個の到着の位置および時刻とに対する期待値を組み込んでおり、それにより、上記Ｗ’Ｃ−１（Ｌ−１，Ｕ）およびＷ’Ｃ−１（Ｌ，Ｕ−１）を計算するための近似とともに式
【０１２３】
【数１５】
0004602086.tif 000016
【０１２４】
は、格子のすべての状態に対する待ち時間の推定のための漸化式となる。
【０１２５】
逆確率を無視する場合、状態（０，０）は格子の終端であり、その待ち時間を、漸化式によってバックアップ（back up）することができる。それは、本質的に、状態の長期間の待ち時間のBellmanバックアップである。Bertsekas著、「Dynamic Programming and Optimal Control」、Athena Scientific、Belmont、Massachusetts、2000を参照のこと。
【０１２６】
状態（０，０）に対する待ち時間は任意であってもよく、より計算を容易にするためにゼロに設定する。
【０１２７】
バックアップのプロセスが、状態（０，０）から空のかごがより多くなる、すなわち図３では右から左の列に向かって進行するにしたがい、格子の同じ列におけるすべての状態に対する待ち時間を計算することにより、各空のかごに対する最適な待機位置を確定することができる。最適な状態は、
【０１２８】
【数１６】
0004602086.tif 000017
【０１２９】
である。
【０１３０】
列Ｃにおけるすべての状態に対する待ち時間がバックアップされるとすぐに、かつ、列＋１の任意のバックアップが実行される前に、最適なポリシを確定する。それは、列Ｃ＋１における状態に対するバックアップは、その列の状態のいずれが安定しておりいずれがスライディングしているかを判断するために、列Ｃに対する最適な状態が必要なためである。
【０１３１】
待機状態の待ち時間のバックアップと待機ポリシ確定のプロセス全体を、図４に示す動的ポリシ手続きにより実行する。
【０１３２】
動的ポリシ手続きは、関数Ｔｉｍｅ（Ｃ，ｕ１，ｕ２）を使用し、これは、かごが、格子の行ｕ１、列Ｃの状態に対応する構成から格子の行ｕ２、列Ｃの状態に対応する構成まで移動する時間を返す。プロセスは、格子の第２の列から計算を開始する。１個の空のかごのみが利用可能である場合、常に、その空のかごをロビーで待機させたままにすることが最適である。これは、乗客の少なくとも半分がロビーに到着する場合に当てはまる。
【０１３３】
本発明を好ましい実施の形態の例により説明したが、本発明の精神および範囲内でさまざまな他の適応および変更を行ってもよい、ということを理解しなければならない。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内にあるかかる変形形態および変更形態すべてを包含する、ということである。
【図面の簡単な説明】
【０１３４】
【図１】本発明による空のかごを待機させるフローチャートである。
【図２】固定待機ポリシに対する擬似コードの図である。
【図３】本発明による方法をモデル化するために使用される格子の状態の図である。
【図４】動的待機ポリシに対する擬似コードの図である。
【図１】
0004602086.tif 000032
【図２】
0004602086.tif 000033
【図３】
0004602086.tif 000034
【図４】
0004602086.tif 000035