New solution procedures for the order picker routing problem in U-shaped pick areas with a movable depot
Open Access
- 7 December 2021
- journal article
- research article
- Published by Springer Nature in OR Spectrum
- Vol. 44 (2) , 535-573
Abstract
This paper develops new solution procedures for the order picker routing problem in U-shaped order picking zones with a movable depot, which has so far only been solved using simple heuristics. The paper presents the first exact solution approach, based on combinatorial Benders decomposition, as well as a heuristic approach based on dynamic programming that extends the idea of the venerable sweep algorithm. In a computational study, we demonstrate that the exact approach can solve small instances well, while the heuristic dynamic programming approach is fast and exhibits an average optimality gap close to zero in all test instances. Moreover, we investigate the influence of various storage assignment policies from the literature and compare them to a newly derived policy that is shown to be advantageous under certain circumstances. Secondly, we investigate the effects of having a movable depot compared to a fixed one and the influence of the effort to move the depot.Keywords
Funding Information
- Technische Universität Darmstadt
This publication has 62 references indexed in Scilit:
- Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithmsFlexible Services and Manufacturing Journal, 2011
- Using a TSP heuristic for routing order pickers in warehousesEuropean Journal of Operational Research, 2010
- Aisle configurations for unit-load warehousesIIE Transactions, 2009
- Designing the layout structure of manual order picking areas in warehousesIIE Transactions, 2008
- Design and control of warehouse order picking: A literature reviewEuropean Journal of Operational Research, 2007
- A model for warehouse layoutIIE Transactions, 2006
- Order batching to minimize total travel time in a parallel-aisle warehouseIIE Transactions, 2005
- On the capacitated vehicle routing problemMathematical Programming, 2003
- The effect of warehouse cross aisles on order picking efficiencyInternational Journal of Production Research, 1999
- The theory of dynamic programmingBulletin of the American Mathematical Society, 1954