2011数学建模优秀论文——交巡警服务平台的设置与调度

交巡警服务平台的设置与调度

摘要

本文对交巡警服务平台的设置与调度问题,应用Dijstra最短路算法，多目标规划，0-1整数规划，时间步长法，针对不同情况的具体问题，分别建立了相应的数学模型，给出了合理的交巡警服务平台的设置与调度方案。

对A区交巡警服务平台管辖范围的分配问题，首先根据节点坐标计算出节点邻接对称矩阵，然后利用Dijstra算法求解出各节点到每个平台的最短距离，并根据到平台最短距原则分配各节点给相应的平台管辖，最后得到了各平台管辖的范围（见表1），同时给出了各平台管辖范围内3分钟路程外的节点（见表1）。

对封锁A区13条要道节点的交巡警服务平台警力调度问题，考虑到各平台出警时间的同步，出警的平台数量最少以及一个平台警力最多封锁一个路口的约束，运用多目标规划，0-1整数规划建立了一个封锁13条要道节点最长时间最小化模型，并运用Lingo求解出平台3,4,5,6,7,9,10,11,12,13,14,15,16分别封锁要道节点16,38,62,48,29,30,12,24,22,21,23,28,14，

得到了A区13条要道全部封锁完成的最短时间为8分钟。

对确定需要增加交巡警服务平台的个数及位置问题，考虑到各平台工作量的均衡及出警时间，运用各平台工作量（所管辖范围内的发案数和）的标准差来衡量其工作量的均衡，建立了一个对每个节点的出警时间不超过3分钟，且各服务平台工作量的标准差最小（各平台工作量越均衡）的数学模型，并得到可在本区增加4个平台，分别增加在节点28,39,48,87.

对评价全市现有交巡警服务平台设置方案的合理性问题，首先根据主城区以及最短距原则将全市各区节点分配给本区现有的平台，然后根据各平台工作量的均衡、出警时间、本区人口密度及发案率对现有平台设置进行了评价，并对明显不合理处进行了调整，给出了新的平台设置方案，同时对新方案各平台工作量，所辖3分钟路程节点数进行了比较，验证了新的平台设置方案明显优于现有平台的设置方案（见表3）。

对于搜捕围堵疑犯的警力调度问题，以3分钟为时间步长，首先计算出疑犯在逃跑3分钟后的每个时间步长内的可达点及花费时间，然后运用多目标规划，0-1整数规划建立一个封锁疑犯所有可达点的最长时间最小化调度模型，并满足交巡警到达疑犯各可达点的时间小于疑犯到达该点时间，进而讨论了疑犯以40km/h，60km/h，90km/h，120km/h四种不同逃

跑速度下的最优搜捕围堵方案（见表4-7）。

最后，对文中所建模型进行了深刻探讨，并对文中所建模型进行了评价，同时给出了最优搜捕围堵方案模型允许疑犯逃跑的最大速度为148km/h，进一步讨论了最优搜捕围堵方案模型的改进。

关键词：Dijstra算法，多目标规划，0-1整数规划，时间步长法

1 问题的重述

“有困难警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：

问题1：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

问题2：对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。

问题3：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。

问题4：针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。

问题5：如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，

犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

2 模型假设

1、假设警车出行线路是双行的，警车在服务于事发节点时不考虑交通拥堵，转弯等的影响；

2、假设巡警通讯、处理案件所花费的时间不必考虑；

3、假设两节点的路线是直线，且事发地点只能在节点处；

4、假设交巡警车在到达事发地点时是匀速行驶（60km/h）；

5、假设每辆警车在服务于事发节点时都是选择最短路线；

6、假设疑犯在逃跑过程中不会停止；

7、假设在全市搜捕疑犯时，各平台警力可跨区进行围堵。

3 符号说明

：A区中交巡警车服务点（）；

：A区中路口节点（包含交巡警车服务点，）；中华蝎王

：路口节点被服务平台的警力封锁的时间；

