湖南工业大学课程设计资料袋学院（系、部）2011~2012 学年第 2 学期课程名称图论及其应用指导教师职称学生姓名ake555 专业班级学号题目交巡警服务平台的设置与调度的优化模型成绩起止日期2013 年6月16 日～2013 年 6 月21 日目录清单课程设计任务书2012—2013学年第2学期学院专业班级课程名称：图论及其应用设计题目：交警服务平台和调度设计问题完成期限：自2013 年 6 月16 日至2013 年 6 月21 日共 1 周指导教师（签字）：年月日系（教研室）主任（签字）：年月日图论及其应用课程设计说明书2013年6 月21 日目录一、问题描述 (5)二、模型假设 (6)三、符号说明 (6)四、模型建立与求解 (6)五、模型评价 (15)六、体会心得 (16)七、参考文献 (16)八、附件 (16)交巡警服务平台的设置与调度的优化模型一问题描述随着人们社会经济的迅猛发展，人们生活的质量的提高，安全意识以深入人心，作为社会秩序的维护者警察对社会稳定起着巨大的作用.警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。
为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。
每个交巡警服务平台的职能和警力配备基本相同。
由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题一：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。
要求为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
问题二：对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，通过求解给出该区交巡警服务平台警力合理的调度方案。
问题三：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，通过分析计算需要增加平台的具体个数和位置。
问题四：针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。
如果有明显不合理的地方，给出解决方案。
问题五：如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
二模型假设1．出警时道路恒畅通（无交通事故、交通堵塞等发生），警车行驶正常；2．在整个路途中，转弯处不需要花费时间；3．假设逃犯驾车逃跑的车速与警车车速相当三符号说明四 模型建立与求解4.1交巡警服务平台管辖范围问题的建立与求解（问题一）4.1.1问题分析：对于问题一，针对题中的限制条件进行分析，归结为动态线性规划问题来解决：首先根据所给条件计算出交巡警平台最大管理半径；其次依所给数据建立动态规划模型，借助Floyd 算法计算出20个交巡警服务平台到各个路口的最短距离；以最大管理半径为判断标准，求解出20个交警服务平台管辖范围。
4.1.2模型的建立与求解：首先，在保证出警时道路恒畅通，警车行驶正常的情况下，设车速恒为v 千米/小时，出警时间不得超过t 分钟，根据题意可知，从交巡警平台到达事发地点所行使的最大路径即为交巡警平台最大管理半径，其最大管理半径为：()l θ= 60tv ⋅⋅∂其中，∂为图中标数与实际比例，1100∂=，t =3分钟，v =60000米/小时， 计算可得：()l θ=30米所以，距离交巡警平台超过30米的路口不属于该交巡警平台的管辖范围。
基于上述分析，我们首先建立了3分钟区域圈，并借助于MATLAB 做出了区域图（作图程序见附录1），图一其次，针对问题一我们建立了动态规划模型，运用Floyd 算法计算每个交巡警服务平台到各个路口的最短距离，并借助于MATLAB 软件实现了算法，随后我们从中筛选出到达每个交巡警服务平台距离小于30米的路口，则连接各路口之间的路线即为该交巡警服务平台的管辖范围。
Floyd 算法的基本思想：直接在图的带权邻接矩阵中插入顶点的方法，依次构造出v 个矩阵12,v D D D ，使最后得到的矩阵v D 成为图的距离矩阵，同时也求插入点矩阵以便得到两点间的最短路径。
Floyd 算法：我们定义v v ⨯的方针序列12,v D D D ；初始化定义'D C =，'ijD 表示边(,)i j 的长度，表示初始的从i 到j 的最短路径的长度，即它是从i 到j 中间不经过其他中间点的最短路径。
迭代：设1k D -已求出，如何得到(0)k D k v ≤≤，1k ij D -表示从i 到j 的中间点不大于1k -的最短路径p ：i j ；考虑将顶点k 加入路径P 得到顶点序列:q i k j ；若q 不是路径，则当前的最短路径仍是上一步结果1k k ijij D D -=； 否则若q 的长度小于p 的长度，则用q 取代p 作为从i 到j 的最短路径。
因为q 的两条子路径i k 和k j 皆是中间点不大于1k -的最短路径，所以从i 到j 中间点不大于k 的最短路径长度为：}{111min ,k k k k ij ij ik kj D D D D ---=+基于以上分析，借助于Floyd 算法，用MATLAB 软件求得各交巡警服务平台到各个路口的最短距离见下表（程序见附录2）：表1接下来，利用上表计算所得数据，以最大管理半径30米为判断标准，从中筛选出到达每个交巡警服务平台距离小于30米的路口，得到A区各交巡警服务平台的管辖范围，其结果如下表所示：表24.34.2警力调度方案问题建立与求解（问题二）：4.2.1问题分析 ：对于问题二，我们要对进出A 区的13条交通要道实现快速完全封锁，就必须使13个交通要道周围的交巡警服务平台到达它们的距离最短。
依据题意，我们假定到达13个交通要道所用时间应该相近，即20个交巡警平台的警力几乎都能在相同的时间内到达十三个路口，若到达某些路口时间差异过大，则必然会影响到整个封锁过程，此时将大大的减少了执行任务的效果. 4.2.2模型的建立与求解：基于以上的分析，我们建立了以最短路为目标函数的线性规划模型，采用了求解最短路的Dijkstra 算法，并借助于LINGO 软件对算法进行了实现，从而得到了进出该区的13条交通要道实现快速完全封锁方案。
Dijkstra 算法的定义：设(,)G V E =是一个有向图，记这个有向图的每一条边（(,)U V E ⊂都有一个权(,)W U V ，在G 中指定一个结点0v ，要求把从0v 到G 的每一个结点()j j v v V ∈的最短有向路找出来（或者指出不存在从0v 到j v 的有向路，即0v 不可达j v ）。
算法如下：设S 为节点集V 的一个节点子集，0v S ∈，设 /c S V S =为S 的节点余集，如果我们记012(,,,)v u u u v 为从0v 到S 的最短路，则必有,c u S v S ∈∈，使得012(,,,)v u u u v 为0v 到u 的最短距离。
设012(,,,)v u u u v 为从0v 到n v 的最短路，令001121(,)(.)(,)(,)n n n d v u w v u w u u w u u -=+++为从0v 到n v 的最短路的权数，A 为V 中任意子集，则00,(,)min ()d v A d v u =为0v 到A 的最短路权数。
于是就有：{}000000(,)(,)(,)(,)(,)(,)min (,)(,)c c d v v d v S d v v d v u w u v d v S d v u d u v ==+=+运用LINGO 软件编程，计算得到A 城区交巡警服务平台警力合理的调度方案如下表所示（程序见附录3）：4.3增加平台个数及位置确定问题的建立与求解（问题三）： 4.3.1问题分析：对于问题三，要确定增加交巡警服务平台的个数和位置，我们必须遵循两个原则：一是增加交巡警服务平台以后各个交巡警服务平台的工作量应达到相对均衡，二是增加交巡警服务平台以后各个交巡警服务平台的出警时间应尽量短，（对于那些因距离过长而出警时间过长的地区增加平台）。
经过综合分析，我们考虑在问题一和问题二解决的基础上，以上述两条原则为判定标准，确定出增加交巡警服务平台的个数和位置。
4.3.2模型的建立与求解：首先，我们计算出各交巡警平台管辖范围内发生案件的总发案率，得到A 区各交巡警服务平台管辖范围内发生案件的总发案率（次）其次，利用原则一，对上述表格中数据进行分析，我们在几个案发率较高的平台恰当位置处增添了新的平台，这样就减轻了这些平台的工作任务，做到了各个交巡警服务平台的工作量达到相对均衡。
接着，我们依据问题一得到相临节点距离的分析，找出了距离明显过大的路线，依据原则二，在这些平台所管辖的路线的合适位置处增添了平台。
随后，我们综合考虑了发案频数较高的路线和距离明显过大的路线，得出了以下结论：由于A1、A3、A4所管辖的路线发案频率过高，通过分析，我们认为应在路线节点标号为66的节点处增添一交巡警服务平台。
由于A18、A20所管辖的路线发案率过高，通过分析，我们认为应在路线节点标号为91的节点处增添一个交巡警服务平台。
由于A7、A8、A9、A15所管辖的路线距离明显过大，加之该路线发案率较高，因此我们认为在路线节点标号为31的节点处应增添一个交巡警服务平台。
由于路线29 30距离明显过大，已超出附近所有交巡警服务平台的管辖范围，加之该处路线比较曲折，我们认为应该在该条路线上增添一个交巡警服务台。
4.4.交巡警服务平台设置方案问题的建立与求解(问题四)：4.4.1问题分析：针对问题四，要研究该城市交巡警服务平台设置方案的合理性，我们应把握以下原则和任务：1、警情主导警务原则：根据管区道路交通流量、拥堵状况、治安复杂情况、发案量高低，科学确定平台管控区域；2、快速出警原则：城区接警后确保快速到达现场；3、方便与安全原则：按照醒目、规范，方便群众和确保安全的原则，科学设置平台。
4、平台设置在遵循上述三大原则的基础上，应当结合辖区地域特征、人口分布、交通状况、治安状况和未来城市发展规划等实际情况，在充分考虑现有警力和财力并确保安全的条件下，科学确定平台的数量和具体位置。