An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses.

*(English)*Zbl 1403.90101Summary: This paper proposes a new metaheuristic routing algorithm for the minimization of the travel distance of pickers in manual warehouses. The algorithm is based on the ant colony optimization (ACO) metaheuristic, which is combined and integrated with the Floyd-Warshall (FW) algorithm, and is therefore referred to as FW-ACO. To assess the performance of the FW-ACO algorithm, two sets of analyses are carried out. Firstly, the capability of the algorithm to provide effective solutions for the picking problem is analyzed as a function of the settings of the main ACO parameters. Secondly, the performance of the FW-ACO algorithm is compared with that of six algorithms typically used to optimize the travel distance of pickers, including exact algorithms for the solution of the travelling salesman problem (where available), two heuristic routing strategies (i.e., S-shape and largest gap) and two metaheuristic algorithms (i.e., the MIN-MAX ant system and Combined+). The comparison is made considering different warehouse layouts and problem complexities. The outcomes obtained suggest that the FW-ACO is a promising algorithm generally able to provide better results than the heuristic and metaheuristic algorithms, and often able to find an exact solution. The FW-ACO algorithm also shows a very efficient computational time, which makes it suitable for defining the route of pickers in real time. The FW-ACO algorithm is finally implemented in a real case study, where constraints exist on the order in which items should be picked, to show its practical usefulness and quantify the resulting savings.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

logistics; ant-colony optimization (ACO); Floyd-Warshall (FW) algorithm; order picker routing; travel distance##### Software:

Algorithm 97
PDF
BibTeX
Cite

\textit{R. De Santis} et al., Eur. J. Oper. Res. 267, No. 1, 120--137 (2018; Zbl 1403.90101)

Full Text:
DOI

##### References:

[1] | Bäck, T., Evolutionary algorithms in theory and practice, (1996), Oxford University Press USA · Zbl 0877.68060 |

[2] | Bellman, R., On a routing problem, Quarterly of Applied Mathematics, 16, 87-90, (1958) · Zbl 0081.14403 |

[3] | Bottani, E.; Cecconi, M.; Vignali, G.; Montanari, R., Optimisation of storage allocation in order picking operations through a genetic algorithm, International Journal of Logistics: Research and Applications, 15, 2, 127-146, (2012) |

[4] | Bottani, E.; Montanari, R.; Rinaldi, M.; Vignali, G., Intelligent algorithms for warehouse management, (Kahraman, C.; Çevik Onar, S., Intelligent techniques in engineering management: Theory and applications, (2015), Springer International Publishing Switzerland), 645-667 |

[5] | Box, G.; Hunter, J.; Hunter, W., Statistics for experimenters: design, innovation, and discovery, (2005), Wiley-Interscience Hoboken (USA) · Zbl 1082.62063 |

[6] | Brezina, I.; Čičková, Z., Solving the travelling salesman problem using the ant colony optimization, Management Information Systems, 6, 4, 10-14, (2011) |

[7] | Caron, F.; Marchet, G.; Perego, A., Routing policies and COI-based storage policies in picker-to-part systems, International Journal of Production Research, 36, 3, 713-732, (1998) · Zbl 0951.90507 |

[8] | Caron, F.; Marchet, G.; Perego, A., Optimal layout in low-level picker-to-part systems, International Journal of Production Research, 38, 1, 101-111, (2000) · Zbl 0945.90508 |

[9] | Çelk, M.; Süral, H., Order picking under random and turnover-based storage policies in fishbone aisle warehouses, IIE Transactions, 46, 3, 283-300, (2014) |

[10] | Chen, F.; Wang, H.; Qi, C.; Xie, Y., An ant colony optimization routing algorithm for two order pickers with congestion consideration, Computers & Industrial Engineering, 66, 1, 77-85, (2013) |

[11] | Chen, F.; Wang, H.; Xie, Y.; Qi, C., An ACO-based online routing method for multiple order pickers with congestion consideration in warehouse, Journal of Intelligent Manufacturing, 27, 2, 389-408, (2016) |

[12] | Colorni, A.; Dorigo, M.; Maniezzo, V., Distributed optimization by ant colonies, (Proceedings of the 1991 European conference on artificial life (ECAL ’91), Paris (France), (1991)), 134-142 |

[13] | Cormen, T.; Leiserson, C.; Rivest, R., Introduction to algorithms, (2009), Massachusetts Institute of Technology USA |

[14] | Coyle, J.; Bardi, E.; Langley, C., The management of business logistics, (1996), West Publishing Company Minneapolis |

[15] | De Jong, J.; Wiering, M., Multiple ant colony systems for the busstop allocation problem, (2001), University of Utrecht, Department of Philology Utrecht (Holland), Retrieved July 2, 2015 |

[16] | de Koster, R.; Van der Poort, E., Routing orderpickers in a warehouse: A comparison between optimal and heuristic solutions, IIE Transactions, 30, 469-480, (1998) |

[17] | de Koster, R.; Le-Duc, T.; Roodbergen, J., Design and control of warehouse order picking: A literature review, European Journal of Operational Research, 182, 2, 481-501, (2007) · Zbl 1121.90385 |

[18] | de Koster, R.; Le-Duc, T.; Zaerpour, N., Determining the number of zones in a Pick-and-sort order picking system, International Journal of Production Research, 50, 3, 757-771, (2012) |

[19] | Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernetics - Part B, 26, 1, 1-13, (1996) |

[20] | Dukic, G.; Oluic, C., Order-picking methods: improving order-picking efficiency, International Journal of Logistics Systems and Management, 3, 4, 451-460, (2007) |

[21] | Eggers, J.; Feillet, D.; Kehl, S.; Wagner, M.; Yannou, B., Optimization of the keyboard arrangement problem using an ant colony algorithm, European Journal of Operational Research, 148, 672-686, (2003) · Zbl 1037.90566 |

[22] | Fidanova, S.; Marinov, P., Number of ants versus number of iterations on ant colony optimization algorithm for wireless sensor layout, (2013), Bulgarian Academy of Science, Institute of Information and Communication Technologies Bulgarian Academy of Science. Retrieved March 20, 2016, from |

[23] | Fidanova, S.; Marinov, P.; Paprzycki, M., Influence of the number of ants on multi-objective ant colony optimization algorithm for wireless sensor network layout, (Proceedings of the 2014 large-scale scientific computing, Lecture notes in computer science, 8353, (2014)), 232-239 |

[24] | Floyd, R., Algorithm 97: shortest path, Communications of the ACM, 5, 6, 345, (1962) |

[25] | Frazelle, E., World-class warehousing and material handling, (2002), McGraw Hill New York |

[26] | Fu, C.; Wang, Y.; Gu, Y.; Ma, M.; Xue, T., Routing optimization of high-level orderpickers in a rectangular warehouse, (Proceedings of the 2011 International Conference on Consumer Electronics, Communications and Networks (CECNet 2011), (2011)), 4388-4391, Article number 5768920 |

[27] | Gademann, N.; Van de Velde, S., Order batching to minimize total travel time in a parallel-aisle warehouse, IIE Transactions, 37, 63-75, (2005) |

[28] | Gu, J.; Goetschalckx, M.; McGinnis, L., Research on warehouse operation: A comprehensive review, European Journal of Operational Research, 177, 1-21, (2007) · Zbl 1111.90321 |

[29] | Hall, R., Distance approximations for routing manual pickers in a warehouse, IIE Transactions, 25, 4, 76-87, (1993) |

[30] | Henn, S., Algorithms for on-line order batching in an order picking warehouse, Computers & Operations Research, 39, 2549-2563, (2012) · Zbl 1251.90007 |

[31] | Henn, S.; Koch, S.; Wascher, G., Order batching in order picking warehouses: A survey of solution approaches, (2011), Retrieved March 18, 2016. |

[32] | Henn, S.; Schmid, V., Metaheuristics for order batching and sequencing in manual order picking systems, Computers & Industrial Engineering, 22, 338-351, (2013) |

[33] | 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 |

[34] | Jane, C.-C.; Laih, Y.-W., A clustering algorithm for item assignment in a synchronized zone order picking system, European Journal of Operational Research, 166, 489-496, (2005) · Zbl 1064.90560 |

[35] | Jarvis, J.; McDowell, E., Optimal product layout in an order picking warehouse, IIE Transactions, 23, 1, 93-102, (1991) |

[36] | Kuhlman, D, A python book: beginning python, advanced python, and python exercises, (2013), Retrieved July 2, 2016. |

[37] | Kulak, O.; Sahin, Y.; Taner, M., Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms, Flexible Services and Manufacturing Journal, 24, 1, 52-80, (2012) |

[38] | Le-Duc, T.; de Koster, R., Travel time estimation and order batching in a 2-block warehouse, European Journal of Operational Research, 176, 1, 374-388, (2007) · Zbl 1137.90332 |

[39] | Lu, W.; McFarlane, D.; Giannikas, V.; Zhang, Q., An algorithm for dynamic order-picking in warehouse operations, European Journal of Operational Research, 248, 1, 107-122, (2016) · Zbl 1346.90148 |

[40] | Lucic, P., Modeling transportation problems using concepts of swarm intelligence and soft computing, (2002), Polytechnic Institute and State University, Civil Engineering Department Virginia (USA), Retrieved June 5, 2015, from |

[41] | Manzini, R.; Bindi, F.; Ferrari, E.; Pareschi, A., Correlated storage assignment and iso-time mapping adopting tri-later stackers. A case study from tile industry, (Manzini, R., Warehousing in the global supply chain - Advanced models, tools and applications for storage systems, (2012), Springer-Verlag London), 373-396 |

[42] | Mariano, C.; Morales, E., MOAQ: an ant-Q algorithm for multiple objective optimization problems, (Proceedings of the 1999 genetic and evolutionary computation conference (GECCO-99), San-Francisco (USA), 1, (1999)), 894-901 |

[43] | 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 |

[44] | Montgomery, D.; Runger, G., Applied statistics and probability for engineers, (2003), John Wiley & Sons, Inc New York (USA) |

[45] | Mowrey, C. H.; Parikh, P. J., Mixed-width aisle configurations for order picking in distribution centers, European Journal of Operational Research, 232, 1, 87-97, (2014) · Zbl 1305.90069 |

[46] | Pan, J. C.-H.; Wu, M.-H., Throughput analysis for order picking system with multiple pickers and aisle congestion considerations, Computers & Operations Research, 39, 7, 1661-1672, (2012) · Zbl 1251.90023 |

[47] | Pan, J. C.-H; Wu, M.-H.; Chang, W.-L., A travel time estimation model for a high-level picker-to-part system with class-based storage policies, European Journal of Operational Research, 237, 1054-1066, (2014) · Zbl 1338.90062 |

[48] | Parikh, P.; Meller, R., A travel-time model for a person-onboard order picking system, European Journal of Operational Research, 200, 385-394, (2010) · Zbl 1177.90250 |

[49] | Petersen, C., An evaluation of order picking routeing policies, International Journal of Operations & Production Management, 17, 11, 1098-1111, (1997) |

[50] | Petersen, C., The impact of routing and storage policies on warehouse efficiency, International Journal of Operations & Production Management, 19, 10, 1053-1064, (1999) |

[51] | Petersen, C., Considerations in order picking zone configuration, International Journal of Operations & Production Management, 22, 7, 793-805, (2002) |

[52] | Petersen, C.; Aase, G., A comparison of picking, storage, and routing policies in manual order picking, International Journal of Production Economics, 92, 1, 11-19, (2004) |

[53] | Petersen, C.; Schmenner, R., An evaluation of routing and volume-based storage policies in an order picking operation, Decision Science, 30, 2, 481-501, (1999) |

[54] | Rao, S. S.; Adil, G. K., Optimal class boundaries, number of aisles, and Pick List size for low-level order picking systems, IIE Transactions, 45, 1309-1321, (2013) |

[55] | 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 |

[56] | Roodbergen, K.; de Koster, R., Routing orderpickers in a warehouse with multiple cross aisles, (Graves, R.; McGinnis, L.; Medeiros, D.; Ward, R.; Wilhelm, M., Progress in material handling research: 1998, (1998), Material Handling Institute Charlotte), 451-467 |

[57] | 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 |

[58] | 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 |

[59] | Roodbergen, K.; Vis, I., A model for warehouse layout, IIE Transactions, 38, 10, 799-811, (2006) |

[60] | Roodbergen, K. J.; Sharp, G. P.; Vis, I. F.A., Designing the layout structure of manual order picking areas in warehouses, IIE Transactions, 40, 1032-1045, (2008) |

[61] | Rouwenhorst, B.; Reuter, B.; Stockrahm, V.; van Houtum, G.; Mantel, R.; Zijm, W., Warehouse design and control: framework and literature review, European Journal of Operational Research, 122, 515-533, (2000) · Zbl 0961.90003 |

[62] | Scholz, A.; Henn, S.; Stuhlmann, M.; Wäscher, G., A new mathematical programming formulation for the single-picker routing problem, European Journal of Operational Research, 253, 68-84, (2016) · Zbl 1346.90175 |

[63] | Shtovba, S., Ant algorithms: theory and applications, Programming and Computer Software, 31, 4, 167-178, (2005) · Zbl 1120.90051 |

[64] | Stützle, T.; Hoos, H., MAX-MIN ant system, Future Generation Computer Systems, 16, 889-914, (2000) |

[65] | Theys, C.; Bräysy, 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 |

[66] | Tompkins, J.; White, J.; Bozer, Y.; Frazelle, E.; Tanchoco, J.; Trevin, J., Facilities planning, (1996), Wiley New York |

[67] | Van Nieuwenhuyse, I.; de Koster, R., Evaluating order throughput time in 2-block warehouses with time window batching, International Journal of Production Economics, 121, 2, 654-664, (2009) |

[68] | Vaughan, T.; Petersen, C., The effect of warehouse cross aisles on order picking efficiency, International Journal of Production Research, 37, 881-897, (1999) · Zbl 0940.90516 |

[69] | Warshall, S., A theorem on Boolean matrices, Journal of the ACM, 9, 1, 11-12, (1962) · Zbl 0118.33104 |

[70] | Webster, S.; Ruben, R.; Yang, K.-K., Impact of storage assignment decisions on a bucket brigade order picking line, Production and Operations Management, 21, 2, 276-290, (2012) |

[71] | Xing, B.; Gao, W.-J.; Nelwamondo, F.; Battle, K.; Marwala, T., Ant colony optimization for automated storage and retrieval system, (Proceedings of the 2010 IEEE congress on evolutionary computation (CEC), Barcelona (Spain), 1, (2010)), 1-7 |

[72] | Zhang, G.; Lai, K., Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem, European Journal of Operational Research, 169, 2, 413-425, (2006) · Zbl 1079.90016 |

[73] | Zhu, W.; Curry, J., Parallel ant colony for nonlinear function optimization with graphics hardware acceleration, (Proceedings of the 2009 IEEE International Conference on Systems, Man, and Cybernetics, San Antonio (USA), (2009), IEEE), 1803-1808 |

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.