A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem

Qiang Meng, Shuaian Wang, Chung Yee Lee

Research output: Journal article publicationJournal articleAcademic researchpeer-review

51 Citations (Scopus)


This paper deals with a practical tramp ship routing problem while taking into account different bunker prices at different ports, which is called the joint tramp ship routing and bunkering (JSRB) problem. Given a set of cargoes to be transported and a set of ports with different bunker prices, the proposed problem determines how to route ships to carry the cargoes and the amount of bunker to purchase at each port, in order to maximize the total profit. After building an integer linear programming model for the JSRB problem, we propose a tailored branch-and-price (B&P) solution approach. The B&P approach incorporates an efficient method for obtaining the optimal bunkering policy and a novel dominance rule for detecting inefficient routing options. The B&P approach is tested with randomly generated large-scale instances derived from real-world planning problems. All of the instances can be solved efficiently. Moreover, the proposed approach for the JSRB problem outperforms the conventional sequential planning approach and can incorporate the prediction of future cargo demand to avoid making myopic decisions.
Original languageEnglish
Pages (from-to)1-19
Number of pages19
JournalTransportation Research Part B: Methodological
Publication statusPublished - 1 Feb 2015
Externally publishedYes


  • Branch-and-price
  • Bunkering
  • Maritime transportation
  • Ship routing and scheduling
  • Tramp shipping

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem'. Together they form a unique fingerprint.

Cite this