FI112856B - Menetelmä ja laitteisto matkustajien allokoimiseksi geneettisellä algoritmilla - Google Patents

Description

x 112856

MENETELMÄ JA LAITTEISTO MATKUSTAJIEN ALLOKOIMISEKSI GENEETTISELLÄ ALGORITMILLA

Keksintö kohdistuu patenttivaatimuksen 1 johdanto-osan mu-5 kaiseen menetelmään ja patenttivaatimuksen 8 laitteistoon matkustajien allokoimiseksi hissikoreihin.

Kun matkustaja haluaa ajaa hissillä, hän tilaa hissin kerrokseen asennetusta ulkokutsunapista. Hissiryhmän ohjaus 10 vastaanottaa ko. hissin tilauksen ja pyrkii päättelemään, mikä hissiryhmään kuuluva hissi pystyy parhaiten palvelemaan kutsun. Tämä toiminta on kutsujen allokointia. Allokoinnin ongelmana on löytää hissi, joka minimoi tietyn kustannustekijän. Allokoinnissa voidaan minimoida matkustajien odotus-15 aikaa, matkustajien matkustusaikaa, hissien pysähdysten lukumäärää tai jotakin useiden kustannustekijöiden eri tavalla painotettua yhdistelmää.

Perinteisesti, haettaessa kutsulle sopivaa hissiä, päättely 20 tehdään tapauskohtaisesti monimutkaisin ehtorakentein. Tämänkin päättelyn lopullisena tavoitteena on minimoida jotain hissiryhmän toimintaa kuvaavaa kustannustekijää, tyypillisesti esim. matkustajien keskimääräistä odotusaikaa. Koska hissiryhmän tila-avaruus on monimutkainen tulee ehtoraken-• 25 teistäkin monimutkaisia ja niihin jää helposti aukkoja, syn tyy tilanteita joissa ohjaus ei toimi parhaalla mahdollisel-; la tavalla. Samoin on vaikeata ottaa huomioon koko hissiryh- ; mää kokonaisuutena. Tästä tyypillinen esimerkki on perintei- ." . nen koontaohjaus, jossa ulkokutsulle annetaan sitä lähinnä ,·* , 3 0 oleva, kutsun suuntaan ajava hissi. Tämä yksinkertainen op- timointiperiaate johtaa kuitenkin hissien ryhmittymiseen, . jolloin hissit ajavat rintamassa samaan suuntaan ja sitä

I t I

kautta hissiryhmän suorituskyvyn laskuun kokonaisuutena.

:; 35 Keksinnön tavoitteena on aikaansaada uusi menetelmä ja lait- .teisto matkustajien allokoimiseksi geneettisellä algoritmil-la. Keksinnön mukainen menetelmä tunnetaan patenttivaatimuk-; ’ sen 1 tunnusmerkkiosasta. Keksinnön mukainen laitteisto puo- '··' lestaan tunnetaan patenttivaatimuksen 8 tunnusmerkkiosasta.

2 112856

Keksinnönmukaisessa ratkaisussa käsitellään ulkokutsujen allokoinnin sijasta matkustajien allokointia. Koska matkustajien allokoinnissa jokainen matkustaja antaa kohdekerroksen-sa, ja koska lähtökerros tiedetään kutsunantolaitteen si-5 jainnista, niin tunnetaan järjestelmään pyrkivät matkustajat yksikäsitteisesti. Näillä täydellisillä lähtötiedoilla his-siryhmäohjaus pääsee etsimään matkustajalle edullista hissiä, ts. voidaan tehdä matkustajien allokointia. Perinteisessä ylös/alas kutsujen allokoinnissa matkustajista saatava 10 tieto on epätäydellistä ja siinä joudutaan tyytymään matkustajien sijasta kutsujen allokointiin, ts. etsitään kutsulle edullista hissiä.

