The quay crane scheduling problem (QCSP) is a global problem and all ports around the world seek to solve it, to get an acceptable time of unloading containers from the vessels or loading containers to the vessels and therefore reducing the docking time in the terminal. This paper proposes three solutions for the QCSP in port of Tripoli-Lebanon, two exact methods which are the mixed integer linear programming and the dynamic programming algorithm, to obtain the optimal solution and one heuristic method which is the genetic algorithm, to obtain near optimal solution within an acceptable CPU time. The main objective of these methods is to minimize the unloading or the loading time of the containers and therefore reduce the waiting time of the vessels in the terminals. We tested and validated our methods for small and large random instances. Finally, we compared the results obtained with these methods for some real instances in the port of Tripoli-Lebanon.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020135
Keywords: Optimization, quay crane, scheduling problem, MILP, dynamic programming, genetic algorithm, case study
@article{RO_2021__55_1_115_0,
author = {Skaf, Ali and Lamrous, Sid and Hammoudan, Zakaria and Manier, Marie-Ange},
title = {Solving methods for the quay crane scheduling problem at port of {Tripoli-Lebanon}},
journal = {RAIRO. Operations Research},
pages = {115--133},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {1},
doi = {10.1051/ro/2020135},
mrnumber = {4228691},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020135/}
}
TY - JOUR AU - Skaf, Ali AU - Lamrous, Sid AU - Hammoudan, Zakaria AU - Manier, Marie-Ange TI - Solving methods for the quay crane scheduling problem at port of Tripoli-Lebanon JO - RAIRO. Operations Research PY - 2021 SP - 115 EP - 133 VL - 55 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020135/ DO - 10.1051/ro/2020135 LA - en ID - RO_2021__55_1_115_0 ER -
%0 Journal Article %A Skaf, Ali %A Lamrous, Sid %A Hammoudan, Zakaria %A Manier, Marie-Ange %T Solving methods for the quay crane scheduling problem at port of Tripoli-Lebanon %J RAIRO. Operations Research %D 2021 %P 115-133 %V 55 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020135/ %R 10.1051/ro/2020135 %G en %F RO_2021__55_1_115_0
Skaf, Ali; Lamrous, Sid; Hammoudan, Zakaria; Manier, Marie-Ange. Solving methods for the quay crane scheduling problem at port of Tripoli-Lebanon. RAIRO. Operations Research, Tome 55 (2021) no. 1, pp. 115-133. doi: 10.1051/ro/2020135
[1] and , The quay crane scheduling problem. J. Manuf. Syst. 36 (2015) 87–94. | DOI
[2] , and , Combination of a dynamic-hybrid berth allocation problem with a quay crane scheduling problem. In: 2016 7th International Conference on Information, Intelligence, Systems & Applications (IISA) (2016). | DOI
[3] , and , A multi-vessel quay crane scheduling problem. In: 2016 7th International Conference on Information, Intelligence, Systems & Applications (IISA) (2016). | DOI
[4] , and , Ant colony system for solving quay crane scheduling problem in container terminal. In: 2014 International Conference on Logistics Operations Management (2014). | DOI
[5] , Dynamic Programming. Princeton University Press (1957). | MR | Zbl
[6] , and , A generalized classification scheme for crane scheduling with interference. Eur. J. Oper. Res. 258 (2017) 343–357. | MR | Zbl | DOI
[7] and , A modified genetic algorithm for quay crane scheduling operations. Expert Syst. App. 39 (2012) 4213–4221. | DOI
[8] , The quay crane scheduling problem. Transp. Res. 23 (1989) 159–175. | DOI
[9] and , An integrated quay crane assignment and scheduling problem. Comput. Ind. Eng. 73 (2014) 115–123. | DOI
[10] , Genetic algorithms in search. Addison-Wesley Professional, Reading, MA (1989). | Zbl
[11] and , Simulation-based optimization on quay crane scheduling of container terminals. In: 2017 29th Chinese Control And Decision Conference (CCDC) (2017). | DOI
[12] , Genetic algorithms, computer programs that evolve in ways that resemble natural selection can solve complex problems even their creators do not fully understand. http://www2.econ.iastate.edu/tesfatsi/holland.GAIntro.htm (1960).
[13] , Mathematical methods of organizing and planning production. Manage. Sci. 4 (1939) 366–422. | MR | Zbl
[14] and , A crane scheduling method for port container terminals. Eur. J. Oper. Res. 156 (2004) 752–768. | Zbl | DOI
[15] , and , A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Comput. Ind. Eng. 56 (2008) 1021–1028. | DOI
[16] , , and , Quay crane scheduling with spatial constraints. Nav. Res. Logistics 51 (2004) 386–406. | MR | Zbl | DOI
[17] , and , A branch-and-price framework for the general double-cycling problem with internal-reshuffles. In: 2015 IEEE 12th International Conference on Networking, Sensing and Control (2015). | DOI
[18] , , and , Approximation algorithm for uniform quay crane scheduling at container ports. Discrete Math. Algorithms App. 8 (2016) 1650018. | MR | Zbl | DOI
[19] , , and , An integrated quay crane assignment and scheduling problem using branch-and-price. In: International Conference on Computational Science and Computational Intelligence (2016).
[20] , and , Multi-objective optimization of the quay crane assignment and scheduling problem: time and movement optimization. In: 2016 7th International Conference on Information, Intelligence, Systems and Applications (IISA) (2016). | DOI
[21] and , A branch and bound solution method for the quay crane scheduling problem. Transp. Res. 24 (1990) 159–172. | DOI
[22] , and , An evolutionary approach to a combined mixed integer programming model of seaside operations as arise in container ports. Adv. Theor. Appl. Comb. Optim. (2017). | MR | Zbl
[23] , , and , Exact method for single vessel and multiple quay cranes to solve scheduling problem at port of tripoli-lebanon. In: 2018 International Conference on Industrial Engineering and Engineering Management (2018).
[24] , , and , Genetic algorithm to optimize unloading of large containers vessel in port of tripoli-lebanon. Decision and Information Technologies (2019).
[25] , , and , Single quay crane and multiple yard trucks scheduling problem with integration of reach-stacker cranes at port of tripoli-lebanon. In: 2019 IEEE International Conference on Systems, Man, and Cybernetics (2019).
[26] and , Container terminal operation and operations research – classification and literature review. OR Spectr. 26 (2004) 3–49. | Zbl | DOI
[27] , , , and , An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports. Comput. Ind. Eng. 56 (2009) 241–248. | DOI
[28] and , Multi quay crane scheduling problem based on aco in container terminals. In: 2009 International Conference on Management and Service Science (2009).
[29] and , An investigation into berth and quay crane scheduling for container terminals based on knowledge. In: International Conference on Future Information Technology and Management Engineering (2010).
[30] , and , Optimization research of joint quay crane scheduling and block selection in container terminals. In: 2017 International Conference on Service Systems and Service Management (2017).
[31] , and , Model and heuristic algorithm for quay crane scheduling at container terminal. In: 9th International Conference on Fuzzy Systems and Knowledge Discovery (2012).
[32] , , and , Scheduling quay cranes and yard trucks for unloading operations in container ports. Ann. Oper. Res. 273 (2016) 455. | MR | Zbl | DOI
Cité par Sources :
