Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic

References

• Altarazi, S. A., and M. M. Ammouri. 2018. “Concurrent Manual-Order-Picking Warehouse Design: A Simulation-Based Design of Experiments Approach.” International Journal of Production Research. doi:10.1080/00207543.2017.1421780.
   PubMed Web of Science ®Google Scholar
• Applegate, D. L., R. E. Bixby, and V. Chvátal. 2011. The Traveling Salesman Problem: A Computational Study. Princeton, NJ: Princeton University Press.
   Google Scholar
• Baïou, M., and A. R. Mahjoub. 2002. “The Steiner Traveling Salesman Polytope and Related Polyhedra.” SIAM Journal of Optimization 13 (2): 498–507. doi: 10.1137/S1052623400322287
   Web of Science ®Google Scholar
• Bartholdi, J. J., and S. Hackman. 2016. “Warehouse and Distribution Science.” Release 0.97. Accessed July 2017. http://www.isye.gatech.edu/jjb/wh/book/editions/wh-sci-0.97.pdf.
   Google Scholar
• Bellmore, M., and G. L. Nemhauser. 1968. “The Traveling Salesman Problem: A Survey.” Operations Research 16 (3): 538–558. doi: 10.1287/opre.16.3.538
   Web of Science ®Google Scholar
• Burkard, R. E., V. G. Deineko, R. Van Dal, J. A. A. Van Der Veen, and G. J. Woeginger. 1998. “Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey.” SIAM Review 40 (3): 496–546. doi: 10.1137/S0036144596297514
   Web of Science ®Google Scholar
• Çelik, M., and H. Süral. 2016. “Order Picking in a Parallel-Aisle Warehouse with Turn Penalties.” International Journal of Production Research 54 (14): 4340–4355. doi: 10.1080/00207543.2016.1154624
   Web of Science ®Google Scholar
• Chabot, T., R. Lahyani, L. C. Coelho, and J. Renaud. 2017. “Order Picking Problems under Weight, Fragility and Category Constraints.” International Journal of Production Research 55 (21): 6361–6379. doi: 10.1080/00207543.2016.1251625
   Web of Science ®Google Scholar
• Chackelson, C., A. Errasti, D. Ciprés, and F. Lahoz. 2013. “Evaluating Order Picking Performance Trade-Offs by Configuring Main Operating Strategies in a Retail Distributor: A Design of Experiments Approach.” International Journal of Production Research 51 (20): 6097–6109. doi: 10.1080/00207543.2013.796421
   Web of Science ®Google Scholar
• Chen, T. L., C. Y. Cheng, Y. Y. Chen, and L. K. Chan. 2015. “An Efficient Hybrid Algorithm for Integrated Order Batching, Sequencing and Routing Problem.” International Journal of Production Economics 159: 158–167. doi: 10.1016/j.ijpe.2014.09.029
   Web of Science ®Google Scholar
• Chen, F., H. Wang, C. Qi, and Y. Xie. 2013. “An Ant Colony Optimization Routing Algorithm for Two Order Pickers with Congestion Consideration.” Computers and Industrial Engineering 66 (1): 77–85. doi: 10.1016/j.cie.2013.06.013
   Web of Science ®Google Scholar
• Chen, F., H. Wang, Y. Xie, and C. Qi. 2016. “An ACO-Based Online Routing Method for Multiple Order Pickers with Congestion Consideration in Warehouse.” Journal of Intelligent Manufacturing 27 (2): 389–408. doi: 10.1007/s10845-014-0871-1
   Web of Science ®Google Scholar
• Chen, F., Y. Wei, and H. Wang. 2017. “A Heuristic Based Batching and Assigning Method for Online Customer Orders.” Flexible Services and Manufacturing Journal. doi:10.1007/s10696–017–9277–7.
   Web of Science ®Google Scholar
