×

zbMATH — the first resource for mathematics

Optimally solving the joint order batching and picker routing problem. (English) Zbl 1375.90025
Summary: We investigate the problem of order batching and picker routing in storage areas. These are labour and capital intensive problems, often responsible for a substantial share of warehouse operating costs. In particular, we consider the case of online grocery shopping in which orders may be composed of dozens of items. We present a formulation for the problem based on an exponential number of connectivity constraints and we introduce a significant number of valid inequalities based on the standard layout of warehouses, composed of parallel aisles and two or more cross-aisles. The proposed inequalities are highly effective and greatly improve computational results. Instances involving up to 20 orders are solved to proven optimality when we jointly consider order batching and picker routing. Instances involving up to 5000 orders are considered where order batching is done heuristically, but picker routing is done optimally.

MSC:
90B05 Inventory, storage, reservoirs
90B06 Transportation, logistics and supply chain management
90C10 Integer programming
Software:
MySQL; CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albareda-Sambola, M.; Alonso-Ayuso, A.; Molina, E.; de Blas, C. S., Variable neighborhood search for order batching in a warehouse, Asia-Pacific Journal of Operational Research, 26, 05, 655-683, (2009) · Zbl 1178.90118
[2] Azadnia, A. H.; Taheri, S.; Ghadimi, P.; Saman, M. Z.M.; Wong, K. Y., Order batching in warehouses by minimizing total tardiness: A hybrid approach of weighted association rule mining and genetic algorithms, The Scientific World Journal, 2013, 1, 1-13, (2013)
[3] Baldacci, R.; Christofides, N.; Mingozzi, A., An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Mathematical Programming, 115, 2, 351-385, (2008) · Zbl 1279.90139
[4] Bartholdi, J. J.; Hackman, S. T., Warehouse & distribution science, release 0.97, (2016)
[5] Belenguer, J. M.; Benavent, E., The capacitated arc routing problem: valid inequalities and facets, Computational Optimization and Applications, 10, 2, 165-187, (1998) · Zbl 0895.90083
[6] Bosco, A.; Laganà, D.; Musmanno, R.; Vocaturo, F., Modeling and solving the mixed capacitated general routing problem, Optimization Letters, 7, 7, 1451-1469, (2013) · Zbl 1280.90008
[7] Chen, M. C.; Wu, H. P., An association-based clustering approach to order batching considering customer demand patterns, Omega, 33, 4, 333-343, (2004)
[8] Cornuéjols, G.; Fonlupt, J.; Naddef, D., The travelling salesman problem on a graph and some related integer polyhedra, Mathematical Programming, 33, 1, 1-27, (1985) · Zbl 0562.90095
[9] Cornuéjols, G.; Naddef, D.; Pulleyblank, W. R., Halin graphs and the travelling salesman problem, Mathematical Programming, 26, 3, 287-294, (1983) · Zbl 0506.90083
[10] CPLEX Optimizer (2016). IBM. Available from http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. Last accessed 15.06.16.
[11] 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, 2, 481-501, (2007) · Zbl 1121.90385
[12] Dekker, R.; de Koster, M. B.M.; Roodbergen, K. J.; van Kalleveen, H., Improving order-picking response time at ankor’s warehouse, Interfaces, 34, 4, 303-313, (2004)
[13] Fleischmann, B., A cutting-plane procedure for the traveling salesman problem on a road network, European Journal of Operational Research, 21, 3, 307-317, (1985) · Zbl 0586.90083
[14] Fonlupt, J.; Nachef, A., Dynamic programming and the graphical traveling salesman problem, Journal of the ACM, 40, 5, 1165-1187, (1993) · Zbl 0795.68174
[15] Fonlupt, J.; Naddef, D., The travelling salesman problem in graphs with some excluded minors, Mathematical Programming, 53, 2, 147-172, (1992) · Zbl 0780.05034
[16] Fukasawa, R.; Longo, H.; Lysgaard, J.; Aragão, M. P.; Reis, M.; Uchoa, E.; Werneck, R. F., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Mathematical Programming, 106, 3, 491-511, (2006) · Zbl 1094.90050
[17] Gibson, D. R.; Sharp, G. P., Order batching procedures, European Journal of Operational Research, 58, 1, 57-67, (1992)
[18] Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum flow problem, Journal of the ACM, 35, 4, 921-940, (1988) · Zbl 0661.90031
[19] 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)
[20] Hays, T.; Keskinocak, P.; de Lopez, V. M., Strategies and challenges of Internet grocery retailing logistics, (Geunes, J.; Akcali, E.; Pardalos, P. M.; Romeijn, H. E.; Shen, Z. J., (2005), Kluwer Academic Publishers), 217-252 · Zbl 1072.90504
[21] Henn, S.; Koch, S.; Wäscher, G., Order batching in order picking warehouses: A survey of solution approaches, (Manzini, R., (2012), Springer London), 105-137)
[22] Henn, S.; Schmid, V., Metaheuristics for order batching and sequencing in manual order picking systems, Computers & Industrial Engineering, 66, 2, 338-351, (2013)
[23] Henn, S.; Wäscher, G., Tabu search heuristics for the order batching problem in manual order picking systems, European Journal of Operational Research, 222, 3, 484-494, (2012) · Zbl 1253.90008
[24] 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, 3, 557-570, (2012) · Zbl 1253.90009
[25] Hong, S.; Johnson, A. L.; Peters, B. A., Large-scale order batching in parallel-aisle picking systems, IIE Transactions, 44, 2, 88-106, (2012)
[26] Hong, S.; Johnson, A. L.; Peters, B. A., Order batching in a bucket brigade order picking system considering picker blocking, Flexible Services and Manufacturing Journal, 28, 3, 425-441, (2016)
[27] Hooker, J. N.; Yan, H.; Grossmann, I.; Raman, R., Logic cuts for processing networks with fixed charges, Computers & Operations Research, 21, 3, 265-279, (1994) · Zbl 0789.90057
[28] Hsu, C. M.; Chen, K. Y.; Chen, M. C., Batching orders in warehouses by minimizing travel distance with genetic algorithms, Computers in Industry, 56, 2, 169-178, (2004)
[29] Irnich, S.; Lagan, D.; Schlebusch, C.; Vocaturo, F., Two-phase branch-and-cut for the mixed capacitated general routing problem, European Journal of Operational Research, 243, 1, 17-29, (2015) · Zbl 1346.90219
[30] de Koster, R.; van der Poort, E. S.; Wolters, M., Efficient order batching methods in warehouses, International Journal of Production Research, 37, 7, 1479-1504, (1999) · Zbl 0948.90508
[31] Lam, C. H.; Choy, K.; Ho, G.; Lee, C., An order-picking operations system for managing the batching activities in a warehouse, International Journal of Systems Science, 45, 6, 1283-1295, (2014) · Zbl 1302.90115
[32] Letchford, A. N.; Nasiri, S. D.; Theis, D. O., Compact formulations of the Steiner traveling salesman problem and related problems, European Journal of Operational Research, 228, 1, 83-92, (2013) · Zbl 1332.90329
[33] Letchford, A. N.; Oukil, A., Vehicle routing on sparse graphs: A literature review and an analysis, (2006)
[34] Letchford, A. N.; Oukil, A., Exploiting sparsity in pricing routines for the capacitated arc routing problem, Computers & Operations Research, 36, 7, 2320-2327, (2009) · Zbl 1158.90321
[35] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21, 2, 498-516, (1973) · Zbl 0256.90038
[36] Lucena, A., Steiner problem in graphs: Lagrangean relaxation and cutting planes, COAL Bulletin, 21, 1, 2-8, (1992)
[37] 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, 3, 968-977, (2014) · Zbl 1304.90040
[38] MySQL Foodmart Database (2008). Available from http://pentaho.dlpage.phi-integration.com/mondrian/mysql-foodmart-database. Last accessed 15.06.16.
[39] Naddef, D., Polyhedral theory and branch-and-cut algorithms for the symmetric TSP, The traveling salesman problem and its variations, 29-116, (2007), Springer US · Zbl 1113.90360
[40] Orloff, C. S., A fundamental problem in vehicle routing, Networks, 4, 1, 35-64, (1974) · Zbl 0368.90130
[41] Padberg, M.; Rinaldi, G., Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut, Operations Research Letters, 6, 1, 1-7, (1987) · Zbl 0618.90082
[42] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, 33, 1, 60-100, (1991) · Zbl 0734.90060
[43] Petersen II, C. G., An evaluation of order picking routing policies, International Journal of Operations & Production Management, 17, 11, 1098-1111, (1997)
[44] Ratliff, H. D.; Rosenthal, A. S., Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem, Operations Research, 31, 3, 507-521, (1983) · Zbl 0523.90060
[45] Roodbergen, K. J.; de Koster, R., Routing methods for warehouses with multiple cross aisles, International Journal of Production Research, 39, 9, 1865-1883, (2001) · Zbl 1060.90519
[46] Roodbergen, K. J.; 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
[47] Schloz, A.; Henn, S.; Stuhlmann, M.; Wascher, G., A new mathematical programming formulation for the single-picker routing problem, European Journal of Operational Research, 253, 1, 68-84, (2016) · Zbl 1346.90175
[48] 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
[49] Tompkins, J. A.; White, J.; Bozer, Y.; Tanchoco, J., Facilities planning, (2010), John Wiley & Sons
[50] Valle, C. A.; Beasley, J. E.; Cunha, A. S., Modelling and solving the joint order batching and picker routing problem in inventories, (Cerulli, R.; Fujishige, S.; Mahjoub, A. R., Combinatorial optimization: 4th international symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers, LNCS, (2016), Springer International Publishing), 81-97 · Zbl 1432.90023
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.