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.