Prioritizing Interrelated Road Projects Using Metaheuristics
Publication: Journal of Infrastructure Systems
Volume 22, Issue 2
Abstract
Projects are considered interrelated when their benefits or costs depend on which other projects are implemented. The timing of such projects may also complicate their analysis. Selection and scheduling of interrelated projects is a challenging optimization problem that has many applications in various fields, including economics, operations research, business, management, and transportation. The goal is to determine which projects should be selected and when they should be funded in order to minimize the total system cost over a planning horizon. Finding the optimal solution for such problems often requires extensive evaluation of possible solutions because of the complex nature and noisy surface of their solution space. This paper applies three metaheuristic algorithms including a genetic algorithm (GA), simulated annealing (SA), and Tabu search (TS) in seeking efficient and consistent solutions to the selection and scheduling problem. These approaches are applied to a special case of link capacity expansion projects to showcase their functionality and compare their performance. The paper’s main contributions are to (1) compare three metaheuristics for this problem in terms of solution quality, computation time, and consistency; (2) consider explicitly the supplier costs as well as user costs in the formulated objective function; and (3) enhance some simplifying assumptions from previous studies by recognizing that candidate projects may not remain economically justifiable throughout the analyzed period. It is found that a GA yields the most consistent solution with the least total cost while SA and TS approaches excel in terms of computation time.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research was partly funded by the Maryland State Highway Administration and the USDOT University Transportation Center Program through the National Center for Strategic Transportation Policies, Investments, and Decisions at the University of Maryland. The opinions in this paper do not necessarily reflect the views of the funding agencies. The authors are solely responsible for all statements in the paper.
References
Ahipasaoglu, D. S., Sun, P., and Todd, M. J. (2008). “Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids.” Optim. Method. Software, 23(1), 5–19.
Bagloee, S. A., and Tavana, M. (2012). “An efficient hybrid heuristic method for prioritising large transportation projects with interdependent activities.” Int. J. Logist. Syst. Manage., 11(1), 114–142.
Ben-Ameur, W. (2004). “Computing the initial temperature of simulated annealing.” Comput. Optim. Appl., 29(3), 369–385.
Bhattacharyya, R., Kumar, P., and Kar, S. (2011). “Fuzzy R&D portfolio selection of interdependent projects.” Comput. Math. Appl., 62(10), 3857–3870.
Bouleimen, K., and Lecocq, H. (2003). “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version.” Eur. J. Oper. Res., 149(2), 268–281.
Černý, V. (1985). “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm.” J. Optim. Theory Appl., 45(1), 41–51.
Chen, X., Zhu, Z., He, X., and Zhang, L. (2015). “Surrogate-based optimization for solving mixed integer network design problem.” Transp. Res. Rec, 15-4556, in press.
Devika, K., Jafarian, A., and Nourbakhsh, V. (2014). “Designing a sustainable closed-loop supply chain network based on triple bottom line approach: A comparison of metaheuristics hybridization techniques.” Eur. J. Oper. Res., 235(3), 594–615.
Disatnik, D. J., and Benninga, S. (2007). “Shrinking the covariance matrix.” J. Portfolio Manage., 33(4), 55–63.
Dueñas-Osorio, L., Craig, J. I., Goodno, B. J., and Bostrom, A. (2007). “Interdependent response of networked systems.” J. Infrastruct. Syst., 185–194.
Durango-Cohen, P. L., and Sarutipand, P. (2007). “Capturing interdependencies and heterogeneity in the management of multifacility transportation infrastructure systems.” J. Infrastruct. Syst., 115–123.
Frank, M., and Wolfe, P. (1956). “An algorithm for quadratic programming.” Nav. Res. Logist. Q., 3(1–2), 95–110.
Gen, M., and Cheng, R. (1997). Genetic algorithms and engineering design, Wiley, New York.
Glover, F. (1986). “Future paths for integer programming and links to artificial intelligence.” Comput. Oper. Res., 13(5), 533–549.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning, Addison Wesley, New York.
Jeon, K., Lee, J., Ukkusuri, S., and Waller, S. (2006). “Selectorecombinative genetic algorithm to relax computational complexity of discrete network design problem.” Transp. Res. Rec., 1964, 91–103.
Jong, J. C., and Schonfeld, P. (2001). “Genetic algorithm for selecting and scheduling interdependent projects.” J. Waterw. Port, Coastal, Ocean Eng., 45–52.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). “Optimization by simulated annealing.” Science, 220(4598), 671–680.
LeBlanc, L. J., Morlok, E. K., and Pierskalla, W. P. (1975). “An efficient approach to solving the road network equilibrium traffic assignment problem.” Transport. Res., 9(5), 309–318.
Li, Z., Roshandeh, A. M., Zhou, B., and Lee, S. H. (2013). “Optimal decision making of interdependent tollway capital investments incorporating risk and uncertainty.” J. Transp. Eng., 686–696.
Markowitz, H. (1952). “Portfolio selection.” J. Financ., 7(1), 77–79.
Michalewicz, Z. (1995). Genetic algorithms + data Structure = evolution programs, Springer, Berlin.
Mika, M., Waligóra, G., and Węglarz, J. (2005). “Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models.” Eur. J. Oper. Res., 164(3), 639–668.
Milatovic, M., and Badiru, A. B. (2004). “Applied mathematics modeling of intelligent mapping and scheduling of interdependent and multi-functional project resources.” Appl. Math. Comput., 149(3), 703–721.
Shayanfar, E., and Schonfeld, P. (2015). “Characteristics of the sioux falls test network.”, Univ. of Maryland, College Park, MD.
Sicilia, J. A., Quemada, C., Royo, B., and Escuín, D. (2015). “An optimization algorithm for solving the rich vehicle routing problem based on variable neighborhood search and Tabu search metaheuristics.” J. Comput. Appl. Math, in press.
Szimba, E., and Rothengatter, W. (2012). “Spending scarce funds more efficiently-including the pattern of interdependence in cost-benefit analysis.” J. Infrastruct. Syst., 242–251.
Tao, X., and Schonfeld, P. (2005). “Lagrangian relaxation heuristic for selecting interdependent transportation projects under cost uncertainty.” Transp. Res. Rec., 1931(1), 74–80.
Tao, X., and Schonfeld, P. (2007). “Island models for a stochastic problem of transportation project selection and scheduling.” Transp. Res. Rec., 2039, 16–23.
Van Vliet, D. (1987). “The Frank-Wolfe algorithm for equilibrium traffic assignment viewed as a variational inequality.” Trans. Res. B-Method, 21(1), 87–89.
Wang, S. L. (2001). “Simulation and optimization of interdependent waterway improvement projects.” Ph.D. dissertation, Univ. of Maryland, College Park, MD.
Wang, S. L., and Schonfeld, P. (2005). “Scheduling interdependent waterway projects through simulation and genetic optimization.” J. Waterw. Port, Coastal, Ocean Eng., 89–97.
Wang, S. L., and Schonfeld, P. (2008). “Scheduling of waterway projects with complex interrelations.” Transp. Res. Rec., 2062, 59–65.
Xu, T., Wei, H., and Hu, G. (2009). “Study on continuous network design problem using simulated annealing and genetic algorithm.” Expert. Syst. Appl., 36(2), 1322–1328.
Information & Authors
Information
Published In
Journal of Infrastructure Systems
Volume 22 • Issue 2 • June 2016
Copyright
© 2016 American Society of Civil Engineers.
History
Received: Dec 31, 2014
Accepted: Nov 4, 2015
Published online: Jan 25, 2016
Published in print: Jun 1, 2016
Discussion open until: Jun 25, 2016
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.