A Branch-and-Price Approach for a Ship Routing Problem with Multiple Products and Inventory Constraints
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.
|Keywords||branch-and-price, column generation, inventory constraints, multiple-products, set-partitioning formulation, ship routing|
|Publisher||Erasmus School of Economics (ESE)|
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 (ESE). Retrieved from http://hdl.handle.net/1765/18255