A Two-Stage Genetic Algorithm for the Truck-Door Assignment Problem with Limited Capacity Vehicles and Storage Area

Abstract

In this paper, we investigate a kind of truck-door assignment problem in a crossdock. Multiple related realistic constraints such as the capacity of trucks, the capacity of temporary storage area, the time windows of trucks as well as the operational time inside the crossdock are considered and therefore, make the assignment problem strongly NP-hard and very challenging. A two-stage genetic algorithm is proposed to solve this problem and the experimental results show the superiority of this approach in comparison to CPLEX solver in terms of effectiveness and efficiency, especially for the large-scale instances. That is, the decision making process can speed up and a near optimal truck-door assignment scheme can be obtained within a relatively short time by applying this two-stage approach in practice.

Keywords

Truck-door assignment / genetic algorithm / two-stage approach / crossdock

References

[1] Agustina D, Lee CKM, Piplani R. Vehicle scheduling and routing at a cross docking center for food supply chains. International Journal of Production Economics, 2014, 152: 29-41.

[2] Bartholdi JJ, Gue K. Reducing labor costs in an LTL cross-docking terminal. Operations Research, 2000, 48: 823-832.

[3] Bartholdi JJ, Gue KR. The best shape for a crossdock. Transportation Science, 2004, 38(2): 235-244.

[4] Boysen N, Malte F. Cross dock scheduling: Classification, literature review and research agenda. Omega, 2010, 38: 413-422.

[5] Dondo R, Cerdá J. A sweep-heuristic based formulation for the vehicle routing problem with cross-docking. Computers and Chemical Engineering, 2013, 48: 293-311.

[6] Fonseca GB, Nogueira TH, Ravetti MG. A hybrid La-grangian metaheuristic for the cross-docking flow shop scheduling problem. European Journal of Operational Research, 2019, 275(1): 139-154.

[7] Jan VB, Paul V, Dirk C. Cross-docking: State of the art. Omega, 2012, 40: 827-846.

[8] Kreng VB, Chen FT. The benefits of a cross-docking delivery strategy: A supply chain collaboration approach. Prodution Planning and Control, 2008, 19(3): 229-241.

[9] Ladier AL, Alpan G. Robust cross-dock scheduling with time windows. Computers & Industrial Engineering, 2016, 99: 16-28.

[10] Leung SCH, Wu Y. A two-stage stochastic programming with recourse model for cross-border distribution with fleet management. Prodution Planning and Control, 2005, 16(1): 60-70.

[11] Li Y, Lim A, Rodrigues B. Crossdocking: JIT scheduling with time windows. Journal of the Operational Research Society, 2004, 55(12): 1342-1351.

[12] Liao CJ, Lin Y, Shih SC. Vehicle routing with cross-docking in the supply chain. Expert Systems with Applications, 2010, 37: 6868-6874.

[13] Liao TW, Egbelu PJ, Chang PC. Two hybrid differential evolution algorithms for optimal inbound and outbound truck sequencing in cross docking operations. Applied Soft Computing, 2012, 12: 3683-3697.

[14] Liao TW, Egbelu PJ, Chang PC. Simultaneous dock assignment and sequencing of inbound trucks under a fixed outbound truck schedule in multi-door cross docking operations. International Journal of Production Economics, 2013, 141: 212-229.

[15] Lim A, Miao Z, Rodrigues B, Xu Z. Transshipment through crossdocks with inventory and time windows. Naval Research Logistics, 2005, 52(8): 724-733.

[16] Ma H, Miao Z, Lim A, Rodrigues B. Crossdocking distribution networks with setup cost and time window constraint. Omega, 2011, 39: 64-72.

[17] Miao Z, Cai S, Xu D. Applying an adaptive tabu search algorithm to optimize truck-dock assignment in the crossdock management system. Expert Systems with Applications, 2014, 41: 16-22.

[18] Miao Z, Lim A, Ma H. Truck dock assignment problem with operational time constraint within crossdocks. European Journal of Operational Research, 2009, 192(1): 105-115.

[19] Miao Z, Yang F, Fu K, Xu D. Transshipment service through crossdocks with both soft and hard time windows constraints. Annals of Operations Research, 2012, 192: 21-47.

[20] Mousavi SM, Tavakkoli-Moghaddam R. A hybrid simulated annealing algorithm for location and routing scheduling problems with cross-docking in the supply chain. Journal of Manufacturing Systems, 2013, 32: 335-347.

[21] Musa R, Arnaout JP, Jung H. Ant colony optimization algorithm to solve for the transportation problem of cross-docking network. Computers and Industrial Engineering, 2010, 59: 85-92.

[22] Nasiri MM, Rahbari A, Werner F, Karimi R. Incorporating supplier selection and order allocation into the vehicle routing and multi-cross-dock scheduling problem. International Journal of Production Research, 2018, 56: 6527-6552.

[23] Nassief W, Contreras I, Jaumard B. A comparison of formulations and relaxations for cross-dock door assignment problems. Computers & Operations Research, 2018, 94: 76-88.

[24] Nikolopoulou AI, Repoussis PP, Tarantilis CD, Zachariadis EE. Moving products between location pairs: Cross-docking versus direct-shipping. European Journal of Operational Research, 2017, 256: 803-819.

[25] Rahbari A, Nasiri MM, Werner F, Musavi MM, Jolai F. The vehicle routing and scheduling problem with cross-docking for perishable products under uncertainty: Two robust bi-objective models. Applied Mathematical Modelling, 2019, 70: 605-625.

[26] Schaffer B. Cross docking can increase efficiency. Automatic I.D. News, 1998, 14(8): 34-37.

[27] Serrano C, Delorme X, Dolgui A. Scheduling of truck arrivals, truck departures and shop-floor operation in a cross-dock platform, based on trucks loading plans. International Journal of Production Economics, 2017, 194: 102-112.

[28] Shakeri M, Low MYH, Turner SJ, Lee EW. An efficient incremental evaluation function for optimizing truck scheduling in a resource-constrained crossdock using metaheuristics. Expert Systems with Applications, 2016, 45: 172-184.

[29] Shi W, Liu Z, Shang J, Cui Y. Multi-criteria robust design of a JIT-based cross-docking distribution center for an auto parts supply chain. European Journal of Operational Research, 2013, 229: 695-706.

[30] Vis IFA, Roodbergen KJ. Positioning of goods in a cross-docking environment. Computers & Industrial Engineering, 2008, 54(3): 677-689.

[31] Zuluaga JPS, Thiell M, Perales RC. Reverse crossdocking. Omega, 2017, 66: 48-57.