Optimization Models and Numerical Algorithms for an Elevator Group Control System

Abstract

An elevator group control system (EGCS) dispatches the elevators under its control to serve each passenger call. New passengers may appear while the elevators are serving their current assignments. This makes the control problem of the EGCS dynamic. The EGCS solves a snapshot instance of the elevator dispatching problem (EDP) anew in intervals less than a second. Its solution defines complete elevator routes by minimizing, e.g., passenger waiting or journey times, according to which the EGCS dispatches the elevators. In this dissertation, the EDP is considered as a bilevel, dynamic, stochastic, multi-objective and integer optimization problem. The bilevel approach is based on the distributed nature of a typical elevator system, in which each elevator has its own independent controller and the EGCS optimizes the service of the calls shared by the elevator group. Hence, the upper-level problem corresponding to the EGCS assigns calls to the elevators, and a lower-level problem for each elevator determines its route to serve the assigned calls. Near-future passenger arrivals are uncertain for the EDP. The number of passengers related to a call and completely new calls are modelled explicitly in the studied stochastic model. For the first time, the EDP takes into account the fact that passengers often travel in socially connected groups. Furthermore, the uncertainties are evaluated in multiple risk scenarios which converts the EDP into a robust optimization problem. Since the EDP is a difficult integer optimization problem, its solution time by an exact algorithm increases exponentially with respect to problem size. The main solution approach is based on a genetic algorithm suitable for real-time optimization in the EGCS. The EDP is also formulated as a mixed integer programming problem and solved by an exact algorithm, which are important for benchmarking and theoretical studies. The EGCS developed in this dissertation was installed as the first double-deck destination control system (DCS) in the world. However, the de facto standard DCS does not perform optimally mainly because of the immediate assignment policy, which does not allow the reassignments of the calls to other elevators. As one possible solution to this challenge, the delayed assignment policy is studied. It allows the reassignments until the last moment but requires new shared guidance devices. The first such system will be realized in the near future. According to the results, delayed assignments improve passenger service quality greatly. Therefore, the delayed double-deck DCS may enable greater core space savings than current industry practice allows.

Hissien ryhmäohjauksen päätehtävänä on lähettää hissi palvelemaan jokaista matkustajien antamaa kutsua. Uusia matkustajia voi saapua auloihin hissien suorittaessa sen hetkisiä tehtäviään, minkä vuoksi ryhmäohjauksen optimointitehtävä on dynaaminen. Ryhmäohjaus reagoi muuttuvaan tilanteeseen ratkaisemalla kutsunjakelutehtävän päivitetyillä tilatiedoilla uudestaan alle sekunnin välein. Mallissa ratkaistaan hissien reitit minimoimalla esimerkiksi matkustajien odotus- tai matkustusaikoja. Reittien perusteella ryhmäohjaus lähettää hissit palvelemaan kutsuja. Tässä väitöskirjassa kutsunjakelutehtävä mallinnetaan kaksitasoisena, dynaamisena, stokastisena, monitavoitteisena ja kokonaislukuoptimointitehtävänä. Kaksitasoinen lähestymistapa perustuu tyypillisen hissijärjestelmän hajautettuun rakenteeseen. Jokaisella hissillä on oma ohjausjärjestelmänsä perustoiminnoilleen. Ryhmäohjaus puolestaan optimoi hissiryhmän yhteisten kutsujen palvelun. Kaksitasomallissa ylätaso vastaa ryhmäohjausta ja jakaa kutsut hisseille. Erillisissä alatason tehtävissä ratkaistaan kunkin hissin reitti annettujen kutsujen palvelemiseksi. Kutsunjakeluun liittyy epävarmuus lähitulevaisuudessa saapuvista matkustajista. Esitetyssä stokastisessa mallissa ennustetaan kutsujen takana olevien henkilöiden lukumäärää sekä täysin uusia kutsuja. Mallissa huomioidaan ensimmäistä kertaa matkustajien taipumus liikkua usein ryhmissä. Epävarmuudet mallinnetaan erikseen useissa skenaarioissa, mikä tekee mallista robustin optimointitehtävän. Kutsunjakelu on luonteeltaan vaikea kokonaislukuoptimointitehtävä, jonka tarkkaan ratkaisemiseen tarvittava aika kasvaa eksponentiaalisesti tehtävän koon kasvaessa. Keskeisin ratkaisumenetelmä on geneettinen algoritmi, jota käytetään myös hissien ryhmäohjauksen reaaliaikaisessa optimoinnissa. Kutsunjakelu mallinnetaan myös kokonaislukutehtävänä ja ratkaistaan tarkalla algoritmilla, joita voidaan hyödyntää vertailuissa muihin lähestymistapoihin ja teoreettisiin tutkimuksiin. Tässä väitöskirjassa kehitetty ryhmäohjaus otettiin käyttöön maailman ensimmäisenä kaksikoristen hissien kohdekutsuohjauksena. Nykyiset kohdekutsuohjaukset eivät kuitenkaan toimi parhaalla mahdollisella tavalla, koska välitön kutsunjakelu ei anna mahdollisuutta uudelleenoptimointiin. Eräänä ratkaisuna tutkittiin viivästettyä kutsunjakelua, jossa kutsun palveleva hissi voidaan vaihtaa toiseen. Viivästetty kutsunjakelu kohdekutsuohjauksessa vaatii kuitenkin uudenlaisia yhteisiä opastuslaitteita matkustajille. Ensimmäinen tällainen järjestelmä otetaan käyttöön lähitulevaisuudessa. Tulosten mukaan viivästetty kutsunjakelu parantaa matkustajien palvelutasoa merkittävästi. Tekniikan avulla voitaneen saavuttaa suurempia tilansäästöjä korkeissa rakennuksissa kuin nykykäytäntö sallii.