Full-shipload tramp ship routing and scheduling with variable speeds

M. Wen*, S. Ropke, H. L. Petersen, R. Larsen, O. B.G. Madsen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

52 Citations (Scopus)

Abstract

This paper investigates the simultaneous optimization problem of routing and sailing speed in the context of full-shipload tramp shipping. In this problem, a set of cargoes can be transported from their load to discharge ports by a fleet of heterogeneous ships of different speed ranges and load-dependent fuel consumption. The objective is to determine which orders to serve and to find the optimal route for each ship and the optimal sailing speed on each leg of the route so that the total profit is maximized. The problem originated from a real-life challenge faced by a Danish tramp shipping company in the tanker business. To solve the problem, a three-index mixed integer linear programming formulation as well as a set packing formulation is presented. A novel Branch-and-Price algorithm with efficient data preprocessing and heuristic column generation is proposed. The computational results on the test instances generated from real-life data show that the heuristic provides optimal solutions for small test instances and near-optimal solutions for larger test instances in a short running time. The effects of speed optimization and the sensitivity of the solutions to the fuel price change are analyzed. It is shown that speed optimization can improve the total profit by 16% on average and the fuel price has a significant effect on the average sailing speed and total profit.

Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalComputers and Operations Research
Volume70
DOIs
Publication statusPublished - 1 Jun 2016

Keywords

  • Heuristic column generation
  • Speed optimization
  • Tramp shipping

Fingerprint

Dive into the research topics of 'Full-shipload tramp ship routing and scheduling with variable speeds'. Together they form a unique fingerprint.

Cite this