An order batching algorithm for wave picking in a parallel-aisle warehouse

被引：93

作者：

Gademann, A.J.R.M. ^{[1
]}

Van Den Berg, J.P. ^{[1
]}

Van Der Hoff, H.H. ^{[1
]}

机构：

[1] Center for Production, Logistics and Operations Management, University of Twente, PO Box 217, 7500 AE Enschede, Netherlands

来源：

IIE Transactions (Institute of Industrial Engineers) | 2001年 / 33卷 / 05期

关键词：

Algorithms - Computer applications - Heuristic methods - Plant management - Problem solving - Response time (computer systems) - Theorem proving - Warehouses;

D O I：

10.1023/A:1011049113445

中图分类号：

学科分类号：

摘要：

In this paper we address the problem of batching orders in a parallel-aisle warehouse, with the objective to minimize the maximum lead time of any of the batches. This is a typical objective for a wave picking operation. Many heuristics have been suggested to solve order batching problems. We present a branch-and-bound algorithm to solve this problem exactly. An initial upper bound for the branch-and-bound algorithm is obtained using a 2-opt heuristic. We present a basic version of the algorithm and show that major improvements are obtained by a simple but very powerful preprocessing step and an improved lower bound. The improvements for the algorithm are developed and tested using a relatively small test set. Next, the improved algorithm is tested on an extensive test set. It appears that problems of moderate size can be solved to optimality in practical time, especially when the number of batches is of importance. The 2-opt heuristic appears to be very powerful, providing tight upper bounds. Therefore, a truncated branch-and-bound algorithm would suffice in practice.

引用

页码：385 / 398