Current Science

Open Access Open Access  Restricted Access Subscription Access

Identifying Critical Links on Disruption-Prone Road Networks:An Approach that Obviates Scenario Enumeration


Affiliations
1 Department of Civil Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400 076, India
2 Department of Civil Engineering, Indian Institute of Technology Palakkad, Palakkad 678 557, India
 

Road networks are susceptible to disruptions. Since disruptions on certain roads have graver impacts, critical link identification is vital in disruption preparedness. To identify critical links, most approaches systematically inject disruptions and evaluate the ensuing after-effects. Since degradation patterns are uncertain, such iterative approaches either presume knowledge of disruption patterns or try numerous patterns but soon escalate to computational impracticality on real-life road networks. This study obviates both, using a novel approach which measures the contribution of each link to a predefined operational limit on the network. It generates a criticality hierarchy on real-life networks, while on hypothetical symmetric networks it rightly identifies all links as critical.

Keywords

Critical Links, Disruptions, Minimax Optimization, Road Networks, Scenario Enumeration.
User
Notifications
Font Size

  • Duke, C. B. et al., Network Science: Report from the Committee on Network Science for Future Army Applications, The National Academies Press, Washington, DC, 2007.

  • Newman, M. E., The structure and function of complex networks. SIAM Rev., 2003, 45, 167–256.

  • Nagurney, A. and Qiang, Q., Fragile networks: identifying vulnerabilities and synergies in an uncertain age. Int. Trans. Oper. Res., 2012, 19, 123–160.

  • Callaway, D. S., Newman, M. E., Strogatz, S. H. and Watts, D. J., Network robustness and fragility: percolation on random graphs. Phys. Rev. Lett., 2000, 85, 5468.

  • Balijepalli, C. and Oppong, O., Measuring vulnerability of road network considering the extent of serviceability of critical road links in urban areas. J. Transp. Geogr., 2014, 39, 145–155.

  • Hines, P., Cotilla-Sanchez, E. and Blumsack, S., Do topological models provide good information about electricity infrastructure vulnerability? Chaos: Interdiscip. J. Nonlinear Sci., 2010, 20, 033122.

  • Barabási, A. L., Linked: How Everything is Connected to Everything Else and What it Means for Business, Science, and Everyday life, Basic Books, New York, USA, 2014.

  • Scott, D. M., Novak, D. C., Aultman-Hall, L. and Guo, F., Network robustness index: a new method for identifying critical links and evaluating the performance of transportation networks. J. Transp. Geogr., 2006, 14, 215–227.

  • Sullivan, J. L., Novak, D. C., Aultman-Hall, L. and Scott, D. M., Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links: a linkbased capacity-reduction approach. Transp. Res. Part A, 2010, 44, 323–336.

  • Cats, O. and Jenelius, E., Planning for the unexpected: the value of reserve capacity for public transport network robustness. Transp. Res. Part A, 2015, 81, 47–61.

  • Taylor, M. A. and D’Este, G. M., Transport network vulnerability: a method for diagnosis of critical locations in transport infrastructure systems. In Critical Infrastructure – Reliability and Vulnerability (eds Murray, A. T. and Grubesic, T.), Springer, Berlin, Germany, 2007, pp. 9–30.

  • Nagurney, A. and Qiang, Q., A network efficiency measure with application to critical infrastructure networks. J. Global Optim., 2008, 40, 261–275.

  • Nagurney, A. and Qiang, Q., A transportation network efficiency measure that captures flows, behavior, and costs with applications to network component importance identification and vulnerability. In Proceedings of the POMS 18th Annual Conference, Dallas, Texas, USA, 2007.

  • Rodríguez-Núñez, E. and García-Palomares, J. C., Measuring the vulnerability of public transport networks. J. Transp. Geogr., 2014, 35, 50–63.

  • Halder, A. K., The method of competing links. Transp. Sci., 1970, 4, 36–51.

  • Sohn, J., Evaluating the significance of highway network links under the flood damage: an accessibility approach. Transp. Res. Part A, 2006, 40, 491–506.

  • Chen, B. Y., Lam, W. H., Sumalee, A., Li, Q. and Li, Z. C., Vulnerability analysis for large-scale and congested road networks with demand uncertainty. Transp. Res. Part A, 2012, 46, 501– 516.

  • Knoop, V. L., Snelder, M., van Zuylen, H. J. and Hoogendoorn, S. P., Link-level vulnerability indicators for real-world networks. Transp. Res. Part A, 2012, 46, 843–854.

  • Murray-Tuite, P. M. and Mahmassani, H. S., Methodology for determining vulnerable links in a transportation network. Transp. Res. Rec., 2004, 1882, 88–96.

  • Bell, M. G., Kanturska, U., Schmöcker, J. D. and Fonzone, A., Attacker–defender models and road network vulnerability. Philos. Trans. R. Soc. London, Ser. A, 2008, 366, 1893–1906.

  • Bhavathrathan, B. K. and Patil, G. R., Capacity uncertainty on urban road networks: A critical state and its applicability in resilience quantification. Comput. Environ. Urban Syst., 2015, 54, 108–118.

  • Bhavathrathan, B. K. and Patil, G. R., Quantifying resilience using a unique critical cost on road networks subject to recurring capacity disruptions. Transportmetrica A: Transp. Sci., 2015, 11, 836–855.

  • Patil, G. R. and Bhavathrathan, B. K., Effect of traffic demand variation on road network resilience. Adv. Complex Syst., 2016, 19, 1650003.

  • Liberatore, F., Scaparra, M. P. and Daskin, M. S., Analysis of facility protection strategies against an uncertain number of attacks: The stochastic R-interdiction median problem with fortification. Comp. Oper. Res., 2011, 38, 357–366.

  • Zhuang, J. and Bier, V. M., Balancing terrorism and natural disasters – defensive strategy with endogenous attacker effort. Oper. Res., 2007, 55, 976–991.

  • Cappanera, P. and Scaparra, M. P., Optimal allocation of protective resources in shortest-path networks. Transp. Sci., 2011, 45, 64–80.

  • Fan, K., Minimax theorems. Proc. Natl. Acad. Sci. USA, 1953, 39, 42–47.

  • Parthasarathy, T. and Raghavan, T. E. S., Some Topics in TwoPerson Games, Elsevier Publishing Company, New York, 1971.

  • Brown, G. W., Iterative solution of games by fictitious play. Acta Anal. Prod. Alloc., 1951, 13, 374–376.

  • Robinson, J., An iterative method of solving a game. Ann. Math., 1951, 54, 296–301.

  • Sheffi, Y., Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Models, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1985.

  • Fishman, G. S., Discrete-Event Simulation: Modeling, Programming and Analysis, Springer Science & Business Media, New York, 2013.

  • Bhavathrathan, B. K. and Patil, G. R., Algorithm to compute urban road network resilience. Transp. Res. Rec., 2018, 2672, 104–115.

  • Fudenberg, D. and Levine, D., The Theory of Learning in Games, The MIT Press, Cambridge, MA, USA, 1998.

  • McMahan, H. B. and Gordony, G. J., A fast bundle-based anytime algorithm for poker and other convex games. In Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, San Juan, Puerto Rico, 2007.

  • Harker, P. T. and Friesz, T. L., Bounding the solution of the continuous equilibrium network design problem. In Papers Presented during the Ninth International Symposium on Transportation and Traffic Theory, Delft, The Netherlands, 1984.

  • Nguyen, S. and Dupuis, C., An efficient method for computing traffic equilibria in networks with asymmetric transportation costs. Transp. Sci., 1984, 18, 185–202.


Abstract Views: 361

PDF Views: 105




  • Identifying Critical Links on Disruption-Prone Road Networks:An Approach that Obviates Scenario Enumeration

Abstract Views: 361  |  PDF Views: 105

Authors

Gopal R. Patil
Department of Civil Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400 076, India
B. K. Bhavathrathan
Department of Civil Engineering, Indian Institute of Technology Palakkad, Palakkad 678 557, India

Abstract


Road networks are susceptible to disruptions. Since disruptions on certain roads have graver impacts, critical link identification is vital in disruption preparedness. To identify critical links, most approaches systematically inject disruptions and evaluate the ensuing after-effects. Since degradation patterns are uncertain, such iterative approaches either presume knowledge of disruption patterns or try numerous patterns but soon escalate to computational impracticality on real-life road networks. This study obviates both, using a novel approach which measures the contribution of each link to a predefined operational limit on the network. It generates a criticality hierarchy on real-life networks, while on hypothetical symmetric networks it rightly identifies all links as critical.

Keywords


Critical Links, Disruptions, Minimax Optimization, Road Networks, Scenario Enumeration.

References





DOI: https://doi.org/10.18520/cs%2Fv118%2Fi3%2F428-438