Integrated Order Batching and Distribution Scheduling in a Single-block Order Picking Warehouse Considering S-Shape Routing Policy


Department of Industrial Engineering, Yazd university, Yazd, Iran


In this paper, a mixed-integer linear programming model is proposed to integrate batch picking and distribution scheduling problems in order to optimize them simultaneously in an order picking warehouse. A tow-phase heuristic algorithm is presented to solve it in reasonable time. The first phase uses a genetic algorithm to evaluate and select permutations of the given set of customers. The second phase uses the route first-cluster method to obtain an effective schedule for a given permutation of customers. Computational experiments represent that integrated approach can lead to significant reduction in the makespan. Moreover, Empirical observations on the performance of the heuristic algorithm are reported.


1.     Experimental validations of the learnable evolution model Henn, S., Koch, S., Doerner, K.F., Strauss, C. and Wäscher, G.J.B.R., "Metaheuristics for the order batching problem in manual order picking systems", Business Research,  Vol. 3, No. 1, (2010), 82-105.
2.     De Koster, M., Van der Poort, E.S. and Wolters, M.J.I.J.o.P.R., "Efficient orderbatching methods in warehouses", International Journal of Production Research,  Vol. 37, No. 7, (1999), 1479-1504.
3.     De Koster, R.J.I.T.o.E.M., "Distribution strategies for online retailers", IEEE Transactions on Engineering Management,  Vol. 50, No. 4, (2003), 448-457.
4.     Gong, Y. and De Koster, R.J.I.T., "A polling-based dynamic order picking system for online retailers", IIE transactions,  Vol. 40, No. 11, (2008), 1070-1082.
5.     Moons, S., Ramaekers, K., Caris, A., Arda, Y.J.F.S. and Journal, M., "Integration of order picking and vehicle routing in a B2C e-commerce context", Flexible Services and Manufacturing Journal,  (2017), 1-31.
6.     Hajiaghaei-Keshteli, M. and Aminnayeri, M.J.A.S.C., "Solving the integrated scheduling of production and rail transportation problem by keshtel algorithm", Applied Soft Computing,  Vol. 25, (2014), 184-203.
7.     Nasiri, E., Afshari, A. and Hajiaghaei-Keshteli, M.J.I.J.o.E.-T.C.A., "Addressing the freight consolidation and containerization problem by recent and hybridized meta-heuristic algorithms", International Journal of Engineering-Transactions C: Aspects,  Vol. 30, No. 3, (2017), 403-410.
8.     Yahyaei, M., Bashiri, M. and Garmeyi, Y.J.I.J.o.E.-T.B.A., "Multi-criteria logistic hub location by network segmentation under criteria weights uncertainty (research note)", International Journal of Engineering-Transactions B: Applications,  Vol. 27, No. 8, (2013), 1205-1214.
9.     Zhang, J., Wang, X., Huang, K.J.C. and Engineering, I., "Integrated on-line scheduling of order batching and delivery under B2C e-commerce", Computers & Industrial Engineering,  Vol. 94, (2016), 280-289.
10.   Chen, Z.-L.J.O.r., "Integrated production and outbound distribution scheduling: Review and extensions", Operations Research,  Vol. 58, No. 1, (2010), 130-148.
11.   Low, C., Chang, C.-M., Gao, B.-Y.J.I.J.o.S.S.O. and Logistics, "Integration of production scheduling and delivery in two echelon supply chain", International Journal of Systems Science: Operations and Logistics,  Vol. 4, No. 2, (2017), 122-134.
12.   Low, C., Chang, C.-M., Li, R.-K. and Huang, C.-L.J.I.J.o.P.E., "Coordination of production scheduling and delivery problems with heterogeneous fleet", International Journal of Production Economics,  Vol. 153, (2014), 139-148.
13.   Low, C., Li, R.-K. and Chang, C.-M.J.I.J.o.P.R., "Integrated scheduling of production and delivery with time windows", International Journal of Production Research,  Vol. 51, No. 3, (2013), 897-909.
14.   Henn, S.J.C. and Research, O., "Algorithms for on-line order batching in an order picking warehouse", Computers & Operations Research,  Vol. 39, No. 11, (2012), 2549-2563.
15.   Bozer, Y.A. and Kile, J.W.J.I.J.o.P.R., "Order batching in walk-and-pick order picking systems", International Journal of Production Research,  Vol. 46, No. 7, (2008), 1887-1909.
16.   Gademann, N. and Velde, S.J.I.t., "Order batching to minimize total travel time in a parallel-aisle warehouse", IIE Transactions,  Vol. 37, No. 1, (2005), 63-75.
17.   Elsayed, E.A.J.T.I.J.o.P.R., "Algorithms for optimal material handling in automatic warehousing systems", The International Journal of Production Research,  Vol. 19, No. 5, (1981), 525-535.
18.   Gibson, D.R. and Sharp, G.P.J.E.J.o.O.R., "Order batching procedures", European Journal of Operational Research,  Vol. 58, No. 1, (1992), 57-67.
19.   Henn, S. and Wäscher, G.J.E.J.o.O.R., "Tabu search heuristics for the order batching problem in manual order picking systems", European Journal of Operational Research,  Vol. 222, No. 3, (2012), 484-494.
20.   Henn, S.J.F.S. and Journal, M., "Order batching and sequencing for the minimization of the total tardiness in picker-to-part warehouses", Flexible Services and Manufacturing Journal,  Vol. 27, No. 1, (2015), 86-114.
21.   Lin, C.-C., Kang, J.-R., Hou, C.-C., Cheng, C.-Y.J.C. and Engineering, I., "Joint order batching and picker manhattan routing problem", Computers & Industrial Engineering,  Vol. 95, (2016), 164-174.
22.   Matusiak, M., de Koster, R., Kroon, L. and Saarinen, J.J.E.J.o.O.R., "A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse", European Journal of Operational Research,  Vol. 236, No. 3, (2014), 968-977.
23.   Menéndez, B., Pardo, E.G., Alonso-Ayuso, A., Molina, E., Duarte, A.J.C. and Research, O., "Variable neighborhood search strategies for the order batching problem", Computers & Operations Research,  Vol. 78, (2017), 500-512.
24.   Zhang, J., Wang, X., Chan, F.T. and Ruan, J.J.A.M.M., "On-line order batching and sequencing problem with multiple pickers: A hybrid rule-based algorithm", Applied Mathematical Modelling,  Vol. 45, (2017), 271-284.
25.   Beasley, J.E.J.O., "Route first—cluster second methods for vehicle routing", Omega,  Vol. 11, No. 4, (1983), 403-408.
26.   Ahuja, R.K., "Network flows: Theory, algorithms, and applications, Pearson Education,  (2017).
27.   Cervone, G., Kaufman, K.K. and Michalski, R.S., "Experimental validations of the learnable evolution model", in Evolutionary Computation, 2000. Proceedings of the 2000 Congress on, IEEE. Vol. 2, (2000), 1064-1071.
28.   Geismar, H.N., Laporte, G., Lei, L. and Sriskandarajah, C.J.I.J.o.C., "The integrated production and transportation scheduling problem for a product with a short lifespan", INFORMS Journal on Computing,  Vol. 20, No. 1, (2008), 21-33.
29.   Czyzyk, J., Mesnier, M.P., Moré, J.J.J.I.C.S. and Engineering, "The neos server", IEEE Computational Science and Engineering,  Vol. 5, No. 3, (1998), 68-75.
30.   Dolan, E. D. J.a.p.c., "Neos server 4.0 administrative guide", arXiv preprint cs/0107034,  Argonne National Laboratory (2001).
31.   Gropp, W., More, J.J.A.t. and optimization, "Optimization environments and the neos server", Approximation Theory and Optimization,  (1997), 167-182.