مسئله‌ی یکپارچه‌ی زمان‌بندی تجهیزات جابجایی و تخصیص مکان ذخیره‌سازی برای کانتینرهای ورودی در پایانه‌های کانتینری

نوع مقاله : پژوهشی

نویسندگان

گروه مهندسی صنایع، دانشکده‌ی مهندسی صنایع، دانشگاه صنعتی ‌اصفهان، ایران.

چکیده

در پژوهش حاضر، مسئله‌ی زمان‌بندی جرثقیل اسکله به‌عنوان مهم‌ترین مسئله‌ی کنار اسکله با مسائل زمان‌بندی کامیون‌ها، جرثقیل محوطه، و تخصیص مکان ذخیره‌سازی به‌عنوان مسائل مطرح در محوطه به‌صورت یکپارچه بررسی شده است. یک مدل برنامه‌ریزی خطی عدد صحیح جدید با هدف کمینه‌سازی هزینه‌ی زمانی تکمیل کانتینرها و هزینه‌ی عملیاتی، شامل: هزینه‌ی تخلیه‌ی کانتینرها از کشتی، حمل آن‌ها به محوطه، و بارگذاری آن‌ها در محوطه ارائه شده است. مسئله‌‌ی اخیر از نظر پیچیدگی محاسباتی در دسته‌ی مسائل  NP-hard قرار می‌گیرد. برای افزایش سرعت حل مدل، قیدهایی با عنوان نامعادله‌های معتبر معرفی و  به مدل اضافه شده‌اند. به‌منظور اعتبارسنجی مدل پیشنهادی، ۲‍۱ نمونه مسئله‌ی طراحی‌شده در نرم‌افزاز گمز پیاده‌سازی و با حل‌کننده‌ی CPLEX اجرا شده‌اند. نتایج محاسباتی نشان داده‌اند که قیدهای مذکور موجب کاهش زمان حل شده‌اند. همچنین، در مسائل بزرگ‌تر، نامعادله‌های اخیر، میانگین درصد انحراف را از ۰۸/۳ به ۷۸/۱ درصد نسبت به حد پایین کاهش داده‌اند.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

An Integrated Problem of Handling Equipment Scheduling and Storage Space Allocation for Inbound Containers at Container Terminal

نویسندگان [English]

  • Zahrasadat Fani Sadrabadi
  • Mehdi Alinaghian
Department of Industrial and Systems Engineering Isfahan University of Technology, Iran.
چکیده [English]

The increasing growth of container transportation has led container terminals, as the primary hubs of cargo transfer in the global supply chain, to continuously improve their efficiency and operations to be successful in this competitive industry. Various problems have arisen in the maritime logistics field owing to the division of container terminals into two sections, quayside and yardside. This study examines the integration of problems on the quayside and the yardside. Specifically, it simultaneously investigates the quay crane scheduling problem as a quayside problem, along with the yard truck scheduling problem, yard crane scheduling problem, and storage space allocation problem as part of the yardside problems. A  new integer linear programming model has been presented for the integrated problem of equipment handling scheduling and storage location allocation. This problem aims to minimize the time required to complete containers and operational costs. These operational costs include unloading containers from vessels using a quay crane, moving them to the yard via yard trucks, and loading them using a yard crane. The integrated problem is classified under the category of NP-hard problems in terms of computational complexity. Furthermore, they were introduced and added to the model according to the problem structure to expedite the resolution of constraints under valid inequalities. To validate the model's accuracy, instances were designed, implemented in GAMS software, and executed using the CPLEX solver. The computational results demonstrate that the incorporation of valid inequalities across all instances reduces computational time. Furthermore, in instances involving larger problems, where the mathematical model was unable to determine the optimal solution within a reasonable time, the addition of valid inequalities yielded solutions with an average gap of 1.78% from the lower bound. By contrast, the proposed model without the inclusion of valid inequalities achieved solutions with a gap of 3.08% from the lower bound.

کلیدواژه‌ها [English]

  • Quay crane scheduling problem
  • yard truck scheduling problem
  • yard crane scheduling problem
  • valid inequalities

مراجع

