# zbMATH — the first resource for mathematics

A hybrid genetic algorithm for the multiple crossdocks problem. (English) Zbl 1264.90113
Summary: We study a multiple crossdocks problem with supplier and customer time windows, where any violation of time windows will incur a penalty cost and the flows through the crossdock are constrained by fixed transportation schedules and crossdock capacities. We prove this problem to be $$\mathcal{NP}$$-hard in the strong sense and therefore focus on developing efficient heuristics. Based on the problem structure, we propose a hybrid genetic algorithm (HGA) integrating greedy technique and variable neighborhood search method to solve the problem. Extensive experiments under different scenarios were conducted, and results show that HGA outperforms CPLEX solver, providing solutions in realistic timescales.

##### MSC:
 90B90 Case-oriented studies in operations research 90B06 Transportation, logistics and supply chain management
CPLEX
Full Text:
##### References:
 [1] D. Simchi-Levi, P. Kaminsky, and E. Simchi-Levi, Designing and Managing the Supply Chain, McGraw-Hill-Irwin, Boston, Mass, USA, 2nd edition, 2003. · Zbl 0979.90061 [2] T. Brockmann, “21 Warehousing trends in the 21st century,” IIE Solutions, vol. 31, pp. 36-40, 1999. [3] Y. Li, A. Lim, and B. Rodrigues, “Crossdocking-JIT scheduling with time windows,” Journal of the Operational Research Society, vol. 55, no. 12, pp. 1342-1351, 2004. · Zbl 1088.90026 · doi:10.1057/palgrave.jors.2601812 [4] M. Gumus and J. H. Bookbinder, “Cross-docking and its implication in location-distribution systems,” Journal of Business Logistics, vol. 25, no. 2, pp. 199-228, 2004. · doi:10.1002/j.2158-1592.2004.tb00187.x [5] K. Krishnan and V. Rao, “Inventory control in N warehouses,” Journal of Industrial Engineering, vol. 16, pp. 212-215, 1965. [6] U. S. Kamarkar and N. R. Patel, “The one-period n-location distribution problem,” Naval Research Logistics, vol. 24, no. 4, pp. 559-575, 1977. · Zbl 0373.90078 · doi:10.1002/nav.3800240405 [7] U. S. Karmarkar, “The multilocation multiperiod inventory problem: bounds and approximations,” Management Science, vol. 33, no. 1, pp. 86-94, 1987. · Zbl 0634.90014 · doi:10.1287/mnsc.33.1.86 [8] G. Tagaras, “Effects of pooling on the optimization and service levels of two-location inventory systems,” IIE Transactions, vol. 21, no. 3, pp. 250-257, 1989. · doi:10.1080/07408178908966229 [9] L. W. Robinson, “Optimal and approximate policies in multiperiod, multilocation inventory models with transshipments,” Operations Research, vol. 38, no. 2, pp. 278-295, 1990. · Zbl 0716.90031 · doi:10.1287/opre.38.2.278 [10] N. Rudi, S. Kapur, and D. F. Pyke, “A two-location inventory model with transshipment and local decision making,” Management Science, vol. 47, no. 12, pp. 1668-1680, 2001. · Zbl 1232.90087 · doi:10.1287/mnsc.47.12.1668.10235 [11] J. Grahovac and A. Chakravarty, “Sharing and lateral transshipment of inventory in a supply chain with expensive low-demand items,” Management Science, vol. 47, no. 4, pp. 579-594, 2001. · Zbl 1232.90054 · doi:10.1287/mnsc.47.4.579.9826 [12] Y. T. Herer and M. Tzur, “The dynamic transshipment problem,” Naval Research Logistics, vol. 48, no. 5, pp. 386-408, 2001. · Zbl 1006.90006 · doi:10.1002/nav.1025 [13] Y. T. Herer, M. Tzur, and E. Yücesan, “Transshipments: an emerging inventory recourse to achieve supply chain leagility,” International Journal of Production Economics, vol. 80, no. 3, pp. 201-212, 2002. · doi:10.1016/S0925-5273(02)00254-2 [14] S. Axsäter, “A new decision rule for lateral transshipments in inventory systems,” Management Science, vol. 49, no. 9, pp. 1168-1179, 2003. · Zbl 1232.90013 · doi:10.1287/mnsc.49.9.1168.16568 [15] S. Axsäter, “Evaluation of unidirectional lateral transshipments and substitutions in inventory systems,” European Journal of Operational Research, vol. 149, no. 2, pp. 438-447, 2003. · Zbl 1033.90001 · doi:10.1016/S0377-2217(02)00447-2 [16] H. Donaldson, E. L. Johnson, H. D. Ratliff, and M. Zhang, “Schedule-driven crossdocking networks,” Research Report, Georgia Institute of Technology, 1999. [17] D. H. Ratcliff, J. van de Vate, and M. Zhang, “Network design for load-driven cross-docking systems,” Research Report, Georgia Institute of Technology, 1999. [18] Z. Miao, A. Lim, and H. Ma, “Truck dock assignment problem with operational time constraint within crossdocks,” European Journal of Operational Research, vol. 192, no. 1, pp. 105-115, 2009. · Zbl 1181.90122 · doi:10.1016/j.ejor.2007.09.031 [19] N. Boysen, M. Fliedner, and A. Scholl, “Scheduling inbound and outbound trucks at cross docking terminals,” OR Spectrum, vol. 32, no. 1, pp. 135-161, 2009. · Zbl 1181.90111 · doi:10.1007/s00291-008-0139-2 [20] A. Lim, Z. Miao, B. Rodrigues, and Z. Xu, “Transshipment through crossdocks with inventory and time windows,” Naval Research Logistics, vol. 52, no. 8, pp. 724-733, 2005. · Zbl 1278.90046 · doi:10.1002/nav.20113 [21] P. Chen, Y. Guo, A. Lim, and B. Rodrigues, “Multiple crossdocks with inventory and time windows,” Computers and Operations Research, vol. 33, no. 1, pp. 43-63, 2006. · Zbl 1089.90007 · doi:10.1016/j.cor.2004.06.002 [22] H. Ma, Z. Miao, A. Lim, and B. Rodrigues, “Crossdocking distribution networks with setup cost and time window constraint,” Omega-International Journal of Management Science, vol. 39, no. 1, pp. 64-72, 2011. · doi:10.1016/j.omega.2010.03.001 [23] L. Hai and A. Lim, “A metaheuristic for the pickup and delivery problem with time windows,” International Journal on Artificial Intelligent Tools, vol. 12, no. 2, pp. 173-186, 2003. · Zbl 05421476 · doi:10.1142/S0218213003001186 [24] M. Gendreau, F. Guertin, J. Y. Potvin, and R. Séguin, “Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries,” Transportation Research Part C, vol. 14, no. 3, pp. 157-174, 2006. · doi:10.1016/j.trc.2006.03.002
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.