(57)【要約】本発明の目的は、乗り場呼びをエレベータ群におけるエレベータに割り当てるための新規な解決策を達成することであり、これにより各エレベータで受信する制御呼びは、可能な限り変更しない。これは、新たな割当て時に開始染色体集団中の一つの染色体として、前回の割当て時に選択された割当てオプションを用いることにより、遺伝的割当てを介して達成される。
2004533383.tif 000002
【特許請求の範囲】
【請求項１】
−一組の割当てオプションすなわち染色体を形成し、これらは、それぞれ、現在有効な乗り場呼びごとに呼びデータおよびエレベータデータを含む工程と、
−染色体ごとに適合性関数値を決定する工程と、
−終了基準に基づき、エレベータ群におけるエレベータにより処理される、最良の染色体を選択し、この染色体に応じて乗り場呼びを割り当てる工程とを含み、
エレベータ群中のエレベータの乗り場呼び装置を用いて発せられた呼びを割り当てる方法において、乗り場呼びの割当てを繰り返すとき、
−前記一組の染色体が形成される際に、割当ての開始条件が実質的に変っていない場合には、前回の割当て時に選択された最良の染色体を前記一組の染色体に加えて、選択結果を前記前回選択された最良の染色体に導くことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前回の割当て時に選択された最良の染色体には、該前回の割当て時に、それに対して計算された適合性関数値を与えることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、前回の割当て時とは、現在の割当て時に先行する割当て時であることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、
−前記最良の染色体の前記適合性関数値には、定数Kを乗じて、修正された適合性関数値を形成し、
−前記染色体は、修正された適合性関数値を与えて、前記一組の染色体に加えることを特徴とする方法。
【請求項５】
請求項４に記載の方法において、前記定数Kは、１より小さな値が与えられることを特徴とする方法。
【請求項６】
請求項４に記載の方法において、前記割当てのヒステリシスは、前記定数Kの値を変更することにより調整することを特徴とする方法。
【請求項７】
請求項１に記載の方法において、前記染色体は、世代を形成し、該世代から、新しい世代を、選択、異種交配、突然変異を介して遺伝的アルゴリズム法により形成することを特徴とする方法。
【請求項８】
請求項７に記載の方法において、前記最良の染色体は、新しい世代の形成前に最初の世代に加えることを特徴とする方法。
【請求項９】
請求項７に記載の方法において、前記最良の染色体は、新しい世代の形成前に第二のまたは後続する世代に加えることを特徴とする方法。
【請求項１０】
請求項１に記載の方法において、前記終了基準を満たす染色体の探索において、
−一つ以上の染色体は、少なくとも一つの遺伝子に関して突然変異を受け、このようにして得られた前記染色体の前記適合性関数値を決定し、
−染色体の突然変異は、前記終了基準が満たされるまで反復することを特徴とする方法。
【請求項１１】
請求項１０に記載の方法において、前記終了基準は、あらかじめ決定された適合性関数値、世代数、処理時間または集団の十分な同質性に到達したときに満たされることを特徴とする方法。
【発明の詳細な説明】
【発明の主題】
【０００１】
本発明は、エレベータ群に含まれるエレベータの乗り場呼び装置を介して与えられる各呼びを、そのエレベータ群におけるそれぞれのエレベータによって処理するように呼びを割り当てる方法および装置に関するものである。特に、本発明は、遺伝的アルゴリズムに基づく割当てシステムにおいて、繰返し定義される割当て決定を安定化する方法に関するものである。
【従来の技術】
【０００２】
乗客は、エレベータに搭乗したいとき、その階にある乗り場呼びボタンを押すことによりエレベータを呼ぶ。エレベータ群制御システムは、その呼びを受けて、その呼びを処理するのに最も適するであろうエレベータ群中の一のエレベータを決定しようと試みる。この動作が呼びの割当てである。割当て関数は、一種の最小化問題であり、その目的は、その関数の解として、一つ以上の選択されたコスト要因に基づく関数値を最小化するエレベータを見つけることである。
【０００３】
呼びおよびそれを処理するエレベータの数量が増加すると、この最小化問題は、より一層複雑なものとなる。これにより、必要とする計算量が、必然的に増大する。割当て処理において最小化すべき量は、乗客の待ち時間、乗客の移動時間、エレベータの停止回数、またはさまざまな手法で重み付けされたいくつかのコスト要因の組合せなどである。
【０００４】
従来、呼びに対して適当なエレベータを見つける際、個々の場合に応じて複雑な条件構成を用いる推論が行われる。この推論の最終目的は、エレベータ群の運行を記述する所定のコスト要因、たとえば、典型的には平均乗客待ち時間を最小化することである。エレベータ群の状態の可能な組合せは複雑であるから、条件構成もまた複雑で、かつギャップを生じやすく、換言すれば、最適な方法で制御が行われない状況が生じる。同様に、エレベータ群全体を総体的に考慮することは困難である。この典型的な例は、乗り場呼びを、それに最も近く、かつ呼びの方向に進行中のエレベータに割り当てる、従来の集合的制御である。
【０００５】
しかし、この簡単な最適化原理は、エレベータの集中化をもたらし、エレベータが揃って同一方向に移動し、したがって、エレベータ群全体としての性能が悪化する。
【０００６】
すべての可能なルート選択肢に対するコスト要因を決定しようとすれば、必要な計算作業量は、処理装置の能力をいとも簡単に超えてしまう。処理すべき呼びの数をCとし、建物がL台のエレベータを有するとき、異なるルート選択肢の数はN=LCとなる。ルート選択肢の数が、呼びの数の増加に伴い急激に増加するので、すべてのルート選択肢をシステム的に考慮することは、小さなエレベータ群においてさえ不可能である。これにより、ルート最適化の実際の適用は制限される。
【０００７】
フィンランド特許出願第951925号において、エレベータ群における乗り場呼び割当て方法を記載している。この方法は、複数の割当てオプションを形成することに基づくもので、各オプションは、呼びデータおよび各乗り場呼びに対するエレベータデータを有し、前記データは、合わせて、乗り場呼びを処理すべきエレベータを定義する。この後、コスト関数の値を、割当てオプションごとに計算し、一つ以上の割当てオプションをそれに含まれる一つ以上のデータ項目について変更し、そこで、このようにして得られた新しい割当てオプションのコスト関数値を計算する。この方法において、コスト関数に基づいて、最良の割当てオプションが選択され、現在有効な乗り場呼びがそれに従ってエレベータ群中のエレベータに割り当てられる。
【０００８】
フィンランド特許出願第951925号による解決策は、可能な全ルート選択肢の計算に比べて、必要な計算作業が実質的に軽減される。このような遺伝的アルゴリズムに基づく方法において、エレベータ群は、一つのエンティティとして扱われ、コスト関数はエレベータ群全体のレベルで最適化される。その最適化は、個々の状況、およびそれに合う手法を考慮することなく実行することができる。コスト関数を修正することにより、所望の運転モードを達成することができる。たとえば、乗客待ち時間、呼び時間、出発回数、走行時間、エネルギー消費量、ロープの磨耗、あるエレベータの使用が割高になる場合の個々のエレベータの運転、それぞれのエレベータの均一な使用等、またはこれらの所望の組合せを最適化することができる。
【０００９】
発生した乗り場呼びが多数ある場合、他のオプションよりも明らかに良好な単一の解または割当てオプションは、必ずしも見出されない。この状況に対して、いくつかの解が存在し、これらは、ほぼ等しく良好である。これが、マルチモダリティと呼ばれる事例である。
【００１０】
上述の遺伝的アルゴリズムは、統計的性質の検索方法であり、同じもしくはほとんど同じ開始値を使用しても、何度も検索を繰り返して、常に同一の解または割当てオプションを生じるという保証はない。割当てが連続的に行われる場合には、これが割当て決定上の不安定性として現れる。エレベータ群におけるエレベータに割り当てられる呼びは、割当て時ごとに変更される。しかし、エレベータ群に対していくつかのほぼ同様に良好な割当てオプションが存在することがわかっていれば、これらの割当てオプションのうちでどれを使用しても差を生じない。これに対して重要なことは、割当てオプションを再び選択する度にその割当てオプションを変更すべきではないことと、しかしながら、割当ての開始パラメータが同一またはほとんど同一のままである限り、一旦選択された解を維持すべきことである。
【００１１】
実際に、これが意味するのは、エレベータ群における状況が変らないままであれば、すなわち、それ以上の呼びを受信せず、かつ、その群にエレベータを加えたり除去したりしなければ、ある一組の呼びに対して選択されたエレベータルートは、最後の呼びを処理するまで維持すべきであることである。これが事実でなければ、エレベータ群におけるエレベータは、二分の一秒毎に新たな制御データを受信するかもしれず、これをエレベータが実行するのは煩雑であり、かつエレベータ群およびシステムが不安定になる。
【００１２】
本発明の目的は、新規な形式の割当て方法を開示することにある。
【００１３】
本発明の目的は、特に、従来技術の割当て方法に見られる上述の欠点を解消し、または少なくともそれらの本質的改善策を提供することにある。
【００１４】
本発明の他の目的は、従来技術の方法よりも、本質的な安定性および信頼性のある割当て方法を開示することにある。
【００１５】
さらに本発明の他の目的は、割当て問題およびエレベータ群制御の解の安定化を可能にして、問題とする割当てオプションが、統計的選択処理によって得られる最良解の一つを生じさえすれば、無変更またはほぼ無変更の一組の呼びを、無変更の割当てオプションによって処理することである。
【００１６】
本発明の構成要件に関しては、特許請求の範囲を参照する。
【発明の簡単な説明】
【００１７】
本発明の目的は、乗り場呼びをエレベータ群におけるエレベータに割り当てるための新規な解決策を、各エレベータで受信する制御呼びを可能な限りほとんど変更しないような手法で実現することにある。
【００１８】
本発明の遺伝的方法において、呼びをエレベータ群におけるエレベータに割り当てるために、いくつかの割当てオプション、すなわち染色体が生成され、そのそれぞれは、発行した各乗り場呼びに対する呼びデータ項目およびエレベータデータ項目を含み、これらのデータ項目または遺伝子は、共に、各乗り場呼びを処理すべきエレベータを決定する。生成された各染色体に対して、ある適合性関数値が定められる。次に、一つ以上の染色体が少なくとも一つの遺伝子に関して変更を受け、こうして得られた染色体に対する適合性関数値が決定される。検索、すなわち新たな染色体の生成は、所定の終了条件が満たされるまで続けられ、これにより最良の染色体が適合性関数値に基づき選択され、かつ各呼びがこの解に応じてエレベータ群におけるエレベータに割り当てられる。呼びの割当ては、異なる要因によって、たびたび繰り返し行われる。実際には、割当ての反復サイクルは、必要であれば二分の一秒またはこれより短くすることもできる。
【００１９】
本発明の方法において、呼び割当て決定のための新たな検索、または新たな割当てサイクルを開始する前に、割当ての開始条件が実質的に変っていない場合には、前回選択された最良の染色体を染色体の組に加えて選択結果を前回選択された最良の染色体に導くようにする。
【００２０】
本発明の方法において、一組の割当てオプションすなわち染色体が一つの世代を形成し、この世代から、一般に、最良のものが再生のために選択されて、染色体の新しい世代を生成する。新しい世代は、選別、異種交配および/または突然変異を介して、遺伝的アルゴリズムの手法によって、選択された染色体から形成される。
【００２１】
本発明における方法は、所望の目標に達するまで、すなわち、たとえば、ある適合性関数値に到達するか、もしくはある数の新世代が形成されるまで継続することができ、または、この方法は、ある処理時間を経過すると中断することができる。他の適用可能な終了基準として、集団の十分な同質性を用いることもできる。
【００２２】
本発明の方法において、最良の染色体は、新しい世代が形成される前に第１の世代に加えられる。また、最良の染色体は、新しい世代が形成される前に第２の世代または後続する世代の一つに加えてもよい。さらに、先行のサイクルの最良染色体の適合性関数値には、定数Kを乗じてもよく、この定数Kは、好ましくは１より小さく、これにより適合性関数値を修正する。その後、修正された適合性関数値を備えた染色体は、染色体の組に加えられる。
【００２３】
「良すぎる」個体または染色体が、新たな検索サイクル中、すなわち新たな割当ての時間に、集団に加えられた場合、これは遺伝的割当てを介してなされる割当て決定の安定性を増大する。単に、「良すぎる」解が先行の割当てサイクルの最終結果であるから、集団の早すぎる収束をもたらし、換言すれば、集団を先行サイクルの解へと導く。遺伝的割当てを記載する関係文献によれば、早すぎる収束は、明らかに有害であり、これは、開始世代に入りこんだ良すぎる個体が、その遺伝子を集団に伝達することにより、最良の選択肢の検索を支配するためであり、その結果、集団は、組の問題に対する解に到達しない。しかし、本発明は、開始値が同一またはほぼ同一であるとき、先行サイクルの解に達することを明確に目的としている。
【００２４】
本発明の解決策は、割当て決定の安定化のための優れた解を提供する。エレベータ群における状況が変化しないままで、追加の呼びを受信せず、かつエレベータを群から除去したり群に加えたりしなければ、既に見出されたエレベータルートは、十分長期に維持するべきである。一方、システム内に新たな呼びが発生するか、またはエレベータの状況が変化すると、検索空間の形も変化し、前回選択された良好な解は、もはや検索空間における最良解でもなく、また最良解の一つでもない。それは、選択処理を介して開始世代に含まれる他の劣等な解のうちの一つの劣等な解である。
【００２５】
本発明の解決策は、エレベータ群におけるエレベータに対する最良の割当て選択肢の選択の際のランダム性を実質的に低減するものである。本発明を適用することにより、遺伝的割当てを用いるエレベータ制御システムにおいて、エレベータ制御決定を安定化するために、統合的装置を実現することができる。さらに、本発明は、ヒステリシス制御装置の導入を可能にする。
【００２６】
以下に、本発明は、添付図面を参照して、実施例によって詳細に説明する。
【００２７】
図１は、１、２、３…、16と番号付けたビルの階を表わす図である。エレベータ群は、三台のエレベータLIFT０、LIFT１およびLIFT２を含み、これらのエレベータは、昇降路２、４および６内を移動し、これらのエレベータかごは、参照番号８、10および12で対応して示されている。これらのエレベータかごは、それぞれ、３階、９階および４階に位置し、それらの移動方向は昇降路の上部に表わした矢印14で示され、これによれば、エレベータかご８および12は、上昇方向に移動中であり、エレベータかご10は、下降方向に移動中である。
【００２８】
昇降路の横には、発生した下降方向および上昇方向への乗り場呼びに対する縦列16および18がある。乗り場呼びは、矢印20によって示される。＊印は、エレベータかご10から１階へ発せられたかご呼びを示す。矢印24は、乗り場呼びが発せられた階を示し、エレベータかごは、その呼びに対して割り当てられる。これにより、11階からの乗り場呼びは、エレベータLIFT０に割り当てられ、７階からの乗り場呼びは、エレベータLIFT１に割り当てられ、14階からの乗り場呼びは、エレベータLIFT２に割り当てられる。
【００２９】
縦列26および27は、エレベータ染色体が使用される場合の割当てオプションの形成を表わしたもので、一つの遺伝子がそれぞれの乗り場呼びに対応している。縦列26は、発生した乗り場呼びを順に示しており、図１の例では、最上階の番号が一番上に、最低階の番号が一番下に位置している。縦列27は、発生したエレベータ染色体を含んで、この染色体は、乗り場呼びの数に対応して、五個の遺伝子30から構成され、これらの遺伝子は、その呼びを処理するエレベータに関する情報を含む。各乗り場呼びに対して、一つの遺伝子が与えられる。矢印32は、遺伝子の形成を表わすものである。エレベータ染色体27および遺伝子102に応じて、エレベータLIFT０は、11階からの呼びを処理する。遺伝子100および101に応じて、エレベータLIFT１は、４階および７階からの呼びを処理し、同様に、遺伝子103および104に応じて、エレベータLIFT２は、13階および14階からの呼びを処理する。エレベータ染色体の形成中に、上昇および下降方向の有効な乗り場呼びは、エンコードされて、エレベータ染色体中の遺伝子の位置が乗り場呼びに関する情報を担持する。割当てが実施された後で、エレベータ染色体中の情報は、対応する乗り場呼びにデコードされる。
【００３０】
図２において、染色体形成後の遺伝的割当ての原則を表わす。染色体から、選択された数Npのエレベータ染色体を含む集団34が生成される。染色体１〜npは、実在する呼びに対して可能な割当て選択肢であり、図１に示された状態、すなわち、４階、７階、11階、13階および14階からの処理すべき五つの下降呼びが存在する状態に相当する。まず、集団34に含まれる染色体内の遺伝子ごとに、無作為にエレベータ番号が与えられ、または、利用可能であれば事前の情報が適用される。さらに、本発明により、一つの染色体80の遺伝子は、先行の割当てサイクルで選択された染色体の遺伝子の値が、左から右に、LIFT０、LIFT０、LIFT２、LIFT２、LIFT１の順に割り付けられる。このとき、これは染色体値の一選択例に過ぎず、かつ図１における最良の選択肢を示すものとは限らないことに注意する。
【００３１】
さらに、集団における他の染色体もまた、無作為に選択され、あるいは既知の選択基準を用いた遺伝子値が与えられる。フィンランド特許出願第951925号には、最良染色体の割当ておよび選択における適合性関数28の、計算および使用の詳細な説明が含まれている。したがって、本出願ではその詳細については記載しない。
【００３２】
以上、本発明をその好ましい実施例を参照して説明した。しかし、本発明は、これらの実施例に限定されることを意図するものではなく、提示される特許請求の範囲内で多数の変更が可能であることはいうまでもない。
【図面の簡単な説明】
【００３３】
【図１】エレベータ染色体の形成を表わした図である。
【図２】本発明にかかる開始時の染色体集団を表わした図である。
【図１】
2004533383.tif 000003
【図２】
2004533383.tif 000004
【国際公開パンフレット】
2004533383.tif 000005
2004533383.tif 000006
2004533383.tif 000007
2004533383.tif 000008
2004533383.tif 000009
2004533383.tif 000010
2004533383.tif 000011
2004533383.tif 000012
2004533383.tif 000013
2004533383.tif 000014
2004533383.tif 000015
2004533383.tif 000016
2004533383.tif 000017
2004533383.tif 000018
2004533383.tif 000019
2004533383.tif 000020
【国際調査報告】
2004533383.tif 000021
2004533383.tif 000022