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.

branch-and-price, column generation, inventory constraints, multiple-products, set-partitioning formulation, ship routing
Erasmus School of Economics
Econometric Institute Research Papers
Report / Econometric Institute, Erasmus University Rotterdam
Erasmus School of Economics

de Mare, R, Spliet, R, & Huisman, D. (2010). A Branch-and-Price Approach for a Ship Routing Problem with Multiple Products and Inventory Constraints (No. EI 2010-05). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–18). Erasmus School of Economics. Retrieved from