Päätöksenteko perustuu geneettisiin algoritmeihin. Aluksi 15 luodaan joukko ratkaisuvaihtoehtoja eli kromosomeja, joiden hyvyys allokointipäätökseksi määritetään. Tämän jälkeen ratkaisuvaihtoehto joukkoa aletaan jalostaa geneettisin menetelmin, joihin kuuluvat mm. edustavien ratkaisuvaihtoehtojen valinta seuraavaan sukupolveen ja vanhemmiksi jälkeläisille, 20 jälkeläisten eli uusien ratkaisuvaihtoehtojen muodostaminen risteyttämällä kunkin ajanhetken parhaimpia ratkaisuvaihtoehtoja toistensa kanssa ja/tai kohdistamalla mutaatioita eli muutoksia luotujen jälkeläisten geeneihin. Kullekin jälkeläiselle on määritettävä hyvyys, jonka jälkeen voidaan » • 25 luoda seuraava ratkaisuvaihtoehtojen sukupolvi tai annetaan ' ratkaisujoukon paras vaihtoehto ongelman ratkaisuksi, jos : ; lopetuskriteeri täyttyy. Geneettinen matkustajien allokointi f ; eroaa aiemmista geneettisistä allokointimenetelmistä ennen- . kaikkea siinä, että perinteisten ylös/alas -ulkokutsujen si- .··, 30 jasta allokoinnissa käsitellään nimenomaan matkustajia eli päätetään mikä hissikori palvelee kutakin matkustajaa toisin ,, , kuin aiemmissa menetelmissä, joissa päätetään mikä hissikori » t ‘.j palvelee kutakin ulkokutsua. Tämä on mahdollista siksi, että *; * lähtökerroksessaan kukin matkustaja antaa kutsunantolait- ; : : 35 teella kohdekerroksensa, jolloin yksittäisten matkustajien tiedot tunnetaan hissijärjestelmässä. Hissijärjestelmän on , \ myös annettava kullekin matkustajalle tieto häntä palvele- vasta hissistä. Kun tieto on annettu matkustajalle, hänelle tarjottua hissikoria ei enää yleensä saisi vaihtaa.

40 3 112856

Keksinnönmukaisen ratkaisun etuna voidaan mainita se, että matkustajien allokoinnin tarjoamalla tarkalla informaatiolla ja esitetyllä menetelmällä on mahdollista parantaa matkustajien palvelutasoa. Järjestelmä pystyy myös tuottamaan talon 5 liikennetilastoa, joka sisältää muun muuassa matkustajien tiedot ja liikkeet rakennuksessa sekä tuottamaan normaalin toiminnan aikana matkustajien palvelua kuvaavat tunnusluvut, kuten esimerkiksi matkustajien odotusajat.

10 Keksintöä kuvataan seuraavassa yksityiskohtaisesti sen erään suoritusesimerkin avulla viitaten piirustuksiin, joissa — kuvio 1 esittää järjestelmän arkkitehtuurin, joka kuvaa järjestelmän laitteistoa, 15 - kuvio 2 esittää matkustajien allokoinnin toimintaa, ja - kuvio 3 esittää esimerkin matkustajien koodaamiseksi kromosomeiksi

