数学建模 最短路程

1、交巡警服务平台的设置与调度摘要本论文主要是关于图论中的“最短路径问题”和“最优搜索问题”。问题所述的模型已经很自然地用图表示出来，所以我们运用图的性质和算法来求解问题。图论中求最短路径通常采用dijkstra算法，但本题涉及的交巡警平台数量较多，即求多个源点到其它所有顶点的距离，所以采用floyd算法求解比较简单，其基本思想是通过程序得到每个节点到其他节点的最优距离。针对问题一，用floyd算法算出每个交巡警平台3分钟内所能到达的全部节点，这些节点就是平台的管辖范围，但仍有3分钟内不能到达的节点，这些节点处就应该增设交巡警服务平台。在快速封锁13条交通要道时，要遵循封锁时间最短、每个平台的警力

2、最多封锁一个路口的原则，运用LINGO程序解答。最后分析得到出警时间至少大于3分钟的节点，及工作量最大的平台，在这些节点处需要增加3个服务平台。针对问题二，需要对发案率进行降序排列，筛选出发案率较高，但是未设置交巡警服务平台的节点。根据六个城区的基本数据，得到每个平台管辖的面积和人口，比较各平台的工作量，从而找出不合理的理由。在搜捕犯罪嫌疑人时要遵循两个原则：搜捕时间最短和围堵区域最小。根据逃犯的位置和逃跑的可能路径建立关于时间T的目标函数和初始概率密度函数，对交巡警的搜捕区域建立探测函数，模型应该满足以下约束条件：最后运用拉格朗日乘数法求得围堵嫌疑人的最佳围堵方案。模型的建立提高了交巡警服务

3、平台的工作效率，同时这个模型也可以运用于最优选址、搜索正在执行任务的敌方潜艇等问题，并可将该模型的算法扩展到其他领域。关键字：交巡警 最短路径 最优搜索 动态规划 floyd算法 1、问题重述交巡警为了更有效地贯彻落实四大职能，需要在市区的交通要道和重要部位设置交巡警服务平台。在警力、管辖范围、封锁能力、搜捕能力等方面有三个基本要求：每个平台的职能和警力配备基本相同、出现突发事件时能够及时赶到事发地、一个平台的警力最多封锁一个路口。问题1：根据附件中给出的中心城区A的交通网络图和现有交巡警服务平台设置情况，分配各平台的管辖范围，使其能在3分钟内赶到管辖区所在的事发地。问题2：发生重大事件时如何

4、调度A区20个平台的警力资源，对该区的13条交通要道实现快速封锁。问题3：根据现有平台的工作量不均衡和出警时间过长的情况，拟在该区再增加2至5个平台，确定增加平台的个数和位置。问题4：分析全市交巡警平台设置方案的合理性，并改正不合理的地方。问题5：该市P点处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已经驾车逃跑。调度全市警力，设计最佳的围堵方案。2、 模型假设1、 警车在出警过程中速度恒为60km/h，不会出现堵车或抛锚等现象。2、 每个路口节点至少有一个交巡警服务平台管辖。3、 交通网络图中两个节点间的道路视为直线段。4、 每个交巡警服务平台的职能和警力配备基本相同。3、参数说明

5、：A区节点的横坐标：A区节点的纵坐标：两节点间的距离:事发地到交巡警服务平台的最大距离:交巡警平台到A区各交通要道的距离：出警时间或者搜捕犯罪嫌疑人的时间 ：犯罪嫌疑人的初始位置：交巡警所在位置 ：初始概率分布函数 ：犯罪嫌疑人逃跑的速度 ：交巡警搜捕到犯罪嫌疑人的概率 ：由搜捕环境所决定的常量 ：拉格朗日乘子:资源（警力，时间）上限：交巡警空间坐标的一个常量pf：最大探测概率4、模型分析及求解通过对题目所给数据的处理，得到中心城区A的每对起点标号和终点标号间的距离。运用这些距离求出每个交巡警服务平台所管辖的区域，从而为分析交巡警服务平台设置方案的合理性提供依据。根据逃犯的位置和路径建立概率密

