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.
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.:
- 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.
- repec:cdl:itsdav:qt95p934gz is not listed on IDEAS
- 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.
- 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.
- 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.
- 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.
- Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
- 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.
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.