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

 |  Login

Show simple item record

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). 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. en
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. 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ä. fi
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


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account