Police Dispatch

— 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.

首先，中国警察承诺接警后三分钟内到达案发现场，同时他们通常以属地化运行。本项目的第一部分是提出了一些算法，用来分配辖区以便日常巡逻和对报案响应，确定新建站的地点以便确保三分钟承诺并均衡化不同站点之间的工作量。本项目建议重庆市在市区增加5个新的站点以便履行三分钟承诺。

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 1^st Prize in Beijing of Chinese Universities Mathematical Contest in Modeling.

项目中提出的算法们通过定量的方法解决了交警遇到的问题，避免了人工决策的不可靠性。本项目获全国大学生数学建模比赛北京赛区一等奖。