Title: Application of the Maximum Flow Problem to Sensor Placement on Urban Road Networks for Homeland Security
Abstract: IntroductionNetworks are essential components of our national infrastructure. However, those networks could be used by terrorists seeking to attack dense urban populations with weapons of mass destruction. In particular, large urban road networks provide many routes that terrorists could use to get close enough to a major city to make a harmful attack. One approach envisioned for protecting urban areas from such attack is to deploy (human-operated or fully automatic) sensors on the roads around cities to detect terrorists and their weapons so they can be stopped before they come within range of their targets. A key challenge to such an approach concerns how many sensors to buy and where to locate them. Indeed, the size and density of road networks would seem to make the cost of buying and operating these sensors prohibitive by requiring placement of sensors on hundreds if not thousands of road segments in order to protect any large city.This challenge led to the work reported here, which shows that, contrary to first appearances, the number of sensors required to cover every possible route into a city is not prohibitively large. We apply graph theory to find a minimum cut set for a road network; i.e., to find a smallest set of road segments on which sensors must be placed to ensure that a terrorist traveling across the road network must encounter at least one sensor. We applied this theory to the actual road network of the New York City metropolitan area, and found that the minimum cut set was about 104 times smaller than the number of road segments in the network--the road network had approximately one million road segments and it yielded a minimum cut set of eighty-nine road segments. Thus, the minimum cut set problem for large urban road networks can be solved. Furthermore, the solution shows that the size of the cut set alone does not make it impractical to deploy a system of sensors that would cover all of the routes into the city on the road network. 1The work reported here specifically concerns finding optimal locations for sensors for detecting terrorists, weapons, or other dangerous materials on roads leading into major cities. However, this work is generally applicable to finding minimum cut sets for any large network. It could be used to find optimal sensor locations on other transportation networks like railroads or subways. It could also be used to support offensive operations by locating a smallest set of segments in an adversary's network that would have to be cut in order to completely stop the flow through the network. Thus, the methodology presented here could have utility in other homeland security and military analyses.There is considerable literature on graph theory, network optimization, and the minimum cut set problem. The references at the end of this article specifically address the minimum cut set problem. The accomplishments of the work reported here were a) to find and implement a practical way of solving large networks for minimum cut sets and b) to discover that the minimum cut set for a large U.S. urban road network was much smaller than what might have been expected given the number of road segments in the network.Analytical ProblemTerrorists seeking to attack a large city might use the roads leading into that city to transport personnel, weapons, or other dangerous materials. One approach for preventing such attacks is to deploy sensors on those roads to detect the movement and allow the interdiction of these entities before the terrorists reach their destination. To evaluate the feasibility of this approach, we would like to know the smallest number of sensors that must be deployed to ensure that a terrorist traveling into a city would encounter a sensor, and, of course, where to locate those sensors. Thus, we sought a methodology that could find a minimum cut set in a city's road network. 2The particular question addressed is as follows. …
Publication Year: 2007
Publication Date: 2007-09-01
Language: en
Type: article
Access and Citation
Cited By Count: 8
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot