模型六巡逻路线完结.docVIP

杭州电子科技大学第十四届大学生数学建模竞赛 (承 诺 书) A B 选择题号： （在方格内打√） 我们承诺： 我们仔细阅读了校大学生数学建模竞赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛的题目是： 我们的参赛报名序号为： 参赛队员 (打印并签名) ： 1. 姓名（打印 张凡 学号 签名 2. 姓名（打印 __朱云__ 学号 签名 3. 姓名（打印 王健 学号 签名 日期： 2013 年 8 月 校评阅编号（由校数模组评阅前进行编号）： 杭州电子科技大学第十四届大学生数学建模竞赛 编 号 专 用 页 校评阅编号（由校数模组评阅前进行编号）： 巡逻路线问题 摘要 本文研究的是某市公安巡特警大队在市区主要街道执行日常巡逻任务的问题，并在满足日常巡逻的条件下给出了巡逻效果最好的方案。 首先我们将整个巡特警中队A和巡特警中队B共同负责日常巡逻的街区图进行处理，用图与网络分析的方法将其表示出来，各道路交叉点我们认为是图中结点。并将图中条件进行数据化处理（结果见问题分析） 在设计整个区域常规巡逻管辖街道的合理划分，本文在应用Dijkstra标号的法基础上设计了算法。对于问题一本文先将原图中各个结点到巡特警中队A和巡特警中队B的最短路径的距离求出，然后进行分析处理，若每一条街道两端的结点到A中队的距离之和小于到B中队距离之和，则认为此街道区域由A中队负责，否则由B中队负责，经MATLAB编程计算，（程序见附录）得到巡特警中队A与B关于常规巡逻管辖街道的合理划分（结果见模型的求解）。 对于问题三我们用Dijkstra标号法可以对巡特警中队A（B）所管辖的区域内进行合理的分析和计算，其中对于转弯的时间我们选择用向量叉乘的思想来解决，将转弯时间加入到问题三的分析后，我们以A（B）为起点（顶点），可以求得各个结点到起点A(B)的最短时间，然后与题目中的约束条件进行对比计算后可以得到A(B)中队3分钟内110警车能够到达的范围，并且根据此算法最终可以找出A（B）中队出警时间最长的地点。 关键词： Dijkstra标号法 图与网络分析 Matlab 一、问题的重述 为了维护城市治安、打击犯罪，某市公安巡特警大队在市区主要街道执行日常巡逻任务。图1为该市巡特警大队划分给巡特警中队A和巡特警中队B共同负责日常巡逻的街区。设巡特警中队A的日常办公与停车地点位于L4路左侧H4路和H5路的正中，巡特警中队B的日常办公与停车地点位于L12路左侧H2路与H4路的正中，如果规定正常情况下警用单人摩托巡逻车平均巡逻车速为每小时15公里（不包括穿马路时间，设穿马路直行需增加2分钟，左拐弯需增加3分钟，右拐弯需增加0.5分钟，），警用单人摩托车巡逻密度要达到至少20分钟有一辆车通过，其中粗实线道路要求每隔20分钟双向均有巡逻车通过，细实线道路每隔20分钟只需任意一个方向有巡逻车通过。110警用汽车主要执行增援任务，要求接警后3分钟内赶到增援地点（不管摩托车还是汽车市区理论最高车速每小时60公里，接警后由市公安局110指挥中心统一指挥），110警用汽车平时可以停在巡特警大队部（位于H12路南侧L8路以东3000米处，过L13路向东还要穿过3个十字路口）、也可以停在行动小组A或B的办公楼停车场内。110警用汽车也可以代替摩托车执行巡逻任务。设图中实线是需要执行巡逻任务的市区主要街道，均为双向道路；虚线是不需要巡逻的次要街道或分属其他行动小组管辖的街道，部分带箭头的道路为单行线，巡逻车也可以在这些虚线道路上上按规定方向借道