Milp formulations for the order batching problem in low-level picker-to-part warehouse systems

Abstract

Sipariş gruplama depoya gelen siparişleri gruplayarak bir arada toplama işlemidir. Bu çalışmada parça toplayıcıların depodan siparişleri çektiği ortamda, Sipariş Gruplama Problemi (SGP) ele alınmıştır. Günümüz depo sistemlerinde karşılaşılan bu problem NP-zor olarak bilinmektedir. SGP, birbirlerine benzer siparişleri gruplayarak, belirli rotalama stratejileri altında parça toplayıcıların kat ettiği toplam mesafeyi en küçüklemeyi amaçlamaktadır. Bu çalışmada toplayıcı olarak işçilerin çalıştığı ve toplayıcıların parçaları almaya gittikleri SGP için Karma Tam Sayılı Doğrusal Programlama (KDTP) gösterimleri geliştirilmiştir. SGP için geliştirdiğimiz KTDP gösterimlerinin doğruluğunu daha iyi açıklamak bilgisayısal deneyler yapılmıştır. Bu amaçla, SGP için geliştirilen KTDP gösterimlerini, çözüm kurucu sezgisel algoritmalarından biri olan kazanç algoritması ile karşılaştırdık.Bilgisayısal çalışmalar KTDP ve kazanç sezgiselinin SGP için olumlu sonuçlar verdiğini gösteriyor. Uyguladığımız sayısal çalışmaların sonuçlarına göre, her iki metodu karşılaştırdığımızda kazanç sezgiselinin daha iyi kabul edilebilir bir sürede sonuç verdiğini söyleyebiliriz. Etkinlik ve çözüm niteliği unsurlarını düşündüğümüzde kazanç sezgiselinin daha iyi bir sonuç verdiğini söyleyebiliriz. Bilgisayısal çıktılarımızı değerlendirdiğimizde önerilen gösterimlerin SGP için iyi bir üst sınır sağladığını söyleyebiliriz. KTDP gösterimleri, sezgisel ve meta sezgisel çalışmalar için karşılaştırmalı değerlendirme sağlayabilir. Gelecek araştırma konusu SGP'ye özel dal sınır ve dal kesme yöntemleri de geliştirilebilir. Anahtar Sözcükler: Sipariş Gruplama Problemi, Karma Tam Sayılı Doğrusal Programlama, Depo Yönetimi

Order picker's routing operation consists of determining the sequence of the order picking. In this study, we consider the Order Batching Problem (OBP) which is shown to be NP-hard. Given both a list of customer orders and order picker's routing policy, the OBP deals with constructing batches of customer orders such that the total travel length of the pickers is minimized. To the best of our knowledge, there are no MILP formulations suggested for the OBPs with traversal and return routing policies in the literature. Basically, we introduce MILP formulations for the OBP and we also perform computational study to better expose the strength of the proposed MILP formulations. For that purpose, we compare the performance of the MILP formulations with the savings algorithm which is known to be one of the best performing construction heuristics for the OBP.The computational results show the usefulness of the MILP and saving heuristic for the OBP. According to our computational experiments, comparing both methods, savings heuristic yields significantly better results in reasonable CPU times. From the experimental results, we observe that the proposed formulations yield quite good upper bounds. These MILP formulations can also be used as benchmarks for other studies which propose heuristic and meta-heuristics for the OBP. As a further research avenue, developing a branch and bound algorithm exploiting the structure of the problem would be an interesting work. Branch and cut algorithms can be also developed by suggesting valid inequalities based on the proposed MILP formulations.Keywords: Order Batching Problem, Mixed Integer Linear Programming, Warehouse Management