A Set-Partitioning-based model for the Berth Allocation Problem under Time-Dependent Limitations

• Published in: European journal of operational research 2016-05, Vol.250 (3), p.1001-1012
• Main Authors: Lalla-Ruiz, Eduardo, Expósito-Izquierdo, Christopher, Melián-Batista, Belén, Moreno-Vega, J. Marcos
• Format: Article
• Language: English
• Subjects: Berth Allocation Problem; Containerization; Maritime container terminal; Mathematical models; Operations research; Optimization model; Optimization techniques; Set Partitioning; Studies; Transportation terminals
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2015.10.021

•A Set-Partitioning-based model for solving this problem is proposed.•This problem is extended to consider a multi-period planning horizon.•Improvements in running time and solution quality over earlier approaches.•A new benchmark suite is proposed. This paper addresses the Berth Allocation Problem under Time-Dependent Limitations. Its goals are to allocate and schedule the available berthing positions for the container vessels arriving toward a maritime container terminal under water depth and tidal constraints. As we discuss, the only optimization model found in the literature does not guarantee the feasibility of the solutions reported in all the cases and is limited to a two-period planning horizon, i.e., one low tide and one high tide period. In this work, we propose an alternative mathematical formulation based upon the Generalized Set Partitioning Problem, which considers a multi-period planning horizon and includes constraints related to berth and vessel time windows. The performance of our optimization model is compared with that of the mathematical model reported in the related literature. In this regard, the computational experiments indicate that our model outperforms the previous one from the literature in several terms: (i) it guarantees the feasibility and optimality of the solutions reported in all the cases, (ii) reduces the computational times about 88 percent on average in the problem instances from the literature, and (iii) presents reasonable computational times in new large problem instances.