6、度函数，对交巡警的搜捕区域建立探测函数，最后运用拉格朗日乘数法得到动态规划的约束条件，用解决动态规划的方法来制定搜捕犯罪嫌疑人的方案。4.1分配各交巡警服务平台的管辖范围中心城区A的每对起点标号和终点标号间的距离在平台的分配管辖范围内，出现突发事件，要求交巡警能在3分钟内到达事发地，且警车时速为60km/h，即平台到所管辖的每个路口节点的距离不超过3km（地图上为30mm）。从全市交通路口线路中筛选出中心城区A的所有交通路口，已知每个节点的坐标，由MATLAB程序和两点间距离公式：S= 公式（11）得到每对起始标号和终点标号间的距离。（见附录：表一） 建立“覆盖圆”以交巡警平台为圆心，以长为3

7、0mm的射线为半径做一个圆。这个圆面所“覆盖”的节点即为平台所管辖的范围。由matlab程序（见附录：程序二）和数据统计得到表二：表二 平台管辖范围表平台编号位置标号管辖范围A11169747576A222434470A3334445666768A444576062636465A5554950515253A666545556575859A7772930323334A8884748A999343537A101010A111111262728A12121225A131313222324A14141421A15151531A16161614363839A171717404142437273A1818

8、18808182838485A1919197779A202020868788899091924.2 警力调度方案本题要求给出该区巡警快速封锁13条交通要道的方案，由于各平台到要道的距离不等，故所用的时间也不一样。由“木桶效应”可知总量取决于最小的一个分量，此题相反：最快封锁全部要道的时间取决于用时最多的那一组交巡警。因此，总方案应使每一组巡警到交通要道的时间尽量短。根据上一小题我们知道每一组巡警的管辖范围，故可以首先调度部分交巡警到其所管辖的范围。由于一个平台的警力最多封锁一个路口，但是有的巡警管辖范围内不止一个要道，所以只能调其附近平台的警力来封锁。建立“网格型线路“，以巡警平台为起点，要道

9、为终点。每两个点之间用距离公式求解，路线的总长度为各段距离之和，挑选出那些线路距离小的线路。S= 公式（12） 调度方案的关键是：调度的警力离始发地距离L最短。最短距离用LINGO程序求解。（见附录：程序三）调度方案如表三：表三 调度方案表巡警平台 经历的路口 要到达的要道 4 16 16 38 8 93536 16 14 14 13 23 12 25 24 11 21 15 28 7 30 29 5 477 30 6 47 48 10 2627 22 9 34102627 124.3在A区增加交巡警平台统计各交巡警平台管辖的节点数可得图一：图一 平台管辖节点数平台A4、 A6、 A17、 A

10、18、 A20管辖的节点都大于7，而平台A10、 A12 、A14 、A15管辖的节点都小于3，工作量不均衡。节点29、30、60、61、62、90、91、92等的出警时间都超过了3分钟，出警时间明显过长。节点30、60、90处出警时间过长并且平台A4、A6、A20的工作量大，因此可以在节点60、30、90处分别设立一个交巡警平台，共计增加了3个平台。4.4 探讨现有交巡警服务平台设置方案的合理性设置交巡警服务平台的原则和方案具体如下：a.每个交巡警服务平台的职能和警力配备基本相同；b.管辖范围内出现突发事件时能够在3分钟内有交巡警到达事发地；c.重大突发事件时，全市所有警力要对所有出入市区的

11、交通要道实现快速封锁；d.每个平台承担的工作量应该基本相等。交巡警服务平台的设置要服从快捷性，该题要求根据设置交巡警服务平台的原则和任务分析平台设置的合理性，题中限制条件是：各交巡警服务平台在所管辖的范围内出现突发事件时，能在3分钟内到达事发地。针对此题，可以将全市分为6个区进行分析，具体步骤如下：计算各区交巡警服务平台在3分钟内到达事发地的比例： 由于计算距离信息比较容易，所以将时间限制转化为距离限制，即交巡警服务平台到事发地的距离在限制的距离内才可能在规定的时间内到达。设事发地到交巡警服务平台的最大距离为R,该题的速度为60 km/h,则最大距离为：km各区的交巡警服务平台数和平台能够到达

