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, 1998. "The Impacts of Environmental Regulations on Industrial Activity: Evidence from the 1970 and 1977 Clean Air Act Amendments and the Census of Manufacturers," Working Papers 787, Princeton University, Department of Economics, Industrial Relations Section..
    9. 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.
    10. Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
    11. repec:cdl:itsdav:qt95p934gz is not listed on IDEAS
    12. 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.
    13. 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. Lucas Javaudin & Andrea Araldo & André de Palma, 2023. "Personalized Incentives with Constrained Regulator’s Budget," THEMA Working Papers 2023-15, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    2. 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.
    3. 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.
    4. 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.
    5. 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. Tibor Szkaliczki, 2025. "Solution Methods for the Multiple-Choice Knapsack Problem and Their Applications," Mathematics, MDPI, vol. 13(7), pages 1-35, March.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. LaPlue, Lawrence D., 2022. "Environmental consequences of natural gas wellhead pricing deregulation," Journal of Environmental Economics and Management, Elsevier, vol. 116(C).
    8. Daron Acemoglu & Amy Finkelstein, 2008. "Input and Technology Choices in Regulated Industries: Evidence from the Health Care Sector," Journal of Political Economy, University of Chicago Press, vol. 116(5), pages 837-880, October.
    9. McLaughlin, Patrick & Potts, Jason, 2019. "RegData: Australia," Working Papers 10062, George Mason University, Mercatus Center.
    10. Mengmeng Qiang & Hangyi Lai & Zhenxi Lyu, 2025. "Carbon Emissions Trading and Employment: Evidence from China," Sustainability, MDPI, vol. 17(4), pages 1-19, February.
    11. Jonathan M. Lee, 2015. "The Impact of Heterogeneous NOx Regulations on Distributed Electricity Generation in U.S. Manufacturing," Working Papers 15-12, Center for Economic Studies, U.S. Census Bureau.
    12. Jonathan Colmer & Ralf Martin & Mirabelle Muûls & Ulrich J. Wagner, 2020. "Does pricing carbon mitigate climate change? Firm-level evidence from the European Union emissions trading scheme," CEP Discussion Papers dp1728, Centre for Economic Performance, LSE.
    13. Cui, Jingbo & Lapan, Harvey E. & Moschini, GianCarlo, 2012. "Are exporters more environmentally friendly than non-exporters? Theory and evidence," ISU General Staff Papers 201210040700001076, Iowa State University, Department of Economics.
    14. Francesco Vona & Giovanni Marin & Davide Consoli, 2019. "Measures, drivers and effects of green employment: evidence from US local labor markets, 2006–2014," Journal of Economic Geography, Oxford University Press, vol. 19(5), pages 1021-1048.
    15. Copeland, Brian R., 2005. "Policy Endogeneity and the Effects of Trade on the Environment," Agricultural and Resource Economics Review, Cambridge University Press, vol. 34(1), pages 1-15, April.
    16. Wang, Huaxing & Li, Tianzi & Zhu, Junfan & Jian, Youting & Wang, Zeyu & Wang, Zengwen, 2023. "China's new environmental protection law: Implications for mineral resource policy, environmental precaution and green finance," Resources Policy, Elsevier, vol. 85(PB).
    17. Sun, Chuanwang & Tie, Ying & Yu, Lili, 2024. "How to achieve both environmental protection and firm performance improvement: Based on China's carbon emissions trading (CET) policy," Energy Economics, Elsevier, vol. 130(C).
    18. Fredriksson, Per G. & List, John A. & Millimet, Daniel L., 2003. "Bureaucratic corruption, environmental policy and inbound US FDI: theory and evidence," Journal of Public Economics, Elsevier, vol. 87(7-8), pages 1407-1430, August.
    19. Ross Levine & Chen Lin & Zigan Wang, 2018. "Pollution and Human Capital Migration: Evidence from Corporate Executives," NBER Working Papers 24389, National Bureau of Economic Research, Inc.

    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.