Kuvassa 1 on esitetty järjestelmän arkkitehtuuri. Kun mat-20 kustaja haluaa tilata hissin, hän ilmoittaa lähtökerrokses-saan kutsunantolaitteella haluamansa määränpääkerroksen. Kutsunantolaite kertoo matkustajalle häntä palvelemaan tulevan hissin. Järjestelmän toiminta käydään seuraavassa läpi vaihe vaiheelta. Kun matkustaja antaa kutsunantolaitteelle ; 25 12 kohdekerroksensa, niin kutsunantolaite muodostaa siitä ! * sanoman "uusi matkustaja” , joka välitetään hissiryhmäohja- : : ukselle. Sanoma sisältää seuraavat tiedot: » * laitetunniste + lähtökerros + lähtöpuoli + kohdekerros 30 + kohdepuoli , Sanoma käsitellään matkustajakirjanpidossa 16, joka pitää kirjaa matkustajista ja heidän tiedoistaan. Kirjanpito liit-tää saapuviin tietoihin yksikäsitteisen matkustajan tunnuk-; ; 35 sen, aika- ja hissitiedot ja tallettaa nämä tiedot (lihavoi- ' ’ ; tu) : matkustajatunniste + lähtökerros + lähtöpuoli + kohde-kerros + kohdepuoli + matkustajan saapumisaika lähtö-40 kerrokseen + matkustajan koriin astumisaika + matkusta- 4 112856 jän saapumisaika kohdekerrokseen + hissi + kori + arvioitu hissikorin saapumisaika lähtökerrokseen Tässä vaiheessa ovat vielä lihavoimattomat kentät määritte-5 lemättömiä. Tiedot talletettuaan matkustajien kirjanpito 16 käynnistää matkustajien allokoinnin lähettämällä sanoman "tee allokointi'’. Matkustajien allokointi 18 pyytää matkus-tajakirjanpidolta 16 kaikki järjestelmässä olevat matkustajat tietoineen. Tämän jälkeen se lähtee hakemaan kaikille 10 allokoimattomille matkustajille hissikoria. Allokoimaton matkustaja on matkustaja, jolle ei ole kohdistettu hissikoria. Kun matkustajien allokointi on päättänyt kunkin allo-koimattoman matkustajan palvelevan hissikorin, se lähettää jokaisesta matkustajasta sanoman ''allokoitu matkustaisi ja"matkustajien kirjanpitoon 16. Sanoma sisältää tiedon matkustajaa palvelevasta hissikorista: matkustajatunniste + hissi + kori + arvioitu hissikorin saapumisaika lähtökerrokseen 20

Matkustajakirjanpidossa 16 päivitetään tieto siitä, mikä hissikori on varattu palvelemaan kyseinen matkustaja. Tässä vaiheessa matkustajasta tiedetään siis seuraavat lihavoidulla tekstillä kirjoitetut tiedot: i 25 matkustajatunniste + lähtökerros + lähtöpuoli + kohde-kerros -f kohdepuoli + matkustajan saapumisaika lähtö-; kerrokseen + matkustajan koriin astumisaika + matkusta- ’ ; jän saapumisaika kohdekerrokseen + hissi + kori + arvi- 30 oitu hissikorin saapumisaika lähtökerrokseen

Matkustajien kirjanpito 16 toimittaa kutsunantolaitteelle 12 sanoman "kuljetuksenne", jolla matkustajalle kerrotaan näyttölaitteella 14 häntä palveleva hissikori ja mahdolli-; : 35 sesti arvio hissin saapumisajasta: laitetunniste + matkustajatunniste + lähtökerros + lähtöpuoli + kohdekerros + kohdepuoli + hissi + kori + arvioitu hissikorin saapumisaika lähtökerrokseen 40 5 112856

Tieto siitä, mikä hissikori matkustajan palvelee, välitetään myös kyseisen korin omistavalle hissille 19.

Hissi 19 pitää matkustajista omaa kirjanpitoa. Hissillä on 5 matkustajia varten kaksi listaa. Toisessa listassa ovat koriin pyrkivät matkustajat ja toisessa korissa parhaillaan olevat matkustajat. Uusi allokoitu matkustaja lisätään ensin koriin pyrkivien matkustajien listalle. Samalla matkustajan lähtökerroksesta tehdään hissin ajoreitille yksi pysähdys-10 kerros. Kun hissi pysähtyy johonkin kerrokseen hissi käy läpi molemmat matkustajalistansa. Matkustaja siirretään koriin pyrkivien matkustajien listalta korissa olevien matkustajien listalle jos (a) hissin pysähdyskerros on sama kuin matkustajan lähtökerros ja (b) hissin on mahdollista jatkaa samaan 15 suuntaan kuin matkustajan kohdekerros edellyttää. Tässä tapauksessa hissi 19 lähettää "matkustaja koriin" -sanoman: matkustajatunniste + matkustajan koriin astumisaika 20 Samalla hissi asettaa ajosekvenssiinsä tulevaksi pysähdys-kerrokseksi koriin siirtyneen matkustajan kohdekerroksen.

