Robenek, T., Umang, N., Bierlaire, M., and Ropke, S. (2012)

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we emphasize the differences in operations between bulk ports and container terminals which emphasizes the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. The proposed algorithm is tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithm can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.