New hybrid genetic algorithms to solve dynamic berth allocation problem

摘要

Berth allocation problem (BAP) is concerned to assign ships to port terminal positions, seeking to minimize the total service time and maximize the quay occupation. A dynamic model with special features is developed to deal with real scenarios from Port Administration of Paranagua and Antonina (APPA), located on the Brazilian coast. To solve the problem, this work proposes two metaheuristics comprise by a novel combination of genetic algorithm and an approximated dynamic programming employed as a local search. Two heuristics for solution space reductions, a confinement procedure in a reduced neighborhood, known as Corridor Method, and an elimination process for unpromising solution regions are designed for local search approach. Case studies present a problem complexity discussion and comparative analysis of the metaheuristics regarding two standard genetic algorithms. The computational experiments explore the optimal solutions for small instances and the best results, solutions variability, and probabilistic plots resorting by ten instances based on real data available by APPA. The results show the reliability of the metaheuristics to deal with large instances and tight schedules in busy port systems.