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

37 Citations (Scopus)

Abstract

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
Volume72
DOIs
Publication statusPublished - 1 Feb 2015
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Cite this