# zbMATH — the first resource for mathematics

A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse. (English) Zbl 1304.90040
Summary: Batching customer orders in a warehouse can result in considerable savings in order pickers’ travel distances. Many picker-to-parts warehouses have precedence constraints in picking a customer order. In this paper a joint order-batching and picker routing method is introduced to solve this combined precedence-constrained routing and order-batching problem. It consists of two sub-algorithms: an optimal $$A^\ast$$-algorithm for the routing; and a simulated annealing algorithm for the batching which estimates the savings gained from batching more than two customer orders to avoid unnecessary routing. For batches of three customer orders, the introduced algorithm produces results with an error of less than 1.2% compared to the optimal solution. It also compares well to other heuristics from literature. A data set from a large Finnish order picking warehouse is rerouted and rebatched resulting in savings of over 5000kilometres or 16% in travel distance in 3months compared to the current method.

##### MSC:
 90B06 Transportation, logistics and supply chain management 90C59 Approximation methods and heuristics in mathematical programming 90B90 Case-oriented studies in operations research
##### Keywords:
heuristics; logistics; order picking; batching; precedence
LKH
Full Text:
##### References:
 [1] Albareda-Sambola, M.; Alonso-Ayuso, A.; Molina, E.; De Blas, C., Variable neighborhood search for order batching in a warehouse, Asia-Pacific Journal of Operational Research, 26, 05, 655-683, (2009) · Zbl 1178.90118 [2] Chan, F., Kumar, V., 2008. A TSSA algorithm based approach to enhance the performance of warehouse system. In: 10th IEEE International Conference on Control, Automation, Robotics and Vision, 2008. ICARCV, pp. 1696-1701. [3] Clarke, G.; Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, 568-581, (1964) [4] Cohn, H.; Fielding, M., Simulated annealing: searching for an optimal temperature schedule, SIAM Journal on Optimization, 9, 3, 779, (1999) · Zbl 0957.60072 [5] Coyle, J.; Bardi, E.; Langley, C., The management of business logistics, (1996), West Publishing Company [6] Dekker, R.; De Koster, R.; Roodbergen, K.; Van Kalleveen, H., Improving order-picking response time at ankor’s warehouse, Interfaces, 34, 4, 303-313, (2004) [7] De Koster, R.; Van der Poort, E., Routing order pickers in a warehouse: a comparison between optimal and heuristic solutions, IIE Transactions, 30, 5, 469-480, (1998) [8] De Koster, R.; Van der Poort, E.; Wolters, M., Efficient orderbatching methods in warehouses, International Journal of Production Research, 37, 7, 1479-1504, (1999) · Zbl 0948.90508 [9] De Koster, R.; Le-Duc, T.; Roodbergen, K., Design and control of warehouse order picking: a literature review, European Journal of Operational Research, 182, 2, 481-501, (2007) · Zbl 1121.90385 [10] Drury, J., Towards More Efficient Order Picking, IMM Monograph 1, (1988), The Institute of Materials Management Cranfield, UK [11] Escudero, L., An inexact algorithm for the sequential ordering problem, European Journal of Operational Research, 37, 2, 236-249, (1988) · Zbl 0653.90036 [12] Gademann, N.; Van de Velde, S., Order batching to minimize total travel time in a parallel-aisle warehouse, IIE Transactions, 37, 1, 63-75, (2005) [13] Hart, P.; Nilsson, N.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics, 4, 2, 100-107, (1968) [14] Helsgaun, K., An effective implementation of the lin-kernighan traveling salesman heuristic, European Journal of Operational Research, 126, 1, 106-130, (2000) · Zbl 0969.90073 [15] Henn, S.; Wäscher, G., Tabu search heuristics for the order batching problem in manual order picking systems, European Journal of Operational Research., (2012) · Zbl 1253.90008 [16] Hong, S.; Johnson, A.; Peters, B., Batch picking in narrow-aisle order picking systems with consideration for picker blocking, European Journal of Operational Research., (2012) · Zbl 1253.90009 [17] Hong, S.; Johnson, A.; Peters, B., Large-scale order batching in parallel-aisle picking systems, IIE Transactions, 44, 2, 88-106, (2012) [18] Hsieh, L.; Huang, Y., New batch construction heuristics to optimise the performance of order picking systems, International Journal of Production Economics, 131, 2, 618-630, (2011) [19] Kohonen, T., The self-organizing map, Proceedings of the IEEE, 78, 9, 1464-1480, (1990) [20] Kubo, M.; Kasugai, H., The precedence constrained traveling salesman problem, Journal of the Operations Research Society of Japan, 34, 2, 152-172, (1991) · Zbl 0747.90102 [21] Lundy, M.; Mees, A., Convergence of an annealing algorithm, Mathematical Programming, 34, 1, 111-124, (1986) · Zbl 0581.90061 [22] MacQueen, J., 1967. Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1. California, USA, p. 14. · Zbl 0214.46201 [23] Miller, C.; Tucker, A.; Zemlin, R., Integer programming formulation of traveling salesman problems, Journal of the ACM, 7, 326-329, (1960) · Zbl 0100.15101 [24] Psaraftis, H., A dynamic programming approach for sequencing groups of identical jobs, Operations Research, 28, 6, 1347-1359, (1980) · Zbl 0447.90040 [25] Psaraftis, H., Dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem, Transportation Science, 14, 2, 130-154, (1980) [26] Psaraftis, H., An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows, Transportation Science, 17, 3, 351-357, (1983) [27] Randolph, W., Distance approximations for routing manual pickers in a warehouse, IIE Transactions, 25, 4, 76-87, (1993) [28] Ratliff, H.; Rosenthal, A., Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem, Operations Research, 31, 3, 507-521, (1983) · Zbl 0523.90060 [29] Roodbergen, K.; De Koster, R., Routing methods for warehouses with multiple cross aisles, International Journal of Production Research, 39, 9, 1865-1883, (2001) · Zbl 1060.90519 [30] Roodbergen, K.; De Koster, R., Routing order pickers in a warehouse with a middle aisle, European Journal of Operational Research, 133, 1, 32-43, (2001) · Zbl 0989.90025 [31] Theys, C.; Braysy, O.; Dullaert, W.; Raa, B., Using a TSP heuristic for routing order pickers in warehouses, European Journal of Operational Research, 200, 3, 755-763, (2010) · Zbl 1177.90044 [32] Tompkins, J.; White, J.; Bozer, Y.; Tanchoco, J., Facilities planning, (2003), John Wiley & Sons [33] Whittley, I.; Smith, G., The attribute based Hill climber, Journal of Mathematical Modelling and Algorithms, 3, 2, 167-178, (2004) · Zbl 1062.90078
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.