Risk-Averse Shortest Path Interdiction
研究了一个网络中的Stackelberg博弈，领导者通过阻断弧段来最小化成本，同时确保跟随者的旅行距离以高概率超过给定阈值，提出了分支切割算法并验证了有效性。
We consider a Stackelberg game in a network where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer than a given threshold, interpreted by a chance constraint. Under the assumption of a wait-and-see follower—i.e., the follower selects a shortest path after seeing realizations of the random arc cost—we propose a branch-and-cut algorithm and apply lifting techniques to exploit the combinatorial structure of the risk-averse leader’s interdiction problem. We demonstrate the computational efficacy of our approaches, risk-averse interdiction solution patterns, and result sensitivity, by testing instances of randomly generated grid networks and real-world transportation networks.