1- Li, S., Jia, S., Tao, Y. and Lin, X., 2024. Gate appointment design in a container terminal: A robust optimization approach. Transportation Research Part E: Logistics And Transportation Review, 184, pp.103495.doi: https://doi.org/10.1016/j.tre.2024.103495
2- Statista, 2022. Size of container ship fleet 2022, by nationality of operator. Statista. Available at: https://www.statista.com/statistics/263858/container (Accessed: 11 February 2026).
3- Azevedo, A.T., de Salles Neto, L.L., Chaves, A.A. and Moretti, A.C., 2018. Solving the 3D stowage planning problem integrated with the quay crane scheduling problem by representation by rules and genetic algorithm. Applied Soft Computing, 65, pp.495–516. https://doi.org/10.1016/j.asoc.2018.01.006
4- Bierwirth, C. and Meisel, F., 2015. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. European Journal Of Operational Research, 244(3), pp.675–689. https://doi.org/10.1016/j.ejor.2014.12.030
5- Daganzo, C.F., 1989. The crane scheduling problem. Transportation Research Part B: Methodological, 23(3), pp.159–175. https://doi.org/10.1016/0191-2615(89)90001-5
6- Peterkofsky, R.I. and Daganzo, C.F., 1990. A branch and bound solution method for the crane scheduling problem. Transportation Research Part B: Methodological, 24(3), pp.159–172. https://doi.org/10.1016/0191-2615(90)90014-P
7- Kim, K.H. and Park, Y.-M., 2004. A crane scheduling method for port container terminals. European Journal Of Operational Research, 156(3), pp.752–768. https://doi.org/10.1016/S0377-2217(03)00133-4
8- Tavakkoli-Moghaddam, R., Makui, A., Salahi, S., Bazzazi, M. and Taheri, F., 2009. An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports. Computers & Industrial Engineering, 56(1), pp.241–248. https://doi.org/10.1016/j.cie.2008.05.011
9- Abou Kasm, O. and Diabat, A., 2020. Next-generation quay crane scheduling. Transportation Research Part C: Emerging Technologies, 114, pp.694–715. https://doi.org/10.1016/j.trc.2020.02.015
10- Al-Dhaheri, N., Jebali, A. and Diabat, A., 2016. The quay crane scheduling problem with nonzero crane repositioning time and vessel stability constraints. Computers & Industrial Engineering, 94,pp.230–244. https://doi.org/10.1016/j.cie.2016.01.011
11- Sun, D., Tang, L. and Baldacci, R., 2019. A Benders decomposition-based framework for solving quay crane scheduling problems. European Journal Of Operational Research, 273(2), pp.504–515. https://doi.org/10.1016/j.ejor.2018.08.009
12- Li, Y., Li, X., Zhang, C. and Wu, T., 2024. Decomposition algorithms for the robust unidirectional quay crane scheduling problems. Computers & Operations Research, 167, pp.106670. https://doi.org/10.1016/j.cor.2024.106670
13- Sun, D., Tang, L., Baldacci, R. and Chen, Z., 2024. A decomposition method for the group-based quay crane scheduling problem. INFORMS Journal On Computing,36,pp.543–570. https://doi.org/10.1287/ijoc.2022.0298
14- Ng, W., 2005. Crane scheduling in container yards with inter-crane interference. European Journal Of Operational Research, 164(1), pp.64–78. https://doi.org/10.1016/j.ejor.2003.11.025
15- Ng, W., 2005. Crane scheduling in container yards with inter-crane interference. European Journal Of Operational Research, 164(1), pp.64–78. https://doi.org/10.1016/j.ejor.2003.11.025
16- Ng, W. and Mak, K., 2005. Yard crane scheduling in port container terminals. Applied Mathematical Modeling, 29, pp.263–276.
17- Li, W., Wu, Y., Petering, M.E., Goh, M. and De Souza, R., 2009. Discrete-time model and algorithms for container yard crane scheduling. European Journal Of Operational Research, 198(1), pp.165–172. https://doi.org/10.1016/j.ejor.2008.08.019
18- He, J., Chang, D., Mi, W. and Yan, W., 2010. A hybrid parallel genetic algorithm for yard crane scheduling. Transportation Research Part E: Logistics And Transportation Review, 46(1), pp.136–155. https://doi.org/10.1016/j.tre.2009.07.002
19- He, J., Huang, Y. and Yan, W., 2015. Yard crane scheduling in a container terminal for the trade-off between efficiency and energy consumption. Advanced Engineering Informatics, 29(1), pp.59–75. https://doi.org/10.1016/j.aei.2014.09.003
20- He, J., Tan, C. and Zhang, Y., 2019. Yard crane scheduling problem in a container terminal considering risk caused by uncertainty. Advanced Engineering Informatics, 39, pp.14–24. https://doi.org/10.1016/j.aei.2018.11.004
21- Liang, C.-J., Chen, M., Gen, M. and Jo, J., 2014. A multi-objective genetic algorithm for yard crane scheduling problem with multiple work lines. Journal Of Intelligent Manufacturing, 25, pp.1013–1024. https://doi.org/10.1007/s10845-013-0792-4
22- Liu, W., Zhu, X., Wang, L., Yan, B. and Zhang, X., 2021. Optimization approach for yard crane scheduling problem with uncertain parameters in container terminals. Journal Of Advanced Transportation,pp.1–15. https://doi.org/10.1155/2021/5537114
23- Bazzazi, M., Safaei, N. and Javadian, N., 2009. A genetic algorithm to solve the storage space allocation problem in a container terminal. Computers & Industrial Engineering, 56(1), pp.44–52. https://doi.org/10.1016/j.cie.2008.03.012
24- Zhang, C., Liu, J., Wan, Y.-W., Murty, K.G. and Linn, R.J., 2003. Storage space allocation in container terminals. Transportation Research Part B: Methodological, 37(10), pp.883–903. https://doi.org/10.1016/S0191-2615(02)00089-9
25- Lin, D.- and Chiang, C.-W., 2017. The storage space allocation problem at a container terminal. Maritime Policy & Management, 44(6), pp.685–704. https://doi.org/10.1080/03088839.2017.1335897
26- Zhang, R.-Q., Wang, M. and Pan, X., 2019. New model of the storage location assignment problem considering demand correlation pattern. Computers & Industrial Engineering, 129, pp.210–219. https://doi.org/10.1016/j.cie.2019.01.027
27- Cao, J., Shi, Q. and Lee, D.-H., 2010. Integrated quay crane and yard truck schedule problem in container terminals. Tsinghua Science & Technology,15(4),pp.467–474. https://doi.org/10.1016/S1007-0214(10)70089-4
28- Kaveshgar, N. and Huynh, N., 2015. Integrated quay crane and yard truck scheduling for unloading inbound containers. International Journal Of Production Economics, 159, pp.168–177. https://doi.org/10.1016/j.ijpe.2014.09.028
29- Tang, L., Zhao, J. and Liu, J., 2014. Modeling and solution of the joint quay crane and truck scheduling problem. European Journal Of Operational Research,236(3),pp.978–990. https://doi.org/10.1016/j.ejor.2013.08.050
30-Lee, D.-H., Wang, H.Q. and Miao, L., 2008. Quay crane scheduling with non-interference constraints in port container terminals. Transportation Research Part E: Logistics And Transportation Review, 44(1), pp.124–135. https://doi.org/10.1016/j.tre.2006.08.001
31- Hop, D.C., Van Hop, N. and Anh, T.T.M., 2021. Adaptive particle swarm optimization for integrated quay crane and yard truck scheduling problem. Computers & Industrial Engineering, 153, pp.107075. https://doi.org/10.1016/j.cie.2020.107075
32- Zhen, L., Yu, S., Wang, S. and Sun, Z., Scheduling quay cranes and yard trucks for unloading operations in container ports. Annals Of Operations Research, pp.455–478. https://doi.org/10.1007/s10479-016-2335-9
33- Skaf, A., Lamrous, S., Hammoudan, Z. and Manier, M.-A., 2021. Integrated quay crane and yard truck scheduling problem at the port of Tripoli-Lebanon. Computers & Industrial Engineering, 159, pp.107448. https://doi.org/10.1016/j.cie.2021.107448
34- Qin, T., Du, Y., Chen, J.H. and Sha, M., 2020. Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel. European Journal Of Operational Research,285(3),pp.884–901. https://doi.org/10.1016/j.ejor.2020.02.021
35- Hsu, H.-P., Wang, C.-N., Fu, H.-P. and Dang, T.-T., 2021. Joint scheduling of yard crane, yard truck, and quay crane for container terminal considering vessel stowage plan: An integrated simulation-based optimization approach. Mathematics, 9(18), pp.22–https://doi.org/10.3390/math9182236
36- Hsu, H.-P., Chou, C.-C. and Wang, C.-N., 2022. Heuristic/metaheuristic-based simulation optimization approaches for integrated scheduling of yard crane, yard truck, and quay crane considering import and export containers. IEEE Access, 10, pp.64650–64670.1109/ACCESS.2022.3180752
37- Kizilay, D., Eliiyi, D.T. and Van Hentenryck, P., 2018. Constraint and mathematical programming models for integrated port container terminal operations. In: W.J. van Hoeve (ed.) Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings, pp.344–360. Springer, Lecture Notes in Computer Science, 10848. https://doi.org/10.1007/978-3-319-93031-2_25
38- Kizilay, D., Van Hentenryck, P. and Eliiyi, D.T., 2020. Constraint programming models for integrated container terminal operations. European Journal Of Operational Research, 286(3), pp.945–962. https://doi.org/10.1016/j.ejor.2020.04.025
39- Luo, J., Wu, Y. and Bergsten Mendes, A., 2016. Modelling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal. Computers & Industrial Engineering, 94, pp.32–44. https://doi.org/10.1016/j.cie.2016.01.010

فایل ها

هم رسانی

ارجاع به این مقاله

آمار