Optimization Online


Approximate Dynamic Programming for a Class of Long-Horizon Maritime Inventory Routing Problems

Dimitri Papageorgiou (dimitri.j.papageorgiou***at***exxonmobil.com)
Myun-Seok Cheon (myun-seok.cheon***at***exxonmobil.com)
George Nemhauser (gnemhaus***at***isye.gatech.edu)
Joel Sokol (jsokol***at***isye.gatech.edu)

Abstract: We study a deterministic maritime inventory routing problem with a long planning horizon. For instances with many ports and many vessels, mixed-integer linear programming (MIP) solvers often require hours to produce good solutions even when the planning horizon is 90 or 120 periods. Building on the recent successes of approximate dynamic programming (ADP) for road-based applications within the transportation community, we develop an ADP procedure to quickly generate good solutions to these problems within minutes. Our algorithm operates by solving many small subproblems (one for each time period) and, in so doing, collecting information about how to produce better solutions. Our main contribution to the ADP community is an algorithm that solves MIP subproblems and uses separable piecewise linear continuous, but not necessarily concave or convex, value function approximations and requires no off-line training. Our algorithm is one of the first of its kind for maritime transportation problems and represents a significant departure from the traditional methods used. In particular, whereas virtually all existing methods are “MIP-centric,” i.e., they rely heavily on a solver to tackle a nontrivial MIP to generate a good or improving solution in a couple of minutes, our framework puts the effort on finding suitable value function approximations and places much less responsibility on the solver. Computational results illustrate that with a relatively simple framework, our ADP approach is able to generate good solutions to instances with many ports and vessels much faster than a commercial solver emphasizing feasibility and a popular local search procedure.

Keywords: approximate dynamic programming, deterministic inventory routing, maritime transportation, mixed-integer linear programming, time decomposition

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 ISyE, Technical Report, 2013

Download: [PDF]

Entry Submitted: 08/09/2013
Entry Accepted: 08/12/2013
Entry Last Modified: 04/06/2014

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