Order batching using an approximation for the distance travelled by pickers
| Autor: | Cristiano Arbex Valle, John E. Beasley |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
050210 logistics & transportation
Order picking Mathematical optimization 021103 operations research Information Systems and Management General Computer Science Computer science Heuristic (computer science) 05 social sciences 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Grid Industrial and Manufacturing Engineering Linear programming relaxation Order (business) Optimization and Control (math.OC) Modeling and Simulation 0502 economics and business FOS: Mathematics Routing (electronic design automation) Integer programming Mathematics - Optimization and Control Integer (computer science) Block (data storage) |
| Popis: | In this paper we investigate the problem of order batching for picker routing. Our approach is applicable to warehouses (storage areas) arranged in the standard rectangular grid layout, so with parallel aisles and two or more cross-aisles. The motivation underlying our work is online grocery shopping in which orders may be composed of dozens of items. The approach presented directly addresses order batching, but uses a distance approximation to influence the batching of orders without directly addressing the routing problem. We present a basic formulation based on deciding the orders to be batched together so as to optimise an objective that approximates the picker routing distance travelled. We extend our formulation by improving the approximation for cases where we have more than one block in the warehouse. We present constraints to remove symmetry in order to lessen the computational effort required, as well as constraints that significantly improve the value of the linear programming relaxation of our formulation. A heuristic algorithm based on partial integer optimisation of our mathematical formulation is also presented. Once order batching has been decided we optimally route each individual picker using a previous approach presented in the literature. Extensive computational results for publicly available test problems involving up to 75 orders are given for both single and multiple block warehouse configurations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|