Optimizing Warehouse Order Batching when Routing Is Precedence Constrained and Pickers Have Varying Skills

Abstract

Warehouses are an important part of most supply chains. By batching customer orders and routing pickers effectively, warehouses aim to increase the efficiency of the order picking process. The contributions of this thesis are related to two extensions to the optimizing of picker-to-parts order picking operations in warehouses. First, precedence constraints are introduced to picker routing, which pose new challenges to order batching algorithms. This is due to the relative complexity of precedence-constrained routing when compared to standard methods for routing pickers. The complexity is mitigated by the use of an effective savings estimate in calculating the properties of large batches, which reduces computation time significantly. This savings estimate is used in a Large Neighborhood Search algorithm, which outperforms heuristics from literature and compares well to optimal solutions (1.2% mean error). An A* algorithm is used for precedence-constrained picker routing. Compared to the performance of a reference warehouse, almost 16% (5000km) in total travel distance can be saved during a three month period. Second, forecasting models of order pickers' batch execution times are built with multilevel modeling using a three-month set of operational data. It is shown that significant differences in picker performance exist. The forecasting models are used in an Adaptive Large Neighborhood Search algorithm in finding the right picker for the job. Compared to a state-of-the-art batching algorithm and to the current practice of assigning work in most warehouses, 9% is saved in total order picking time. These results show that differences among order pickers should be taken into account when optimizing order picking operations in warehouses. This is the first work where forecasting models are used to predict the performance of individual order pickers, and where such models are exploited with a job assigning algorithm.

Varastot ovat tärkeä osa teollisuuden ja vähittäismyynnin toimitusketjuja. Varastojen keräilyprosessia on pyritty tehostamaan keruureittien optimoinnilla sekä yhdistämällä tilauksia isommiksi kokonaisuuksiksi, jotka voidaan kerätä yhden keruureitin varrelta lähtöpisteeseen välillä palaamatta. Tämän väitöskirjan tieteelliset kontribuutiot laajentavat tieteen nykyisiä varastojen vähittäiskeräilyprosessin optimoinnin käytäntöjä. Kerättävien tuotteiden välillä voi olla etusijarajoitteita, ts. jotkut tuotteet tulisi kerätä ennen toisia. Perinteiset keräilijöiden reitittämiseen käytetyt algoritmit eivät ota tätä huomioon. Etusijarajoitettu reitittäminen on laskennallisesti verraittain raskasta. Tilausten yhdistämiseen käytetyt algoritmit kutsuvat reititysalgoritmia aina löytäessään uuden tilausyhdistelmän. Reitityksen ollessa etusijarajoitettua, jatkuva reitittäminen tekee kirjallisuudessa esitettyjen algoritmien käytöstä epäkäytännöllistä ratkaisuun kuluvan ajan vuoksi. Tässä työssä esitetään tapa vähentää laskennallisesti raskasta reititystä käyttäen säästettyyn matkaan perustuvia estimaatteja. Estimaatteja käytetään tilausten yhdistämisalgoritmissa varsinaisen reitityksen sijaan. Tämä nopeuttaa ratkaisun löytämistä laadusta tinkimättä: esitetty algoritmi löytää paremman ratkaisun tilausten yhdistämisongelmaan nopeammin kuin mikään testatuista verrokkialgoritmeista, varsinkin jos tilauksia on paljon. Optimaalisiin ratkaisuihin verrattuna, esitetty algoritmi pärjää hyvin, saavuttaen keskimäärin 1,2% epätarkemman tuloksen. Referenssivaraston alkuperäisten keruureittien kokonaismatkaan verrattuna säästöä kertyi 16%, eli noin 5000 km kolmen kuukauden ajanjaksona. Kolmen kuukauden keruudatan pohjalta monitasomallinusmenetelmän avulla luodaan keruutehtävän kokonaisaikaa ennustavat kerääjäkohtaiset mallit. Ennuste riippuu kerääjästä ja työtehtävän parametreistä. Työntekijöiden välisten erojen tilastollinen merkittävyys osoitetaan varianssianalyysia käyttäen. Ennustemalleja käytetään adaptiivisessa hakualgoritmissa, joka etsii parhaita keräilijä/tilaus/tilausyhdistelmä-kombinaatioita isosta hakuavaruudesta. Verrattuna tieteen nykytilaan, jossa tilaukset yhdistetään kokonaismatkaa minimoiden, mutta ei oteta keräilijöiden taitoja huomioon, saavutetaan 9% säästöt kokonaiskeruuajassa. Nämä tulokset osoittavat, että keräilijöiden taidot tulisi ottaa huomioon keräilyvaraston toimintojen optimoinnissa.