12、的节点已知，可以利用Floyd算法计算3分钟内交巡警服务平台能够到达的各节点的最短距离，将最短距离和3km进行比较，如果最短距离大于3km，则不满足条件，统计满足条件的节点，然后将能到达的节点数除以交巡警服务平台所能到达的所有节点数，得到服务平台在3分钟内能到达事发地的比例，根据比例的大小即可以看出交巡警服务平台设置的合理性（比例越大代表设置得越合理）。 筛选出平台覆盖率小于90%的区域： 计算出各区交巡警服务平台的覆盖比率，由于不可能都达到100%，所以设置为90%，筛选出比率在90%以下的区域。以及全市交通路口节点数据筛选出发案率大于1.6，但是未设立交巡警平台的节点（见附录：表四）统计表

13、四可得各区域发案率大于等于1.6，但是没有设立交巡警服务平台的节点个数见图二：图二 各区未设平台节点数由图二可知：区域A、E某些节点发案率较高但是未设立交巡警服务平台的节点个数较多，所以在发生突发事件时很难在3分钟内到达事发地，综合上述分析可知：交巡警服务平台设置不合理。 筛选出工作压力大的区域：根据各个城区的平台数、面积、人口分析得到平均每个平台管辖的面积和人口如表五： 表五 平台工作压力表全市六个城区平台个数每个平台管辖的面积（平方公里）每个平台管理的人数（万）A201.103.00B812.882.63C1713.002.89D2614.732.81E1528.805.10F1617.1

14、33.31从表五中可以知道：在全市的六个区中，只有B区设置的平台个数为一位数，除了A和E区外，其余的四个区域每个平台管辖的面积都是十几平方公里，A区每个平台管辖的面积最少，仅有1.10平方公里，所以A区的交巡警服务平台的工作强度不大；区域E中每个平台的管辖面积为28.80平方公里，远远大于其他地区，在警力配备基本相同的情况下，倘若发生突发事件，交巡警无法在3分钟内赶到事发地点。除了区域E外，每个交巡警平台管理的人数在3万人左右，只有区域E每个交巡警平台管理的人数为5.10万人，相对而言管理的人数就比较多，会导致管理效率降低，发生重大事件时形势难以控制，这两个不合理的地方都增加了平台的工作量 确

15、定需要设置的交巡警服务平台的个数： 将筛选出的区域分别求解，将交巡警服务平台在3分钟内到达事发地的比例限制在90%，然后利用Matlab计算出满足条件的各区的最少平台数，用最少平台数减去各自区域所设置的平台数得到的值即是各区所需要设置的平台个数。4.5 追捕犯罪嫌疑人的最佳围堵方案本问是“最优搜索”问题中的“双边搜索”，逃犯企图逃避被发现，甚至反击交巡警。最优搜索问题包括三个基本要素：其一、犯罪嫌疑人位置和移动路径的初始概率分布。其二、探测函数。假定犯罪嫌疑人确实位于某个区域，则将投入这个区域搜索的资源（如时间）与成功搜索到目标的概率之间的函数关系建立成为探测函数。其三，对时间警力的约束条件。

16、搜索不可能无休止的进行下去，搜索的时间、人力资源都是受到限制的。给定探索函数和目标函数的概率分布后，最优搜索理论要解决的核心问题就是在各平台警力和配备一定的情况下，如何分配警力资源使得成功搜索到犯罪嫌疑人的可能性最大，或搜索代价最小。利用以上搜索理论进行问题优化的关键是建立合理的数学模型：概率密度函数已知犯罪嫌疑人位于空间Rn的某个子集A中，它的初始位置用向量X表示，各交巡警平台的初始位置用向量Z表示： 公式（13） 通常情况下，这个向量不能准确给出，为了描述逃犯位置的不确定性，我们用初始概率分布函数表示，定义如下： 公式（14） 概率密度函数定义如下： 公式（15） 探测函数探索问题的第二个

17、要素是探测函数。探测函数给出将投入到整个城区的时间与给定犯罪嫌疑人位于该区域时成功探测到该逃犯的可能性大小联系起来的函数关系。探测函数是指逃犯落在某一区域内，交巡警在该区域上进行搜索后发现犯罪嫌疑人的概率，用函数b表示，。这里的假设条件是探测到犯罪嫌疑人的概率仅与分配的警力有关，与分配的方式无关。在离散搜索空间中有： 公式（16）探测函数是搜索问题中的一个基本要素，我们运用视觉探测模型如图三：OhSab图三 探测模型示意图假设犯罪嫌疑人位于平面上的X点，交巡警的位置在空间Z点处，探测函数b与嫌疑人所在平面和交巡警与目标位置所在直线的立体角成正比例。即： 公式（17）其中k是一个由搜索环境所决定

