A Branch-and-Price Approach for a Ship Routing Problem with Multiple Products and Inventory Constraints
2010-02-23
Research Paper
| Related Files |
|---|
View PDF Version
(ei201005.pdf, 0.2MB) |
In the oil industry, different oil components are blended in a refinery to fuel products. These products are transported to different harbors by ship. Due to the limited storage capacity at the harbors and the undesirability of a stock-out, inventory levels at the harbors have to be taken into account during the construction of the ship routes. In this paper, we give a detailed description of this problem, which we call the ship routing problem with multiple products and inventory constraints. Furthermore, we formulate this problem as a generalized set-covering problem, and we present a Branch-and-Price algorithm to solve it. The pricing problems have a very complex nature. We discuss a dynamic programming algorithm to solve them to optimality.
- column generation
- branch-and-price
- inventory constraints
- multiple-products
- set-partitioning formulation
- ship routing
- compartment
- harbor
- arrival
- grade
- problem
- inventory
- quantity
- harbor-grade
- harbor i
- constraint
- arrival m
- sequence
- service
- compartment c
- inventory level
- grade g
- network
- level
- inventory constraints
- subproblem
