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

Dimitri J. Papageorgiou (), Myun-Seok Cheon (), George Nemhauser () and Joel Sokol ()
Additional contact information
Dimitri J. Papageorgiou: Corporate Strategic Research, ExxonMobil Research and Engineering Company, Annandale, New Jersey 08801
Myun-Seok Cheon: Corporate Strategic Research, ExxonMobil Research and Engineering Company, Annandale, New Jersey 08801
George Nemhauser: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Joel Sokol: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Transportation Science, 2015, vol. 49, issue 4, 870-885

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 generate good solutions to these problems within minutes. Our algorithm operates by solving many small subproblems (one for each time period) and by 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 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0542 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:49:y:2015:i:4:p:870-885

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().