Benders Decomposition using Core-Maximal Cuts and Its Application to the Single-Picker Routing Problem with Scattered Storage

André Hessenius (), Christian Manz () and Stefan Irnich ()
Additional contact information
André Hessenius: Johannes-Gutenberg University, Germany
Christian Manz: Johannes-Gutenberg University, Germany
Stefan Irnich: Johannes-Gutenberg University, Germany

No 2511, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: We present a new solution approach to the single-picker routing problem with scattered storage (SPRP-SS) for order picking in warehouses. Heßler and Irnich (INFORMS J. on Comp. 36(6):1417–1435, 2024) demonstrated how to construct an extension to Ratliff and Rosenthal’s state space to incorporate the scattered storage dimension. Based on this extended state space, we propose a new formulation that makes two types of decisions: selection of pick positions and determination of the tour that visits the chosen pick positions. This novel formulation is an ideal starting point for a Benders decomposition. For this approach, a fast convergence is crucial. To this end, we analyze properties of the optimality cuts. We examine the most popular type of cut from the literature—the Magnanti-Wong cut—and determine how modified subproblems, such as Magnanti and Wong’s, generate stronger cuts than arbitrary subproblem solutions. As a result, we propose core-maximal cuts as a new type of optimality cut. In our computational experiments, we compare the resulting Benders decomposition algorithm with three mixed-integer linear programming formulations, as well as alternative Benders approaches. Core-maximal cuts can be used also for other Benders subproblems as well. We showcase the application to the capacitated facility location problem and the fixed charge network flow problem. Results show that this approach often requires fewer Benders iterations and has shorter total computation times than established Benders decomposition algorithms.

Keywords: Benders decomposition; Benders cuts; Routing; warehousing; picker Routing; scattered storage (search for similar items in EconPapers)
Pages: 30 pages
Date: 2025-12-18
References: Add references at CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2511.pdf first version, 2025 (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:jgu:wpaper:2511

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().