Average-Case Performance of Rollout Algorithms for Knapsack Problems
Author
Abstract
Suggested Citation
DOI: 10.1007/s10957-014-0603-x
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Luca Bertazzi, 2012. "Minimum and Worst-Case Performance Ratios of Rollout Algorithms," Journal of Optimization Theory and Applications, Springer, vol. 152(2), pages 378-393, February.
- Gennady Diubin & Alexander Korbut, 2003. "The average behaviour of greedy algorithms for the knapsack problem: General distributions," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 57(3), pages 449-479, August.
- Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- del Castillo, Enrique & Beretta, Alessia & Semeraro, Quirico, 2017. "Optimal setup of a multihead weighing machine," European Journal of Operational Research, Elsevier, vol. 259(1), pages 384-393.
- Goodson, Justin C. & Thomas, Barrett W. & Ohlmann, Jeffrey W., 2017. "A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs," European Journal of Operational Research, Elsevier, vol. 258(1), pages 216-229.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Bertazzi, Luca & Bosco, Adamo & Laganà, Demetrio, 2015. "Managing stochastic demand in an Inventory Routing Problem with transportation procurement," Omega, Elsevier, vol. 56(C), pages 112-121.
- Goodson, Justin C. & Thomas, Barrett W. & Ohlmann, Jeffrey W., 2017. "A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs," European Journal of Operational Research, Elsevier, vol. 258(1), pages 216-229.
- Bertazzi, Luca & Secomandi, Nicola, 2018. "Faster rollout search for the vehicle routing problem with stochastic demands and restocking," European Journal of Operational Research, Elsevier, vol. 270(2), pages 487-497.
- François V. Louveaux & Juan-José Salazar-González, 2018. "Exact Approach for the Vehicle Routing Problem with Stochastic Demands and Preventive Returns," Service Science, INFORMS, vol. 52(6), pages 1463-1478, December.
- Jiarui Han & Tze Lai & Viktor Spivakovsky, 2006. "Approximate Policy Optimization and Adaptive Control in Regression Models," Computational Economics, Springer;Society for Computational Economics, vol. 27(4), pages 433-452, June.
- Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
- Hugo P. Simão & Jeff Day & Abraham P. George & Ted Gifford & John Nienow & Warren B. Powell, 2009. "An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application," Transportation Science, INFORMS, vol. 43(2), pages 178-197, May.
- Li, Haitao & Womer, Norman K., 2015. "Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming," European Journal of Operational Research, Elsevier, vol. 246(1), pages 20-33.
- Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2021. "A Multi-Depot Vehicle Routing Problem with Stochastic Road Capacity and Reduced Two-Stage Stochastic Integer Linear Programming Models for Rollout Algorithm," Mathematics, MDPI, vol. 9(13), pages 1-44, July.
- Subramanyam, Anirudh & Wang, Akang & Gounaris, Chrysanthos E., 2018. "A scenario decomposition algorithm for strategic time window assignment vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 296-317.
- Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
- Karels, Vincent C.G. & Rei, Walter & Veelenturf, Lucas P. & Van Woensel, Tom, 2024. "A vehicle routing problem with multiple service agreements," European Journal of Operational Research, Elsevier, vol. 313(1), pages 129-145.
- Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
- Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
- del Castillo, Enrique & Beretta, Alessia & Semeraro, Quirico, 2017. "Optimal setup of a multihead weighing machine," European Journal of Operational Research, Elsevier, vol. 259(1), pages 384-393.
- Alan L. Erera & Juan C. Morales & Martin Savelsbergh, 2010. "The Vehicle Routing Problem with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 44(4), pages 474-492, November.
- Briseida Sarasola & Karl Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
- Bosse, Alexander & Ulmer, Marlin W. & Manni, Emanuele & Mattfeld, Dirk C., 2023. "Dynamic priority rules for combining on-demand passenger transportation and transportation of goods," European Journal of Operational Research, Elsevier, vol. 309(1), pages 399-408.
- Sayarshad, Hamid R. & Gao, H. Oliver, 2018. "A non-myopic dynamic inventory routing and pricing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 83-98.
- Joseph Y. J. Chow & Hamid R. Sayarshad, 2016. "Reference Policies for Non-myopic Sequential Network Design and Timing Problems," Networks and Spatial Economics, Springer, vol. 16(4), pages 1183-1209, December.
More about this item
Keywords
Rollout algorithms; Lookahead; Knapsack problems; Approximate dynamic programming;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:165:y:2015:i:3:d:10.1007_s10957-014-0603-x. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.