TY - JOUR

T1 - Network interdiction with asymmetric cost uncertainty

AU - Nguyen, Di H.

AU - Smith, J. Cole

N1 - Funding Information:
The authors gratefully acknowledge the comments of Editor Rebennack and four anonymous referees, whose remarks greatly helped us improve the exposition of this study.
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2022/2/16

Y1 - 2022/2/16

N2 - We study a shortest-path interdiction problem in which the interdictor acts first to lengthen a subset of arcs, and an evader acts second to select a shortest path across the network. In this problem, the cost for an evader's arc consists of a base cost if the arc is not interdicted, plus an additional cost that is incurred if the arc is interdicted. The interdictor is not aware of the base costs when the interdiction action is taken, but does know that the base cost values are uniformly distributed within given (arc-specific) intervals. The evader, on the other hand, observes the exact value of the base costs, plus the additional costs due to interdiction actions. The interdictor's problem is thus to maximize the expected minimum cost attainable by the evader. We provide a partitioning algorithm for computing an exact optimal solution to this problem, leveraging bounds gleaned from Jensen's inequality as proposed in an earlier study on a maximum-flow interdiction problem. We also provide several algorithmic strategies for accelerating the convergence of the algorithm and demonstrate their effectiveness on randomly generated instances.

AB - We study a shortest-path interdiction problem in which the interdictor acts first to lengthen a subset of arcs, and an evader acts second to select a shortest path across the network. In this problem, the cost for an evader's arc consists of a base cost if the arc is not interdicted, plus an additional cost that is incurred if the arc is interdicted. The interdictor is not aware of the base costs when the interdiction action is taken, but does know that the base cost values are uniformly distributed within given (arc-specific) intervals. The evader, on the other hand, observes the exact value of the base costs, plus the additional costs due to interdiction actions. The interdictor's problem is thus to maximize the expected minimum cost attainable by the evader. We provide a partitioning algorithm for computing an exact optimal solution to this problem, leveraging bounds gleaned from Jensen's inequality as proposed in an earlier study on a maximum-flow interdiction problem. We also provide several algorithmic strategies for accelerating the convergence of the algorithm and demonstrate their effectiveness on randomly generated instances.

KW - Interdiction

KW - Networks

KW - Uncertainty

UR - http://www.scopus.com/inward/record.url?scp=85106944090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85106944090&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2021.04.055

DO - 10.1016/j.ejor.2021.04.055

M3 - Article

AN - SCOPUS:85106944090

VL - 297

SP - 239

EP - 251

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -