Branch-Price-and-Cut-Based Solution of Order Batching Problems

Julia Wahlen () and Timo Gschwind ()
Additional contact information
Julia Wahlen: Faculty of Business Studies and Economics, RPTU Kaiserslautern-Landau, 67663 Kaiserslautern, Germany
Timo Gschwind: Faculty of Business Studies and Economics, RPTU Kaiserslautern-Landau, 67663 Kaiserslautern, Germany

Transportation Science, 2023, vol. 57, issue 3, 756-777

Abstract: Given a set of customer orders each comprising one or more individual items to be picked, the order batching problem (OBP) in warehousing consists of designing a set of picking batches such that each customer order is assigned to exactly one batch, all batches satisfy the capacity restriction of the pickers, and the total distance traveled by the pickers is minimal. In order to collect the items of a batch, the pickers traverse the warehouse using a predefined routing strategy. We propose a branch-price-and-cut (BPC) algorithm for the exact solution of the OBP investigating the routing strategies traversal, return, midpoint, largest gap, combined, and optimal. The column-generation pricing problem is modeled as a shortest path problem with resource constraints (SPPRC) that can be adapted to handle the implications from nonrobust valid inequalities and branching decisions. The SPPRC pricing problem is solved by means of an effective labeling algorithm that relies on strong completion bounds. Capacity cuts and subset-row cuts are used to strengthen the lower bounds. Furthermore, we derive two BPC-based heuristics to identify high-quality solutions in short computation times. Extensive computational results demonstrate the effectiveness of the proposed methods. The BPC is faster by two orders of magnitude compared with the state-of-the-art exact approach and can solve to optimality hundreds of instances that were previously unsolved. The BPC-based heuristics are able to significantly improve the gaps reported for the state-of-the-art heuristic and provide hundreds of new best-known solutions.

Keywords: warehousing; order batching; branch-price-and-cut; picker routing (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.1198 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:3:p:756-777

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().