Optimal Allocation of Protective Resources in Shortest-Path Networks

A game-theoretic approach for allocating protection resources among the components of a network so as to maximize its robustness to external disruptions is introduced in this article. The authors specifically consider shortest-path networks where disruptions may result in traffic flow delays through the affected components or even in the complete loss of some elements. The authors propose a multilevel program to identify the set of components to harden so as to minimize, after a worst-case disruption of some unprotected components, the length of the shortest path between a supply node and a demand node. To solve the multilevel problem to optimality, an implicit enumeration algorithm is then developed. The approach is streamlined by solving the lower-level interdiction problem heuristically at each enumeration tree node and by using some variable fixing rules to reduce lower-level problem dimension. A thorough computational investigation demonstrates that the proposed solution method is able to identify optimal protection strategies for significantly sized networks. The paper is concluded with a study of solution approach sensitivity to variations of the problem parameters such as the level of disruption and protective resources and the distribution of the arc lengths and delays.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Authors:
  • Cappanera, Paola
  • Scaparra, Maria Paola
• Publication Date: 2011-2

Language

• English

Media Info

• Media Type: Print
• Features: Bibliography; Figures; Tables;
• Pagination: pp 64-80
• Serial:
  • Transportation Science
  • Volume: 45
  • Issue Number: 1
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Game theory; Networks; Optimization; Resource allocation; Shortest path algorithms
• Uncontrolled Terms: Implicit enumeration algorithm; Multilevel networks; Sensitivity parameters; Supply and demand; Traffic network disruption
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; I70: Traffic and Transport;

Filing Info

• Accession Number: 01333387
• Record Type: Publication
• Files: TRIS
• Created Date: Mar 21 2011 2:13PM