To main content

A traveling salesman problem with pickups and deliveries, time windows and draft limits: case study from chemical shipping

Abstract

This paper introduces and studies a real in-port ship routing and scheduling problem faced by chemical shipping companies. We show that this problem can be modeled as a Traveling Salesman Problem with Pickups and Deliveries, Time Windows and Draft Limits (TSPPD-TWDL). We propose a mathematical formulation for the TSPPD-TWDL and suggest a solution method based on forward dynamic programming (DP) to solve the problem. A set of label extension rules are also proposed to accelerate and enhance the performance of the algorithm. Computational studies show that the label extension rules are essential to the DP-algorithm, and the proposed solution method is able to solve real-sized in-port routing and scheduling problems in chemical shipping efficiently.

Category

Academic article

Language

English

Author(s)

  • Mari Jevne Arnesen
  • Magnhild Gjestvang
  • Xin Wang
  • Kjetil Fagerholt
  • Kristian Thun
  • Jørgen Glomvik Rakke

Affiliation

  • Norwegian University of Science and Technology
  • SINTEF Ocean / Energi og transport

Year

2016

Published in

Computers & Operations Research

ISSN

0305-0548

Publisher

Elsevier

Volume

77

Page(s)

20 - 31

View this publication at Cristin