Stochastic Optimization Model and Solution Algorithm for Highway Investment Decision Making under Budget Uncertainty
Publication: Journal of Transportation Engineering
Volume 135, Issue 6
Abstract
One of the key tasks in highway investment decision making is to conduct project selection. The existing optimization models for project selection concerning an entire highway system do not address the issue of budget uncertainty, limiting their ability to produce truly optimal results. This paper presents a stochastic optimization model that explicitly addresses budget uncertainty in highway investment decision making. The model is formulated as the stochastic multichoice multidimensional Knapsack problem with -stage budget recourses that facilitates the selection of a subset of candidate highway projects, proposed to address the needs of a highway system across a multiyear project selection and programming period, in the most cost-effective manner. An efficient solution algorithm with the computational complexity of is developed for the proposed model. A computational study is performed to compare the investment decision outcomes by applying the proposed model with and without budget uncertainty considerations. It is revealed that budget uncertainty can significantly affect the investment decision outcomes and the proposed model can generate robust results that will enhance highway investment decisions.
Get full access to this article
View all available purchase options and get full access to this article.
References
Aggarwal, V., Deo, N., and Sarkar, D. (1992). “The Knapsack problem with disjoint multiple-choice constraints.” Naval Res. Logistics Quart., 39, 213–227.
Akbar, M. M., Manning, E. G., Shoja, G. C., and Khan, S. (2001). “Heuristic solutions for the multiple-choice multi-dimension Knapsack problem.” Working Paper, Univ. of Victoria, Victoria B.C., Canada.
Armstrong, R. D., Kung, D. S., Sinha, P., and Zoltners, A. A. (1983). “A computational study of a multiple-choice Knapsack algorithm.” ACM Trans. Math. Softw., 9(2), 184–198.
Ben-Akiva, M., Humplick, F., Madanat, S. M., and Ramaswamy, R. (1991). “Latent performance approach to infrastructure management.” Transportation Research Record. 1311, Transportation Research Board, Washington, D.C., 188–195.
Birge, J. R., and Louveaux, F. (1997). Introduction to stochastic programming, Springer, New York.
Cesare, M. J., Santamaria, C., Turkstra, C. J., and Vanmarcke, E. (1994). “Risk-based bridge management: Optimization and inspection scheduling.” Can. J. Civ. Eng., 21(6), 897–902.
Chu, P. C., and Beasley, J. E. (1998). “A genetic algorithm for the multidimensional Knapsack problem.” J. Heuristics, 4, 63–86.
de la Garza, J. M., Drew, D. R., and Chasey, A. D. (1998). “Simulating highway infrastructure management polices.” J. Manage. Eng., 14(5), 64–72.
Dyer, M. E., Riha, W. O., and Walker, J. (1995). “A hybrid dynamic programming/branch-and-bound algorithm for the multiple-choice Knapsack problem.” J. Comput. Appl. Math., 58, 43–54.
Feighan, K. J., Shahin, M. Y., Sinha, K. C., and White, T. D. (1988). “An application of dynamic programming and other mathematical techniques to pavement management systems.” Transportation Research Record. 1200, Transportation Research Board, Washington, D.C., 90–98.
Federal Highway Administration (FHwA). (1987). “Bridge management systems.” Demonstration Project No. 71, U.S. Department of Transportation, Washington, D.C.
Federal Highway Administration (FHwA). (1991). Pavement management systems, U.S. Department of Transportation, Washington, D.C.
Freville, A., and Plateau, G. (1994). “An efficient preprocessing procedure for the multidimensional 0–1 Knapsack problem.” Discrete Appl. Math., 49, 189–212.
Friesz, T., and Fernandez, E. J. (1979). “A model of optimal transport maintenance with demand responsiveness.” Transp. Res., Part B: Methodol., 13(4), 317–339.
Geoffroy, D. N., and Shufon, J. J. (1992). “Network level pavement management in New York state: A goal-oriented approach.” Transportation Research Record. 1344, Transportation Research Board, Washington, D.C., 57–65.
Haas, R., Hudson, W. R., and Zaniewski, J. P. (1994). Modern pavement management, Krieger, Melbourne, Fla.
Harper, W. V., et al. (1990). “Stochastic optimization subsystem of a network-level bridge management system.” Transportation Research Record. 1268, Transportation Research Board, Washington, D.C., 68–74.
Isa Al-Subhi, K. M., Johnston, D. W., and Farid, F. (1989). “Optimizing system-level bridge maintenance, rehabilitation, and replacement decisions.” North Carolina State Univ., Raleigh, N.C.
Klamroth, K., and Wieck, M. M. (2001). “Dynamic programming approaches to the multiple criteria Knapsack problem.” Working Paper, Clemson Univ., Clemson, S.C.
Li, Z., and Sinha, K. C. (2004). “A methodology for multicriteria decision making in highway asset management.” Transportation Research Record. 1885, Transportation Research Board, Washington, D.C., 79–87.
Lorie, J. H., and Savage, L. J. (1955). “Three problems in rationing capital.” J. Business, XXVIII(4), 229–239.
Magazine, M. J., and Oguz, O. (1984). “A heuristic algorithm for the multidimensional zero-one Knapsack problem.” Eur. J. Oper. Res., 16, 319–326.
Martello, S., and Toth, P. (1990). Knapsack problems: Algorithms and computer implementations, Wiley, Chichester, U.K.
Neumann, L. A. (1997). “Methods for capital programming and project selection.” NCHRP Synthesis No. 243, National Academy Press, Washington, D.C.
Osorio, M. A., and Glover, F. (2001). “Logic cuts using surrogate constraint analysis in the multidimensional Knapsack problem.” Working Paper, Imperial College of Science, Technology and Medicine, London, and Univ. of Colorado at Boulder, Boulder, Colo.
Ouyang, Y., and Madanat, S. M. (2004). “Optimal scheduling of rehabilitation activities for multiple pavement facilities: Exact and approximation solutions.” Transp. Res., Part A: Policy Pract., 38(5), 347–365.
Ravirala, V., and Grivas, D. A. (1995). “Goal-programming methodology for integrating pavement and bridge programs.” J. Transp. Eng., 121(4), 345–351.
Salem, O., AbouRizk, S., and Ariaratnam, S. (2003). “Risk-based life-cycle costing of infrastructure rehabilitation and construction alternatives.” J. Infrastruct. Syst., 9(1), 6–15.
Sinha, K. C., and Fwa, T. F. (1988). “On the concept of total highway management.” Transportation Research Record. 1229, Transportation Research Board, Washington, D.C., 79–88.
Sinha, P., and Zoltners, A. A. (1979). “The multiple-choice Knapsack problem.” Oper. Res., 27(3), 503–515.
Teng, J. Y., and Tzeng, G. H. (1996). “A multiobjective programming approach for selecting non-independent transportation investment alternatives.” Transp. Res., Part B: Methodol., 30(4), 291–307.
Toyoda, Y. (1975). “A simplified algorithm for obtaining approximate solutions to zero-one programming problems.” Manage. Sci., 21, 1417–1427.
Volgenant, A., and Zoon, J. A. (1990). “An improved heuristic for multidimensional 0–1 Knapsack problems.” J. Oper. Res. Soc., 41(10), 963–970.
Weingartner, H. M. (1963). Mathematical programming and the analysis of capital budgeting problems, Prentice-Hall, Englewood Cliffs, N.J.
Weissmann, J., Harrison, R., Burns, N. H., and Hudson, W. R. (1990). “Selecting rehabilitation and replacement bridge projects, extending the life of bridges.” ASTM Spec. Tech. Publ., 1100, 3–17.
Zimmerman, K. A. (1995). “Pavement management methodologies to select projects and recommend preservation treatments.” NCHRP Synthesis No. 222, National Academy Press, Washington, D.C.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 135 • Issue 6 • June 2009
Pages: 371 - 379
Copyright
© 2009 ASCE.
History
Received: Dec 5, 2007
Accepted: Dec 8, 2008
Published online: May 15, 2009
Published in print: Jun 2009
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.