To operate a cross-dock successfully, an efficient assignment of trucks to docks is one of the key decisions. In this paper, we are interested in the cross-dock assignment of trucks to docks problem, where the number of trucks exceeds the number of docks. The objective is to minimize the cost of transferring goods within the cross-dock while avoiding delivery penalties. This problem being NP-hard, we use Variable Neighborhood Search metaheurisitc (VNS) to solve it approximately. More specifically, we conduct a structured empirical study to compare several VNS configurations and to find which is/are the most effective for this cross-dock problem. In this work, first we analyze the way the search strategy and the neighborhood operators can be combined in a VNS framework according to their efficiency within a local search. Then the best configurations are tested within three VNS variants, namely Basic VNS (BVNS), General VNS (GVNS) using Basic VND (B-VND) and GVNS using Union VND (U-VND) according to the number of used operators and the order of applying these operators. Finally we evaluate the influence of the stopping criterion within these variants. Some significant differences among these configurations are shown and illustrated by conducting the Friedman test.
Keywords: Cross-dock, metaheuristics, local search, variable neighborhood search, variable neighborhood descent
@article{RO_2021__55_S1_S2291_0,
author = {Daquin, C\'ecilia and Allaoui, Hamid and Goncalves, Gilles and Hsu, Tient\'e},
title = {Variable neighborhood search based algorithms for crossdock truck assignment},
journal = {RAIRO. Operations Research},
pages = {S2291--S2323},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020087},
mrnumber = {4223146},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020087/}
}
TY - JOUR AU - Daquin, Cécilia AU - Allaoui, Hamid AU - Goncalves, Gilles AU - Hsu, Tienté TI - Variable neighborhood search based algorithms for crossdock truck assignment JO - RAIRO. Operations Research PY - 2021 SP - S2291 EP - S2323 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020087/ DO - 10.1051/ro/2020087 LA - en ID - RO_2021__55_S1_S2291_0 ER -
%0 Journal Article %A Daquin, Cécilia %A Allaoui, Hamid %A Goncalves, Gilles %A Hsu, Tienté %T Variable neighborhood search based algorithms for crossdock truck assignment %J RAIRO. Operations Research %D 2021 %P S2291-S2323 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020087/ %R 10.1051/ro/2020087 %G en %F RO_2021__55_S1_S2291_0
Daquin, Cécilia; Allaoui, Hamid; Goncalves, Gilles; Hsu, Tienté. Variable neighborhood search based algorithms for crossdock truck assignment. RAIRO. Operations Research, Tome 55 (2021), pp. S2291-S2323. doi: 10.1051/ro/2020087
[1] , , and , Heuristic solutions for transshipment problems in a multiple door cross docking warehouse. Comput. Ind. Eng. 61 (2011) 402–408. | DOI
[2] , and , A bounded dynamic programming approach to schedule operations in a cross docking platform. Comput. Ind. Eng. 60 (2011) 385–396. | DOI
[3] and , Effective cross docking for improving distribution efficiencies. Int. J. Logistics 3 (2000) 291–302. | DOI
[4] , and , Aircraft stand assignment to minimize walking. J. Trans. Eng. 110 (1984) 55–66. | DOI
[5] , and , Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage. Expert Syst. App. 38 (2011) 1964–1979. | DOI
[6] and , Cross dock scheduling: Classification, literature review and research agenda. Omega 38 (2010) 413–422. | DOI
[7] , and , Synchronization in cross-docking networks: a research classification and framework. Eur. J. Oper. Res. 239 (2014) 593–608. | DOI
[8] and , Minimizing the makespan in a two-machine cross-docking flow shop problem. Eur. J. Oper. Res. 193 (2009) 59–72. ISSN 0377-2217. | MR | Zbl | DOI
[9] and , Trailer to door assignment in a synchronous cross-dock operation. Int. J. Logistics Syst. Manag. 5 (2009) 574–590. | DOI
[10] , The Friedman test. In: Practical Nonparametric Statistics. John Wiley & Sons, New York, NY (1999) 369–373.
[11] , , and , New heuristics for over-constrained flight to gate assignments. J. Oper. Res. Soc. 55 (2004) 760–768. | Zbl | DOI
[12] , , and , The over-constrained airport gate assignment problem. Comput. Oper. Res. 32 (2005) 1867–1880. | Zbl | DOI
[13] and , The heterogeneous vehicle routing and truck scheduling problem in a multi-door cross-dock system. Comput. Chem. Eng. 76 (2015) 42–62. | DOI
[14] , and , A hybrid Lagrangian metaheuristic for the cross-docking flow shop scheduling problem. Eur. J. Oper. Res. 275 (2019) 139–154. | MR | DOI
[15] , , and , A branch-and-cut algorithm for the truck dock assignment problem with operational time constraints. Eur. J. Oper. Res. 249 (2016) 1144–1152. | MR | DOI
[16] , , and , Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5 (2017) 423–454. | MR | DOI
[17] and , Cross-docking operations: current research versus industry practice. Omega 62 (2016) 145–162. | DOI
[18] , and , Airport Gate Scheduling with Time Windows. Artif. Intell. Rev. 24 (2005) 5–31. | Zbl | DOI
[19] , , and , Truck dock assignment problem with operational time constraint within crossdocks, edited by and . In: Advances in Applied Artificial Intelligence, Vol. 4031 of Lecture Notes in Computer Science. Springer, Berlin-Heidelberg (2006) 262–271.
[20] , and , Truck dock assignment problem with time windows and capacity constraint in transshipment network through crossdocks. In: Computational Science and Its Applications – ICCSA 2006, Vol. 3982 of Lecture Notes in Computer Science. Springer, Berlin-Heidelberg (2006) 688–697. | Zbl
[21] , and , Truck dock assignment problem with operational time constraint within crossdocks. Eur. J. Oper. Res. 192 (2009) 105–115. | Zbl | DOI
[22] , and , Applying an adaptive tabu search algorithm to optimize truck-dock assignment in the crossdock management system. Expert Syst. App. 41 (2014) 16–22. | DOI
[23] , , and , A two-stage genetic algorithm for the truck-door assignment problem with limited capacity vehicles and storage area. J. Syst. Sci. Syst. Eng. 28 (2019) 285–298. | DOI
[24] , , , and , Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. Int. Trans. Oper. Res. 24 (2017) 615–633. | MR | DOI
[25] and , Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. | MR | Zbl | DOI
[26] , Scheduling trucks in cross docking systems with temporary storage and repetitive pattern for shipping trucks. Appl. Soft Comput. 36 (2015) 468–486. | DOI
[27] , , and , A novel multi-objective meta-heuristic model for solving cross-docking scheduling problems. Appl. Soft Comput. 31 (2015) 30–47. | DOI
[28] , and , A mixed-integer programming formulation and Lagrangean relaxation for the cross-dock door assignment problem. Int. J. Prod. Res. 54 (2016) 494–508. | DOI
[29] , and , A comparison of formulations and relaxations for cross-dock door assignment problems. Comput. Oper. Res. 94 (2018) 76–88. | MR | DOI
[30] , The quadratic assignment problem: evaluation of exact and heuristic algorithms. (1979).
[31] , Staging approaches to reduce overall cost in a crossdock environment. Ph.D. thesis, University of Missouri–Columbia, CO (2005).
[32] and , Determination of staging needs in a crossdock environment. In: Proceedings of 2004 Industrial Engineering Research Conference (2004).
[33] and , An optimal solution to a dock door assignment problem. Comput. Ind. Eng. 23 (1992) 283–286. | DOI
[34] and , Scheduling trucks in cross-docking systems: robust meta-heuristics. Comput. Ind. Eng. 58 (2010) 12–24. | DOI
[35] , and , Cross-docking: State of the art. Omega 40 (2012) 827–846. | DOI
[36] and , Positioning of goods in a cross-docking environment. Comput. Ind. Eng. 54 (2008) 677–689. | DOI
[37] and , Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. Eur. J. Oper. Res. 184 (2008) 377–396. | Zbl | DOI
Cité par Sources :
