A Mathematical Model and Grouping Imperialist Competitive Algorithm for Integrated Quay Crane and Yard Truck Scheduling Problem with Non-crossing Constraint

Document Type : Original Article

Authors

Industrial & Systems Engineering Dept., Tarbiat Modares University, Tehran, Iran

Abstract

In this research, an integrated approach is presented to simultaneously solve quay crane scheduling and yard truck scheduling problems. A mathematical model was proposed considering the main real-world assumptions such as quay crane non-crossing, precedence constraints and variable berthing times for vessels with the aim of minimizing vessels completion time. Based on the numerical results, this proposed mathematical model has suitable efficiency for solving small instances. Two versions of imperialist competitive algorithm (ICA) are presented to heuristically solve the problem. The grouping version of  algorithm (G-ICA) is used to solve the large-sized instances based on considering the allocation of trucks as a grouping problem. Effectiveness of the proposed metaheuristics on small-sized problems is compared with the optimal results of the mathematical model. In order to compare the efficiency of the proposed algorithms for large-sized instances, several instances were generated and solved, and the performance of algorithms has been compared with each other. Moreover, a simulated annealing (SA) algorithm is developed to solve the problem and evaluate the performance of the proposed ICA algorithms. Based on the experimental results, the G-ICA has a better performance compared to the ICA and SA. Also an instance of a container terminal in Iran has been investigated which shows that the proposed model and solution methods are applicable in real-world problems.

Keywords

References

