Stochastic In-Port Routing in Chemical Shipping
Abstract
Chemical tankers spend a substantial amount of time in port as the developmentof port infrastructure has not followed the fast paced increase in theworld fleet. The resulting traffic at terminals causes ships to wait for a longtime before a terminal is ready to accommodate it. A large amount of uncertaintyis associated with the waiting times, which complicates the planning ofport operations.
The aim of the thesis is to investigate the benefits of including uncertainty inthe in-port routing problem of a chemical tanker. The chemical tanker hasto pick up and deliver a given number of cargoes located at different terminalswhile complying with capacity and draft limit constraints. The waitingtimes at the terminals are stochastic, which results in stochastic travel timesbetween terminals. The problem studied in this thesis is a stochastic pickupand delivery problem. The problem is dynamic by nature, and both a staticand a dynamic version of the problem are solved. A review of deterministicand stochastic routing problems resembling the pickup and delivery problemis presented. To our knowledge, few or none have studied the pickup and deliveryproblem where travel times are stochastic. Our thesis contributes to theliterature by studying the pickup and delivery problem with uncertain traveltimes, subject to constraining draft limits. In addition, due to the particularlynarrow port channel in the case port, we consider the ship's movement asmovement along a straight line. This gives a unique relation between stochasticwaiting times at terminals and travel times between terminals. As far aswe know, this has not been studied before, and the unique conditions andaspects of the travel times this gives are examined and discussed.
The stochastic waiting times at terminals are assumed normally distributed.The stochastic travel times between cargoes in different terminals and thestochastic waiting time at the destination terminal are correlated. The distributionof the arc travel times are assumed normally distributed, and approximationsare used to obtain the distributions.Both a static and a dynamic version of the problem are solved. The objective is to find the route that maximizes the probability of completing within agiven threshold. As the objective function is non-linear fractional, which isnot straightforward to handle, specialized solution methods are used. An exactalgorithm presented by Nikolova et al. (2006) is used to solve both versionsof the problem. What confidence level is required for a route to be optimaldepends on the risk profile of the decision maker. When solving the staticversion of the problem, the optimal route for the given threshold is identifiedprior to route execution, while the dynamic problem is solved using the exactalgorithm iteratively to decide which cargo to service next.
When solving the static version of the problem, a base set of 100 test instancesis generated and tested. The instances are generated based on realistic inputdata from Houston Ship Channel. We find that for less than 20% of theinstances, the optimal stochastic solution performs better than the optimaldeterministic. However, the improvements in threshold and confidence levelis less than 0.5% for all instances.
An evaluation of the applied approximation of the distribution of arc traveltimes shows that our model suggests less variance to be associated with theroutes than what is the real case. This means that the value of the stochasticsolution might be higher than what our results suggest. The results fromsolving the dynamic version of the problem support the findings from solvingthe static version of the problem.