Matkustajien kirjanpito päivittää ''matkustaja koriin'' sanoman tiedoilla ko. matkustajan koriin astumisajan. Tämän ; 25 jälkeen matkustajasta tiedetään seuraavat tiedot (lihavoi- : tu) : matkustajatunniste + lähtökerros + lähtöpuoli + kohde-kerros + kohdepuoli + matkustajan saapumisaika lähtö-30 kerrokseen + matkustajan koriin astumisaika + matkusta jan saapumisaika kohdekerrokseen + hissi + kori + his-sikorin saapumisaika lähtökerrokseen

Matkustajien kohdekerrokset käsitellään vastaavalla tavalla.

, ; 35 Kun hissi pysähtyy kerrokseen hissi käy läpi listansa koris- sa olevista matkustajista. Matkustaja poistetaan tältä lis-, ', taita jos hissin pysähdyskerros on sama kuin matkustajan ' ; ‘ kohdekerros. Tällöin matkustaja on päässyt perille ja hissi lähettää "matkustaja perillä" - sanoman: 40 c 112856

O

matkustajatunniste + matkustajan saapumisaika kohdekerrokseen

Matkustajien kirjanpito päivittää " matkustaja perillä'' 5 sanoman tiedoilla ko. matkustajan saapumisajan kohdekerrok-seen. Lopuksi matkustajien kirjanpito poistaa ko. matkustajan omasta kirjanpidostaan ja lähettää tilastoja keräävälle yksikölle tiedot palvellusta matkustajasta "palveltu matkustaja' '-sanomalla, jossa on siis ajantasalla kaikki matkusta-10 jaan liittyvät tiedot: matkustajatunniste + lähtökerros + lähtöpuoli + kohde-kerros + kohdepuoli + matkustajan saapumisaika lähtö-kerrokseen + matkustajan koriin astumisaika + matkusta-15 jän saapumisaika kohdekerrokseen + hissi + kori + his- sikorin saapumisaika lähtökerrokseen

Yksittäisistä matkustajista voidaan näillä tiedoilla muodostaa rakennuksen liikennetilastot 11, joilla kuvataan matkus-20 tajaliikennettä eri kerrosten välillä tyypillisesti kellonajan mukaan. Tämä on vaikeaa perinteisessä järjestelmässä, jossa pystytään arvioimaan vain kerrokseen alhaalta ja ylhäältä tulevat ja lähtevät liikennekomponentit, mutta ei tarkasti kerrosten välistä liikenteellistä yhteyttä. Samoin ; 25 matkustajien tiedoista voidaan muodostaa hissiryhmän palve- ; : lutasoa kuvaavat täsmälliset perustunnusluvut 13, tyypilli- : sesti kellonajan mukaan: matkustajien odotusaika, ajoaika ja matkustusaika. Myös nämä tiedot ovat epätarkkoja perinteisissä ohjausjärjestelmissä.

,: , 3 0

Kuviossa 2 on esitetty matkustajien allokoinnin toiminta. ,, , Aluksi kaikkien matkustajien tiedot luetaan 2 0 matkustajien allokoinnin omaan paikalliseen tietovarastoonsa 22. Tämän '>·' jälkeen matkustajat ryhmitellään 23 allokoituihin 24 ja al- : ; , 35 lokoimattomiin 26 matkustajiin. Allokoiduilla matkustajilla on hissikori jo varattuna, ts. tiedetään mikä hissikori kun-, kin matkustajan palvelee, kun taas allokoimattomille matkus- tajille ei ole varattu hissikoria. Molemman tyyppiset mat- ' kustajat viedään hissiryhmän mallille 28, joka sisältää his- 40 sien käyttäytymissäännöt ja perustiedot, kuten nopeus, kori- 112856 7 en koot, hissien lukumäärä jne. Perusideana on, että mallille vietäessä jokaisella matkustajalla on osoitettuna hissi ja hissimalli selvittää sille tarjotun ratkaisuvaihtoehdon hyvyyden 30, joka voi olla esimerkiksi matkustajien odotus-, 5 ajo- tai matkustusaika tai näiden yhdistelmä. Koska matkustajien allokoinnissa tunnetaan yksittäiset matkustajat, voidaan em. tunnusluvut laskea hissimallissa hyvinkin tarkasti.

