交巡警服务平台的设置与调配.doc

2011 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性如有违反竞赛规则的行为，我们将受到严肃处理我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 3264 所属学校（请填写完整的全名）： 湛江师范学院 参赛队员 (打印并签名) ：1. 张旭峰 2. 何家慧 3. 陈碧娥 指导教师或指导教师组负责人 (打印并签名)： 赵海清 日期： 2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1交巡警服务平台的设置与调配摘要根据实际情况和需要来设置和调配交巡警的服务平台，使警力资源合理充分利用.问题一分为 3 个小问题,分别为问题 1,2,3.问题二,分为 2 个小问题.分别为问题 4,5.对于问题 1,利用图论中的最短路径问题，建立了最短路有向图模型，并考虑道路双向型问题。

主要方法为 Dijkstra 算法并用 Matlabt 编程得到 daoluwang 程序得到服务平台所管辖的所有路口,结果见表一.对于问题 2，用运筹学中的目标规划，首先确定为一个求最短路问题,在求出最优解的基础上再进一步建立一个合理分配的整数规划2013minijZjcX模型通过借助指派数学算法和 WinQSB 软件进行计算，再对模型进行合理的推断和多次检验，得出服务平台对 A 区进行封锁的最短路径总和的最短路程为 461.88(百米)对于问题 3，建立在问题 1 的基础上，权矩阵由两路口之间距离由公式转变为路口与发案率共同组合的优化权矩阵 并将其它限..2ijijijdffD ijD制 3 分钟时间问题加以修改从而得到 A 区再增加四个平台,标号分别为 28.38.39.58的路口.对于问题 4，建立在问题 1 的基础上，将 A 区扩大到六个区，通过优劣评价系数来决策服务平台设置方案的合理性根据覆盖率 判断 B 区覆盖最小,与iiiqRkp iq人口密度 一起相比,A 区服务台分配最不合理.iP对于问题 5，先建立在问题 2 的模型上从 A 区出发考虑，再建立在模型 1 的基础上，从全区出发，从中找到交警服务平台到围堵路口的最小权，与路径。

关键字： Dijkstra 算法，最短路模型，0－1 整数规划，Matlab一、问题重述2由于城市优化问题需要在市区的一些交通要道和重要部位设置交巡警服务平台如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题根据某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）找出 A 区 20 个交巡警服务平台所管辖的路口以定其管辖范围要求：尽量能在 3 分钟内到达事故地点 （警车的时速为 60km/h）（2）重大突发事件，调度全区 20 个交巡警服务平台的警力资源快速全封锁 A 区 13条交通要道给出警力调度方案要求：一个要道至少一个服务平台全部警力3）增加 2 至 5 个平台，确定需要增加平台的具体个数和位置4）给出六区 A，B，C，D，E，F 的交巡警服务平台合理设置方案5）P（第 32 个节点）如发生了重大刑事案件，为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案二、问题分析(一) 问题 1 的分析问题 1 要求找出 A 区 20 个交巡警服务平台所管辖的路口，并以定其管辖范围已知（1）各结点的坐标；（2）20 个服务平台的标号；（3）所能走的各路口的路线和路程。

通过已知条件，可以找出服务平台到路口的最短路径，并确定在服务平台 30 百米（警车以 60Km/h 的时速在 3 分钟内到达事发地）的交叉路口由此判定此路口是否归该服务平台来管辖这属于最短路径问题，对于此题可以用 daoluwang(见程序说明)来解答，然后，根据计算的结果判断每个路口是否都有归属的服务平台二) 问题 2 的分析问题 2 要求给出全区 20 个交巡警服务平台的警力资源快速全封锁 A 区 13 条交通要道的调度方案根据实际问题，只要把 13 个出入 A 区的要口给封锁，那么 A 区的 13条要到就会全部封锁了，即将 20 个服务平台的警力资源分配给 13 个出入要口已知（1）20 个服务平台的坐标；（2）13 个出入 A 区的标号 （3）A 区交通路口的路线通过已知条件，可以进行每段直接路线的距离求解，然后建立一个 92*92 的实对称矩阵；进而通过 winQSB 软件，可以进一步确定每个交巡警服务平台到任一个需要封锁要口的最短距离并再利用已求出的最短距离系数矩阵，进行资源分配优化，从而得出最佳的交巡警服务平台调配方案这是一个优化模型的问题，其中涉及到最短路线的求解，应用 winQSB 软件实现，最终解决了资源分配优化的问题。

