Optimization Online


Two-Stage Decomposition Algorithms for Single Product Maritime Inventory Routing

Dimitri Papageorgiou(dimitri.j.papageorgiou***at***exxonmobil.com)
Ahmet Keha(ahmet.b.keha***at***exxonmobil.com)
George Nemhauser(gnemhaus***at***isye.gatech.edu)
Joel Sokol(jsokol***at***isye.gatech.edu)

Abstract: We present two decomposition algorithms for single product deep-sea maritime inventory routing problems (MIRPs) that possess a core substructure common in many real-world applications. The problem involves routing vessels, each belonging to a particular vessel class, between loading and discharging ports, each belonging to a particular region. Our algorithms iteratively solve a MIRP by zooming out and then zooming in on the problem. Specifically, in the “zoomed out” phase, we solve a first-stage master problem in which aggregate information about regions and vessel classes is used to route vessels between regions, while only implicitly considering inventory and capacity requirements, berth limits, and other side constraints. In the “zoomed in” phase, we solve a series of second-stage subproblems, one for each region, in which individual vessels are routed through each region and load and discharge quantities are determined. Computational experience shows that an integrated approach that combines these two algorithms is vastly superior to solving the problem directly with a commercial mixed-integer programming solver.

Keywords: aggregation, decomposition, deterministic inventory routing, lot-sizing, maritime transportation, mixed-integer linear programming

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Applications -- OR and Management Sciences (Supply Chain Management )

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Georgia Institute of Technology, September 2013.

Download: [PDF]

Entry Submitted: 09/21/2013
Entry Accepted: 09/22/2013
Entry Last Modified: 09/21/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society