To main content

A traveling salesman problem with pickups and deliveries and stochastic travel times: An application from chemical shipping

Abstract

This paper introduces a single-ship routing problem with stochastic travel times that is faced by a chemical shipping company in the Port of Houston. We take into explicit consideration the uncertain waiting times associated with the terminals inside the port, and the resulting inefficient transits caused by severe congestion. We show that the problem can be modeled as a stochastic Traveling Salesman Problem with Pickups and Deliveries (TSPPD), in which the goal is to find the route within the port with maximized probability that its total length does not exceed a threshold. We show that it is important to properly address the inefficient transits, and that including uncertainty in the travel times can have an impact in the choice of optimal route inside a port. We further show that the layout of the relevant terminals as well as their distances to the anchorage are important drivers of such impact. We conclude with the suggestion that one can use the proposed model and method to find a set of alternative routes, followed by a re-evaluation process since our method encompasses an approximation that underestimates the variation of the route completion time.
Read the publication

Category

Academic article

Language

English

Author(s)

Affiliation

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

Year

2018

Published in

European Journal of Operational Research

ISSN

0377-2217

Volume

269

Issue

3

Page(s)

844 - 859

View this publication at Norwegian Research Information Repository