MIP-Heuristics for Minimum Cost Berth Allocation Problem

The dynamic minimum cost berth allocation problem (BAP) is considered with an aim to minimize the total costs of waiting and handling, as well as earliness or tardiness of completion, for all ships. BAP can be presented as the Mixed Integer Linear Program (MILP) with a large number of 0-1 variables, making it suitable for the application of Mixed Integer Programming (MIP) heuristics. Three well known MIP heuristics have been applied: local branching, variable neighborhood branching and variable neighborhood decomposition search for 0-1 MIP, where the last one performs the best. In the computational experiments, the results of the above mentioned MIP heuristics with the CPLEX commercial solver within the same CPU time limit are compared. For small size examples, variable neighborhood decomposition search for 0-1 MIP heuristic method was able to find optimal solutions for all instances and to outperform CPLEX regarding computation times. The results for medium size test examples indicate that the complexity prevents this problem from being efficiently treated by any of the three general purpose solution methods considered in this paper.