• Cheng, C. Y., Y. Y. Chen, T. L. Chen, and J. J. W. Yoo. 2015. “Using a Hybrid Approach Based on the Particle Swarm Optimization and Ant Colony Optimization to Solve a Joint Order Batching and Picker Routing Problem.” International Journal of Production Economics 170: 805–814. doi: 10.1016/j.ijpe.2015.03.021
   Web of Science ®Google Scholar
• Cornuéjols, G., J. Fonlupt, and D. Naddef. 1985. “The Traveling Salesman Problem on a Graph and Some Related Integer Polyhedra.” Mathematical Programming 33: 1–27. doi: 10.1007/BF01582008
   Web of Science ®Google Scholar
• De Koster, R., R. Le-Duc, and K. J. Roodbergen. 2007. “Design and Control of Warehouse Order Picking: A Literature Review.” European Journal of Operational Research 182 (2): 481–501. doi: 10.1016/j.ejor.2006.07.009
   Web of Science ®Google Scholar
• De Koster, R., and E. van der Poort. 1998. “Routing Orderpickers in a Warehouse: A Comparison Between Optimal and Heuristic Solutions.” IIE Transactions 30: 469–480. doi: 10.1080/07408179808966487
   Web of Science ®Google Scholar
• De Santis, R., R. Montanari, G. Vignali, and E. Bottani. 2018. “An Adapted Ant Colony Optimization Algorithm for the Minimization of the Travel Distance of Pickers in Manual Warehouses.” European Journal of Operational Research 267 (1): 120–137. doi: 10.1016/j.ejor.2017.11.017
   Web of Science ®Google Scholar
• Dijkstra, A. S., and K. J. Roodbergen. 2017. “Exact Route-Length Formulas and a Storage Location Assignment Heuristic for Picker-to-Parts Warehouses.” Transportation Research Part E: Logistics and Transportation Review 102: 38–59. doi: 10.1016/j.tre.2017.04.003
   Web of Science ®Google Scholar
• Garey, M. R., R. L. Graham, and D. S. Johnson. 1976. “Some NP-Complete Geometric Problems.” In Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 10–22. New York: Association for Computing Machinery.
   Google Scholar
• Garey, M. R., and D. S. Johnson. 1979. Computers and Intractability. New York: W. H. Freeman.
   Google Scholar
• Giannikas, V., W. Lu, B. Robertson, and D. McFarlane. 2017. “An Interventionist Strategy for Warehouse Order Picking: Evidence from Two Case Studies.” International Journal of Production Economics 189: 63–76. doi: 10.1016/j.ijpe.2017.04.002
   Web of Science ®Google Scholar
• Grosse, E. H., C. H. Glock, M. Y. Jaber, and W. P. Neumann. 2015. “Incorporating Human Factors in Order Picking Planning Models: Framework and Research Opportunities.” International Journal of Production Research 53 (3): 695–717. doi: 10.1080/00207543.2014.919424
   Web of Science ®Google Scholar
• Gue, K. R., and R. D. Meller. 2009. “Aisle Configurations for Unit-Load Warehouses.” IIE Transactions 41 (3): 171–182. doi: 10.1080/07408170802112726
   Web of Science ®Google Scholar
• Hall, R. W. 1993. “Distance Approximations for Routing Manual Pickers in a Warehouse.” IIE Transactions 25 (4): 76–87. doi: 10.1080/07408179308964306
   Web of Science ®Google Scholar
• Helsgaun, K. 2000. “An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.” European Journal of Operational Research 126 (1): 106–130. doi: 10.1016/S0377-2217(99)00284-2
   Web of Science ®Google Scholar
• Henn, S., and V. Schmid. 2013. “Metaheuristics for Order Batching and Sequencing in Manual Order Picking Systems.” Computers and Industrial Engineering 66 (2): 338–351. doi: 10.1016/j.cie.2013.07.003
   Web of Science ®Google Scholar
• Itai, A., C. H. Papadimitriou, and J. L. Szwarcfiter. 1982. “Hamilton Paths in Grid Graphs.” SIAM Journal of Computing 11 (4): 676–686. doi: 10.1137/0211056
   Web of Science ®Google Scholar
