A platform for research: civil engineering, architecture and urbanism
A platform for research: civil engineering, architecture and urbanism
Assessing the effectiveness of k-shortest path sets in problems of network interdiction
Abstract This paper focuses on the network interdiction problem and integration of a solution methodology based on k-shortest path sets. We design and conduct an experiment using the road network of Northridge, California to assess performance of the k-shortest path approach under varying assumptions which include homogeneous and heterogeneous arc metrics, the use or non-use of pseudo nodes and alternate origin-destination scenarios. We compare the obtained solutions from the k-shortest path set approach to optimal solutions obtained by implementing Benders Decomposition and observe the differences in computation time and the objective gap for all cases of the experimental design. We also introduce a similarity measure based on spatial analysis techniques to compare coverage as a secondary measure of performance. The observed findings support the use of a k-shortest path set approach in situations where computation time prohibits the need to derive an optimal solution. Additionally, we show that the k-shortest path set approach performs better on heterogeneous networks and that only a small number need be used for k to achieve strong interdiction solutions.
Assessing the effectiveness of k-shortest path sets in problems of network interdiction
Abstract This paper focuses on the network interdiction problem and integration of a solution methodology based on k-shortest path sets. We design and conduct an experiment using the road network of Northridge, California to assess performance of the k-shortest path approach under varying assumptions which include homogeneous and heterogeneous arc metrics, the use or non-use of pseudo nodes and alternate origin-destination scenarios. We compare the obtained solutions from the k-shortest path set approach to optimal solutions obtained by implementing Benders Decomposition and observe the differences in computation time and the objective gap for all cases of the experimental design. We also introduce a similarity measure based on spatial analysis techniques to compare coverage as a secondary measure of performance. The observed findings support the use of a k-shortest path set approach in situations where computation time prohibits the need to derive an optimal solution. Additionally, we show that the k-shortest path set approach performs better on heterogeneous networks and that only a small number need be used for k to achieve strong interdiction solutions.
Assessing the effectiveness of k-shortest path sets in problems of network interdiction
Yates, Justin (author) / Wang, Xinghua (author) / Chen, Nannan (author)
Optimization and Engineering ; 15 ; 721-749
2013-05-31
29 pages
Article (Journal)
Electronic Resource
English
Assessing the effectiveness of k-shortest path sets in problems of network interdiction
| Online Contents | 2013
Time Dependent Shortest Path on Urban Transportation Network
| British Library Conference Proceedings | 2005