×

zbMATH — the first resource for mathematics

A route-selecting order batching model with the S-shape routes in a parallel-aisle order picking system. (English) Zbl 1394.90089
Summary: This paper introduces a route-selecting order batching model with the S-shape routing method in parallel-aisle order picking (SRSB). Order pickers in a wide-aisle system prefer the S-shape route taking a u-turn at the last aisle to shorten the travel distance. Although u-turns improve operations, they actually increase computational complexity in order batching. Our study defines a route-set for the S-shape routes and composites a best fit route for batches from the predefined S-shape routes while partitioning orders into batches. The large-scale extension of the SRSB obtains near-optimal solutions by the tight lower bound of the by identifying the route-selection based relaxed batching model. A comparison of the heuristics solution and its pairing lower bound shows 3.5–6.8 percent optimal gaps on average in a six-aisle parallel-aisle system over a 200–500 orders time-window, which outperforms an available best large-scale algorithm with a 9.9 percent shorter travel distance on average. Using the identified lower bound, we evaluate other large-scale batching algorithms in the published literature. We find that a popular savings algorithm shows 8.3–19.8 percent optimal gaps over a variety of large-scale simulation cases.

MSC:
90B06 Transportation, logistics and supply chain management
90B80 Discrete location and assignment
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90B50 Management decision making, including multiple objectives
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581, (1964)
[2] De Koster, R.; Le-Duc, T.; Roodbergen, K. J., Design and control of warehouse order picking: A literature review, European Journal of Operational Research, 182, 481-501, (2007) · Zbl 1121.90385
[3] De Koster, R.; Van der Poort, E. S.; Wolters, M., Efficient orderbatching methods in warehouses, International Journal of Production Research, 37, 1479-1504, (1999) · Zbl 0948.90508
[4] Frazelle, E., World-class warehousing and material handling, (2002), McGraw-Hill New York
[5] Gademann, N.; Van de Velde, S., Order batching to minimize total travel time in a parallel-aisle warehouse, IIE Transactions, 37, 63-75, (2005)
[6] Gademann, N.; Van den Berg, J.; Van der Hoff, H., An order batching algorithm for wave picking in a parallel-aisle warehouse, IIE Transactions, 33, 385-398, (2001)
[7] Hong, S.; Johnson, A. L.; Peters, B. A., Batch picking in narrow-aisle order picking systems with consideration for picker blocking, European Journal of Operational Research, 221, 557-570, (2012) · Zbl 1253.90009
[8] Hong, S.; Johnson, A. L.; Peters, B. A., Large-scale order batching in parallel-aisle picking systems, IIE Transactions, 44, 88-106, (2012)
[9] Hsu, C.-M.; Chen, K.-Y.; Chen, M.-C., Batching orders in warehouses by minimizing travel distance with genetic algorithms, Computers in Industry, 56, 169-178, (2005)
[10] Matthews, J.; Visagie, S., Order sequencing on a unidirectional cyclical picking line, European Journal of Operational Research, 231, 79-87, (2013) · Zbl 1317.90306
[11] Matusiak, M.; de Koster, R.; Kroon, L.; Saarinen, J., A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse, European Journal of Operational Research, 236, 968-977, (2014) · Zbl 1304.90040
[12] Petersen, C. G., An evaluation of order picking routeing policies, International Journal of Operations & Production Management, 17, 1098-1111, (1997)
[13] Ratliff, H. D.; Rosenthal, A. S., Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem, Operations Research, 31, 507-521, (1983) · Zbl 0523.90060
[14] Ruben, R. A.; Jacobs, F. R., Batch construction heuristics and storage assignment strategies for walk/ride and Pick systems, Management Science, 45, 575-596, (1999) · Zbl 1231.90054
[15] Tompkins, J. A.; Bozer, Y. A.; Tanchoco, J. M.A., Facilities planning, (2003), John Wiley Hoboken, NJ
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.