VNS-based Approach to Minimum Cost Hybrid Berth Allocation Problem

Abstract

This study considers the Minimum Cost Hybrid Berth Allocation Problem (MCHBAP) with fixed handling times of vessels. The goal of MCHBAP is to minimize the total costs of waiting and handling, as well as earliness or tardiness of completion, for all vessels. It is well known that even simpler variants of Berth Allocation Problems are NP hard. Therefore, meta-heuristic methods represent the natural choice to deal with MCHBAP. A new optimization method based on the deterministic variant of Variable Neighborhood Search (VNS) method is developed. Namely, we define three types of neighborhoods based on sequence pair solution representation and incorporated them into Variable Neighborhood Descent (VND) environment. The proposed VND implementation is tested on two sets of examples and compared with other metaheuristic approaches from the recent literature. Our computational results show that the proposed VND is able to find optimal solutions for real life test instances significantly faster than other methods. On randomly generated instances, VND outperformed other methods with respect to the running time with negligible deterioration of solution quality for 4 out of 15 examples.