三) 问题 3 的分析问题 3 是根据交警服务平台的工作量不均衡和有些地方出警时间过长的实际问题，增加 2 至 5 个平台并确定需要增加平台的具体个数和位置是问题 1 的推广考虑到了交警工作时间，故权不单是距离决定，也有发案率来决定 (四) 问题 4 的分析问题 4 要求给出六区 A，B，C，D，E，F 的交巡警服务平台合理设置方案如要要研究配置方案的合理性，那么就要确定评价方案合理性的指标这同样是问题 1 的推广根据要求条件和附件给出的数据，可以通过问题 1 的解法来计算出交叉路口的覆盖率（每个区的服务平台在一定的条件下能够管辖的路口个3数占总路口数的比率）和人口密度来评价方案的合理性五) 问题 5 的分析假设，交警与逃犯单位时间行驶距离相同寻找服务点点到各路的最短权，使得P 点到路口的路程要比服务点到路口少 3 分钟的路程三、模型假设1. 假设题目所给的交通路线是双向的；2．假设交巡警接到任务后就会出警；3．假设每个交巡警服务平台的职能和警力配备相同；4．假设每个交叉路口只归一个交巡警服务平台管理；四、定义与符号说明～节点为 的交叉路口的横坐标ixi～节点为 的交叉路口的纵坐标iy～节点为 的交叉路口到节点为 的交叉路口的路程ijdi j～第 个交巡警服务平台的位置标号iA～第 个路口节点标号iV～第 个交巡警服务平台 到第 个路口节点标号 的最短路程ijciAjjV～标号为 个路口的案发率ifi～第 区的服务平台的优劣评价系数iR～第 区的服务平台的人口密度iP～第 区的服务平台的覆盖率iq五、模型的建立与求解第二部分：问题的解答（一）问题 1 的解答(最短路径模型)　1、模型的建立引理[3]：在赋权有向图中，求一条总权最小的 到 的问题，就是最短路径问iVj题。

4Dijkstra 算法的基本思想：如果 的最短距径，则它的子路12,.,.,ijnvv一定是从 到 的最短路径ijvivj要求出交巡警服务平台到路口的路程，那么就要确定最短的路径在此用图论法来解决该问题从而建立有向图服务平台 做为图的顶点，距离 做为图的权要求所求两点之间的最小权值，iAijd（1）22ijijijxy1,mnijiZd, ,.30ijist1,20i ,92j（2） 其中， 到 最短路径的路程ij大致走向图如下：考虑由 表示现设有交巡警服务平台与节点 直接或i1,20A（ ） j1,29A（ ）间接共同构成了一个赋权有向图其中弧 表示第 i 个交巡警服务平台到第 j 个(,)ijA节点的路程；节点的疏密程度以及各节点案发率的高低52、 模型的求解步骤用 MATLAB 编程（见附件） ，计算出 A 区每个服务平台对应的管辖交叉路口和到它们的距离，如下表一：求解步骤说明：（1） 建立从 到 的有向图，找到从 到 的最短路径，及路程如果重复，ViVj把之间路程小的 分在 组中,得到数据 aa,bb. 将两顶点与权（距离）统ji计出表 1（见附件） （由 daoluwang_1.m 求得） ，并放入 excel 之中统计。

2） 将 B 中两列交换次序，重新建立如上模型得到数据 aaf,bbf. 将两顶点与权统计出表 2（见附件） （由 daoluwang_1f.m） ，并放入 excel 之中统计3） 合并表格 1 与 2，找出重复数据，并将权大者剔除4） 找出表格中未出现的 路口，如果在 B 可以直接找到 或 那么jV()iVA(,)i就将 赋给 否则在 B 中找到与 最近的数据最终得到表一iViAjDaoluwang（以 Daoluwang 开头的程序）的流程图：输入 A输入 Bb0=剔除 Bd=所有可行路之间的距离权 w=dd终点反向：终点——>起点输入数据：A.txt——全市交通路口数据 前三列 A 区数据B.txt――全市交通路口的路线 A2：B144AA．Txt――全市交通路口数据 前三列数据BB．Txt――全市路口缝线fa.txt――全市交通路口 发案率 A 区数据f.txt――全市交通路口 发案率数据输出数据：b0.dat――B 剔除 A 区以外路线的数据b00.dat――b0 的两列交换位置c.dat――B 两列点之间的距离CC．dat――BB 两列点之间的距离aa.dat――A 区报务台到控制点路线——正向bb.dat――A 区服务台到控制点权——正向aaf.dat――A 区报务台到控制点路线——反向bbf.dat――A 区服务台到控制点权——反向aaa.dat――A 区报务台到控制点新路线——正向bbb.dat――A 区服务台到控制点优化权——正向aaaf.dat――A 区报务台到控制点新路线——反向bbbf.dat――A 区服务台到控制点优化权——反向13r.dat——全区各服务点到控制点的个数——正向rf.dat——全区各服务点到控制点的个数——反向zdlq.dat——全区中服务台到控件点优化权——正向zdlq.dat——全区中服务台到控件点优化权——反向AF.txt——全区中服务台到控件点优化权——正向(由 zdlq.dat 生成)AFf.txt——全区中服务台到控件点优化权——反向（由 zdlqf.dat 生成）p1.dat——全区中 p 点到各控制点的路线——正向P2.dat——全区中 p 点到各控制点的优化权——正向p1f.dat——全区中 p 点到各控制点的路线——反向P2f.dat——全区中 p 点到各控制点的优化权——反向程序：tch_B——剔除 B 中不在 A 区的路线lucheng——b 数组中第一列与第二列间的距离（函数为：c=lucheng(a,b。