On the Optimal Interdiction of Transportation Networks

Tianyun Zhang, Makan Fardad

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the optimal interdiction problem in transportation networks as a game in which an attacker acts as the player who goes first and, subject to budget constraints, fails nodes (partially or fully) at time zero so as to maximize the total travel time of the mass. A centralized network operator then acts as the player who goes second and, subject to the system's dynamics, routes the mass so as to minimize its total travel time. We prove that the attacker's best action is to find the most consequential nodes and employ his resources to fail them fully, so that the optimal attack is both sparse and binary. We then propose an algorithm to numerically solve the optimal interdiction problem, and demonstrate the utility of our approach through illustrative examples.

Original languageEnglish (US)
Title of host publication2020 American Control Conference, ACC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4701-4706
Number of pages6
ISBN (Electronic)9781538682661
DOIs
StatePublished - Jul 2020
Event2020 American Control Conference, ACC 2020 - Denver, United States
Duration: Jul 1 2020Jul 3 2020

Publication series

NameProceedings of the American Control Conference
Volume2020-July
ISSN (Print)0743-1619

Conference

Conference2020 American Control Conference, ACC 2020
CountryUnited States
CityDenver
Period7/1/207/3/20

Keywords

  • Cascading failures
  • flow networks
  • linear programming
  • network interdiction
  • optimization
  • sparsity
  • traffic networks

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'On the Optimal Interdiction of Transportation Networks'. Together they form a unique fingerprint.

Cite this