×

zbMATH — the first resource for mathematics

Using a TSP heuristic for routing order pickers in warehouses. (English) Zbl 1177.90044
Summary: We deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin-Kernighan-Helsgaun) TSP heuristic. Additionally, we examine if combining problem-specific solution concepts from dedicated heuristics with high-quality local search features could be useful. Lastly, we verify whether the sophistication of ‘state-of-the-art’ local search heuristics is necessary for routing order pickers in warehouses, or whether a subset of features suffices to generate high-quality solutions.

MSC:
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Applegate, D., Bixby, R., Chvátal, V., Cook, W., 2008. Concorde TSP Solver. URL <http://www.tsp.gatech.edu/concorde/>.
[2] Bartholdi, J.J., Hackman, S.T., 2006. Warehouse and Distribution Science. Release 0.80. URL <http://www.warehouse-science.com>.
[3] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transportation science, 39, 104-118, (2005)
[4] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part II: metaheuristics, Transportation science, 39, 119-139, (2005)
[5] Cornuéjols, G.; Fonlupt, J.; Naddef, D., The traveling salesman problem on a graph and some related integer polyhedra, Mathematical programming, 33, 1-27, (1985) · Zbl 0562.90095
[6] Coyle, J.J.; Bardi, E.J.; Langley, C.J., The management of business logistics, (1996), St. Paul West
[7] Daniels, R.L.; Rummel, J.L.; Schantz, R., A model for warehouse order picking, European journal of operational research, 105, 1-17, (1998) · Zbl 0957.90002
[8] 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
[9] De Koster, R.; Van der Poort, E.S., Routing orderpickers in a warehouse: A comparison between optimal and heuristic solutions, IIE transactions, 30, 469-480, (1998)
[10] Drury, J., 1988. Towards more efficient order picking. IMM Monograph No. 1, Report. The Institute of Materials Management, Cranfield.
[11] Gendreau, M.; Potvin, J.-Y.; Bräysy, O.; Hasle, G.; Løkketangen, A., Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography, (), 143-169 · Zbl 1187.90001
[12] Goetschalckx, M.; Ratliff, H.D., Order picking in an aisle, IIE transactions, 20, 53-62, (1988)
[13] ()
[14] Gu, J.; Goetschalckx, M.; McGinnis, L.F., Research on warehouse operation: A comprehensive review, European journal of operational research, 177, 1-21, (2007) · Zbl 1111.90321
[15] Hall, R.W., Distance approximation for routing manual pickers in a warehouse, IIE transactions, 25, 76-87, (1993)
[16] Helsgaun, K., An effective implementation of the lin – kernighan traveling salesman heuristic, European journal of operational research, 126, 106-130, (2000) · Zbl 0969.90073
[17] Le-Duc, T.; De Koster, R.B.M., Travel distance estimation and storage zone optimization in a 2-block class-based storage strategy warehouse, International journal of production research, 43, 3561-3581, (2005) · Zbl 1082.90504
[18] Makris, P.A.; Giakoumakis, I.G., k-interchange heuristic as an optimization procedure for material handling applications, Applied mathematical modelling, 27, 345-358, (2003) · Zbl 1023.90014
[19] Matsumoto, M.; Nishimura, T., Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM transactions on modeling and computer simulation, 8, 3-30, (1998) · Zbl 0917.65005
[20] Petersen, C.G., Routing and storage policy interaction in order picking operations, Decision sciences institute Proceedings, 1614-1616, (1995)
[21] Petersen, C.G., An evaluation of order picking routing policies, International journal of operations and production management, 17, 1098-1111, (1997)
[22] Petersen, C.G., The impact of routing and storage policies on warehouse efficiency, International journal of operations and production management, 19, 1053-1064, (1999)
[23] Petersen, C.G.; Aase, G., A comparison of picking, storage, and routing policies in manual order picking, International journal of production economics, 92, 11-19, (2004)
[24] Petersen, C.G.; Schmenner, R.W., An evaluation of routing and volume-based storage policies in an order picking operation, Decision sciences, 30, 481-501, (1999)
[25] 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
[26] Renaud, J., Ruiz, A., forthcoming. Improving product location and order picking activities in a distribution centre. Journal of the Operational Research Society. · Zbl 1155.90443
[27] Roodbergen, K.J., 2001. Layout and routing methods for warehouses. Ph.D. Thesis, RSM Erasmus Universiteit Rotterdam, The Netherlands. · Zbl 1060.90519
[28] Roodbergen, K.J.; De Koster, R., Routing order pickers in a warehouse with a middle aisle, European journal of operational research, 133, 32-43, (2001) · Zbl 0989.90025
[29] Theys, C., Dullaert, W., Herroelen, W., 2007. Routing order pickers in multiple block warehouses. In: Hilferink, P., Rietveld, P., van den Hanenberg, T. (Eds.), Proceedings of the BIVEC-GIBET Research Day. Nautilus Academic Books Zelzate, Rotterdam, The Netherlands, pp. 10-30.
[30] Vaughan, T.S.; Petersen, C.G., The effect of warehouse cross aisles on order picking efficiency, International journal of production research, 37, 881-897, (1999) · Zbl 0940.90516
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.