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

Aurora Smith Elgesem, Eline Sophie Skogen, Xin Wang and Kjetil Fagerholt

European Journal of Operational Research, 2018, vol. 269, issue 3, 844-859

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.

Keywords: OR in maritime industry; Traveling salesman problem with pickup and delivery; Stochastic travel time; Monte Carlo simulation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718301383
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:269:y:2018:i:3:p:844-859

DOI: 10.1016/j.ejor.2018.02.023

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().