Robust location of hidden interdictions on a shortest path network

N. Orkun Baycik and Kelly M. Sullivan

IISE Transactions, 2019, vol. 51, issue 12, 1332-1347

Abstract: We study a version of the shortest path network interdiction problem in which the follower seeks a path of minimum length on a network and the leader seeks to maximize the follower’s path length by interdicting arcs. We consider placement of interdictions that are not visible to the follower; however, we seek to locate interdictions in a manner that is robust against the possibility that some information about the interdictions becomes known to the follower. We formulate the problem as a bilevel program and derive some properties of the inner problem, which enables solving the problem optimally via a Benders decomposition approach. We derive supervalid inequalities to improve the performance of the algorithm and test the performance of the algorithm on randomly generated, varying-sized grid networks and acyclic networks. We apply our approach to investigate the tradeoffs between conservative (i.e., the follower discovers all interdiction locations) and risky (i.e., the follower discovers no interdiction locations) assumptions regarding the leader’s information advantage.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2019.1597316 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:51:y:2019:i:12:p:1332-1347

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2019.1597316

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().