Optimization Models and Numerical Algorithms for an Elevator Group Control System

Thumbnail Image

Files

isbn9789526075396.pdf (699.11 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2017-09-15
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2017

Department

Matematiikan ja systeemianalyysin laitos
Department of Mathematics and Systems Analysis

Major/Subject

Mcode

Degree programme

Language

en

Pages

50 + app. 94

Series

Aalto University publication series DOCTORAL DISSERTATIONS, 139/2017

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.

Description

Supervising professor

Ehtamo, Harri, Prof., Aalto University School of Science, Department of Mathematics and Systems Analysis, Finland

Thesis advisor

Siikonen, Marja-Liisa, Dr., KONE Corporation, Finland

Keywords

bilevel optimization, stochastic optimal control, robust optimization, genetic algorithm, simulation, elevator dispatching, double-deck elevator, destination control, kaksitasoinen optimointi, stokastinen optimiohjaus, robusti optimointi, geneettinen algoritmi, simulointi, hissien kutsunjakelu, kaksikorinen hissi, kohdekutsuohjaus

Other note

Parts

  • [Publication 1]: Sorsa, J., M-L. Siikonen, H. Ehtamo. 2003. Optimal control of double-deck elevator group using genetic algorithm. International Transactions in Operational Research 10(1) 103–114.
    DOI: 10.1111/1475-3995.00397 View at publisher
  • [Publication 2]: Sorsa, J., M-L. Siikonen. 2006. Double-Deck Destination Control System. In: A. Lustig (Ed.), 2006, Elevator Technology 16, 318–327, IAEE, ISBN 965-90338-4-2. Republished in Elevatori, 37(5) 42–56, 2008
  • [Publication 3]: Sorsa, J., M. Ruokokoski. 2013. Multiple objectives and system constraints in doubledeck elevator dispatching. In: M. Collan, J. H¨am¨al¨ainen, P. Luukka (Eds.), 2013, Proceedings of the Finnish Operations Research Society 40th Anniversary Workshop -FORS40, 48–51, LUT Scientific and Expertise Publications No. 13, Research Reports, ISBN 978-952-265-435-6
  • [Publication 4]: Ruokokoski, M., J. Sorsa, M-L. Siikonen, H. Ehtamo. 2016. Assignment formulation for the Elevator Dispatching Problem with destination control and its performance analysis. European Journal of Operational Research 252(2) 397–406.
    DOI: 10.1016/j.ejor.2016.01.019 View at publisher
  • [Publication 5]: Sorsa, J., H. Ehtamo, J-M. Kuusinen, M. Ruokokoski, M-L. Siikonen. 2017. Modeling uncertain passenger arrivals in the elevator dispatching problem with destination control. Optimization Letters 1–15. Published online 23 March,
    DOI: 10.1007/s11590-017-1130-0 View at publisher
  • [Publication 6]: Sorsa, J. 2017. A real-time genetic algorithm for the bilevel double-deck elevator dispatching problem. EURO Journal on Computational Optimization, 27 pages (submitted manuscript)

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-60-7539-6

Collections

[diss] Perustieteiden korkeakoulu / SCI