Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem

摘要

This paper considers the Dynamic Berth Allocation Problem, in which vessels are assigned to discrete positions in berths. This problem, whose goal is to minimize the total time the vessels stay at the port, constitutes one of the most important processes at any containers terminal. We propose a hybrid metaheuristic that combines Tabu Search with Path Relinking, T~2S~*+PR. The results reached by this hybrid algorithm are compared with the optimal values given by the best mathematical model that appears in the literature for this problem, GSPP, and with a tabu search algorithm from the literature, t~2s. For small instances, the algorithm T~2S~* + PR is able to obtain most of the optimal solutions in an amount of computational time that is lower than the time required to solve the GSPP model. For medium and large size instances, GSPP cannot be solved to optimality, whereas the proposed hybrid algorithm outperforms t~2s. Moreover, the computational experiments carried out in this paper confirm the robustness of the proposed algorithm with respect to both the parameters governing the procedure and the problem size.