×

zbMATH — the first resource for mathematics

Transshipment service through crossdocks with both soft and hard time windows. (English) Zbl 1233.90286
Summary: Recently, crossdocking techniques have been successfully applied in responsive supply chain management. However, most researches focused on physical layout of a crossdock, or scheduling operations within a crossdock. In this paper, we study a multi-crossdock transshipment service problem with both soft and hard time windows. The flows from suppliers to customers via the crossdocks are constrained by fixed transportation schedules. Cargos can be delayed and consolidated in crossdocks, and both suppliers and customers have specific hard time windows. In addition to hard time windows, customers also have less-restrictive time windows, called soft time windows. The problem to minimize the total cost of the multi-crossdock distribution network, including transportation cost, inventory handling cost and penalty cost, can be proved to be NP-hard in the strong sense and hence efficient heuristics are desired. We propose two types of meta-heuristic algorithms, called adaptive tabu search and adaptive genetic algorithm, respectively, to solve the problem efficiently. We conduct extensive experiments and the results show that both of them outperform CPLEX solver and provide fairly good solutions within realistic timescales. We also perform sensitivity analysis and obtain a number of managerial insights.

MSC:
90C90 Applications of mathematical programming
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
CPLEX; Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balamurugan, R., Ramakrishnan, C. V., & Nidur, S. (2008). Performance evaluation of a two stage adaptive genetic algorithm (TSAGA) in structural topology optimization. Applied Soft Computing. doi: 10.1016/j.asoc.2007.10.022 .
[2] Bressloff, P. C. (1995). Stochastic dynamics of reinforcement learning. Network: Computation in Neural Systems, 6(2), 289–307. · Zbl 0839.68081 · doi:10.1088/0954-898X/6/2/009
[3] Chen, P., Guo, Y. S., Lim, A., & Rodriguesd, B. (2006). Multiple crossdocks with inventory and time windows. Computers & Operations Research, 33(1), 43–63. · Zbl 1089.90007 · doi:10.1016/j.cor.2004.06.002
[4] Consoli, S., Darby-Dowman, K., Mladenović, N., & Moreno Pérez, J.A. (2009). Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem. European Journal of Operational Research, 196(2), 440–449. · Zbl 1163.90766 · doi:10.1016/j.ejor.2008.03.014
[5] Donaldson, H., Johnson, E. L., Ratliff, H. D., & Zhang, M. (1999). Schedule-driven crossdocking networks. Research Report, Georgia Institute of Technology.
[6] Fagerholt, K. (2001). Ship scheduling with soft time windows: an optimisation based approach. European Journal of Operational Research, 131(3), 559–571. · Zbl 0994.90069 · doi:10.1016/S0377-2217(00)00098-9
[7] Glover, F., & Laguna, M. (1997). Tabu search. Dordrecht: Kluwer Academic. · Zbl 0930.90083
[8] Gue, K. R. (1999). The effects of trailer scheduling on the layout of freight terminals. Transportation Science, 33(4), 419–428. · Zbl 0961.90503 · doi:10.1287/trsc.33.4.419
[9] Gendreau, M., Guertin, F., Potvin, J. Y., & Séguin, R. (2006). Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transportation Research Part C: Emerging Technologies, 3(14), 157–174. · doi:10.1016/j.trc.2006.03.002
[10] Hansen, P., Mladenović, N., & Moreno Pérez, J.A. (2010). Variable neighbourhood search: methods and applications. Annals of Operations Research, 175(1), 367–407. · Zbl 1185.90211 · doi:10.1007/s10479-009-0657-6
[11] Hashimoto, H., Ibaraki, T., Imahori, S., & Yagiura, M. (2006). The vehicle routing problem with flexible time windows and traveling times. Discrete Applied Mathematics, 154(16), 2271–2290. · Zbl 1130.90053 · doi:10.1016/j.dam.2006.04.009
[12] Hansen, P., & Mladenovi, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 3(130), 449–467. · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[13] Ioannou, G., Kritikos, M., & Prastacos, G. (2003). A problem generator-solver heuristic for vehicle routing with soft time windows. The International Journal of Management Science, Omega, 1(31), 41–53. · doi:10.1016/S0305-0483(02)00064-6
[14] Keskin, B. B., & Üster, H. (2007). A scatter search-based heuristic to locate capacitated transshipment points. Computers & Operations Research, 34(10), 3112–3125. · Zbl 1185.90134 · doi:10.1016/j.cor.2005.11.020
[15] Kaelo, P., & Ali, M. M. (2007). Integrated crossover rules in real coded genetic algorithms. European Journal of Operational Research, 176(1), 60–76. · Zbl 1137.90735 · doi:10.1016/j.ejor.2005.07.025
[16] Kim, H. J., & Hooker, J. N. (2002). Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach. Annals of Operations Research, 115(1–4), 95–124. · Zbl 1013.90010 · doi:10.1023/A:1021145103592
[17] Lee, Y. H., Jung, J. W., & Lee, K. M. (2006). Vehicle routing scheduling for cross-docking in the supply chain. Computers & Industrial Engineering, 51(2), 247–256. · doi:10.1016/j.cie.2006.02.006
[18] Li, H., & Lim, A. (2003). A Metaheuristic for the pickup and delivery problem with time windows. International Journal on Artificial Intelligent Tools, 2(12), 173–186. · Zbl 05421476 · doi:10.1142/S0218213003001186
[19] Li, Y., Lim, A., & Rodrigues, B. (2004). Crossdocking: JIT scheduling with time windows. Journal of the Operational Research Society, 55(12), 1342–1351. · Zbl 1088.90026 · doi:10.1057/palgrave.jors.2601812
[20] Lim, A., Miao, Z., Rodrigues, B., & Xu, Z. (2005). Transshipment through crossdocks with inventory and time windows. Naval Research Logistics, 52(8), 724–733. · Zbl 1278.90046 · doi:10.1002/nav.20113
[21] Miao, Z., Lim, A., & Ma, H. (2009a). Truck dock assignment problem with operational time constraint within crossdocks. European Journal of Operational Research, 192(1), 105–115. · Zbl 1181.90122 · doi:10.1016/j.ejor.2007.09.031
[22] Miao, Z., Yang, F., & Fu, K. (2009b). A hybrid two-stage genetic algorithm for the transshipment problem in crossdocking networks. Working paper. School of Management, Xiamen University, P.R. China.
[23] Michel, L., Shvartsman, A., & Sonderegger, E. (2010). Optimal deployment of eventually-serializable data services. Annals of Operations Research, doi: 10.1007/s10479-010-0684-3 . · Zbl 1225.90089
[24] Mladenović, N., & Hansen, P. (1997). Variable neighborhoodsearch. Computers & Operations Research, 11(24), 1097–1100. · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[25] Najim, K., Pibouleau, L., & Le Lann, M. V. (1990). Optimization technique based on learning automata. Journal of Optimization Theory and Applications, 64(2), 331–347. · Zbl 0687.90092 · doi:10.1007/BF00939452
[26] Ratcliff, D. H., van de Vate, J., & Zhang, M. (1999). Network design for load-driven cross-docking systems, Research Report, Georgia Institute of Technology.
[27] Ross, A., & Jayaraman, V. (2008). An evaluation of new heuristics for the location of cross-docks distribution centers in supply chain network design. Computers & Industrial Engineering, 55(1), 64–79. · doi:10.1016/j.cie.2007.12.001
[28] Schaffer, B. (1998). Cross docking can increase efficiency. Automatic I.D. News, 14(8), 34–37.
[29] Shaffer, B. (2000). Implementing a successful crossdocking operation. Plant Engineering, 54(3), 128–134.
[30] Sung, S., & Song, H. (2003). Integrated service network design for a cross-docking supply chain network. Journal of the Operational Research Society, 54(12), 1283–1295. · Zbl 1203.90034 · doi:10.1057/palgrave.jors.2601645
[31] Tsui, L., & Chang, C. (1990). A microcomputer based decision support tool for assigning dock doors in freight yards. Computers & Industrial Engineering, 19(1–4), 309–312. · doi:10.1016/0360-8352(90)90128-9
[32] Tsui, L., & Chang, C. (1992). An optimal solution to a dock door assignment problem. Computers & Industrial Engineering, 23(1–4), 283–286. · doi:10.1016/0360-8352(92)90117-3
[33] Vis, I. F. A., & Roodbergen, K. J. (2008). Positioning of goods in a cross-docking environment. Computers & Industrial Engineering, 54(3), 677–689. · doi:10.1016/j.cie.2007.10.004
[34] Vansteenwegen, P., Souffriau, W., & Sörensen, K. (2009). Solving the mobile mapping van problem: a hybrid metaheuristic for capacitated arc routing with soft time windows. Computer & Operations Research (In Press). Available online, 18 May. · Zbl 1188.90042
[35] Yu, W., & Egbelu, P. J. (2008). Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. European Journal of Operational Research, 184(1), 377–396. · Zbl 1278.90177 · doi:10.1016/j.ejor.2006.10.047
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.