《图论在服务平台合理设置中的应用》由会员分享，可在线阅读，更多相关《图论在服务平台合理设置中的应用（17页珍藏版）》请在金锄头文库上搜索。
1、大庆师范学院本科生毕业论文图论在服务平台合理设置中的应用院 （系） 数学科学学院 专 业 数学与应用数学 研 究 方 向 应用数学 学 生 姓 名 李鑫李鑫 学 号 200801052699 指导教师姓名 沙元霞 指导教师职称 讲师 2012 年 6 月 1 日大庆师范学院本科毕业论文I摘 要服务平台的合理设置，是一个动态规划问题.在交巡警平台中，需要确定每个交巡警平台到与其不相邻节点的最佳的出警路线，在求解过程中，筛选出无法在三分钟内到达的节点路口，对这类节点依据其特征进行划分，据此划分出各交巡警服务平台的管辖范围使其在接警后三分钟内尽量到达事发地点；针对道路封锁问题，考虑其特征，首先建立
2、0-1 规划模型将所求问题转化为求二部图的最大权匹配问题，其次构造 0-1 赋权矩阵，最终利用改进的匈牙利算法求解出对该区的交通要道进行快速封锁的合理的交巡警服务平台调度方案；从均衡交巡警服务平台工作量的目的出发，合理增加交巡警平台，使其工作量达到均衡.在此基础上，针对该市的现有交巡警平台的设置情况，利用最佳路径模型分析该市交巡警平台设置方案的合理性.关键词：交巡警平台；flody 算法 ；匈牙利算法；matlab 程序大庆师范学院本科毕业论文IIAbstractReasonable set of the service platform is a dynamic programming pr
3、oblem . Patrol platform , you need to determine the best out of the police line in each Patrol platform to its non-adjacent nodes , node junction in the solution process , the filter can not arrive within three minutes of such nodes according to their characteristics divided accordingly divided into
4、 the jurisdiction of the Traffic and Patrol services platform , so that within three minutes after the alarm try to arrive at the site of the incident ; for road blockade , considering its characteristics , First 0-1 programming model to the demand problem is transformed for the sake of the maximum
5、weight matching of bipartite graph , followed by tectonic 0-1 empower matrix , the final use of the improved Hungarian algorithm to solve the traffic arteries rapid blockade reasonable Traffic Patrol service platform scheduling programs; the purpose of the workload of the service platform of balance
6、d Traffic Patrol , a reasonable increase in the Patrol platform , so that workload to reach equilibrium . On this basis , the setting for the city s existing platform Patrol . Keywords: Patrol platform;Flody Algorithm;Hungarian Algorithm; Matlab Program大庆师范学院本科毕业论文III目录目录第一章 前言1第二章 基本假设符号说明及问题分析42.1
7、 基本假设42.2 符号说明42.3 问题分析52.3.1 模型一的问题分析52.3.2 模型二的问题分析5第二章 模型的建立与求解63.1 服务平台设置模型的建立与求解73.1.1 交巡警服务平台的管辖范围模型73.1.2 紧急情况道路全面封锁模型93.1.3 增设交巡警服务平台模型113.2 合理性检验模型12第四章 服务平台设置模型的评价12参考文献13大庆师范学院本科毕业论文1第一章 前言面对各种突发事件，即使在科技高度发达的今天，也有显得束手无策的时候，许多国家政府、科学家为预防事故，保障生命财产安全作了一定的工作，例如澳大利亚在 1993 年 1 月成立了应急管理署（） ，负责处理
8、自然、人为、技术等方EMA面的灾害，在事故或灾害发生时，及时、有效地迎对各种重大紧急事件和灾害.近十年来，我国科技带动生产力不断发展，国家经济实力不断增强，然而另一方安全生产形势却相当严峻，每年因各类生产事故造成大量的人员伤亡、经济损失.尤其是在一些大目标点，作为人类经济、文化、政治、科技信息的中心，由于其“人口集中、建筑集中、生产集中、财富集中”的特点，一旦发生重大事故，将会引起相当惨重的损失.为了保障安全生产、预防各类事故.我国正在各省（市）目标点逐步设立交巡警平台.2010 年 2 月 7 日，一只名为“交巡警”的全新警种在重庆诞生.这一警种拥有包括枪支在内的 “高精尖”装备，代替过去的
9、交警和巡警 .交巡警平台是将刑事执法、治安管理、交通管理、服务群众四大职能有机融合的新型防控体系.在人流量极大、治安状况比较复杂、交通持续比较混乱的事故多发带产生强大的司法制衡力、社会治安的驾驭力、打击罪犯的冲击力.保证在事故发生的第一时间赶到现场.大力的减少了社会上各种混乱行为的发生.使居民的生命财产安全得以保障.警务平台能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接警和处警时间，提高了反应时效，为社会的和谐提供了有力保障.以某市市中心 A 区为例，通过对数据的调查研究，根据道路数据和地图数据（附件 1 附图 1） ，该区共有 92 个节点，其中有 20
10、个警务平台，为了简化问题相邻两个节点之间近似认为是直线，且所有事发现场均在道路上.我们将要解决以下问题：为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地.对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁.实际中一个平台的警力最多封锁一个路口，我们给出该区交巡警服务平台警力合理的调度方案.根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，利用图论确定需要增加平台的具体个数和位置.大庆师范学院
11、本科毕业论文2针对全市（主城六区，）的具体情况，按照设置交巡警ABCDEF服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性.如果有明显不合理，请给出解决方案.如果该市地点（第 32 个节点）处发生了重大P刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑.为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案.第二章 基本假设符号说明及问题分析2.1 基本假设1.出警时道路恒畅通（无交通事故、交通堵塞等发生） ，警车行驶正常；大庆师范学院本科毕业论文32.在整个路途中，通过各种通讯工具，走的路程都是最短路程；3.在整个路途中，转弯处不需要花费时间；4.
12、相邻两个节点之间近似认为是直线；5.警车行驶过程中不再发生案件；6.不考虑接警时间；7.每个交巡警服务平台的职能和警力配备基本相同；8.警察按最短的路程赶往目的地；2.2 符号说明-恒定车速v-图中标数与实际比例-出警所用最大时间t-从交巡警平台到达出事地块所行驶的最小路程 R2.3 问题分析2.3.1 模型一的问题分析（1）要解决管辖范围的划分，必须针对城市中的限制条件进行分析，计算出交警平台的设立路口离其最远的地块的距离即可.原因如下：以下计算均以图中标数计算,其中为图中标数与实际比例，那么设为交巡警平台的路口需满足的条件为：在保证出警时道路恒畅通，警车行驶正常的情况下，由题意知，车速恒为
13、 千v米/小时，出警时间不得超过 分钟，则从交巡警平台到达出事地块所行使的最大路t径：60tvR 由假设所给出数据3t 分钟，60000v 米/小时，1:100000可得： R=3000 米 所以，交巡警平台所管辖的范围，即不能为超出到达出事点路程 3000 米的所 有点.利用算法计算各平台到所有节点距离，进而筛选出路程 3000 米以内所有Floyd节点.（2）对于第二个问题，可直接利用效率矩阵不是方阵的指派问题模型及改进的匈牙利算法解决.大庆师范学院本科毕业论文4效率矩阵不是方阵的指派问题模型1. 若人多事少，可以添上一些虚拟的事，这些事被个人做的费用可取作为零；2. 若人少事多，可以添上
14、一些虚拟的人，他们做各事的费用可区为零；3. 若一个人可同时做几件事，可以将这人化为相同的几个人，费用不变；4.若规定某人不能做某事，求最小时则可令这人做的事费用为充分大的数（在中可取为） ；求最大时则可令这人做这事的费用为 0，然后按目标函数的Matlabinf指派问题数学模型的求解方式求解.此问题属于第一种情况.（3）计算区总案发率，根据上面所得各交巡警平台所管辖范围，由按发率A大小衡量相对工作量，进而确定需要增加平台的具体个数和位置.2.3.1 模型二的问题分析可以将问题一进行推广应用，分别求出主城六区交巡警平台所管辖范围内相对工作量大小，交巡警平台案发率与最优值比较，偏差很大认为方案不
15、合理.大庆师范学院本科毕业论文5第三章 服务平台设置的图论模型3.1 服务平台设置模型的建立与求解经过数据的调查，得到了城区各位置坐标的数据，对这些数据进行分析，用Matlab 描点，将所用路口进行标号，可得下图，利用此图解决以下问题.3.1.1 交巡警服务平台的管辖范围模型考虑到我们需要计算交巡警平台管辖范围，我们考虑先去计算平台到其他各点的距离，其中有联通与断开的区别，取断开为.计算中，不直接相连按折线计算.此inf时，考虑用算法.Flody基本思想为:两节点之间最短路径要么是相邻时最短，要么是以通过几个中心节点时最短.从开始，由计算.然后算法再由计算.将这个过程0D0D1DFlody1D2D重复进行下去，直至, 求得为止.1nDnD该计算的基本思路如下,设已知:1.顶点 到顶点的最短路径,其中只容许前()个顶点即作为中间im1m1,2,.1m顶点.2.从顶点到顶点的最短
