Optimal Allocation of Protective Resources in Shortest-Path Networks

Paola Cappanera () and Maria Paola Scaparra ()
Additional contact information
Paola Cappanera: Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, 50139 Firenze, Italy
Maria Paola Scaparra: Kent Business School, University of Kent, Canterbury CT2 7PE, United Kingdom

Transportation Science, 2011, vol. 45, issue 1, 64-80

Abstract: This article introduces a game-theoretic approach for allocating protection resources among the components of a network so as to maximize its robustness to external disruptions. Specifically, we 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. A multilevel program is proposed to identify the set of components to harden so as to minimize the length of the shortest path between a supply node and a demand node after a worst-case disruption of some unprotected components. An implicit enumeration algorithm is then developed to solve the multilevel problem to optimality. The approach is streamlined by solving the lower-level interdiction problem heuristically at each node of an enumeration tree and by using some variable fixing rules to reduce the dimension of the lower-level problems. A thorough computational investigation demonstrates that the proposed solution method is able to identify optimal protection strategies for networks of significant size. The paper is concluded with a study of the sensitivity of the solution approach to variations of the problem parameters such as the level of disruption and protective resources and the distribution of the arc lengths and delays.

Keywords: network interdiction; multilevel programming; shortest path; resource allocation (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0340 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:45:y:2011:i:1:p:64-80

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().