Decomposing inventory routing problems with approximate value functions. (English) Zbl 1202.90021
Summary: We present a time decomposition for inventory routing problems. The methodology is based on valuing inventory with a concave piecewise linear function and then combining solutions to single-period subproblems using dynamic programming techniques. Computational experiments show that the resulting value function accurately captures the inventory’s value, and solving the multiperiod problem as a sequence of single-period subproblems drastically decreases computational time without sacrificing solution quality.
References:
| [1] | Adelman, Price-directed replenishment of subsets: Methodology and its application to inventory routing, Manuf Serv Operat Manage 5 pp 348– (2003) |
| [2] | Adelman, A price-directed approach to stochastic inventory/routing, Operat Res 52 pp 499– (2004) · Zbl 1165.90302 |
| [3] | Bertsekas, Neuro-dynamic programming (1996) |
| [4] | Blair, The value function of an integer program, Math Program 23 pp 237– (1982) · Zbl 0482.90068 |
| [5] | Campbell, The inventory routing problem, Fleet management and logistics, chapter 4 pp 95– (1998) · doi:10.1007/978-1-4615-5755-5_4 |
| [6] | Campbell, A decomposition approach for the inventory-routing problem, Trans Sci 38 pp 488– (2004) |
| [7] | Christiansen, Decomposition of a combined inventory and time constrained ship routing problem, Trans Sci 33 pp 3– (1999) · Zbl 1002.90509 |
| [8] | Christiansen, A method for solving ship routing problems with inventory constraints, Ann Operat Res 81 pp 357– (1998) · Zbl 0906.90055 |
| [9] | Christiansen, Modelling path flows for a combined ship routing and inventory management problem, Ann Operat Res 82 pp 391– (1998) · Zbl 0911.90147 |
| [10] | J.-F. Cordeau G. Laporte M. W. P. Savelsbergh D. Vigo Vehicle routing Handbook in operations research and management science: transportation C. Barnhart G. Laporte Elsevier 2007 14 chapter 6 367 428 |
| [11] | Column Generation (2005) · Zbl 1084.90002 |
| [12] | Drexl, Lot sizing and scheduling-Survey and extensions, Eur J of Oper Res 99 pp 221– (1997) · Zbl 0923.90067 |
| [13] | F. G. Engineer Shortest path based column generation for integer programming, Ph.D. thesis 2009 |
| [14] | Hewitt, Combining exact and heuristic approaches for the capacitated fixed charge network flow problem, INFORMS J Comput 22 pp 314– (2010) · Zbl 1243.90031 |
| [15] | Klabjan, An infinite-dimensional linear programming algorithm for deterministic semi-markov decision processes on borel spaces, Math Operat Res 32 pp 528– (2007) · Zbl 1279.90111 |
| [16] | Kleywegt, The stochastic inventory routing problem with direct deliveries, Trans Sci 36 pp 94– (2002) · Zbl 1065.90508 |
| [17] | Kleywegt, Dynamic programming approximations for a stochastic inventory routing problem, Trans Sci 38 pp 42– (2004) |
| [18] | Longstaff, Valuing American options by simulation: a simple least-squares approach, Rev Financ Stud 14 pp 113– (2001) · Zbl 1386.91144 |
| [19] | Magnani, Convex piecewise-linear fitting, Optim Eng 10 pp 1– (2009) · Zbl 1273.65086 |
| [20] | McClain, Dynamics of exponential smoothing with trend and seasonal terms, Manage Sci 20 pp 1300– (1974) · Zbl 0304.62012 |
| [21] | S. Michel F. Vanderbeck 2008 http://hal.inria.fr/docs/00/33/90/37/PDF/techRepR2.pdf |
| [22] | Minkoff, A Markov decision model and decomposition heuristic for dynamic vehicle dispatching, Oper Res 41 pp 77– (1993) · Zbl 0771.90038 |
| [23] | Moin, Inventory routing problems: a logistical overview, J Oper Res Soc 58 pp 1185– (2007) · Zbl 1192.90012 |
| [24] | N. Nananukul Lot-sizing and inventory routing for a production-distribution supply chain 2008 |
| [25] | Nemhauser, Integer and combinatorial optimization (1999) |
| [26] | Pochet, Production planning by mixed integer programming (2006) · Zbl 1102.90039 |
| [27] | Powell, Approximate dynamic programming: Solving the curses of dimensionality (2007) · Zbl 1156.90021 |
| [28] | Savelsbergh, Inventory routing with continuous moves, Comput Oper Res 34 pp 1744– (2007) · Zbl 1159.90304 |
| [29] | Savelsbergh, An optimization algorithm for the inventory routing problem with continuous moves, Comput Oper Res 35 pp 2266– (2008) · Zbl 1179.90021 |
| [30] | Schenk, Intramarket optimization for express package carriers, Transp Sci 42 pp 530– (2008) |
| [31] | Schenk, Intra market optimization for express package carriers with station to station travel and proportional sorting, Comput Oper Res 37 pp 1749– (2010) · Zbl 1188.90039 |
| [32] | Topaloglu, An algorithm for approximating piecewise linear concave functions from sample gradients, Oper Res Lett 31 pp 66– (2003) · Zbl 1031.90024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
