Stochastic ship fleet routing with inventory limits
Abstract
This thesis describes a stochastic ship routing problem with inventory
management. The problem involves finding a set of least costs routes for
a fleet of ships transporting a single commodity when the demand for the
commodity is uncertain. Storage at consumption and supply ports is limited
and inventory levels are monitored in the model. Consumer demands are at
a constant rate within each time period in the deterministic problem, and in
the stochastic problem, the demand rate for a period is not known until the
beginning of that period. The demand situation in each time period can be
described by a scenario tree with corresponding probabilities.
Several possible solution approaches for solving the problem are studied in
the thesis. This problem can be formulated as a mixed integer programming
(MIP) model. However solving the problem this way is very time consuming
even for a deterministic problem with small problem size. In order to solve the
stochastic problem, we develop a decomposition formulation and solve it using
a Branch and Price framework. A master problem (set partitioning with extra
inventory constraints) is built, and the subproblems, one for each ship, involve
solving stochastic dynamic programming problems to generate columns for the
master problem. Each column corresponds to one possible tree of schedules
for one ship giving the schedule for the ship for all demand scenarios. In each
branch-and-bound node, the node problem is solved by iterating between the
master problem and the subproblems. Dual variables can be obtained solving
the master problem and are used in the subproblems to generate the most
promising columns for the master problem. Computational results are given
showing that medium sized problems can be solved successfully.
Several extensions to the original model are developed, including a variable
speed model, a diverting model, and a model which allows ships to do extra
tasks in return for a bonus. Possible solution approaches for solving the
variable speed and the diverting model are presented and computational
results are given.