Premium
Shortest path network interdiction with asymmetric information
Author(s) -
Bayrak Halil,
Bailey Matthew D.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20236
Subject(s) - interdiction , shortest path problem , mathematical optimization , path (computing) , computer science , integer (computer science) , longest path problem , mathematics , theoretical computer science , graph , computer network , engineering , programming language , aerospace engineering
We consider an extension of the shortest path network interdiction problem. In this problem an evader attempts to minimize the length of the shortest path between the origin and the destination in a network, while an interdictor attempts to maximize the length of this shortest path by interdicting network arcs using limited resources. We consider the case where there is asymmetric information, i.e., the evader and the interdictor have different levels of information about the network. We formulate this problem as a nonlinear mixed integer program and show that this formulation can be converted to a linear mixed integer program. Computational results demonstrate improvements in the objective function values over the shortest path network interdiction problem with symmetric information. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008