Jokaisella matkustajalla on siis hissiryhmän mallille vietä-10 essä määritetty hissikori. Allokoiduille matkustajille hissi on lopullisesti kiinnitetty eikä sitä voi enää vaihtaa, kun taas allokoimattomille matkustajille geneettinen algoritmi tarjoaa eri hissikorivaihtoehtoja ja etsii periaatteensa mukaan allokoimattomille matkustajille hissikorit, joita käyt-15 tämällä matkustajien palvelu on mahdollisimman hyvää hy-vyysarvolla ilmaistuna. Geneettiseen algoritmiin kuuluva koodausyksikkö 34 lisää jokaisesta allokoimattomasta matkustajasta yhden geenin geneettisen algoritmin kromosomirakenteeseen. Samalla se tarkistaa lähtö- ja kohdekerrosten pal-20 velurajoitukset 33 uiko- ja korikutsulukituksilta sekä eri ohjaustoimintojen kontrolliyksiköiltä. Lisätessään geenin koodausyksikkö 34 täyttää myös koodikirjaa 35, joka kertoo minkä tyyppisestä geenistä on kyse. Esimerkiksi kerroksessa vapaana seisovalle hissille pitää kiinnittää suunta. Etukä-.'v| 25 teen on vaikeata päätellä kumpaan suuntaan hissin olisi ", edullisempi lähteä palvelemaan sille allokoituja matkusta- : . , jia. Ongelmasta selvitään, kun vapaan hissin tapauksessa !' ' otetaan kromosomiin mukaan hissin suuntaa 3 6 edustava geeni " ja annetaan geneettisen haun selvittää myös hissille edulli- ’· 3 0 sempi aloitussuunta. Dekoodausyksikkö 32 purkaa koodikirjan * ' avulla geneettisen haun aikana geneettisen algoritmin muo dostamat kromosomit hissimallin ymmärtämään muotoon. Geneet- - * : ' ί tisen haun päätyttyä komentojen toimeenpanoyksikkö hakee 1 ; ratkaisukromosomin GA (geneettinen algoritmi) -ytimeltä 38 35 ja käyttää dekoodausfuntiota. Tämän tuloksena dekoodausyk- sikkö asettaa allokoimattomien matkustajien hissitietokent-tiin löydetyn ratkaisun mukaiset hissikorit. Lopuksi toi-: ; meenpanoyksikkö 39 lähettää jokaisesta allokoimattomasta matkustajasta edellisessä kappaleessa kuvatun "allokoitu 40 matkustaja" -sanoman. Geenin sijainti kromosomissa määrittää 8 112856 matkustajan identiteetin ja geenin arvo määrittää hissiko-rin, joka palvelee matkustajan. Vapaiden hissien suuntagee-nit voidaan koodata esimerkiksi matkustajageenien perään kromosomin loppuun. Sinänsä geenien järjestyksellä ei ole 5 merkitystä, koska koodikirja kertoo geenin tyypit ja ominaisuudet. Korit ja hissit liitetään yhteen vasta hissimallis-sa.

