# Polyhedral Analysis of Up-peak Traffic Patterns in Elevator Dispatching Problem

 dc.contributor Aalto-yliopisto fi dc.contributor Aalto University en dc.contributor.advisor Ruokokoski, Mirko dc.contributor.author Husgafvel, Vesa dc.date.accessioned 2016-05-12T10:37:28Z dc.date.available 2016-05-12T10:37:28Z dc.date.issued 2016-05-10 dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/20311 dc.description.abstract Up-peak traffic is a common situation arising in elevator routing, where most of the transportation requests given by passengers are directed from lower floors to upper floors of a building. In this thesis, we examine three up-peak traffic patterns that differ from each other with respect to the number of elevators or the capacity of elevators. Analysis is based on a mixed-integer programming formulation of the elevator dispatching problem (EDP). en Solutions of linear integer optimization problems span a convex hull, which is called a polytope. By examining the structure of a polytope, it is possible to find out special features of the problem to be studied. A central variable in description of a polytope is dimension, which is defined as the number of affinely independent vectors contained in a polytope. In this work, we determine the dimension of each up-peak traffic pattern polytope to be studied, or in the case we are not able to give an exact formula, we determine a lower and an upper bound for the value of dimension. In addition, in each case we determine the number of feasible solutions and the number of arcs in the reduced graph. Results relating to different patterns are compared with each other and with polyhedral results of similar optimization problems that appear in literature. The obtained results of this work give new, fundamental knowledge of the polyhedral structure of up-peak traffic patterns - a subject that has not been previously studied. We believe that by combining our results with similar research results, e.g., polyhedral results of down-peak traffic patterns, our knowledge of the elevator dispatching problem deepens, which will help in designing of EDP solving algorithms. dc.description.abstract Ylösruuhka on yleinen hissien reitityksessä esiintyvä tilanne, jossa suurin osa matkustajien antamista siirtokutsuista kohdistuu rakennuksen alemmista kerroksista ylempiin kerroksiin. Tässä työssä tutkitaan kolmea ylösruuhkamuodostelmaa, jotka eroavat toisistaan käytettävissä olevien hissien lukumäärän tai hissien kapasiteetin suhteen. Analyysi pohjautuu hissien reititysongelman (EDP) lineaariseen sekalukuptimointiformulaatioon. fi Lineaaristen kokonaislukuoptimointitehtävien ratkaisut virittävät konveksin kuoren, jota sanotaan tehtävän polytoopiksi. Polytoopin rakennetta tutkimalla on mahdollista selvittää tarkasteltavan tehtävän erityispiirteitä. Keskeinen polytooppia kuvaava suure on dimensio, joka määritellään polytoopin sisältämien affiinisti riippumattomien vektorien lukumääränä. Työssä määrätään kunkin tutkittavan ylösruuhkamuodostelman polytoopin dimensio tai dimension arvolle määrätään ala- ja yläraja. Lisäksi kussakin tapauksessa määrätään käypien ratkaisujen lukumäärä sekä kaarien lukumäärä redusoidussa graafissa. Eri muodostelmiin liittyviä tuloksia vertaillaan sekä keskenään että kirjallisuudessa esiintyvien samankaltaisten optimointiongelmien polyhedraalitulosten kanssa. Työssä saadut tulokset antavat uutta, perustavanlaatuista tietoa ylösruuhkamuodostelmien polyhedraalirakenteesta - aiheesta jota ei ole aiemmin tutkittu. On uskottavaa että yhdistämällä saatuja tuloksia aiempien tutkimustulosten (esim. alasruuhkamuodostelmia koskevien tulosten) kanssa, hissien reititysongelman tuntemus paranee, mikä puolestaan edistää ratkaisualgoritmien kehitystä. dc.format.extent 8+77 dc.format.mimetype application/pdf en dc.language.iso en en dc.title Polyhedral Analysis of Up-peak Traffic Patterns in Elevator Dispatching Problem en dc.title Ylösruuhkamuodostelmien polyhedraalianalyysi hissien reititysongelmassa fi dc.type G2 Pro gradu, diplomityö fi dc.contributor.school Perustieteiden korkeakoulu fi dc.subject.keyword elevator routing en dc.subject.keyword integer optimization en dc.subject.keyword up-peak traffic en dc.subject.keyword polytope en dc.subject.keyword polyhedral analysis en dc.identifier.urn URN:NBN:fi:aalto-201605121985 dc.programme.major Systeemi- ja operaatiotutkimus fi dc.programme.mcode F3008 fi dc.type.ontasot Master's thesis en dc.type.ontasot Diplomityö fi dc.contributor.supervisor Ehtamo, Harri dc.programme Teknillisen fysiikan ja matematiikan koulutusohjelma fi
﻿