Highlights Consider a practical ship routing problem with COA selection and uncertain voyage costs. Develop a tailored branch-and-price-and-cut solution approach. Conduct extensive numerical experiments to test the performance of the algorithm and analyze the value of robust optimization.
Abstract Maritime transportation forms the backbone of the world merchandise trade. In this paper, we consider a problem that combines three interconnected subproblems in tramp shipping: the fleet adjustment problem, the cargo selection problem, and the ship routing problem. For cargo selection, we consider the decision behaviors under the setting of Contract of Affreightment (COA), in which cargoes should be rejected or accepted as a batch. In view of the uncertainties observed in maritime transportation, we formulate the problem in a robust way so that the solutions can protect the profitability of shipping companies against variations in voyage costs. We first provide compact mixed integer linear programming formulations for the problem and then convert them into a strengthened set covering model. A tailored branch-and-price-and-cut algorithm is developed to solve the set covering model. The algorithm is enhanced by a multi-cut generation technique aimed at tightening the lower bounds and a primal heuristic aimed at finding high-quality upper bounds. Extensive computational results show that our algorithm yields optimal or near-optimal solutions to realistic instances within short computing times and that the enhancement techniques significantly improve the efficiency of the algorithm.
The Robust Bulk Ship Routing Problem with Batched Cargo Selection
Transportation Research Part B: Methodological ; 143 ; 124-159
2020-11-08
36 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch