Skip to main content
Kent Academic Repository

Optimal allocation of protective resources in shortest path networks

Cappanera, Paola, Scaparra, Maria Paola (2011) Optimal allocation of protective resources in shortest path networks. Transportation Science, 45 (1). pp. 64-80. ISSN 0041-1655. (doi:10.1287/trsc.1100.0340) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:27441)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://dx.doi.org/10.1287/trsc.1100.0340

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 in the complete loss of some elements. A multi-level 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 multi-level 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.

Item Type: Article
DOI/Identification number: 10.1287/trsc.1100.0340
Subjects: Q Science
H Social Sciences > HD Industries. Land use. Labor > HD29 Operational Research - Applications
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Funders: Engineering and Physical Sciences Research Council (https://ror.org/0439y7842)
Depositing User: Paola Scaparra
Date Deposited: 29 Jun 2011 16:33 UTC
Last Modified: 19 Sep 2023 15:04 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/27441 (The current URI for this page, for reference purposes)

University of Kent Author Information

Scaparra, Maria Paola.

Creator's ORCID: https://orcid.org/0000-0002-2725-5439
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.