— Police Dispatch for Blocking Intersections and Manhunts Based on Graph Algorithms
It is a research teamwork finished during Chinese Universities Mathematical Modeling Contest in Modeling in 2011. 这是2011年中国全国大学生数学建模竞赛的小组研究成果。
This project focuses on two main problems faced by Chinese traffic police, distributing watching areas to the traffic police substations and dispatching the police for emergency.
Firstly, Chinese police has a “three-minutes” promise, i.e. the police officers must arrive the scene within three minutes after requests, and they normally work in their own watching areas. The first part of the project proposes algorithms for allocating the watching areas for responses and patrols and determining the location of new stations to realize the three-minutes promise and to balance the workload among stations, where the researchers use Chinese Postman Problem to measure the patrol workload plus the expectation of the workload for handling traffic accidents. The project suggested Chongqing, a Chinese city, build 5 more stations in the downtown to fulfill the three-minutes promise.
Secondly, Chinese police is also responsible for traffic blocking in emergency. This project proposes an algorithm to dispatch the traffic police for manhunts or other blocking intersection assignments. It abstracts the dispatch of traffic police for blocking intersections into perfect matching problem in a bipartite graph. By using binary search, the researchers propose the algorithm to give the dispatch with the least time consumption by police. Then, defining the search radius, the researchers solve the encirclement of manhunts by blocking some critical intersections before the suspect’s arrival. Another binary search used here makes the search radius least to save the budget and time.
The algorithms proposed in this project solve the problem in a quantitative method, and avoid the unreliability of human decision. This project won the 1st Prize in Beijing of Chinese Universities Mathematical Contest in Modeling.