الگوریتم حل مساله تخصیص کانتینرهای دریایی با توجه به ظرفیت و زمان انتظار

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

نویسندگان

1 دانشجوی دکتری مهندسی صنایع دانشکده مهندسی صنایع پردیس البرز دانشگاه تهران

2 استاد دانشکده مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران

چکیده

مفهوم تخلیه و بارگیری کانتینرها در بنادر کانتینری به منظور تخلیه و بارگیری، تحت عنوان تخصیص کانتینر مطرح می‏شود. در این تحقیق فرض گردیده‏است که کانتینرها بین بخشهای مختلف بندر انتقال می‏یابند و باید بین بخشهای موجود بندر جهت انتقال تخصیص یابند. تخصیص به گونه‏ای صورت می‏گیرد که هزینه‏‏ها حداقل گردد. برای داشتن یک مدل‏سازی مناسب و کارآمد رابطه بین بخشهای مختلف نوشته شده‏است. در این مقاله مساله تخصیص کانتینرها به کشتی‌ها ، محوطه‌ها ،گمرک ها ، سرزمین اصلی و جرثقیل به صورت مجزا مورد بررسی قرار می گیرد . همچنین مساله تخصیص کشتی ها به اسکله ها نیز مورد مطالعه قرار می گیرد ؛ در هر دو قسمت زمان حمل و ظرفیت محوطه ها به صورت محدودیت در مساله اعمال گردیده است . به علت NP-Hard بودن مساله به دست اوردن جواب بهینه در زمان معقول امکان پذبر نیست. پس از مدلسازی ریاضی، بعلت پیچیدگی مسأله ، برای حل از دو الگوریتم ابتکاری استفاده شده است . اولین الگوریتم با روش ازدحام ذرات تخصیص کشتی ها به اسکله ها را انجام می دهد و پس از آن الگوریتم دوم با روش ژنتیک تخصیص کانتینرها به قسمت های مختلف را انجام می دهد . در نهایت تجزیه و تحلیل و مقایسه الگوریتم پیشنهادی انجام می‌شود. نتایج محاسبات نشان می‌دهد که الگوریتم پیشنهادی دارای کارایی بسیار بالایی در عمل و در دنیای واقعی می باشد .

کلیدواژه‌ها


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

Problem solving algorithm for the allocation of marine containers according to the capacity and waiting time

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

  • MohammadSaviz AsadiLari 1
  • Fariborz Jolai 2
  • Reza Tavakkoli-Moghaddam 2
  • Jafar Razmi 2
1 Ph.D. student, School of Industrial Engineering, College of Engineering, University of Tehran
2 Professor, School of Industrial Engineering, College of Engineering, University of Tehran
چکیده [English]

The concept of container unloading and loading in container ports for the purpose of unloading and loading is referred to as container allocation. This study assumes that the containers are transported between different segments of the port and must be allocated between the existing segments of the port for transport. The allocation is made to minimize costs. For a good and efficient modeling is written the relationship between the different sections.In this paper, the issue of the allocation of containers to ships, yards, customs, mainland and cranes is examined separately. Also, the problem of allocating ships to the berths is also studied. in both parts, the time of transportation and the capacity of the enclosures are limited in the problem. The literature review shows that the results obtained from solving this problem are not applicable in practice. After mathematical modeling, due to the NP-hardness of the problem, two innovative algorithms have been used to solve the problem. The first PSO method performs the assignment of ships to the dock, and then the second algorithm uses the GA method to allocate containers to different parts. Finally, the proposed algorithm is analyzed and compared. The results of the calculations show that the proposed algorithm has a very high performance in practice and in the real world.

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

  • Allocation of containers
  • allocation of ships
  • genetic algorithm
  • pso algorithm