1. UNCTAD, Review of the maritime transport 2013, United
Nations Conference on Trade and Development, Geneva:
Switzerland, 2013. 
2. Ng, W.C. and Mak, K. L., “Quay crane scheduling in container
terminals”, Engineering Optimization, Vol. 38, No. 6, (2006),
723–737.  
3. Zegordi, S.H. and Nahavandi, N., “Measuring productivity
indexes and efficiency in the container terminal at port Rajaei”,
Scientia Iranica, Vol. 9, No. 3, (2002), 248–254.  
4. Tongzon, J. and Heng, W., “Port privatization, efficiency and
competitiveness: Some empirical evidence from container ports
(terminals)”, Transportation Research Part A: Policy and
Practice, Vol. 39, No. 5, (2005), 405–424.  
5. Tang, L., Zhao, J. and Liu, J., “Modeling and solution of the joint
quay crane and truck scheduling problem”, European Journal of 
Operational Research, Vol. 236, No. 3, (2014), 978–990. 
6. Daganzo, C. F., “The crane scheduling problem”, Transportation 
Research Part B: Methodological, Vol. 23, No. 3, (1989), 159–175.  
7. Kim, K.H. and Park, Y. M., “A crane scheduling method for port
container terminals”, European Journal of Operational
Research, Vol. 156, No. 3, (2004), 752–768.  
8. Moccia, L., Cordeau, J.F., Gaudioso, M. and Laporte, G., “A
branch‐and‐cut algorithm for the quay crane scheduling problem
in a container terminal”, Naval Research Logistics (NRL), Vol.
53, No. 1, (2006), 45–59.  
9. Bierwirth, C. and Meisel, F., “A fast heuristic for quay crane
scheduling with interference constraints”, Journal of Scheduling,
Vol. 12, No. 4, (2009), 345–360.  
10. Tavakkoli-Moghaddam, R., Makui, A., Salahi, S., Bazzazi, M.
and Taheri, F., “An efficient algorithm for solving a new 
mathematical model for a quay crane scheduling problem in
container ports”, Computers & Industrial Engineering, Vol. 56,
No. 1, (2009), 241–248.  
11. Nguyen, S., Zhang, M., Johnston, M. and Tan, K. C., “Hybrid
evolutionary computation methods for quay crane scheduling
problems”, Computers & Operations Research, Vol. 40, No. 8,
(2013), 2083–2093.  
12. Kaveshgar, N., Huynh, N. and Rahimian, S. K., “An efficient
genetic algorithm for solving the quay crane scheduling problem”,
Expert Systems with Applications, Vol. 39, No. 18, (2012),
13108–13117.  
13. Liu, J., Wan, Y.W. and Wang, L., “Quay crane scheduling at
container terminals to minimize the maximum relative tardiness
of vessel departures”, Naval Research Logistics (NRL), Vol. 53,
No. 1, (2006), 60–74.  
14. Emde, S., “Optimally scheduling interfering and non‐interfering
cranes”, Naval Research Logistics (NRL), Vol. 64, No. 6, (2017),
476–489.  
15. Sammarra, M., Cordeau, J.F., Laporte, G. and Monaco, M. F., “A
tabu search heuristic for the quay crane scheduling problem”,
Journal of Scheduling, Vol. 10, No. 4–5, (2007), 327–336.  
16. Liang, C., Fan, L., Xu, D., Ding, Y. and Gen, M., “Research on
coupling scheduling of quay crane dispatch and configuration in
the container terminal”, Computers & Industrial Engineering,
Vol. 125, (2018), 649–657.  
17. Sun, D., Tang, L. and Baldacci, R., “A Benders decompositionbased
framework for solving quay crane scheduling problems”,
European Journal of Operational Research, Vol. 273, No. 2,
(2019), 504–515.  
18. Kasm, O.A. and Diabat, A., “The quay crane scheduling problem
with non-crossing and safety clearance constraints: An exact
solution approach”, Computers & Operations Research, Vol.
107, (2019), 189–199.  
19. Bierwirth, C. and Meisel, F., “A survey of berth allocation and
quay crane scheduling problems in container terminals”,
European Journal of Operational Research, Vol. 202, No. 3,
(2010), 615–627.  
20. Bierwirth, C. and Meisel, F., “A follow-up survey of berth
allocation and quay crane scheduling problems in container
terminals”, European Journal of Operational Research, Vol.
244, No. 3, (2015), 675–689.  
21. Bish, E. K., “A multiple-crane-constrained scheduling problem in
a container terminal”, European Journal of Operational
Research, Vol. 144, No. 1, (2003), 83–107.  
22. Nishimura, E., Imai, A. and Papadimitriou, S., “Yard trailer
routing at a maritime container terminal”, Transportation
Research Part E: Logistics and Transportation Review, Vol. 41,
No. 1, (2005), 53–76.  
23. Ng, W.C., Mak, K.L. and Zhang, Y. X., “Scheduling trucks in
container terminals using a genetic algorithm”, Engineering
Optimization, Vol. 39, No. 1, (2007), 33–47.  
24. Hu, Z.H., Sheu, J.B. and Luo, J. X., “Sequencing twin automated
stacking cranes in a block at automated container terminal”,
Transportation Research Part C: Emerging Technologies, Vol.
69, (2016), 208–227.  
25. Sidoti, D., Avvari, G.V., Mishra, M., Zhang, L., Nadella, B.K.,
Peak, J.E., Hansen, J.A. and Pattipati, K. R., “A multiobjective
path-planning algorithm with time windows for asset routing in a
dynamic weather-impacted environment”, IEEE Transactions
on Systems, Man, and Cybernetics: Systems, Vol. 47, No. 12,
(2016), 3256–3271.  

 
26. Yang, Y., Zhong, M., Dessouky, Y. and Postolache, O., “An
integrated scheduling method for AGV routing in automated
container terminals”, Computers & Industrial Engineering, Vol.
126, (2018), 482–493.  
27. Chen, L., Bostel, N., Dejax, P., Cai, J. and Xi, L., “A tabu search
algorithm for the integrated scheduling problem of container
handling systems in a maritime terminal”, European Journal of
Operational Research, Vol. 181, No. 1, (2007), 40–58.  
28. Cao, J., Shi, Q. and Lee, D. H., “Integrated quay crane and yard
truck schedule problem in container terminals”, Tsinghua science
and technology, Vol. 15, No. 4, (2010), 467–474.  
29. Chen, L., Langevin, A. and Lu, Z., “, 2013. Integrated scheduling
of crane handling and truck transportation in a maritime container
terminal”, Research, European Journal of Operational, Vol.
225, No. 1, (2013), 142–152.  
30. Kaveshgar, N. and Huynh, N., “Integrated quay crane and yard
truck scheduling for unloading inbound containers”,
International Journal of Production Economics, Vol. 159,
(2015), 168–177.  
31. He, J., Huang, Y., Yan, W. and Wang, S., “Integrated internal
truck, yard crane and quay crane scheduling in a container
terminal considering energy consumption”, Expert Systems with
Applications, Vol. 42, No. 5, (2015), 2464–2487.  
32. Karam, A., ElTawil, A.B. and Harraz, N. A., “Simultaneous
assignment of quay cranes and internal trucks in container
terminals”, International Journal of Industrial and Systems
Engineering, Vol. 24, No. 1, (2016), 107–125.  
33. Vahdani, B., Mansour, F., Soltani, M. and Veysmoradi, D., “Biobjective
optimization for integrating quay crane and internal
truck assignment with challenges of trucks sharing”, KnowledgeBased
Systems, Vol. 163, (2019), 675–692.
34. Pinedo, M., Scheduling, Vol. 29, New York: Springer, 2012.
35. Yegane, B.Y., Kamalabadia, I.N. and Khanlarzadeb, N., “Critical 
Path Method for Lot Streaming Problem in Flexible Job Shop
Environment”, International Journal of Engineering -
Transactions B: Applications, Vol. 30, No. 2, (2017), 261–269.  
36. Atashpaz-Gargari, E. and Lucas, C., “Imperialist competitive
algorithm: an algorithm for optimization inspired by imperialistic
competition”, In 2007 IEEE congress on evolutionary
computation, IEEE, (2007), 4661–4667.  
37. Hosseinirad, S. M., “A Hierarchy Topology Design Using a
Hybrid Evolutionary Algorithm in Wireless Sensor Networks”,
International Journal of Engineering - Transactions A: Basics,
Vol. 31, No. 10, (2018), 1651–1658.  
38. Azizmohammadi, R., Amiri, M., Tavakkoli-Moghaddam, R. and
Mohammadi, M., “Solving a redundancy allocation problem by a
hybrid multi-objective imperialist competitive algorithm. , 26(9),
pp..”, International Journal of Engineering - Transactions C:
Aspects, Vol. 26, No. 9, (2013), 1031–1042.  
39. Kashan, A.H., Kashan, M.H. and Karimiyan, S., “A particle
swarm optimizer for grouping problems”, Information Sciences,
Vol. 252, (2013), 81–95.  
40. Behjat, S. and Salmasi, N., “Total completion time minimisation
of no-wait flowshop group scheduling problem with sequence
dependent setup times”, European Journal of Industrial
Engineering, Vol. 11, No. 1, (2017), 22–48.  
41. Montgomery, D.C., Design and analysis of experiments, John
wiley & sons, 2017. 
 
 
International Journal of Engineering
Volume 32, Issue 10
TRANSACTIONS A: Basics
October 2019
Pages 1464-1479

Files

Cited by

Share

How to cite

Statistics