(57)【要約】  エレベータ群のための準最適スケジューリング方法は、予想交通情報を使用する。より詳細には、予想交通情報は、客にとってのパフォーマンスを高めることにその目的がある、スナップショット問題を定義するために使用される。スナップショット問題を解くために、目的関数が、問題の個別かご副問題への分解を容易にする形態に変換される。副問題は、上位レベルの乗客のかごへの割り当てと、下位レベルの個別かごの配車という、２つのレベルの定式化を使用して、独立に解かれる。準最適な乗客選択および個別かご配車が得られる。その後、個別かごは、乗客にとって準最適な結果を達成する群制御の解に到達するように、反復プロセスを通して調整される。
2008538737.tif 000002
【特許請求の範囲】
【請求項１】
エレベータ群をスケジューリングする方法であって、
スナップショット問題を生成するために、ルックアヘッド時間窓内の、乗客の到着時刻、到着階、および降車階に関する予想情報をモデル化するステップと、
乗客のかごへの割り当ておよびかご配車を決定するために、前記スナップショット問題内のすべての乗客の合計サービス時間に基づいて目的関数を最小化することによって、前記スナップショット問題を解くステップと、
を含む方法。
【請求項２】
前記スナップショット問題を解くステップが、
各エレベータかごについて最適な乗客のかごへの割り当てを選択することと、
かごシミュレーションモデルを使用して、前記選択された乗客のかごへの割り当てに基づいて、個別かごの最適な配車を決定することと、
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記目的関数が、すべての乗客の待ち時間および輸送時間の加重和を含むことを特徴とする請求項１に記載の方法。
【請求項４】
すべての乗客Ｉについての前記加重和が、
【数１】
2008538737.tif 000033
であり、乗客ｉについて、Ｔi＝αＴiW＋βＴiTであり、ここで、αおよびβは重み、ＴiWは待ち時間、ＴiTは輸送時間であることを特徴とする請求項２に記載の方法。
【請求項５】
前記目的関数を最小化することが、
前記スナップショット問題の分解を容易にする形式に前記目的関数を変換するステップと、
ラグランジュ双対関数を形成するために、前記変換された目的関数および前記乗客かご割り当て制約にラグランジュ緩和を適用するステップと、
代理最適化フレームワーク内で前記ラグランジュ双対関数を解くステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記ラグランジュ双対関数を解くステップが、中止基準が満たされるまで、
乗客かご割り当て制約の緩和を通して個別かご副問題を得ることと、
局所探索法を使用して副問題を独立に解くことと、
代理最適化を使用することによって、乗数の反復更新を通して、個別かごを調整することと、
前記乗数反復更新の中止時に乗客かご割り当て制約が破られている場合、準最適解のために、発見的手法を使用することによって、実現可能な割り当てを構成することと、
を繰り返すステップを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記局所探索法が、
発見的手法を使用することによって、乗客選択を評価し、ランク付けするステップと、
前記ランク付けに基づいて、正確なパフォーマンスのために、動的プログラミングを使用して、トップ選択を評価するステップと、
を含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記代理最適化中に、先の選択よりも良い選択が、乗数更新の方向性を定めるために使用されることを特徴とする請求項７に記載の方法。
【請求項９】
乗数が、準最適解のために、代理最適化を使用することによって、反復的に更新されることを特徴とする請求項６に記載の方法。
【請求項１０】
初期反復時に、すべての乗数が、ゼロに設定され、すべての副問題が、乗客を選択しないことによって最小化されることを特徴とする請求項９に記載の方法。
【請求項１１】
エレベータ群をスケジューリングする方法であって、
乗客の到着時刻、到着階、および降車階に関する予想情報を受け取るステップと、
ルックアヘッド時間窓内のすべての未割り当て乗客の合計サービス時間に基づいて目的関数を形成するステップと、
スナップショット問題の分解を容易にする加法的形式に前記目的関数を変換するステップと、
前記変換された目的関数にラグランジュ緩和を適用するステップと、
反復的に単一かご副問題を解き、ラグランジュ乗数を更新するステップと、
各かごについて乗客かご割り当ておよびかご配車を選択するステップと、
を含む方法。
【請求項１２】
前記目的関数が、すべての乗客の待ち時間および輸送時間の加重和を含むことを特徴とする請求項１０に記載の方法。
【請求項１３】
すべての乗客Ｉについての前記加重和が、
【数２】
2008538737.tif 000034
であり、乗客ｉについて、Ｔi＝αＴiW＋βＴiTであり、ここで、αおよびβは重み、ＴiWは待ち時間、ＴiTは輸送時間であることを特徴とする請求項１２に記載の方法。
【請求項１４】
エレベータ群の運転を制御する方法であって、
乗客の到着時刻、到着階、および降車階に関する予想情報を受け取るステップと、
リアルタイムに、前記予想情報、かご定員制約およびかごダイナミクス情報を含む個別かごシミュレーションモデル、ならびにパフォーマンスメトリックの加重和である目的関数に基づいて、乗客のかごへの割り当ておよびかごの配車を選択するステップと、
前記選択ステップに基づいて、かごを配車するステップと、
を含む方法。
【請求項１５】
最適化するステップが、前記かごの各々について、
乗客割り当ての最適選択を行うことと、
各乗客選択についてかごパフォーマンスを決定することと、
を含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記目的関数が、すべての乗客の待ち時間および輸送時間の加重和を含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
すべての乗客Ｉについての前記加重和が、
【数３】
2008538737.tif 000035
であり、乗客ｉについて、Ｔi＝αＴiW＋βＴiTであり、ここで、αおよびβは重み、ＴiWは待ち時間、ＴiTは輸送時間であることを特徴とする請求項１６に記載の方法。
【請求項１８】
エレベータ群の運転を制御する方法であって、
予想交通情報を受け取るステップと、
スナップショット問題を生成するために、前記エレベータ群の現在の状態に対して予想交通情報をモデル化するステップであって、前記スナップショット問題が、前記乗客の各々が単一のかごに割り当てられることを要求する乗客割り当て制約を含む、モデル化するステップと、
目的関数を最適化するために、前記スナップショット問題を、
前記スナップショット問題を緩和された問題に変換するために、前記乗客割り当て制約を緩和することと、
前記緩和された問題を独立かご副問題に分解することと、
乗客割り当てを生成するために、すべての独立かご副問題を解くことと、
によって解くステップと、
を含む方法。
【請求項１９】
前記予想交通情報を統計的情報を用いて補足するステップと、
エレベータの発車間時間およびエレベータ定員のあるパーセンテージに達する乗車人数に関するエレベータ解放制約に基づいて、エレベータを解放するステップと、
をさらに含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
建物の階をゾーンに分割するステップと、
エレベータが必要とされる可能性の高いゾーンを識別するステップと、
前記識別されたゾーンでエレベータを待機させるステップと、
をさらに含むことを特徴とする請求項１８に記載の方法。
【請求項２１】
前記目的関数内に脱出時間副問題を含むステップをさらに含むことを特徴とする請求項１８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エレベータ制御の分野に関し、詳細には、建物内でグループとして動作するエレベータのスケジューリングに関する。
【０００２】
なお、本出願は、２００５年４月１５日に米国で出願された、米国仮特許出願第６０／６７１６９８号からの優先権を主張し、同仮特許出願は、参照により本明細書に組み込まれる。
【背景技術】
【０００３】
群エレベータのスケジューリングは、輸送効率にとっての重要な問題として、長い間認識されている。しかし、この問題は、混成のシステムダイナミクス、状態空間および決定空間の組み合わせの増加、時間的に変動する不確実な乗客需要、厳重な運転制約、ならびにオンラインスケジューリング用のリアルタイム計算要求のために難しい。
【０００４】
最近、行先入力を備えたエレベータシステムが導入された。行先入力システムでは、乗客は、サービスを受けるのに先立ち、行先階を登録するように求められる。したがって、かごの割り当てを決定するときには、乗客の行先が分かっているので、より多くの情報が、群エレベータのスケジューリング用に利用可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
さらに、情報技術の進展に伴って、１つの有望な動向は、様々な新しいセンサまたは需要推定技術からの予想交通情報を使用して、不確実性を減らし、パフォーマンスを著しく高めることである。予想交通情報を用いる準最適スケジューリングは、予想交通情報を使用せずに決定されたスケジューリングと比べて、より優れたパフォーマンスをもたらす。
【課題を解決するための手段】
【０００６】
本発明は、予想交通情報を使用する、エレベータ群のためのスケジューリング方法に関する。より詳細には、予想交通情報は、客にとってのパフォーマンスを高めることにその目的がある、スナップショット問題を定義するために使用される。スナップショット問題を解くために、目的関数が、問題を個別かご副問題に分解するのを容易にする形態に変換される。副問題は、上位レベルの乗客のかごへの割り当てと、下位レベルの個別かごの配車という、２つのレベルの定式化を使用して、個別に解かれる。準最適な乗客選択および個別かご配車が得られる。その後、個別かごは、乗客にとって準最適な結果を達成する群制御の解に到達するように、反復プロセスを通して調整される。この方法は、予想情報が僅かな場合または全くない場合に、エレベータ待機の操作に、および調整された緊急避難に拡張することができる。
【発明を実施するための最良の形態】
【０００７】
図１は、４つのエレベータ１２からなるグループによってサービスされる、１０階Ｆ１〜Ｆ１０を有する建物１０を示す。かごＪ１〜Ｊ４は、群エレベータコントロール１４の制御下で、エレベータ１２の昇降路内を移動する。かごＪ１〜Ｊ４のスケジューリングは、実際または予想のサービス要求を表す入力に基づいて調整される。
【０００８】
群エレベータコントロール１４は、乗客ｉの到着時刻ｔiと、乗客ｉの到着階ｆiaと、乗客ｉの行先階ｆidと、についての情報を提供する需要情報入力を受け取る。予想交通情報入力の１つのソースは、エレベータから距離を置いて配置されたキーパッドを有する行先入力システムであり、その結果、乗客は、エレベータに乗車するのに先立ち、行先階をキー入力することによってサービスを要求することができる。予想交通情報のその他のソースは、乗場に通じる廊下にあるセンサ、ビデオカメラ、識別カードリーダ、および予測需要に基づいて特定の行先階行きのかごを事前予約または要求するために群エレベータコントロールにネットワーク接続されたコンピュータシステムを含む。例えば、ホテル会議スケジュールシステムは、会議がいつ始まり、またはいつ終わるか、したがって、エレベータサービスに対する需要をいつ生み出すかに関する情報を提供するために、群エレベータコントロール１４とインタフェースをとることができる。
【０００９】
群エレベータコントロール１４は、乗客をかごにどのように割り当てるか、また乗客を乗せ、運ぶためにかごをどのように配車するかを決定するために、予想または既知の将来交通需要を利用する、コンピュータベースのシステムである。予想交通情報を使用して、群エレベータコントロール１４は、乗客にサービスする際に、高められたエレベータのパフォーマンスを実現する。パフォーマンスメトリックの複数の可能な選択肢の１つは、サービスを要求するすべての乗客の合計サービス時間を短縮することである。この目的またはその他の任意の目的は、乗客かご割り当て制約およびかご定員制約に矛盾せず、またかごダイナミクスに従った方法で、満たされなければならない。
【００１０】
予想交通情報は、窓内に収まる情報を入力から選択するために、群エレベータコントロール１４によって使用される。各窓スナップショットとともに、予想交通情報は、客にとってのパフォーマンスを最適化する目的関数を定式化するために使用される。
【００１１】
図１に示されるようなエレベータ群を運転する際、エレベータ１２は独立であるが、エレベータ群の個別かごＪ１〜Ｊ４は、共通の乗客の集まりにサービスすることを通じて結合される。各乗客に対して、その乗客にサービスするエレベータは、ただ１つしか存在しない。しかし、乗客の組が個別かごに割り当てられると、１つのかごの配車は、その他のかごから独立となる。
【００１２】
この結合されながらも分離可能な問題の構造は、乗客割り当てが上位レベルにあり、単一かご配車が下位レベルにある、簡単でありながら革新的な２層定式化を確立するために、群エレベータコントロール１４によって使用される。
【００１３】
エレベータ配車問題は、乗客かご割り当て制約の緩和を通して、個別かご副問題に分解される。その後、各かご毎に、そのかごによってサービスされる最善の乗客の組を選択するために、探索が実行される。単一かごダイナミクスおよびかご定員制約は、各かごのパフォーマンスが最良になる最善の乗客の組をもたらすために、単一かごシミュレーションモデル内に組み込まれる。その後、個別かごの結果は、客にとっての準最適解に到達するために、乗数を更新する反復プロセスを通して調整される。上記の方法は、予想情報が僅かな場合または全くない場合に、エレベータ待機の操作に、および調整された緊急避難に拡張することができる。
【００１４】
ルックアヘッド窓が、予想需要情報をモデル化するために使用され、窓内の既知または推定交通が考察される。乗客対かご割り当て制約は、１次不等式制約として確立され、共通の乗客の集まりにサービスすることを通して個別かごが結合されるので、「結合」制約である。かご定員制約およびかごダイナミクスは、個別かごシミュレーションモデル内に組み込まれる。目的関数は、例えば、乗客の待ち時間、サービス時間もしくは必要とされるエレベータエネルギ、または乗客が行先に着くまでに経験するかごの停車回数など、乗客毎、かご毎、建物毎の尺度の範囲内で自由に選ぶことができる。
【００１５】
図１に示された例によって示されるように、システムは、Ｆ個の階と、Ｊ個のエレベータとを有する建物である。かごダイナミクスおよびかご定員制約を含む、エレベータのパラメータが与えられる。エレベータ群の現在の状態は、かごダイナミクスおよびかご定員制約に加えて、例えば、かごに割り当て済の乗客、昇降路内のかごの位置、かごが加速中か、減速中か、かごの進行方向、かごの速度など、各エレベータの運転状態を含む。例えば、ある階で戸を開いて停止しているかご、階と階との間を移動中のかごなど。
【００１６】
予想交通情報は、ルックアヘッド窓によってモデル化される。窓内に到着した各乗客ｉの到着時刻ｔia、到着階ｆia、および行先階ｆidによって指定される予想交通情報は、既知であると仮定される。予想交通情報は、予想交通情報がかごにまだ割り当てられていない乗客に関する点で、エレベータ群の現在の状態から区別することができる。異なる乗客インタフェースまたは需要推定方法から生じるものなど、異なる数量の予想交通情報を有するケースは、窓サイズを調整することによって対処することができる。その後、ローリングホライズン方式が、窓と併せて使用され、スナップショット問題は、定期的または必要に応じて解かれる。スナップショット問題の場合、Ｓpは、かごに乗せられてはいるが、まだ行先階まで運ばれていないＩp人の乗客からなる組を表し、Ｓcは、まだかごに乗せられていないＩc人の乗客からなる組を表すとする。併せて、行先階に運ばれるＩ人の乗客（Ｉ＝Ｉc＋Ｉp）が存在する。この方法は、いつ割り当てに関与（ｃｏｍｍｉｔ）するかを選択する上で、大きな柔軟性を可能にする。乗客のＩcの人数は、１からＩの間で変動することができ、様々な関与方針（ｃｏｍｍｉｔｍｅｎｔ  ｐｏｌｉｃｙ）を可能にする。問題が解かれると、群エレベータコントロール１４は、次の再スケジューリング点以前にかごに乗せられる、Ｉc人の乗客の一部の割り当てにのみ関与し、その他の乗客への関与は先延ばしする。
【００１７】
考察される制約は、かご間の結合制約と、個別かご制約とを含む。前者の制約は、各乗客はただ１つのかごに割り当てられなければならない、すなわち、
【００１８】
【数４】
2008538737.tif 000003
【００１９】
であることを述べた、乗客かご割り当て制約を含み、ここで、δijは、乗客ｉがかごｊに割り当てられていれば１、そうでない場合０に等しい、０／１を指示する変数である。スナップショット問題の場合、すべてのｉ∈Ｉp（すなわち、かごに乗せられてはいるが、まだ行先階まで運ばれていない乗客）についてのδijは、決まっており、すべてのｉ∈Ｉc（すなわち、まだかごに乗せられていない、これから運ばれる乗客）についてのδijのみが、最適化される。個別かごは、共通の乗客の集まりにサービスしなければならないので、結合されていることに留意されたい。個別かご制約は、かご定員制約
【００２０】
【数５】
2008538737.tif 000004
【００２１】
を含み、ここで、Ｃｊは、かごｊの定員であり、ζijtは、乗客ｉが時刻ｔにおいてかごｊ内にいれば１、そうでない場合０に等しい、０／１を指示する変数である（ｔip≦ｔ＜ｔidの場合に限って、ζijt＝１）。上の式において、乗客ｉの乗車時刻ｔipおよび降車時刻ｔidは、与えられた割り当てに対して個別かごがどのように配車されるかのみに依存し、配車方策φによって、
【００２２】
【数６】
2008538737.tif 000005
【００２３】
と表される。変数｛ζijt｝の数が多く、関数φが複雑過ぎて記述できなくなり得ることを考慮して、制約（２）および制約（３）は、明示的には表されず、個別かごのシミュレーションモデル内に組み込まれる。戸開時間、戸開放時間（戸を開いたままにしておく最小時間間隔）、戸閉時間、ならびに乗客１人当たりの入時間および出時間など、その他のエレベータパラメータも、シミュレーションモデルで使用される。
【００２４】
群エレベータコントロール１４の目的は、スケジューリングが、あるパフォーマンス基準に関して、より高い客（乗客または建物管理者）の満足をもたらすことである。この方法によって可能にされる１つの可能性は、待ち時間の加重和に焦点を定めることである。例えば、乗客ｉについて、待ち時間ＴiWは、乗客ｉの到着時刻と乗車時刻との間の時間間隔（ＴiW≡ｔip−ｔia）であり、輸送時間は、乗車時刻と降車時刻との間の時間間隔（ＴiT≡ｔid−ｔip）である。サービス時間Ｔiは、上記２つの和であり、すなわち、到着時刻と降車時刻との間の差（ＴiS≡ｔid−ｔia）である。時間定義が、図２に示されている。待ち時間は、到着時刻と乗車時刻との間の時間間隔である。輸送時間は、乗車時刻と降車時刻との間の時間間隔である。この例では、目的は、すべての乗客の待ち時間と輸送時間との加重和を最小化することであり、すなわち、
【００２５】
【数７】
2008538737.tif 000006
【００２６】
上の式において、αおよびβは、設計者によって指定される重みである。α＝β＝１のとき、Ｔi＝ＴiSであり、α＝１かつβ＝０のとき、Ｔi＝ＴiWであることに留意されたい。目的関数は、エレベータを動かすのに必要とされるエネルギ、およびエレベータによって行われる停車の回数など、その他のパフォーマンスメトリックを含むこともできることに留意されたい。目的関数（４）の最適化は、制約（１），（２），（３）の影響を受ける。この例は、その他の制約の使用を制限するものとして読まれるべきではない。
【００２７】
目的関数の定式化は、建物形態および交通パターンについて特別な仮定はなされなかったので、任意の建物形態および交通パターンに適用可能である。
【００２８】
本明細書で説明されるように、結合乗客かご割り当て制約（１）は、１次不等式制約であり、かご定員制約（２）およびかごダイナミクス（３）は、個別かごシミュレーションモデル内に組み込まれる。したがって、目的関数（４）は最初に、問題の個別かご副問題への分解を容易にする形態に変換される。その後、分解および調整手法は、結合乗客かご割り当て制約（１）の緩和を通して展開され、個別かご副問題をもたらす。かご副問題は、システムパフォーマンスに対する、かごへの乗客割り当ての感度を計算する。これは、一連のステップで達成される。第１のステップは、どの乗客が特定のかごに割り当てられるかを決定することである。この割り当てステップは、局所探索方法を使用して解くことができる。このような方法の１つでは、当技術分野で知られるように、粗い評価を用いてもランク付けが強固になるような順序最適化概念に基づいた発見的手法を使用して、乗客選択が、最初に速やかに評価され、ランク付けされる。このランク付け情報を用いて、トップ選択が、正確なパフォーマンスのために、単一かご配車を最適化する動的プログラミングによって評価される。代理最適化フレームワーク内では、先の選択より「良い」選択は、乗数更新の方向性を定める上で「十分に良い」。その後、個別かごは、代理最適化を使用することによる乗数の反復更新を通して、準最適解のために調整される。この手法のフレームワークが、図３に示されている。具体的なステップが、以下に提示される。
【００２９】
図３は、各スナップショット問題を解くための２レベルの解法２０を示している。方法は、初期化ステップ２２で開始する。分解および調整手法が、結合乗客かご割り当て制約の緩和２４を通して展開され、緩和された問題を生成する。緩和された問題は、かご副問題２６に分解され、かご副問題は、独立に解かれる。かご割り当て問題内における第１のステップ２８は、かごに割り当てる乗客を選択することである。第２のステップは、かごダイナミクスモデル３４と、それに続く結果パフォーマンスの評価３６とを使用して、準最適単一かご配車３２を特定するために、単一かごモデル３０を使用する。すべてのかご副問題が解かれると、次のステップは、実現可能な乗客のかごへの割り当て３８を構成することであり、その後に、中止基準４０の使用が続く。基準４０は、解が十分に準最適であるとき、さらなる反復の中止を決定する。準最適ではない場合、次の反復において、かご副問題２６からの勾配情報を使用して、乗数が更新される（ステップ４２）。
【００３０】
目的関数（４）を個別かご副問題に分解するには、目的関数は、個別かごに関して加法的でなければならない。したがって、目的関数（４）は、割り当て制約（１）を使用することによって、
【００３１】
【数８】
2008538737.tif 000007
【００３２】
と書き直される。この加法形式を用いて、割り当て制約（１）は、ラグランジュの非負の乗数｛λi｝を使用することによって、
【００３３】
【数９】
2008538737.tif 000008
【００３４】
と緩和される。式（７）からｊに関係するすべての項を集めることによって、かごｊの副問題は、
【００３５】
【数１０】
2008538737.tif 000009
【００３６】
として得られ、定員制約（２）およびかごダイナミクス（３）の影響を受ける。
【００３７】
新規かつ効率的な手法が、かごｊの副問題（８）を解くために使用される。かご副問題（８）は、与えられた１組の乗数について、最適乗客選択および選択された乗客の最適ルーティングを得ることである。大きな探索空間が関係することを考慮すると、最適解を得ることは難しい。それにも関わらず、代理劣勾配法に基づくならば、乗数を更新する適切な方向性を生み出すのに、ある条件下におけるただ１つまたは少数の副問題の近似最適化で十分である。Ｘ．Ｚｈａｏ、Ｐ．Ｂ．Ｌｕｈ、Ｊ．Ｗａｎｇ、「Ｔｈｅ  Ｓｕｒｒｏｇａｔｅ  Ｇｒａｄｉｅｎｔ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｌａｇｒａｎｇｉａｎ  Ｒｅｌａｘａｔｉｏｎ  Ｍｅｔｈｏｄ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｏｐｔｉｍｉｚａｔｉｏｎ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ、Ｖｏｌ．１００、Ｎｏ．３、１９９９年３月、６９９〜７１２ページを参照されたい。この特性を利用することによって、目標は、局所探索法を使用することによって、より良い乗客選択を、選択された乗客の効果的な配車とともに得ることになる。副問題は、発見的手法および動的プログラミングと併せて、局所探索法を使用することによって、独立に解かれる。
【００３８】
図３に示される乗客割り当て２８の実施形態の一例は、図４に示される局所探索法５０である。最初に、ツリー探索技法に基づいて、１度に１乗客を変化させることによって、乗客選択が生成される。局所探索５０における各ノードについて（すなわち、乗客選択δijを与えた場合）、問題は、以下のような最適化単一かご配車を用いて、パフォーマンスを評価することである。
【００３９】
【数１１】
2008538737.tif 000010
【００４０】
局所探索５０では、粗い評価を用いてもランク付けが強固になるような順序最適化概念に基づいた発見的手法を使用して、乗客選択が、最初に速やかに評価され、ランク付けされる。
【００４１】
その後、図４に示されるように、局所探索５０のトップ候補が、正確なパフォーマンスのために、単一かごモデル３０によって評価される。それが元の選択より良い場合、それが受け入れられる。それ以外の場合、第２の最良が評価される。より良い選択が見つからない場合、元の選択が維持され、次の副問題が解かれる。代理最適化フレームワーク内では、先の選択より「良い」選択は、乗数更新の方向性を定める上で「十分に良い」。
【００４２】
局所探索手順の擬似コードが、表１に示されている。
【００４３】
【表１】
2008538737.tif 000011
【００４４】
単一かごルーティング方針が確定されると、乗客のかごへの割り当ての特定の選択から生じるパフォーマンスが評価されることができる。この方法は、単一か配車方針の任意の選択を許容する。例えば、当技術分野で知られるように、フルコレクティブ（ｆｕｌｌ  ｃｏｌｌｅｃｔｉｖｅ）として知られる一般的な単一かご配車方針。
【００４５】
問題（式９）を解く１つの方法では、単一かごモデル３０は、かご軌跡を最適化し、乗客選択を評価する、シミュレーションベースの動的プログラミング（ＤＰ）法として実施される。使用され得る単一かごモデル３０の具体例は、以下で説明されるように、計算要件を低減するために、ＤＰステージ、状態、決定、およびコストの新規な定義を有する。主要なアイデアは、片方向運行について、停車階が与えられた場合、かご軌跡は一意に指定されるというものである。これを用いて、方向を変えないかごの片方向運行として、ステージが定義される。
【００４６】
時刻ｔkに開始するステージについて、ＤＰ状態は、時刻ｔkにおけるかご位置ｆjと、かごの進行方向ｄjと、時刻ｔkにおいて行先階にまだ運ばれていない乗客からなる組Ｓkのステータス（乗客ｉのステータスは、到着時刻ｔiaと、到着階ｆiaと、行先階ｆidとを含む）とを含む。したがって、状態は、
【００４７】
【数１２】
2008538737.tif 000012
【００４８】
によって表される。
【００４９】
状態の決定は、停車階と、かごが進行方向を変える反転階と、現在のステージで運ばれる乗客（停車階の間を移動する乗客に限定）とを含む。したがって、決定は、Ｕk＝｛ｕi｜∀ｉ∈Ｓk｝によって表されることができ、ここで、ｕiは、ステージｋにおいて乗客ｉが行先階に運ばれていれば１、そうでない場合０に等しい、０／１を決定する変数である。ｔkにおいてすでにかごｊ内にいる乗客については、ｕiは常に１である。同一の到着階および降車階を有する乗客の場合、先着順サービスルールに従って乗せられる。
【００５０】
説明の目的で、待ち時間および輸送時間パフォーマンスメトリックに焦点を定めると、ＸkおよびＵkを与えた場合、ステージｋにおいて運ばれる乗客の乗車時刻ｔipおよび降車時刻ｔid、ならびにステージｋ＋１の開始時刻ｔk+1が、単一かごシミュレーションを通して得られる。各乗客について、待ち時間または輸送時間は、各ステージ（すなわち、各片方向運行）における乗客の時間遅延に加えられることに留意されたい。したがって、式（９）の目的関数、即ちすべての乗客の待ち時間および輸送時間の加重和は、以下のようにステージに分割することができる。
【００５１】
図５は、ステージに関するコストの図である。ステージｋは、時刻ｔkに開始し、時刻ｔk+1に終了する。ステージｋにおいて運ばれる乗客（ｕi＝１）の場合、ステージｋにおける待ち時間は、ｔip−ｍａｘ（ｔk，ｔia）であり、輸送時間は、ｔid−ｔipである。ステージｋにおいて運ばれない乗客（ｕi＝０）の場合、ステージｋにおける待ち時間は、ｔk+1−ｍａｘ（ｔk，ｔia）であり、輸送時間は、０である。したがって、目的関数（□*待ち時間＋□*輸送時間）は、以下のステージに関するコストに組み入れられることができる。
【００５２】
【数１３】
2008538737.tif 000013
【００５３】
上記の定義を用いて、単一配車の最適軌跡が、順方向動的プログラミングを使用することによって得られる。
【００５４】
代理劣勾配法に基づくならば、乗数を更新する適切な方向性を生み出すのに、ある条件下におけるただ１つまたは少数の副問題の近似最適化で十分である。最初に、すべての副問題が、初期反復において最小化されるべきである。乗数を初期化する速やかな方法は、｛□j｝0＝｛０｝であるとき、すべての副問題の最適解は｛□ij*｜∀ｊ｝0＝｛０｝であるという観察に基づいている（表２の擬似コードを参照されたい）。したがって、｛□j｝0および｛δij｝0の初期値は、容易に得ることができる。第ｋの反復における現在解（｛□j｝k，｛δij｝k）を与えると、代理双対は、
【００５５】
【数１４】
2008538737.tif 000014
【００５６】
である。ラグランジュ乗数は、
【００５７】
【数１５】
2008538737.tif 000015
【００５８】
に従って更新され、ここで、代理劣勾配の成分は、
【００５９】
【数１６】
2008538737.tif 000016
【００６０】
であり、ステップサイズｓkは、
【００６１】
【数１７】
2008538737.tif 000017
【００６２】
を満足する。最適双対Ｌ*を推定するため、実現可能な｛δij｝kが、５回の反復毎に構成され、実現可能なコストが評価される。第ｋの反復において、Ｐkが、それまでに得られた最小実現可能コストとして定義される。ＰkがＬ*の上限であり、代理双対がＬ*の下限であることを考慮して、最適双対は、以下のように推定される。
【００６３】
【数１８】
2008538737.tif 000018
【００６４】
推定最適双対コストを用いると、ステップサイズは、
【００６５】
【数１９】
2008538737.tif 000019
【００６６】
である。｛□j｝k+1を与えて、かご副問題ｊ（ｊ＝ｋ  ｍｏｄ  Ｊ）を選択し、｛□ij｝k+1が、
Ｌj（｛λik+1｝，｛δijk+1｝）＜Ｌj（｛λik+1｝，｛δijk｝）    （１８）
を満足するように、発見的手法およびＤＰ（表２を参照）と併せて局所探索を使用することによって、｛□ij｝k+1を得るために、「近似最適化」を実行する。したがって、その他のかごの｛□ij'｜ｊ’≠ｊ｝k+1を最近の利用可能な値に保ちながら、かごｊ（ｊ＝ｋ  ｍｏｄ  Ｊ）の｛□ij｝k+1が得られる。更新値｛□j｝k+1および更新値｛δij｝k+1を用いて、プロセスは繰り返される。
【００６７】
双対ギャップが□より小さいか、または最大反復回数に到達した場合、アルゴリズムは中止する。大きな時間窓を有するケースでは、反復回数の上限は取り除かれる。その理由は、このケースはオフライン最適化のためのものであり、最大の関心事は、ＣＰＵ時間ではなく、解の最適性にあるからである。
【００６８】
実現不可能な解をもってアルゴリズムが中止した場合、実現可能な解を構成するために、発見的手法のルールが以下のように使用される。
【００６９】
・違反する割り当てを有する、すなわち、
【００７０】
【数２０】
2008538737.tif 000020
【００７１】
である乗客を識別する。
【００７２】
・１とＪとの間の乱数ｊ’を生成する。
【００７３】
・δij'＝１、かつ∀ｊ≠ｊ’についてδij'＝０となるように、この乗客をかごｊ’に割り当てる。
【００７４】
【表２】
2008538737.tif 000021
【００７５】
ローリングホライズン方式が、窓と併せて使用される。スナップショット問題は、定期的に解かれる。
【００７６】
図６は、ルックアヘッド窓が有限の持続時間からなるケースを示している。図６では、７５％オーバーラップする非ゼロの移動窓が示されている。窓サイズは、Ｔであり、再スケジューリング間隔は、０．２５Ｔであり、再スケジューリング点は、ｔ1およびｔ2である。現在の時間瞬間がｔ2であると仮定する。ｔ2とｔ2＋Ｔとの間のすべての交通情報が与えられると仮定する。したがって、異なるレベルの予想交通情報を有するケースは、適切にＴを調整することによってモデル化することができる。
【００７７】
（将来交通情報を僅かしかまたは全くもたないケース）
小さなまたはゼロの時間窓を有することによってモデル化される、将来交通情報を僅かしかまたは全くもたないケースの場合、上記のスナップショット問題の最適化は、「近視的」であり、全体的パフォーマンスは、良好でないことがある。例えば、ロビーにおいて利用可能な４機のエレベータと、アップピーク交通時にほぼ同時にロビーに到着する行先階を異にする４人の乗客と、が存在すると仮定する。このスナップショット問題に対する、例えば、合計サービス時間を最小にするための「最良」決定は、各乗客に１つのエレベータを配車することである。しかし、これは、エレベータの「集団化（ｂｕｎｃｈｉｎｇ）」、すなわち、エレベータが互いの近くで移動することを引き起こす。その場合、４人の乗客より僅かに遅れて到着した乗客は、エレベータの１つがロビーに戻って来るまで待たなければならず、貧弱な全体的パフォーマンスをもたらす。集団化は、十分な将来情報を有するケースでは、それほどの問題ではない。
【００７８】
別の問題は、乗客の到着が少なく、将来交通情報を僅かしかまたは全くもたない場合に、双方向交通についての乗客待ち時間を短縮することである。パフォーマンスは、エレベータが必要とされる可能性の高い階に、あらかじめエレベータを「待機」させることによって改善され得ることが示された。上で提示された方法は、これら２つの問題に一貫した方式で対処するために拡張された。
【００７９】
（アップピーク用の最適化の統計的方法）
将来交通情報を僅かしかまたは全くもたない場合のアップピークについてのスナップショット解法の近視的困難を克服するため、乗客が時間不変レートで到着する、行先階分布が与えられた、定常的モデルについて考察する。統計的分析に基づいて、エレベータの定員がエレベータの「発車間時間（ｉｎｔｅｒ−ｄｅｐａｒｔｕｒｅ  ｔｉｍｅ）」内の新規到着を収容するのに十分であると仮定した場合、等しい時間間隔でロビーからエレベータを解放（ｒｅｌｅａｓｅ）することによって、このようなアップピーク交通に対して、良好な定常パフォーマンスが達成され得ることが示された。この発車間時間は、単一エレベータの往復運行時間をエレベータの数で除算したものとして計算され、往復運行時間は、交通統計に依存する。
【００８０】
上記のことに基づいて、上で提示された方法は、時間窓内で入手可能なものを超えたオンライン統計情報を組み入れることによって、また発車間時間の概念を採用することによって強化される。結果として得られるアップピーク用の「最適化の統計的方法」は、ロビーからのエレベータの発車に間隔を置くために、２つの「エレベータ解放条件」を定式化に追加することである。具体的には、乗客の流れが一定の場合、エレベータは、ロビーに止め置かれ、発車間時間τ毎に解放され、すなわち、
ｔm＋τ≦ｔm+1    （１９）
であり、ここで、ｔmおよびｔm+1は、連続するエレベータ発車時刻である。式（１９）を用いて、エレベータは、将来の乗客の到着を待つ。発車間時間τは、定常性の仮定がない場合、オンラインで計算されることが必要である。これは、時間窓内で入手可能な到着および行先と、時間窓を超えた統計的情報とを使用することによって、方法を拡張することによって行われ、後者は、各階における最近の乗客到着および乗客の行先に基づいて、統計的に得られる。突発的な到着に対処するため、エレベータ定員のあるパーセンテージが満たされたとき、エレベータは解放され、すなわち、
【００８１】
【数２１】
2008538737.tif 000022
【００８２】
であり、ここで、νは、エレベータ定員の与えられたパーセンテージである。
【００８３】
問題を解くために、上で提示された分解および調整手法が使用され、上記の２つの条件（１９），（２０）が、代理最適化フレームワーク内で個々の副問題を解くときに、ロビーにおけるエレベータの解放をトリガするために使用される。具体的には、特定のエレベータの副問題を解くときに、その他の副問題の決定が、それらの最新の利用可能値で取られ、２つの解放条件が、局所探索手順内に組み込まれる。
【００８４】
（低到着レートの場合の双方向用の待機戦略）
将来情報が僅かしかまたは全くない場合の双方向交通用の待機戦略を開発するための、発明者らのアイデアは、建物を複数のオーバーラップしない「ゾーン」に分割することであり、各ゾーンは、１組の隣接する階からなる。次の乗客が個々のゾーンに到着する確率が推定され、乗客割り当てをもたない「フリー」エレベータは、エレベータが必要とされる可能性の高いゾーンに待機させられる。エレベータの過剰な移動を回避するため、同じゾーン内の階は区別されない。
【００８５】
具体的には、フリーエレベータの合計数をＪ’とするように、エレベータはフリーになると仮定され、ここで、１≦Ｊ’≦Ｊである。次の乗客が階ｆに到着する確率Ｐfは、最近の到着情報に基づいて統計的に推定され、次の乗客がゾーンｎに到着する確率は、
【００８６】
【数２２】
2008538737.tif 000023
【００８７】
である。その場合、ゾーンｎに待機させる所望エレベータの数は、
【００８８】
【数２３】
2008538737.tif 000024
【００８９】
（小数点以下切り捨て）として計算される。様々なゾーンにすでに待機させてあるエレベータの数と
【００９０】
【数２４】
2008538737.tif 000025
【００９１】
を比較することによって、フリーエレベータを必要としているゾーンが識別される。その後、新しいフリーエレベータが、これらのゾーンの最寄の１つで待機させられる。この待機戦略は、単一アルゴリズムを形成するために最適化の統計的方法に組み込まれ、エレベータがフリーになったときに呼び出される。
【００９２】
（緊急モードにおけるスケジューリング）
通常運転中の良好なパフォーマンスに加えて、群エレベータスケジューリングは、国土安全保障問題によってもたらされた迅速脱出に対して、新しい意義を有する。高層の建物では、緊急避難の場合、階段は混雑し、上層階から地上までの長い距離の間に人々の歩調は落ち、年配者および障害者は全く階段を使用できないかもしれないので、階段は非効率的である。Ｈ．Ｈａｋｏｎｅｎ、「Ｓｉｍｕｌａｔｉｏｎ  ｏｆ  Ｂｕｉｌｄｉｎｇ  Ｔｒａｆｆｉｃ  ａｎｄ  Ｅｖａｃｕａｔｉｏｎ  ｂｙ  Ｅｌｅｖａｔｏｒｓ」、Ｌｉｃｅｎｔｉａｔｅ  Ｔｈｅｓｉｓ、Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｐｈｙｓｉｃｓ  ａｎｄ  Ｍａｔｈｅｍａｔｉｃｓ、Ｈｅｌｓｉｎｋｉ  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ、２００３年において示された。建物の一翼での化学兵器もしくは生物兵器の検出または火災などのある種のケースについて、避難用に「安全なエレベータ」を使用する可能性が、Ｊ．Ｋｏｓｈａｋ、「Ｅｌｅｖａｔｏｒ  Ｅｖａｃｕａｔｉｏｎ  ｉｎ  Ｅｍｅｒｇｅｎｃｙ  Ｓｉｔｕａｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｕｓｅ  ｏｆ  Ｅｌｅｖａｔｏｒｓ  ｉｎ  Ｆｉｒｅｓ  ａｎｄ  Ｏｔｈｅｒ  Ｅｍｅｒｇｅｎｃｉｅｓ、Ａｔｌａｎｔａ、Ｇｅｏｒｇｉａ、２００４年３月、２〜４ページにおいて示された。調整された緊急避難は、主要な脱出方法であり、各階の占有者は、調整された秩序立った方法で避難させられる。主要な脱出方法として、ここでは調整された緊急避難が考察され、各階の占有者は、調整された秩序立った方式で避難させられる。事前計画に基づいて、交通は、全体的な脱出時間を最小化するために、エレベータと階段との間でバランスが取られると仮定される。エレベータ脱出時間Ｔeは、エレベータに割り当てられたすべての乗客を避難させるのに必要とされる時間であり、すなわち、
【００９３】
【数２５】
2008538737.tif 000026
【００９４】
である。到着時刻、到着階、および行先階（すなわち、ロビー）を含む交通情報が、時間窓内で知られ、占有者は、乗客のエレベータへの割り当て決定に従うと仮定する。その場合、問題は、エレベータ脱出時間Ｔeを最小化すること、すなわち、
【００９５】
【数２６】
2008538737.tif 000027
【００９６】
であり、エレベータの位置および進行方向を与えられて、乗客のエレベータへの割り当て制約および個別エレベータ制約の影響を受ける。
【００９７】
式（２１）の目的関数は、エレベータに関して加法的ではない。したがって、先に説明された分解および調整手法は、この問題を解くために直接適用することはできない。それにも関わらず、Ｔcjを、エレベータｊがそれに割り当てられたすべての乗客を避難させるのに必要な時間、すなわち、
【００９８】
【数２７】
2008538737.tif 000028
【００９９】
であるとする。すべてのｊについて、Ｔcjが脱出時間Ｔeよりも小さいか、または等しいことを要求することによって、目的関数は、以下の１次不等式の「脱出時間制約」をエレベータ毎に１つ追加した、加法的形式で書くことができる。
【０１００】
Ｔcj≦Ｔe，∀ｊ    （２２）
（２２）とともに、最適化の統計的方法が適用される。加法的ラグランジュ関数が、非負の乗数｛λi｝を用いて割り当て制約を緩和し、非負の乗数｛μj｝を用いて脱出時間制約を緩和することによって得られ、すなわち、
【０１０１】
【数２８】
2008538737.tif 000029
【０１０２】
となる。その後、エレベータ副問題が構成されて、解かれ、Ｔeについての新しい「脱出時間副問題」が、以下に提示するように導入される。
【０１０３】
（２３）からエレベータｊに関連するすべての項を集めることによって、エレベータｊの副問題が、
【０１０４】
【数２９】
2008538737.tif 000030
【０１０５】
として得られ、個別エレベータ制約の影響を受ける。この副問題は、先に提示された順序最適化ベースの局所探索を使用することによって解くことができ、探索ツリーのノードは、「３パス（ｔｈｒｅｅ−ｐａｓｓａｇｅ）の発見的手法」を使用することによって、最初に粗く評価され、ランク付けされる。その後、トップランクのノードが、ＤＰを使用することによって正確に最適化され、Ｔcjは、以下のステージに関するコストによって表される。
【０１０６】
ｇk（ｘk，ｕk）＝ｔk+1−ｔk    （２５）
追加の脱出時間副問題は、式（２３）からＴeに関連するすべての項を集めることによって得られる。
【０１０７】
【数３０】
2008538737.tif 000031
【０１０８】
非正の１次係数を有する２次形式であることを考えると、この副問題は、容易に解くことができる。第ｎの反復において｛μj｝を更新するために使用される代理劣勾配の成分は、
【０１０９】
【数３１】
2008538737.tif 000032
【０１１０】
である。準最適解のために、先に説明されたことの後に、乗数更新反復が続く。
【０１１１】
本発明は、予想交通情報を用いて群エレベータ制御をモデル化し、改善する、一貫した方法を提供する。ルックアヘッド窓が、予想交通情報をモデル化するために最初に導入され、窓内の交通情報が知られ、窓外の情報は無視される。異なるレベルの予想交通情報を有するケースは、窓サイズを適切に調整することによってモデル化することができる。群エレベータスケジューリングの主要な特性が、上位レベルの乗客のかごへの割り当てと、下位レベルの個別かごの配車という、革新的な２レベルの定式化を確立するために使用される。この定式化は、建物形態および交通パターンについて特別な仮定はなされなかったので、異なる建物形態および交通パターンに適用可能である。単一かごダイナミクスの詳細は、個別かごシミュレーションモデル内に組み込まれる。したがって、定式化は、シミュレーションベースの動的プログラミング法を含む、単一かご配車用の異なる方策を組み入れる柔軟性をもつ。
【０１１２】
予想交通情報に基づいた準最適な乗客のかごへの割り当ておよび割り当てのための準最適な個別かごルーティングを達成するために、分解および調整手法が、結合乗客かご割り当て制約の緩和を通して使用される。かご副問題は、独立に解かれる。局所探索においては、発見的手法を使用することによって、乗客選択が、最初に速やかに評価され、ランク付けされる。このランク付け情報を用いて、トップ選択が、正確なパフォーマンスのために、単一かごルーティングを改善する、ステージ、状態、決定、およびコストの新規な定義を有する動的プログラミングによって評価される。その後、個別かごは、準最適解のために、代理最適化を使用することによって、ラグランジュ乗数の反復更新を通して調整される。
【０１１３】
本発明が、例および好ましい実施形態を参照しながら説明されたが、本発明の主旨および範囲から逸脱することなく、形態および細部に変更を施し得ることは、当業者であれば理解されよう。
【図面の簡単な説明】
【０１１４】
【図１】予想交通情報を使用して制御されるエレベータ群の図である。
【図２】乗客の到着時刻と降車時刻との間の時間メトリックを示す図である。
【図３】２レベルの解法を示すフローチャートである。
【図４】局所探索を示す図である。
【図５】ステージに関するコストを示す図である。
【図６】オーバーラップが７５％の非ゼロルックアヘッド移動窓を示す図である。
【図１】
2008538737.tif 000036
【図２】
2008538737.tif 000037
【図３】
2008538737.tif 000038
【図４】
2008538737.tif 000039
【図５】
2008538737.tif 000040
【図６】
2008538737.tif 000041