Polyhedral analysis of up-peak traffic patterns in elevator dispatching problem

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.

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ä.