Genetic Based Algorithms to Solving Multi-Quays Berth Allocation Problem with Setup Time Constraints

• Autorzy: Chatnugrob Sangsawang , Cholthida Longploypad
• Języki publikacji: EN

Abstrakty

EN

Background: This study focuses on efficient berth planning in multi-purpose terminal composed of multiple quays. A multi-quay berth offers infrastructure, equipment, and services for different types of cargo and vessels to meet the needs of users from various freight markets. Moreover, each berth from any quay can be dedicated for one or two different types of cargo and vessels. To improve port efficiency in terms of reducing the waiting time of ships, this study addresses the Multi-Quay Berth Allocation Problem (MQ-BAP), where discrete berthing layout is considered along with setup time constraints and practical constraints such as time windows and safety distances between ships. Sequence dependent setup times may arise due to the berth can convert from dedicated function to another function according to the variance of cargo demand. This problem was inspired by a real case of a multi-purpose port in Thailand. Methods: To solve the problem, we propose a mixed-integer programming model to find the optimal solutions for small instances. Furthermore, we adapted a metaheuristic solution approach based on Genetic algorithm (GA) to solving the MQ-BAP model in large-scale problem cases. Results: Numerical experiments are carried out on randomly generated instances for multi-purpose terminals to assess the effectiveness of the proposed model and the efficiency of the proposed algorithm. The results show that our proposed GA provides a near-optimal solution by average 4.77% from the optimal and show a higher efficiency over Particle swarm optimization (PSO) and current practice situation, which are first come first serve (FCFS) rule by 1.38% and 5.61%, respectively. Conclusions: We conclude that our proposed GA is an efficient algorithm for near-optimal MQ-BAP with setup time constraint at acceptable of computation time. The computational results reveal that the reliability of the metaheuristics to deal with large instances is very efficient in solving the problem considered. (original abstract)

Słowa kluczowe

EN

Commodity markets; Sea transport; Organization of seaports; Genetic algorithms

PL

Rynki towarowe; Transport morski; Organizacja portów morskich; Algorytmy genetyczne

• Czasopismo: LogForum
• Rocznik: 2022
• Tom: 18
• Numer: nr 4
• Strony: 505--515

Twórcy

autor

Chatnugrob Sangsawang

• Kasetsart University, Thailand

autor

Cholthida Longploypad

• Kasetsart University, Thailand

Bibliografia

• Bacalhau E. T., Casacio L., de Azevedo A. T., 2021, New hybrid genetic algorithms to solve dynamic berth allocation problem, Expert Systems with Applications, 167, Article 114198, https://doi.org/10.1016/j.eswa.2020.114198
• Bierwirth C., Meisel F., 2010, A survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 202(3), 615-627, https://doi.org/10.1016/j.ejor.2009.05.031
• Bierwirth C., 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), 675-689, https://doi.org/10.1016/j.ejor.2014.12.030
• Carlo H. J., Vis I. F., Roodbergen K. J, 2015, Seaside operations in container terminals: Literature overview, trends, and research directions, Flexible Services and Manufacturing Journal, 27(1), 224-262, https://doi.org/10.1007/s10696-013-9178-3
• Cheimanoff N., Fontane F., Kitri M. N., Tchernev N., 2021, Exact and heuristic methods for the berth allocation problem with multiple continuous quays in tidal bulk terminals, Expert Systems With Applications, 201, Article 117141, https://doi.org/10.1016/j.eswa.2022.117141
• Chen L., and Huang Y., 2017, A dynamic continuous berth allocation method based on genetic algorithm, Proceeding - In 2017 3rd IEEE International Conference on Control Science and Systems Engineering (ICCSSE), IEEE, 770-773, https://doi.org/10.1109/CCSSE.2017.8088038
• Frojan P., Correcher J. F., Alvarez-Valdes R., Koulouris G., Tamarit J. M., 2015, The continuous berth allocation problem in a container terminal with multiple quays, Expert Systems with Applications, 42(21), 7356-7366, https://doi.org/10.1016/j.eswa.2015.05.018
• Holland J. H., 1992, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, Cambridge: MIT press.
• Hsu H. P., Chiang T. L., Wang C. N., Fu H. P., Chou C. C., 2019, A Hybrid GA with Variable Quay Crane Assignment for Solving Berth Allocation Problem and Quay Crane Assignment Problem Simultaneously, Sustainability, 11(7), 2018-2038, https://doi.org/10.3390/su11072018
• Imai A., Nagaiwa K., Tat C. W., 1997, Efficient planning of berth allocation for container terminals in Asia, Journal of Advanced Transportation, 31(1), 75-94, https://doi.org/10.1002/atr.5670310107
• Imai A., Nishimura E., Papadimitriou S., 2001, The dynamic berth allocation problem for a container port, Transportation Research Part B, 35(4), 401-417, https://doi.org/10.1016/S0191-2615(99)00057-0
• Jos B. C., Harimanikandan M., Rajendran C., Ziegler H., 2019, Minimum cost berth allocation problem in maritime logistics: new mixed integer programming models, Sdhan, 44(6), Article 149, https://doi.org/10.1007/s12046-019-1128-7
• Kennedy J., Eberhart R., 1995, Particle swarm optimization, Proceedings - In international conference on neural networks (ICNN'95), IEEE, 4, 1942-1948, https://doi.org/10.1109/ICNN.1995.488968
• Krimi I., Todosijevi´c R., Benmansour R., Ratli M., El Cadi A. A., Aloullal A., 2020, Modelling and solving the multi-quays berth allocation and crane assignment problem with availability constraints. Journal of Global Optimization, 78(2), 349-373, https://doi.org/10.1007/s10898-020-00884-1
• Mauri G. R., Ribeiro G. M., Lorena L. A. N., Laporte G., 2016, An adaptive large neighbourhood search for the discrete and continuous berth allocation problem, Computers & Operations Research, 70,140-154, https://doi.org/10.1016/j.cor.2016.01.002
• Prencipe L. P., Marinelli M., 2021, A novel mathematical formulation for solving the dynamic and discrete berth allocation problem by using the Bee Colony Optimisation algorithm, Applied Intelligence, 51(7), 4127-4142, https://doi.org/10.1007/s10489-020-02062-y
• UNCTAD, 2021, Review of maritime transport 2021. Available: https://unctad.org/system/files/official-document/rmt2021_en_0.pdf [Accessed: 18 June 2022].
• Xu Y., Xue K., Du Y., 2018, Berth scheduling problem considering traffic limitations in the navigation channel, Sustainability, 10(12), 4795-4816, https://doi.org/10.3390/su10124795

Identyfikatory

DOI

10.17270/J.LOG.2022.786