Multiple Choice Knapsack Problem: Example of planning choice in transportation
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.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- 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.
- repec:cdl:itsdav:qt95p934gz is not listed on IDEAS
- 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.
- 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.
- 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.
- 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.
- 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.
- 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,"
787, Princeton University, Department of Economics, Industrial Relations Section..
- 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.
- Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
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.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.