• Johnson, D. S., and C. H. Papadimitriou. 1985. “Computational Complexity.” In The Traveling Salesman Problem, edited by E. L. Lawler, J. K. Lenstra, J. K. Rinnooy Kan, and D. B. Shmoys, 37–85. Hoboken, NJ: John Wiley.
   Google Scholar
• Karp, R. M. 1972. “Reducibility among Combinatorial Problems.” In Complexity of Computer Computations, edited by R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, 85–103. Boston, MA: Springer US.
   Google Scholar
• Kou, X., G. Xu, and C. Yi. 2018. “Belt-Conveyor Based Efficient Parallel Storage System Design and Travel Time Model Analysis.” International Journal of Production Research. doi:10.1080/00207543.2018.1436784.
   PubMed Web of Science ®Google Scholar
• Li, J., R. Huang, and J. B. Dai. 2017. “Joint Optimisation of Order Batching and Picker Routing in the Online Retailer's Warehouse in China.” International Journal of Production Research 55 (2): 447–461. doi: 10.1080/00207543.2016.1187313
   Web of Science ®Google Scholar
• Lin, S. 1965. “Computer Solution of the Traveling Salesman Problem.” Bell Systems Technical Journal 44: 2245–2269. doi: 10.1002/j.1538-7305.1965.tb04146.x
   Google Scholar
• Lin, C. C., J. R. Kang, C. C. Hou, and C. Y. Cheng. 2016. “Joint Order Batching and Picker Manhattan Routing Problem.” Computers and Industrial Engineering 95: 164–174. doi: 10.1016/j.cie.2016.03.009
   Web of Science ®Google Scholar
• Makris, P. A., and I. G. Giakoumakis. 2003. “k-Interchange Heuristic as an Optimization Procedure for Material Handling Applications.” Applied Mathematical Modelling 27 (5): 345–358. doi: 10.1016/S0307-904X(02)00137-3
   Web of Science ®Google Scholar
• Matthews, J., and S. Visagie. 2013. “Order Sequencing on a Unidirectional Cyclical Picking Line.” European Journal of Operational Research 231 (1): 79–87. doi: 10.1016/j.ejor.2013.05.011
   Web of Science ®Google Scholar
• Matusiak, M., R. de Koster, L. Kroon, and J. Saarinen. 2014. “A Fast Simulated Annealing Method for Batching Precedence-Constrained Customer Orders in a Warehouse.” European Journal of Operational Research 236 (3): 968–977. doi: 10.1016/j.ejor.2013.06.001
   Web of Science ®Google Scholar
• Öncan, T. 2015. “MILP Formulations and an Iterated Local Search Algorithm with Tabu Thresholding for the Order Batching Problem.” European Journal of Operational Research 243 (1): 142–155. doi: 10.1016/j.ejor.2014.11.025
   Web of Science ®Google Scholar
• Öztürkoğlu, Ö., K. R. Gue, and R. D. Meller. 2012. “Optimal Unit-Load Warehouse Designs for Single-Command Operations.” IIE Transactions 44 (6): 459–475. doi: 10.1080/0740817X.2011.636793
   Web of Science ®Google Scholar
• Pansart, L., N. Catusse, and H. Cambazard. 2017. “Exact Algorithms for the Picking Problem.” ArXiv:1703.00699.
   Google Scholar
• Papadimitriou, C. H. 1977. “The Euclidean Travelling Salesman Problem Is NP-Complete.” Theoretical Computer Science 4 (3): 237–244. doi: 10.1016/0304-3975(77)90012-3
   Google Scholar
• Ratliff, H. D., and A. S. Rosenthal. 1983. “Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem.” Operations Research 31 (3): 507–521. doi: 10.1287/opre.31.3.507
   Web of Science ®Google Scholar
• Roodbergen, K. J., and R. de Koster. 2001a. “Routing Methods for Warehouses with Multiple Cross Aisles.” International Journal of Production Research 39 (9): 1865–1883. doi: 10.1080/00207540110028128
   Web of Science ®Google Scholar
