GENETIC BASED ALGORITHMS TO SOLVING MULTI-QUAYS BERTH ALLOCATION PROBLEM WITH SETUP TIME CONSTRAINTS

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.