-Ak, A. and Erera, A. (2006) "Simultaneous berth and quay crane scheduling for container ports"., Working paper, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta
-Barkhof, F (2007) "Magnetic resonance imaging effects of interferon beta-1b in the BENEFIT study: integrated 2-year results", Archives of Neurology, Vol. 64, No. 9, pp. 1292-1298
-Borumand, A. and Beheshtinia, M. (2018) "A developed genetic algorithm for solving the multi-objective supply chain scheduling problem", Kybernetes, Vol. 47, No. 7, pp. 1401-1419.
-Beheshtinia, M., Ghasemi, A. and Farokhnia, M. (2018) "Supply chain scheduling and routing in multi-site manufacturing system (Case study: a drug manufacturing company)", Journal of Modelling in Management, Vol. 13, No. 1, pp. 27-49.
-Cao, C., Gao, Z. and Li, K. (2012) "Capacity allocation problem with random demands for the rail container carrier", European Journal of Operational Research., Vol. 217, No. 1, pp. 214-221
-Cia, B., Huang, S., Liu, D., Dissanavake, G. (2014) "Rescheduling policies for large-scale task allocation of autonomous straddle carriers under uncertainty at automated container terminals", Robotics, and Autonomous Systems., Vol. 62, No. 4, pp. 506-514
-Dai J., Lin, W., Moorthy R. and Teo, C. P.  (2008) "Berth allocation planning optimization in container terminals", Supply Chain Analysis., Springer Vol. 119, No. 1, pp. 69-104
-Daganzo, C. F. (1989) "The crane scheduling problem", Transportation Research Part B: Methodological, Vol. 23, No. 3, pp. 159-175
-Do, N. A. D., Nielsen, I. E., Chen, G. and Nielsen, P. (2016) "A simulation-based genetic algorithm approach for reducing emissions from import container pick-up operation at container terminal", Annals of Operations Research Nielsen., Vol. 242, No. 2, pp. 285-301
-Frojan, P., Correcher, J. F., Alvarez-Valdes, R., Koulouris, G. and Manuel, J. (2015) "The continuous berth allocation problem in a container terminal with multiple quays", Expert Systems with Applications, Vol. 42, No. 21, pp. 7356-7366
-Giallombardo, G., (2008) "The Tactical Berth Allocation Problem (TBAP) with quay crane assignment and transshipment-related quadratic yard costs", European Transport Conference (ETC), Noordwijkerhout, Netherlands, 6-8 October 2008.
-Guan, Y (2002) "A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis", Operations Research Letters., Vol. 30, No. 5, pp. 343-350
-Güven, C., and Türsel, D. (2014) 'Trip allocation and stacking policies at a container terminal", Transportation Research Procedia., Vol. 3, No. 1, pp. 565-573
-Han, X. L., Gong, X. and Jo, J. (2015) "A new continuous berth allocation and quay crane assignment model in container terminal", Computers and Industrial Engineering., Vol. 89, No. 1, pp. 15-22
-Harris, G (2007) "Container terminal simulation", Proc. of Huntsville Simulation Conference, Huntsville, Alabama, USA, 30 October - 01 November 2007.
-He, J. (2016) "Berth allocation and quay crane assignment in a container terminal for the trade-off between time-saving and energy-saving", Journal of Advanced Engineering Informatics., Vol. 30, No. 3, pp. 390-405.
-Hirashima, Y. (2008) "A Q-learning system for container transfer scheduling based on shipping order at container terminals", International Journal of Innovative Computing, Information and Control., Vol. 4 , No. 3, pp. 547-558
-Hsu, W. K. K. (2009) "Improvement of Service Quality for Container Terminals", International Journal of Production Economics., Vol. 122, No. 1,  pp. 56-66
-Imai, A., Nishimura, E. and Papadimitriou, S. (2005) "Berth allocation in a container port: Using a continuous location space approach", Transportation Research Part B: Methodological,. Vol. 39, No. 4 pp. 199-221
-Imai, A. (2008) "The simultaneous berth and quay crane allocation problem", Transportation Research Part E: Logistics and Transportation Review,. Vol. 44, No. 5, pp. 900-920
- De Weille, J. and A. Ray (1974) "The optimum port capacity", Journal of Transport Economics and Policy,. Vol. 17, No. 1, pp. 244-259
-Jiang, X. J., and Gang, J. (2017) "A branch-and-price method for integrated yard crane deployment and container allocation in transshipment yards", Transportation Research Part B: Methodological., Vol. 98, No. 1, pp. 62-75
-Le, Y. and Ieda, H. (2009) "Evolution dynamics of container port systems with a geo-economic concentration index: A comparison of Japan, China and Korea", Proceedings of the Eastern Asia Society for Transportation Studies, Surabaya, Indonesia, 16-19 November 2009, Vol. 7, No. 1, pp. 428-438
-Lee, D.-H., Gang, J. and Hang, J. (2012) "Terminal and yard allocation problem for a container transshipment hub with multiple terminals", Transportation Research Part E: Logistics and Transportation Review., Vol. 48, No. 2, pp. 516-528
-Li, J.-A., Leung, S. C. H., Wu, Y. and Liu, K. (2007) "Allocation of empty containers between multi-ports" European Journal of Operational Research., Vol. 182, No. 1, pp. 400-12.
-Liu, D. and Yang, H. (2015) "Joint slot allocation and dynamic pricing of container sea–rail multimodal transportation", Journal of Traffic, and Transportation Engineering., Vol. 2, No. 3, pp. 198-208
-Liang, C., Huang, Y. and Yang, Y. (2009) ''A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning", Computers & Industrial Engineering,. Vol. 56, No. 3, pp. 1021-1028
-Lokuge, P. and Alahakoon, D. (2007) "Improving the adaptability in automated vessel scheduling in container ports using intelligent software agents ", European Journal of Operational Research., Vol. 177, No. 3, pp. 1985-2015
-Kasypi, M. and Muhammad, Z. (2006) "A regression model for vessel turnaround time", Tokyo Academic, Industry & Cultural Integration Tour., pp. 1-15
-Kent del Pilar Londoño, M. and Kent, P. E.  (2003) "A Tale of Two Ports", Office of the Chief Economist for Latin America and the Caribbean The World Bank
-Kim, K. H. and Moon, K. C. (2003) "Berth scheduling by simulated annealing", Transportation Research Part B: Methodological,. Vol. 37, No. 6, pp. 541-560
-Lee, D. H., Song, L.  and Wang, H.  (2006) "Bilevel programming model and solutions of berth allocation and quay crane scheduling", Transportation Research Board 85th Annual Meeting, Washington, D.C., USA, 22-26 January 2006.
-Lim, A. (1998) "The berth planning problem", Operations Research Letters,. Vol. 22, No. 2, pp. 105-110
-Liu, J., Wan,  Y. W. and Wang. L.  (2006) "Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures", Naval Research Logistics (NRL),. Vol. 53, No. 1, pp. 60-74
-Meier, L. and Schumann, R. (2007) "Coordination of Interdependent Planning Systems, a Case Study", Informatik trifft Logistik., Vol.1,No.1 pp. 389-396
-Mehri, S. and Haghshenas, H. (2018) “Containerized transport mode choice between rail and road in Iran”, Journal of Transportation Engineering., Vol. 9, No. 4, pp. 631-646
-Myung, Y.-S., and Moon, I. (2014) "A network flow model for the optimal allocation of both foldable and standard containers", Operations Research Letters., Vol. 42, No. 7, pp. 484-488
-Onut, S. and Saglam, C. O.  (2008) "Modeling and optimization of general cargo port operations through fuzzy minimal spanning tree and fuzzy dynamic programming approaches", International Journal of Innovative Computing, Information and Control. Vol. 4, No. 8, pp. 1835-1851
-Park, K. and Kim, K. H. (2002) "Berth scheduling for container terminals by using a sub-gradient optimization technique", Journal of the Operational Research Society, Vol. 53, No. 9, pp. 1054-1062
-Peterkofsky, R.I. and Daganzo, C. F. (1990) "A branch and bound solution method for the crane scheduling problem", Transportation Research Part B: Methodological., Vol. 24, No. 3, pp. 159-172
-Sheng, L., Hongxia, Z., Xisong, D. and Changjian, C. (2016) "A heuristic algorithm for container loading of pallets with infill boxes", European Journal of Operational Research,. Vol. 252, No. 3, pp. 728-736.
-Song, L., Cherrett, T. and Guan, T. (2012) "Study on berth planning problem in a container seaport: Using an integrated programming approach", Computers & Industrial Engineering,. Vol.62, No.1, pp. 119-128
-Toffolo, T. A. M., Esprit, E., Wauters, T. and Vanden, G. (2018) "A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem", European Journal of Operational Research., Vol. 257, No. 2, pp. 526-38
-Tongzon, J. L. and Ganesalingam, S. (2014) "An evaluation of ASEAN port performance and efficiency", Asian Economic Journal,. Vol. 8, No. 3, pp. 317-330
-Türkoğulları, Y. B., Taşkın, Z. C., Aras, N. and Kuban, I (2017) "Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals", European Journal of Operational Research., Vol.254, No.3, pp. 985-1001
-Wang, H., Wang, S., Meng, G. (2014) "Simultaneous optimization of schedule coordination and cargo allocation for liner container shipping networks", Transportation Research Part E: Logistics Meng, and Transportation Review., Vol. 70, No. 5, pp. 261-273
-Wang, Y., Jiang, X., Lee, L. H., Chew, E. K. P. and Choon, K. (2017) "Tree based searching approaches for integrated vehicle dispatching and container allocation in a transshipment hub", Expert Systems with Applications., Vol.74, No.1, pp 139-150
-Wong, A. K.-S. (2008) "Optimization of container process at multimodal container terminals". PhD thesis, Queensland University of Technology, Queensland, Australia
-Xie, Y., Liang, X., Ma, L. and Houmin,  J. (2018) "Empty container management and coordination in intermodal transport", European Journal of Operational Research., Vol.257, No.1, pp. 223-232
-Yu, M. and Qi, X. (2013) "Storage space allocation models for inbound containers in an automatic container terminal", European Journal of Operational Research., Vol. 226, No. 1, pp. 32-45
-Zehendner, E., Feillet, D. and Jaillet, J. (2018) "An algorithm with performance guarantee for the online container relocation problem", European Journal of Operational Research., Vol.259, No.1, pp 48-62
-Zeng, Q. and Yang, Z. (2009) ''Integrating simulation and optimization to schedule loading operations in container terminals'', Computers & Operations Research., Vol. 36, No. 6, pp. 1935-1944
-Zhang, C., Wu, T., Kim, K. H. and Miao, L. (2014) ''Conservative allocation models for outbound containers in container terminals'', European Journal of Operational Research., Vol. 238, No. 1, pp. 155-65