The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Order batching to minimize total travel time in a parallel-aisle warehouse
Abstract
Although the picking of items may make up as much as 60% of all labor activities in a warehouse and may account for as much as 65% of all operating expenses, many order picking problems are still not well understood. Indeed, usually simple rules of thumb or straightforward constructive heuristics are used in practice, even in state-of-the-art warehouse management systems, however, it might well be that more attractive algorithmic alternatives could be developed. We address one such a fundamental materials handling problem: the batching of orders in a parallel-aisle warehouse so as to minimize the total traveling time needed to pick all items. Many heuristics have been proposed for this problem, however, a fundamental analysis of the problem is still lacking. In this paper, we first address the computational complexity of the problem. We prove that this problem is NP-hard in the strong sense but that it is solvable in polynomial time if no batch contains more than two orders. This result is not really surprising but it justifies the development of approximation and/or enumerative optimization algorithms for the general case. Our primary goal is to develop a branch-and-price optimization algorithm for the problem. To this end, we model the problem as a generalized set partitioning problem and present a column generation algorithm to solve its linear programming relaxation. Furthermore, we develop a new approximation algorithm for the problem. Finally, we test the performance of the branch-and-price algorithm and the approximation algorithm on a comprehensive set of instances. The computational experiments show the compelling performance of both algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Edmonds, J. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-045-4 · Cited by 2,428
Branch-and-price: column generation for solving huge integer programs
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998) · Operations Research · doi:10.1287/opre.46.3.316 · Cited by 2,219
Edmonds, J. (2009) · Classic Papers in Combinatorics · doi:10.1007/978-0-8176-4842-8_26 · Cited by 1,517
Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
Ratliff, H. D., & Rosenthal, A. S. (1983) · Operations Research · doi:10.1287/opre.31.3.507 · Cited by 628
An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
Gabow, H. N. (1976) · Journal of the ACM · doi:10.1145/321941.321942 · Cited by 342
An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
Congram, R. K., Potts, C. N., & van de Velde, S. L. (2002) · INFORMS Journal on Computing · doi:10.1287/ijoc.14.1.52.7712 · Cited by 306
Efficient orderbatching methods in warehouses
de Koster, R. B. M., van der Poort, E. S., & Wolters, M. (1999) · International Journal of Production Research · doi:10.1080/002075499191094 · Cited by 261
Abu‐Mostafa, Y. S. (1987) · Cited by 257
An exact algorithm for IP column generation
Vanderbeck, F., & Wolsey, L. A. (1996) · Operations Research Letters · doi:10.1016/0167-6377(96)00033-8 · Cited by 244
Cited by
Research on warehouse operation: A comprehensive review
Gu, J., Goetschalckx, M., & McGinnis, L. F. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2006.02.025 · Cited by 965
Incorporating human factors in order picking planning models: framework and research opportunities
Grosse, E. H., Glock, C. H., Jaber, M. Y., & Neumann, W. P. (2015) · International Journal of Production Research · doi:10.1080/00207543.2014.919424 · Cited by 373
On-Time Last-Mile Delivery: Order Assignment with Travel-Time Predictors
Liu, S., He, L., & Max Shen, Z.-J. (2021) · Management Science · doi:10.1287/mnsc.2020.3741 · Cited by 268
Design and control of warehouse order picking: A literature review
de Koster, R., Le-Duc, T., & Roodbergen, K. J. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2006.07.009 · Cited by 114
Pashkevich, N., Haftor, D., Karlsson, M., & Chowdhury, S. (2019) · Sustainability · doi:10.3390/su11236708 · Cited by 20
Metadata
- Authors
- GADEMANN, N., & VELDE, S.
- Venue
- IIE Transactions
- Publisher
- Informa UK Limited
- Published
- 2005-01
- Volume
- 37
- Issue
- 1
- Pages
- 63-75
- ISSN
- 0740-817X (ISSN-L)
- 1545-8830
- OpenAlex
- W1987361686
- Cited by
- 295
- References
- 26
- FWCI
- 9.93
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Order batching to minimize total travel time in a parallel-aisle warehouse. https://app.cochat.ai/papers/10.1080/07408170590516917
- The paper
- GADEMANN, N., & VELDE, S. (2005). Order batching to minimize total travel time in a parallel-aisle warehouse. IIE Transactions. https://doi.org/10.1080/07408170590516917
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.