The Robust Bulk Ship Routing Problem with Batched Cargo Selection

Lingxiao Wu, Shuaian Wang, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)124-159
Number of pages36
JournalTransportation Research Part B: Methodological
Volume143
Early online date30 Nov 2020
DOIs
Publication statusPublished - 31 Jan 2021

Keywords

  • Batched cargo selection
  • Branch-and-price-and-cut
  • Bulk tramp shipping
  • Robust optimization
  • Ship routing

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Cite this