Elevator packing with various objects using cyclic placement method and quadratic line search

Abstract

In this Master's thesis, we will develop an algorithm for packing an elevator with various objects. For simplicity, our model is two-dimensional and we model the objects as capsules and rectangles and their combinations. The objects will arrive from an elevator door one by one until no more can be fitted. The aim here is to maximize the number of objects in the elevator, with no overlapping.

The optimization model is based on the concept of object overlapping. This means that initially, we let the objects first overlap each other. Then, we adjust their places to minimize their overlapping area. So, the objective function is the total overlapping area of all the objects. A feasible configuration in the elevator is one with the total overlapping area being equal to zero.

For overlapping, we use two concepts. One is the geometrical overlapping area which is found in the literature. The other is overlapping distance, a concept developed here. Even though the objective function is not differentiable, we use gradient-based optimization methods. We show a way of simplifying the gradient evaluation by canceling a significant amount of counterterms, which speeds up the algorithm drastically.

We first solve the basic capsule packing problem. We use the gradient method, the Broyden–Fletcher–Goldfarb–Shanno method (BFGS), and the cyclic placement method (CPM) which is a special case of a block coordinate method. From the practical point of view, the CPM is the best method. In fact, the CPM decomposes the problem so that only one capsule is adjusted at a time in a sequential fashion. Especially with a modified quadratic line search method, the CPM works very efficiently. These observations are a result of extensive numerical testing.

We finally use our basic capsule packing algorithm for certain application cases. In the first application, we construct a model for capsule and rectangle combinations, which model passengers with suitcases. In the second case, we fit shopping carts and passengers into the elevator.

In this thesis, we form a mathematical optimization model for packing various capsule-rectangle combinations, and study various optimization methods to solve them effectively. Our focus is on the models and algorithms, rather than solving particular cases. We also develop a considerable amount of theory to study the concepts and methods used.

Tässä diplomityössä kehitetään algoritmi hissin täyttämiseen erilaisilla kappaleilla. Mallimme on kaksiulotteinen ja mallinnamme kappaleet kapseleina, suorakulmioina ja niiden yhdistelminä. Kappaleet saapuvat hissin ovesta yksi kerrallaan, kunnes hissi on täynnä. Tarkoitus on maksimoida kappaleiden määrä hississä siten, etteivät ne ole päällekkäin.

Optimointimallimme perustuu kappaleiden päällekkäisyyteen. Annamme kappaleiden olla ensin päällekkäin, ja sitten minimoimme tätä päällekkäisyyttä. Kohdefunktiomme on siis summa kaikista päällekkäisistä pinta-aloista. Käypä konfiguraatio hississä on silloin, kun kohdefunktion arvo on nolla.

Käytämme päällekkäisyyden mittaamiseen kahta käsitettä. Ensimmäinen on geometrinen leikkauspinta-ala, mikä löytyy kirjallisuudesta. Toinen on päällekkäisyyspituus, joka on kirjoittajan kehittämä konsepti. Vaikka kohdefunktio ei ole differentioituva, käytämme gradienttipohjaisia menetelmiä. Näytämme, miten gradientin numeerista laskentaa voidaan sieventää kumoamalla vastatermejä, mikä nopeuttaa algoritmia merkittävästi.

Ensin ratkaisemme kapselin pakkaustehtävän. Ratkaisuun käytämme gradienttimenetelmää, Broyden–Fletcher–Goldfarb–Shanno -menetelmää (BFGS), sekä syklistä sijoittelumenetelmää (CPM). CPM on paras menetelmä kaikkiin tässä työssä esitettyihin tehtäviin. CPM hajauttaa tehtävän siten, että vain yhtä kappaletta liikutetaan kerrallaan. Etenkin räätälöidyllä kvadraattisella viivahaulla CPM toimii erittäin tehokkaasti. Väitteet perustellaan kattavan simulaatiodatan avulla.

Lopuksi käytämme algoritmia kahdessa sovelluksessa. Ensimmäisessä sovelluksessa tutkimme kapselin ja suorakulmion yhdistelmää, jolla mallinamme ihmisiä matkalaukun kanssa. Toisessa sovelluksessa täytämme hissejä ostoskärryillä sekä ihmisillä.

Tässä diplomityössä muodostamme matemaattisen optimointimallin kapseli-suorakulmio kombinaatioiden pakkaamiseen, ja tutkimme minkälaiset optimointimenetelmät ratkaisevat sen tehokkaasti. Keskitymme mallien ja algoritmien yleisiin ominaisuuksiin, emmekä niinkään esimerkkitapausten ratkaisuun. Työssä on myös huomattava määrä teoriaa käytettyihin konsepteihin ja menetelmiin liittyen.