### Technical Report ERGO 11-022

#### Solving stochastic ship fleet routing problems with inventory management using branch and price

*Ken I.M. McKinnon and Yu Yu*

##### Abstract:

This paper describes a stochastic ship routing problem with inventory
management. The problem involves finding a set of least cost routes for a
fleet of ships transporting a single commodity when the demand for the
commodity is uncertain. Storage at supply and consumption 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.

A decomposition formulation is given and it is solved using a Branch and Price
framework. A master problem (set partitioning with extra inventory constraints)
is built, and the subproblems, one for each ship, are solved by stochastic
dynamic programming and yeild the columns for the master problem. Each column
corresponds to one possible tree of actions for one ship giving its schedule
loading/unloading quantities for all demand scenarios. Computational results
are given showing that medium sized problems can be solved successfully.

##### Download:

ERGO-11-022.pdf

##### History:

Written: 8 April 2011

##### Status:

Working paper