IDEAS home Printed from https://ideas.repec.org/a/eee/epplan/v33y2010i2p128-137.html
   My bibliography  Save this article

Multiple Choice Knapsack Problem: Example of planning choice in transportation

Author

Listed:
  • Zhong, Tao
  • Young, Rhonda

Abstract

Transportation programming, a process of selecting projects for funding given budget and other constraints, is becoming more complex as a result of new federal laws, local planning regulations, and increased public involvement. This article describes the use of an integer programming tool, Multiple Choice Knapsack Problem (MCKP), to provide optimal solutions to transportation programming problems in cases where alternative versions of projects are under consideration. In this paper, optimization methods for use in the transportation programming process are compared and then the process of building and solving the optimization problems is discussed. The concepts about the use of MCKP are presented and a real-world transportation programming example at various budget levels is provided. This article illustrates how the use of MCKP addresses the modern complexities and provides timely solutions in transportation programming practice. While the article uses transportation programming as a case study, MCKP can be useful in other fields where a similar decision among a subset of the alternatives is required.

Suggested Citation

  • Zhong, Tao & Young, Rhonda, 2010. "Multiple Choice Knapsack Problem: Example of planning choice in transportation," Evaluation and Program Planning, Elsevier, vol. 33(2), pages 128-137, May.
    • Handle: RePEc:eee:epplan:v:33:y:2010:i:2:p:128-137
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0149-7189(09)00041-X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dudzinski, Krzysztof & Walukiewicz, Stanislaw, 1987. "Exact methods for the knapsack problem and its generalizations," European Journal of Operational Research, Elsevier, vol. 28(1), pages 3-21, January.
    2. John D. C. Little, 1970. "Models and Managers: The Concept of a Decision Calculus," Management Science, INFORMS, vol. 16(8), pages 466-485, April.
    3. Claus Rinner & Jacek Malczewski, 2002. "Web-enabled spatial decision analysis using Ordered Weighted Averaging (OWA)," Journal of Geographical Systems, Springer, vol. 4(4), pages 385-403, December.
    4. Moreb, Ahmad A., 1996. "Linear programming model for finding optimal roadway grades that minimize earthwork cost," European Journal of Operational Research, Elsevier, vol. 93(1), pages 148-154, August.
    5. Prabhakant Sinha & Andris A. Zoltners, 1979. "The Multiple-Choice Knapsack Problem," Operations Research, INFORMS, vol. 27(3), pages 503-515, June.
    6. Nauss, Robert M., 1978. "The 0-1 knapsack problem with multiple choice constraints," European Journal of Operational Research, Elsevier, vol. 2(2), pages 125-131, March.
    7. Ben-Ayed, Omar & Boyce, David E. & Blair, Charles E., 1988. "A general bilevel linear programming formulation of the network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 22(4), pages 311-318, August.
    8. Michael Greenstone, 2002. "The Impacts of Environmental Regulations on Industrial Activity: Evidence from the 1970 and 1977 Clean Air Act Amendments and the Census of Manufactures," Journal of Political Economy, University of Chicago Press, vol. 110(6), pages 1175-1219, December.
    9. Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
    10. repec:cdl:itsdav:qt95p934gz is not listed on IDEAS
    11. Pisinger, David, 1995. "A minimal algorithm for the multiple-choice knapsack problem," European Journal of Operational Research, Elsevier, vol. 83(2), pages 394-410, June.
    12. Jintrawet, Attachai, 1995. "A decision support system for rapid assessment of lowland rice-based cropping alternatives in Thailand," Agricultural Systems, Elsevier, vol. 47(2), pages 245-258.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mancini, Simona & Triki, Chefi & Piya, Sujan, 2022. "Optimal selection of touristic packages based on user preferences during sports mega-events," European Journal of Operational Research, Elsevier, vol. 302(3), pages 819-830.
    2. Ewa M. Bednarczuk & Janusz Miroforidis & Przemysław Pyzel, 2018. "A multi-criteria approach to approximate solution of multiple-choice knapsack problem," Computational Optimization and Applications, Springer, vol. 70(3), pages 889-910, July.
    3. Lucas Javaudin & Andrea Araldo & André de Palma, 2021. "Large-Scale Allocation of Personalized Incentives," THEMA Working Papers 2021-08, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    4. Shen-Tsu Wang, 2018. "An Analysis of the Optimal Customer Clusters Using Dynamic Multi-Objective Decision," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 17(02), pages 547-582, March.

    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.
    1. Drexl, Andreas & Jørnsten, Kurt, 2007. "Pricing the multiple-choice nested knapsack problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 626, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    2. Ewa M. Bednarczuk & Janusz Miroforidis & Przemysław Pyzel, 2018. "A multi-criteria approach to approximate solution of multiple-choice knapsack problem," Computational Optimization and Applications, Springer, vol. 70(3), pages 889-910, July.
    3. Boysen, Nils & Fliedner, Malte, 2008. "A versatile algorithm for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 184(1), pages 39-56, January.
    4. Zhu, Xiaoyan & Wilhelm, Wilbert E., 2007. "Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context," European Journal of Operational Research, Elsevier, vol. 183(2), pages 564-577, December.
    5. Abdelkader Sbihi, 2007. "A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 13(4), pages 337-351, May.
    6. Degraeve, Z. & Jans, R.F., 2003. "Improved Lower Bounds For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-026-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    7. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Post-Print halshs-03322716, HAL.
    8. Andris A. Zoltners & Prabhakant Sinha, 2005. "The 2004 ISMS Practice Prize Winner—Sales Territory Design: Thirty Years of Modeling and Implementation," Marketing Science, INFORMS, vol. 24(3), pages 313-331, September.
    9. Yuji Nakagawa & Ross J. W. James & César Rego & Chanaka Edirisinghe, 2014. "Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models," Management Science, INFORMS, vol. 60(3), pages 695-707, March.
    10. Tue R. L. Christensen & Kim Allan Andersen & Andreas Klose, 2013. "Solving the Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem by Dynamic Programming," Transportation Science, INFORMS, vol. 47(3), pages 428-438, August.
    11. Edward Y H Lin & Chung-Min Wu, 2004. "The multiple-choice multi-period knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 187-197, February.
    12. Dauzère-Pérès, Stéphane & Hassoun, Michael, 2020. "On the importance of variability when managing metrology capacity," European Journal of Operational Research, Elsevier, vol. 282(1), pages 267-276.
    13. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-03322716, HAL.
    14. Johnston, Robert E. & Khan, Lutfar R., 1995. "Bounds for nested knapsack problems," European Journal of Operational Research, Elsevier, vol. 81(1), pages 154-165, February.
    15. Gasparini, Gaia & Brunelli, Matteo & Chiriac, Marius Dan, 2022. "Multi-period portfolio decision analysis: A case study in the infrastructure management sector," Operations Research Perspectives, Elsevier, vol. 9(C).
    16. Sung, C. S. & Cho, Y. K., 2000. "Reliability optimization of a series system with multiple-choice and budget constraints," European Journal of Operational Research, Elsevier, vol. 127(1), pages 159-171, November.
    17. Wishon, Christopher & Villalobos, J. Rene, 2016. "Robust efficiency measures for linear knapsack problem variants," European Journal of Operational Research, Elsevier, vol. 254(2), pages 398-409.
    18. Coniglio, Stefano & Furini, Fabio & San Segundo, Pablo, 2021. "A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts," European Journal of Operational Research, Elsevier, vol. 289(2), pages 435-455.
    19. Maxime C. Cohen & Swati Gupta & Jeremy J. Kalas & Georgia Perakis, 2020. "An Efficient Algorithm for Dynamic Pricing Using a Graphical Representation," Production and Operations Management, Production and Operations Management Society, vol. 29(10), pages 2326-2349, October.
    20. Endre Boros & Noam Goldberg & Paul Kantor & Jonathan Word, 2011. "Optimal sequential inspection policies," Annals of Operations Research, Springer, vol. 187(1), pages 89-119, July.

    Corrections

    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:eee:epplan:v:33:y:2010:i:2:p:128-137. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/evalprogplan .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.