Kuviossa 3 esitetään esimerkin avulla kromosomien ja niiden 10 geenien muodostaminen matkustaja-allokoinnissa. Kuvan esi-merkkirakennuksessa on kymmenen kerrosta ja neljä yksikoris-ta hissiä, joiden tunnistenumerointi ja suuntatiedot esitetään kunkin hissikuilun yläpuolella. Hissit sijaitsevat hissikuiluissaan siten, että hissi 1 on alimmassa kerroksessa 15 1, hissi 2 kerroksessa 4, hissi 3 kerroksessa 7 ja hissi 4:n paikka on kerroksessa 10. Matkustajat ja heidän antamat koh-dekerrokset esitetään heidän menosuunnasta riippuen joko hissiryhmän vasemmalla tai oikealla puolella. Matkustajat, jotka ovat antaneet kutsun alaspäin kuvataan hissiryhmän va-20 semmalla puolella. Esimerkissä heitä on neljä kappaletta. Ylimmästä kerroksesta eli kerroksesta 10 kutsun antanut matkustaja haluaa mennä alimpaan kerrokseen 1. Kerroksesta 8 on annettu kaksi kutsua alassuuntaan, joista toinen on kerrokseen 5 ja toinen kerrokseen 1. Kerroksesta 5 alaspäin pyrki-• 25 vän matkustajan kohde on kerros 1. Vastaavalla tavalla mat- : kustajät, joiden suunta on ylöspäin, esitetään hissiryhmän ; oikealla puolella. Kerroksessa 3 on yksi matkustaja, jonka ; määränpää on kerros 7. Kerroksessa 5 on kaksi henkilöä koh- , teenaan kerros 10, jonne on myös menossa kerroksen 8 matkus- 30 taja. Esimerkissä on sekä allokoimattomia että allokoituja matkustajia. Alassuuntaan kerroksessa 5 on allokoitu matkus-, , taja hissille 3. Muut matkustajat ovat allokoimattomia. Vas- ; taavasti ylössuuntaan antaneista matkustajista kerroksessa 3 on allokoitu matkustaja hissille 1 ja muut matkustajat ovat : ; : 3 5 allokoimattomia.

, Kromosomin muodostamisen pääperiaate on se, että kutakin kutsun antanutta, kerros tasolla olevaa matkustajaa vastaa •t geeni ja geenin arvo eli alleeli ratkaisee sen, mikä hissi- 40 kori kunkin yksittäisen matkustajan palvelee. Lisäksi samal- 9 112856 la kerrostasolla olevia matkustajia, joilla on sama määränpää, voidaan haluttaessa käsitellä yhtenä geeninä eli erityisenä matkustajaryhmägeeninä. Aivan kuin yksittäistä matkustajaa koskevan geenin eli matkustajageenin arvo tarkoit-5 taa, mikä hissikori hänet palvelee, vastaavalla tavalla mahdollisen matkustajaryhmägeenin arvo kertoo, mikä hissikori heidät palvelee. Esimerkki matkustajaryhmägeenistä on kerroksessa 5, missä matkustajaryhmägeeni pitää sisällään kaksi matkustajaa, joilla molemmilla on sama määränpääkerros 10. 10 Matkustajaryhmä voidaan muodostaa, jos kerroksessa on samaan kohteeseen meneviä matkustajia.

Esimerkissä kromosomi muodostuminen esitetään hissiryhmän alapuolella. Kerrostasoilla olevista matkustajista sekä ker-15 roksen 5 matkustajaryhmästä lähtevillä nuolilla osoitetaan geenien sijainti kromosomissa. Kromosomissa alaspäin haluavat matkustajat sijaitsevat lähtökerroksiensa mukaan laskevassa järjestyksessä ennen ylöspäin haluavia matkustajia, jotka ovat kromosomissa lähtökerrostensa mukaan nousevassa 20 järjestyksessä. Näin ollen kerroksessa 10 olevaa matkustajaa vastaa kromosomin ensimmäinen geeni, jonka jälkeen tulevat kerroksen 8 alaspäin suuntaavia matkustajia tarkoittavat geenit. Näistä kahdesta kerroksessa 8 olevasta matkustajasta ei ole muodostettu matkustajaryhmägeeniä, koska heillä on 25 eri määränpää. Neljäntenä geeninä on kerroksen 5 alaspäin haluava matkustaja. Viidentenä geeninä on kerroksen 3 ylös- päin menevä matkustaja. Kuudentena geeninä tulee kerroksen 5 ; matkustajaryhmägeeni, joka kokoaa molemmat kerrokseen 10 ha- : luavat matkustajat yhdeksi geeniksi. Matkustajaryhmägeeniä ‘ , 30 seuraa seitsemäs geeni, joka on kerroksen 8 ylöspäin menevää matkustajaa tarkoittava geeni. Geenien keskinäisellä järjes-·_ tyksellä ei sinänsä ole merkitystä, koska geenin positio kromosomissa voidaan koodata vapaasti ilmaisemaan mikä geeni on kyseessä.