：犯罪嫌疑人驾车从P点到第个路口节点的距离；

: 犯罪嫌疑人驾车从P逃跑的速度。

4 模型的分析、建立与求解

4.1 A区交巡警服务平台管辖范围的分配模型

为了使A区中任意一个节点在发生事故后都有交巡警车在最短时间内到达并服务于该点，根据假设1-5，并为了使得事发地点有明确的交巡警平台服务，即一个节点只被一个平台所管辖，我们给出了下面的算法模型：

模型1(A区各交巡警服务平台分配管辖范围模型)成绩管理系统

Step1:构造邻接对称矩阵，为中的元素。其中，,,分别为点与点的坐标。

Step2:依据邻接对称矩阵，利用Dijstra 算法求出节点到交巡警服务平台的最短距离。贝塔分布

Step3:按最短距原则分配节点到平台中。

根据上述算法模型，运用MATLAB程序(见附录program1)求解得出A区交巡警服务台管辖路口节点表（见表1）。

表1 A区交巡警服务台覆盖路口节点表

灰斜体节点表示所属平台不能在3分钟内可达
服务台	路口节点	服务台河北卫视真情旋律	路口节点
1	1， 67，68，69， 71， 73，74，75，76， 78	11	11， 26，27
2	2，39，40，43，44， 70， 72	12	12，25
3	3，54，55， 65，66	13	13，21，22，23，24
4	4，57，60，62，63，64	14	14
5	5，49，50，51，52，53，56，58，59	15	15，28，29
6	6	16	16， 36，37，38
7	7， 30， 32， 47，48，61	17	17，41，42
8	8， 33，46	18	18， 80，81，82，83
9	我和qq的故事9， 31， 34，35，45	19	19， 77， 79
10	10	20	20，84，85，86，87，88，89，90，91，92

同时考虑到所管辖节点到平台的时间尽量在3分钟路程内，我们可进一步计算平台到所管辖节点的时间，发现有六个节点（28,29,38,39,61,92，见表1）在所属管辖平台并不能在3分钟内到达，又由于每个节点是按照最短距进行分配，所以这六个节点只能按照表1分配给相应的平台，而A区其余所有节点都可以在所属平台范围内3分钟到达，故按照节点距平台的最短距原则进行分配，就可使得各平台在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

4.2 封锁A区13条要道节点的交巡警服务平台警力的调度模型

对于重大突发事件，需要快速封锁全区13条要道节点，根据假设1-5，并考虑到每一个平台的警力最多封锁一个路口节点，同时考虑到现实中警力资源有限，出警时间相同的条件，故问题可转化为各平台出警时间的同步，出警的平台数量最少以及一个平台警力最多封锁一个路口的约束条件下，如何从20个平台中选择13个平台封锁13条要道节点，并使得完成封锁每条要道的时间的最大值要最小，即需要建立一个最长时间最小化模型，因此可运用多目标规划及0-1整数规划理论建立模型。

设为路口节点被交巡警服务平台的封锁情况，即

并假设为所有服务平台的警力都到达指定封锁路口的最大时间，即

在发生重大突发事件后，由于每个平台的警力同时出警，所以目标为到达要道节点所花费时间最长的平台所用的时间最短，即

下面讨论约束函数。

（1）警力平台的约束。由于一个平台的警力最多封锁一个要道节点的路口，所以

，

（2）出入城区路口的约束。由于现实中警力资源有限，要求出警的平台数量最少，故每一个要道节点只能被一个平台封锁，所以

，

为了能够利用Lingo进行方便求解，需要将上述多目标问题进行转化，得到

运用Matlab和Lingo程序（见附录program2，LINGO2）可求解出如下平台警力的调度方案。

表2 封锁A区13条要道节点的交巡警服务平台警力的调度方案双灵固本散

平台3路口16	平台4路口38	平台5路口62
平台6路口48	平台7路口29	平台9路口30
平台10路口12	平台11路口24	平台12路口22
平台13路口21	平台14路口23	平台15路口28
平台16路口14