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


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.




Written: 8 April 2011


Working paper