An exact solution approach for the order batching problem

Muter I., ÖNCAN T.

IIE TRANSACTIONS, cilt.47, sa.7, ss.728-738, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 47 Sayı: 7
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1080/0740817x.2014.991478
  • Dergi Adı: IIE TRANSACTIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.728-738
  • Galatasaray Üniversitesi Adresli: Evet

Özet

In this article, we deal with the Order Batching Problem (OBP) considering traversal, return, and midpoint routing policies. We consider the Set Partitioning Problem formulation of the OBP and develop a specially tailored column generation-based algorithm for this problem. We suggest acceleration techniques such as a column pool strategy and a relaxation of the column generation subproblem. Also, a specially devised upper-bounding procedure and a lower-bounding method based on column generation that is strengthened by adding subset-row inequalities are employed. According to the computational results, the proposed solution approach manages to solve OBP instances with up to 100 orders to optimality.