35

Kuvion 3 geenien lukumäärä voi vaihdella 5:stä 8:aan riippu-. '. en siitä kuinka kerroksessa 5 olevat, saman määränpään omaa- vat matkustajat käsitellään ja otetaanko allokoidut matkus-*"’ tajät mukaan kromosomirakenteeseen. Kahdesta kerroksesta 5 40 kerrokseen 10 suuntaavasta matkustajasta voidaan muodostaa 10 112856 matkustajaryhmägeeni tai vaihtoehtoisesti kumpikin matkustaja voidaan käsitellä itsenäisesti, jolloin heitä molempia vastaa yksi geeni kromosomin rakenteessa. Riippuen valitusta käsittelytavasta heitä vastaa joko yksi tai kaksi geeniä 5 kromosomin rakenteessa.

Kuvan esimerkissä on kaksi matkustajaa, joille on allokoitu hissikori aiemmalla allokointikerralla, muille matkustajille se tässä tapauksessa on etsittävä. Kerroksen 5 matkustajalle 10 on allokoitu hissille 3. Vastaavasti kerroksen 3 matkustajalle on allokoitu hissille 1. Tästä syystä näitä matkustajia vastaavilla geeneillä on ainoastaan yksi mahdollinen arvo, joka tarkoittaa kerroksen 5 matkustajan tapauksessa hissiä 3 ja kerroksen 3 matkustajan tapauksessa hissiä 1. Koska 15 muille matkustajille ei ole allokoitu hissikoria, näillä matkustajia vastaavilla geeneillä on neljä mahdollista his-sikorivaihtoehtoa, jotka tarkoittavat hissejä 1, 2, 3 ja 4.

Koska kerroksen 3 ja 5 matkustajia palvelevat hissit tiedetään ennalta ja ne pysyvät päätöksenteossa muuttumattomina, 20 niitä ei välttämättä tarvitse ottaa mukaan lopulliseen kromosomirakenteeseen, vaan ne voidaan viedä suoraan hissimal-lille osana asianomaisten hissien reittejä. Tämä aikaansaa sen, että kyseiset kerroksen 3 ja 5 matkustajat otetaan kuitenkin huomioon päätöksenteossa, vaikka kyseiset geenit ei-, 25 vät olisikaan mukana varsinaisessa kromosomirakenteessa.

j Koska kromosomirakenne käsittelee hissikoreja, menetelmä so- veltuu käytettäväksi hissiryhmissä, joissa voi olla yksi ja/tai useampikorisia hissejä.

30

Keksintöä ei rajata pelkästään edellä esiteltyjä sovellu-, tusesimerkkejä koskevaksi, vaan monet muunnokset ovat mah- dollisia pysyttäessä patenttivaatimusten määrittelemissä ’*··' puitteissa.

35

Claims (11)

11 112856

1. Menetelmä matkustajien allokoimiseksi (18) hissiryhmässä, jossa menetelmässä kukin matkustaja antaa kutsulaitteella 5 (12) kohdekerroksensa, jolloin matkustajan lähtö- ja kohde- kerros on määritetty, tunnettu siitä, että matkustaja allokoidaan (18) häntä palvelevalle hissikorille geneettisellä allokointimenetelmällä (38) siten, että - hissien ajoreitit koodataan vaihtoehtoisiin kromosomeihin, 10 jolloin kromosomin geeniin on tallennettu matkustajan ja hissikorin tarvittavat tiedot, että - geneettisiä menetelmiä hyödyntäen kehitetään vaihtoehtoisia kromosomeja ja näistä valitaan paras kromosomi ja että - parhaan kromosomin osoittamat matkustajat ohjataan kro-15 mosomin edustamiin hissikoreihin ja että - parhaan kromosomin osoittamat hissikorit ohjataan palvelemaan kromosomiin talletettuja matkustajia.

