Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
Approximate Dynamic Programming for a Class of Long-Horizon Maritime Inventory Routing Problems
Beteiligte:
Papageorgiou, Dimitri J.;
Cheon, Myun-Seok;
Nemhauser, George;
Sokol, Joel
Erschienen:
Institute for Operations Research and the Management Sciences (INFORMS), 2015
Erschienen in:
Transportation Science, 49 (2015) 4, Seite 870-885
Sprache:
Englisch
DOI:
10.1287/trsc.2014.0542
ISSN:
0041-1655;
1526-5447
Entstehung:
Anmerkungen:
Beschreibung:
<jats:p> 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. </jats:p>