| dc.description.abstract | Chemical tankers spend a substantial amount of time in port as the development
of port infrastructure has not followed the fast paced increase in the
world fleet. The resulting traffic at terminals causes ships to wait for a long
time before a terminal is ready to accommodate it. A large amount of uncertainty
is associated with the waiting times, which complicates the planning of
port operations.
The aim of the thesis is to investigate the benefits of including uncertainty in
the in-port routing problem of a chemical tanker. The chemical tanker has
to pick up and deliver a given number of cargoes located at different terminals
while complying with capacity and draft limit constraints. The waiting
times at the terminals are stochastic, which results in stochastic travel times
between terminals. The problem studied in this thesis is a stochastic pickup
and delivery problem. The problem is dynamic by nature, and both a static
and a dynamic version of the problem are solved. A review of deterministic
and stochastic routing problems resembling the pickup and delivery problem
is presented. To our knowledge, few or none have studied the pickup and delivery
problem where travel times are stochastic. Our thesis contributes to the
literature by studying the pickup and delivery problem with uncertain travel
times, subject to constraining draft limits. In addition, due to the particularly
narrow port channel in the case port, we consider the ship's movement as
movement along a straight line. This gives a unique relation between stochastic
waiting times at terminals and travel times between terminals. As far as
we know, this has not been studied before, and the unique conditions and
aspects 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 the
stochastic waiting time at the destination terminal are correlated. The distribution
of the arc travel times are assumed normally distributed, and approximations
are 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 a
given threshold. As the objective function is non-linear fractional, which is
not straightforward to handle, specialized solution methods are used. An exact
algorithm presented by Nikolova et al. (2006) is used to solve both versions
of the problem. What confidence level is required for a route to be optimal
depends on the risk profile of the decision maker. When solving the static
version of the problem, the optimal route for the given threshold is identified
prior to route execution, while the dynamic problem is solved using the exact
algorithm iteratively to decide which cargo to service next.
When solving the static version of the problem, a base set of 100 test instances
is generated and tested. The instances are generated based on realistic input
data from Houston Ship Channel. We find that for less than 20% of the
instances, the optimal stochastic solution performs better than the optimal
deterministic. However, the improvements in threshold and confidence level
is less than 0.5% for all instances.
An evaluation of the applied approximation of the distribution of arc travel
times shows that our model suggests less variance to be associated with the
routes than what is the real case. This means that the value of the stochastic
solution might be higher than what our results suggest. The results from
solving the dynamic version of the problem support the findings from solving
the static version of the problem. | |