18、的常量。如图32，当a, b的值相对于h, r, s非常小时，立体视觉可以定义为之积。 公式（18）因为是嫌疑人与交巡警在平面的投影距离，且在一般情况下有，因此有： 公式（19）所以该模型被称为探测法则。 用拉格朗日乘数法用于解决任意目标函数min(t)在任意实数集上的带约束的问题，按照前面的定义： 公式（110）得到最大探测概率pf且满足约束条件： 公式（111）其中K是资源（警力，时间）上限。构造拉格朗日函数l如下： 公式（112）其中叫做拉格朗日乘子，它是一个参数。交巡警要想成功抓获嫌疑人必须满足一下约束条件： 公式（113） 利用附件的数据及以上模型分析可得：A区与D、C、F、E区邻接

19、。固嫌疑犯只能向D、C、E、F四个方向逃去。在A区去往E的道路上设置了多处交巡警服务平台，且与P点相距很近，固不能逃亡E区。由A区通往E区、F区各有两条路，均在离P很近的敌方设有平台。嫌犯唯一能够逃离A区的路径只能是C区，由于3分钟后才接到报警，故嫌疑犯能够骗过他附近的交巡警平台进入到C区，最后很可能从237号节点逃走。所以应该尽可能的多调集警力到C区增援。5、模型评价但总的来说，整个模型的思路清晰，遵循了可操作性原则、科学性原则、可比性原则，该模型建立了在较理想状态下交巡警服务平台的最优设置，减少了出警时间，提高了出警效率，可以给生活中交巡警平台的设立一些参考，具有一定的实用价值。另外还设计

20、了一套搜捕犯罪嫌疑人的方案，可使交巡警在接到任务后更好的在较短时间分配救援力量，选择最佳行进路径，以争取更多的时间执行任务，取得更好的执行效果。6、模型应用本模型较好地解决了公交司机排班的最优化问题。随着南昌市经济的迅速发展，人口增加人流量增大，公交线路的正常运营时畅通城市的有力保障。该模型也可以运用到其他优化问题中去，比如：酒店、百货公司工作人员的排班问题，某些人力、物力资源的合理配置问题等。本模型较好的解决了交巡警平台的最佳选址问题，当事故发生时，交巡警可以在第一时间到达事发地点，有效的改善了交巡警在执行任务中的效率。在经济迅猛发展的今天，城市加速扩展，人口迅速增长，交巡警平台的设置是平安

21、城市的最好保障，该模型也可以运用到其他最优选址问题中去，比如：关于消防救援工作最优路径问题、重大生产安全事故应急救援问题、公共交通的最优路径问题、工厂假设最优选址问题等。搜捕犯罪嫌疑人的模型也可以用于其他领域。对静止目标的搜索，如搜索沉落海洋的失事传播、搜索工厂污染源；对机动目标的搜索，即搜索目标的运动规律对搜索者是可知的，并不是不变的，如搜索在海上迷失方向的船舶；对规避目标的搜索：被搜索目标企图逃跑避免被发现，甚至反击搜索者，搜索者与被搜索目标之间是敌意的、非合作的、双方是搜索与逃避的关系，如搜索正在执行任务的敌方潜艇。7、参考文献【1】韩中庚，数学建模方法及其应用，北京：高等教育出版社，2010年11月。【2】杨启帆、何勇、谈之奕，数学建模竞赛，浙江：浙江大学出版社，2005年7月。【3】赵静、但琦，数学建模与数学实验，北京：高等教育出版社，2003年6月。【4】曹吉利、张东生、赵临龙，数学模型方法及其应用，重庆：重庆大学出版社，2005年3月 【5】肖华勇，基于MATLAB和LINGO的数学实验，西安：西北工业大学出版社，2009年3月附录表1：发案率大于1.6但是未设立交巡警服务平台的