Multiple-sink shortest path network interdiction problem
1Yildiz Technical University, Dept. of Industrial Eng., Esenler-İSTANBUL
2Karadeniz Technical University, Dept. of Industrial Engineering, TRABZON
2Karadeniz Technical University, Dept. of Industrial Engineering, TRABZON
Sigma J Eng Nat Sci 2018; 9(): 395-403
Abstract
This paper defines and studies the multiple-sink shortest path problem (MS-NIP). The MS-NIP corresponds to many real-life problems relating to especially terrorist actions. In the MS-NIP, a network user seeks the shortest path to meet the demands of sink nodes while an interdictor aims to maximize the shortest path of a network user by interdicting the arc(s). In this study, we formulate exact mathematical models of the network user and interdictor for the MS-NIP and apply them on an illustrative example. We test the model depending on the different interdiction budget levels and discuss the obtained results.
Keywords: OR in defense, shortest path problem, network interdiction problem, mixed-integer programming.