• Roodbergen, K. J., and R. de Koster. 2001b. “Routing Order Pickers in a Warehouse with a Middle Aisle.” European Journal of Operational Research 133 (1): 32–43. doi: 10.1016/S0377-2217(00)00177-6
   Web of Science ®Google Scholar
• Roodbergen, K. J., I. F. A. Vis, and G. D. Taylor. 2015. “Simultaneous Determination of Warehouse Layout and Control Policies.” International Journal of Production Research 53 (11): 3306–3326. doi: 10.1080/00207543.2014.978029
   Web of Science ®Google Scholar
• Ruberg, Y., and A. Scholz. 2016. “A Mathematical Programming Formulation for the Single-Picker Routing Problem in a Multi-Block Layout.” Working Paper 2/2016. Faculty of Economics and Management, Universität Magdeburg, Germany.
   Google Scholar
• Scholz, A. 2016. “An Exact Solution Approach for the Single-Picker Routing Problem in Warehouses with an Arbitrary Block Layout.” Working Paper 6/2016. Faculty of Economics and Management, Universität Magdeburg, Germany.
   Google Scholar
• Scholz, A., S. Henn, M. Stuhlmann, and G. Wäscher. 2016. “A New Mathematical Programming Formulation for the Single-Picker Routing Problem.” European Journal of Operational Research 253 (1): 68–84. doi: 10.1016/j.ejor.2016.02.018
   Web of Science ®Google Scholar
• Scholz, A., and G. Wäscher. 2017. “Order Batching and Picker Routing in Manual Order Picking Systems: The Benefits of Integrated Routing.” Central European Journal of Operations Research 25 (2): 491–520. doi: 10.1007/s10100-017-0467-x
   Web of Science ®Google Scholar
• Shqair, M., S. Altarazi, and S. Al-Shihabi. 2014. “A Statistical Study Employing Agent-Based Modeling to Estimate the Effects of Different Warehouse Parameters on the Distance Traveled in Warehouses.” Simulation Modelling Practice and Theory 49: 122–135. doi: 10.1016/j.simpat.2014.08.002
   Web of Science ®Google Scholar
• Theys, C., O. Bräysy, W. Dullaert, and B. Raa. 2010. “Using a TSP Heuristic for Routing Order Pickers in Warehouses.” European Journal of Operational Research 200 (3): 755–763. doi: 10.1016/j.ejor.2009.01.036
   Web of Science ®Google Scholar
• Tompkins, J. A., J. A. White, Y. A. Bozer, and J. M. A. Tanchoco. 2010. Facilities Planning. Hoboken, NJ: John Wiley.
   Google Scholar
• Umans, C., and W. Lenhart. 1997. “Hamiltonian Cycles in Solid Grid Graphs.” In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 496–505. Miami Beach, FL: IEEE.
   Google Scholar
• Valle, C. A., J. E. Beasley, and A. S. da Cunha. 2017. “Optimally Solving the Joint Order Batching and Picker Routing Problem.” European Journal of Operational Research 262 (3): 817–834. doi: 10.1016/j.ejor.2017.03.069
   Web of Science ®Google Scholar
• van Gils, T., K. Ramaekers, A. Caris, and R. B. M. de Koster. 2018. “Designing Efficient Order Picking Systems by Combining Planning Problems: State-of-the-Art Classification and Review.” European Journal of Operational Research 267 (1): 1–15. doi: 10.1016/j.ejor.2017.09.002
   Web of Science ®Google Scholar
• Vaughan, T. S., and C. G. Petersen. 1999. “The Effect of Warehouse Cross Aisles on Order Picking Efficiency.” International Journal of Production Research 37 (4): 881–897. doi: 10.1080/002075499191580
   Web of Science ®Google Scholar
• Wu, Y., C. Zhou, Y. Wu, and X. T. R. Kong. 2017. “Zone Merge Sequencing in an Automated Order Picking System.” International Journal of Production Research 55 (21): 6500–6515. doi: 10.1080/00207543.2016.1264641
   Web of Science ®Google Scholar