2. Patenttivaatimuksen 1 mukainen menetelmä, tunnettu siitä, 20 että kromosomit on muodostettu siten, että geenin paikka kromosomissa määrittää matkustajan identiteetin ja geenin arvo eli alleeli määrittää matkustajaa palvelevan hissikorin . ; 25

3. Jonkin patenttivaatimuksen 1-2 mukainen menetelmä, tun- : nettu siitä, että geenissä on useita alleelivaihtoehtoja : niin kauan kuin geneettinen algoritmi (38) on käynnissä.

4. Jonkin patenttivaatimuksen 1-3 mukainen menetelmä, tun- 30 nettu siitä, että aiemmilla allokointikierroksilla matkusta jille kiinnitetyt hissikorit tallennetaan kromosomin geeneiksi joiden alleeli on muuttumaton ja edustaa matkustajalle jo allokoitua koria. ; ! 35

5. Jonkin patenttivaatimuksen 1-4 mukainen menetelmä, tun nettu siitä, että geneettinen allokointi suoritetaan GA-ytimessä, josta toimenpanoyksikkö (39) hakee matkustajalle ' valitun hissikorin, joka viedään tämän korin omaavalle his- sille allokoituna matkustajana (24). 40 12 112856

6. Jonkin patenttivaatimuksen 1-5 mukainen menetelmä, tunnettu siitä, että geneettisen algoritmin (38) pysähdyttyä toimeenpanoyksikkö (39) kutsuu dekoodausfunktiota (32), jolloin GA-ytimestä saadaan allokoimattomien matkustajien (26) 5 hissitietokenttiin parhaan kromosomin mukaiset hissikorit.

7. Jonkin patenttivaatimuksen 1-6 mukainen menetelmä, tunnettu siitä, että kaksi tai useampia matkustajia voidaan käsitellä yhteisesti yhdellä matkustajaryhmägeenillä. 10

8. Laitteisto hissiryhmään kuuluvien matkustajien allokoi-miseksi siten, että kukin matkustaja antaa kutsulaitteella kohdekerroksensa, jolloin matkustajan lähtö- ja kohdekerros on määritetty ja kutakin matkustajaa palvelee yksi hissiryh- 15 män hissikori, tunnettu siitä, että laitteistoon kuuluu his-simalli (28), välineet matkustajia ja niitä palvelevien korien määrittävien geenien muodostamiseksi, geneettisen algoritmin ydin eli GA-ydin (38) sekä koodausyksikkö (34) , jolloin koodausyksikkö (34) täyttää koodikirjaa (35) ja kertoo 20 minkälaisesta geenistä on kysymys ja purkaa koodikirjan avulla geneettisen haun aikana GA-ytimen muodostamat kromosomit hissimallin (28) ymmärtämään muotoon, ja että laitteistoon kuuluu välineet matkustajien palvelemiseksi valittujen geenien mukaisesti. : 25

9. Patenttivaatimuksen 8 mukainen mukainen laitteisto tun- ; nettu siitä, että laitteistoon kuuluu toimeenpanoyksikkö : (39), joka lähettää jokaisesta allokoimattomasta matkusta jasta (26) "allokoitu matkustaja"-sanoman sille hissille, 30 jonka hissikorille matkustaja on allokoitu.

, 10. Patenttivaatimuksien 8 ja 9 mukainen mukainen laitteisto tunnettu siitä, että hissi lisää allokoidun matkustajan (24) lähtö- ja kohdekerroksista pysähdykset ajoreittiinsä. 35

11. Patenttivaatimuksien 8-10 mukainen mukainen laitteisto tunnettu siitä, että laitteistoon kuuluu tilastointiyksikkö, joka kokoaa yksittäisistä matkustajista talon liikenne-matriisin (11) eli talon jokaisen kerrosparin väliset lii-40 kennevirrat, kokoaa tilastot matkustajien palvelutasosta jo- 112856 ta kuvaavat matkustajien odotus-, korissaolo- sekä matkus-tusaj at. 112856