交巡警服务平台的设置与调度数模论文.doc

交巡警服务平台的设置与调度数模论文交巡警服务平台的设置与调度摘要本文讨论了交巡警服务平台的设置和调度问题。交巡警在日常道路管理中发挥着不可替代的作用，但警务资源有限，为了使警务资源发挥作用最大必须对有限的交巡警服务平台、平台管辖范围、警务资源等进行合理配置。在问题一第1问中要对交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。我们将其转化为最短路径问题应用Floyd算法求出A区每个道路结点到交巡警平台的最短路径，通过任意节点归离它最近的服务平台管理的原则将其分配给该交巡警平台管辖。在问题一第2问中我们提出了两个中不同的模型，分别针对总体出警时间和个体出警时间，第一种方案最快完成封锁需，第二种最快完成封锁的时间为8分钟，因此选后者最为最佳解决模型。具体调配方案见表1右侧。在问题一第3问中，我们以方差作为衡量交巡警服务平台的工作量的标准，以出警时间尽量小于三分钟作为控制出警时间的标准，建立优化模型，在MATLAB的计算下得出：再增加5个交巡警服务平台,分别在节点39、48、58、68、87能使工作量均衡量最小，方差从8.43314降到2.89。 在问题二第1问中，对各区交巡警服务平台设置是否合理分为两个方向，其一为交巡警服务平台设置数目是否合理，其二为交巡警服务平台设置的地理位置是否合理。对前者采用主成分分析法，对后者沿用问题一中的模型，经分析可知其平台设置不合理，需改进，我们在满足出警时间尽量在3分钟内、保证各交巡警服务平台工作量均衡的原则下提出了解决方案，即增加市区服务平台数，最后结果显示，我们的解决发案是各区平台方差明显下降，超出3分钟出警时间点明显减少。在问题二第2问中，该问题实质为指派问题,使用 0-1规划解决交巡警服务平台是否对嫌疑犯进行搜捕的问题,实现三分钟后交巡警可以在较短的时间内搜捕到嫌疑犯。 关键字最短路径，Floyd算法，优化，主成分分析法，0-1规划1问题重述11问题背景“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。12问题内容现需建立数学模型解决以下问题：（1）图一给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。图1：A区的交通网络与平台设置的示意图图2：全市六区交通网络与平台设置的示意图说明：（1）图中实线表示市区道路；红色线表示连接两个区之间的道路；（2）实圆点“”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；（3）星号“*”表示出入城区的路口节点；（4）圆圈“”表示现有交巡警服务平台的设置点；（5）圆圈加星号“* ”表示在出入城区的路口处设置了交巡警服务平台；（6）附图2中的不同颜色表示不同的区。2模型假设（1）假设该市每条道路路况相同；（2）假设警车在每条路况中都保持60km/h（即1000m/min）的速度；（3）假设交巡警到达了某条路段的交叉路口节点即控制了该路段；（4）假设交巡警工作地理范围仅为交通网络图中给出的道路范围； （5）假设交巡警处理案件的时间为定值；（6）假设计算交巡警工作量时不考虑行驶时间；（7）假设不同的区互相不管辖，同一个区仅管辖本区内的路口节点；（8）假设嫌疑犯以的速度逃逸。3符号规定区编号的交巡警平台的坐标，区编号的节点的坐标，编号的交警平台到达编号的节点的距离，单位：m编号的交巡警平台到达编号的节点的时间,单位：min警车速度，单位：1000m/min编号的交巡警平台管辖的道路结点的集合（建立模型时不包括点本身，最终结果中包含点）0-1变量各交巡警服务平台处理的案件次数的方差编号的交巡警服务平台管辖范围内编号点的案发率各节点平均案发率区内交巡警服务平台数4问题分析该题为典型的图论与资源合理配置的问题，我们运用经典的Floyd算法和动态规划解决分配交巡警管辖范围、警务调动、服务平台设置合理性分析等问题。41问题一的分析411问题一（）的分析问题一（）要为各交巡警服务平台分配管辖范围，我们将其转化为求最短路径问题，若使警车尽可能在三分钟之内到达事发地，即求出距离交警平台3000m之内的道路节点有哪些，若有道路节点距所有交警平台均大于3000m，则采取就近将其分配给距离最近的交警平台。412问题一（）的分析问题一（）要实现对13个路口的封锁，而实际中一个平台的警力最多封锁一个路口，为实现快速全封锁必须使封锁时间最短，现有两种模型：面向全体交巡警服务平台，实现总体调动时间最短,节省警务资源；面向一个交巡警服务平台，实现一个交巡警服务平台的调动时间最短。在结果中进行比较，选出较优方案。413问题一（）的分析问题一（）要解决交巡警服务平台的工作量不均衡和出警时间过长的问题，我们以每个交巡警服务平台处理案件次数的方差作为衡量工作量的标准，以交巡警到达管辖范围的最大时间小于作为衡量出警时间的标准，优化求解增加的交巡警平台数以及增加的具体位置。42问题二的分析421问题二（）的分析 由上题可知交巡警服务平台设置要求即保证出警时间较短、保证各交巡警服务平台工作量均衡。使用主成分分析法对各区交巡警服务平台设置数目是否合理进行分析；沿用问题一第三问模型对各区交巡警服务平台地理位置的设置是否合理进行分析，并对不合理的设置给出具体的解决方案。422问题二（）的分析 要实现对嫌疑犯的快速搜捕，应确定三分钟之内嫌疑犯可能到达的路口节点，再根据这些节点确定搜捕方案。5模型的建立与求解51问题一的模型建立与求解：分配各交巡警服务平台的管辖范围511数据的基本处理在MATLAB中引用Excel表格将每两个相邻节点（车辆通过时不经过第三个节点）的距离计算出来；在算法中引入，对于相邻的两个节点记为，对于不直接相连的两个节点记为；假设该图邻接矩阵为,存放各节点之间的距离，其中 ； ； ； 又该图为无向图，为对称矩阵，。51.2模型的建立要保证警车尽量会在3分钟内到达突发事件现场，则有： 找出相应的点对应点：（一）当对应唯一一个点时，则；（二）当对应多个点时，；（三）当没有对应的点时，采取就近原则，。求解结果：；。具体管辖散点图见下图：图3.合理的调度方案51.1数据处理在该题的解答过程中引入0-1变量，对没有经过的相邻节点记为0，对被经过的两个相邻节点记为1，其中 ：编号为的交巡警服务平台，； ：第个出入区的路口标号，其对应的路口标号为51.2两种模型的建立与比较建立：模型一：面向全体交巡警服务平台，实现总体调动时间最短实质为优化问题，其模型为： 模型二：面向一个交巡警服务平台，实现最后完成调度的交巡警服务平台调动时间最短，即最终完成调动时间最短。实质为优化问题，其模型为： 经LINGO和MATLAB计算后可得：模型一模型二出入区路口编号时间/min出入区路口编号时间/min211383.9288113624.8413620.35211383.928512482.475833166.02710300.5831512482.47892910.4930610303.293161.532579298.0155105227.7079105227.7079117243.8053117243.8053136230.5126236.477142140131125.97712112014421 3.265 158284.7518158284.75181642110.0060162146.7117表1模型一时间总计：，出警最短时间为；模型二时间总计为，出警最短时间为。比较：针对总体考虑时，模型一时间较短，但其出警时间较长；针对个体考虑时，模型二出警时间较短，但其总体调度时间较长。按照“尽快出警”原则，当发生重大突发事件时，应在最短的时间内封锁路口，模型二比模型一更符合题意，因此我们选择模型二，具体调配方案见表1右侧。确定需要增加平台的具体个数和位置51.1模型的建立若使各交巡警服务平台工作量均衡，则有方差取最小值；若使出警时间较短，则应满足交巡警服务平台到其管辖的节点最长时间尽量小于。方差计算方法： 优化模型： 对于：当对应唯一一个点时，则；当对应多个点时，；当没有对应的点时，采取就近原则，。求解结果：新增交巡警服务台编号：39、48、58、68、87 原始方差：8.4314 新增结点后方差：2.89新增交巡警服务台后其管辖节点及时间分别为：编号案发率123456789101112131415，16171819203948586787表2由上表可知，增加新交巡警服务平台之后仅有编号15的交巡警服务平台到达其管辖节点时间较长，大于三分钟。52问题二的模型建立与求解合理性分析52.1模型的建立按照要求，交巡警平台的设置主要遵循以下原则1:1、警情主导警务原则：根据管区道路交通流量、拥堵状况、治安复杂情况、发案量高低，科学确定平台管控区域； 2、快速处警原则：城区接警后确保快速到达现场； 3、方便与安全原则：按照醒目、规范，方便群众和确保安全的原则，科学设置平台。 平台设置在遵循上述三大原则的基础上，应当结合辖区地域特征、人口分布、交通状况、治安状况和未来城市发展规划等实际情况，在充分考虑现有警力和财力并确保安全的条件下，科学确定平台的数量和具体位置。先对题目中给出的各区的交巡警服务平台分配管辖范围，模型沿用问题一第一问。对交巡警平台设置数目的合理性分析（主成分分析）：交巡警服务平台的设置数目主要与该区面积、人口、工作量（案发率）、工作量方差等有关。 区域编号 指标ABCDEF地域面积/22.00 103.00 221.00 383.00 432.00 274.00 人口/万人60.00 21.00 49.00 73.00 76.00 53.00 区域每天总发案次数117.75 66.40 187.20 67.80 151.17 96.92 工作量均值a/每天发案率5.89 8.30 11.01 7.53 10.08 8.81 工作量方差8.43 15.46 32.14 12.77 15.20 30.00 出警时间大于3的节点数6.00 4.00 43.00 12.00 29.00 34.00 表3用表示区，各区的地域面积、人口数、区域每天总的发案次数、工作量均值、工作量方差、出警时间大于3的节点数的取值分别记作，构造矩阵（1）数据标准化处理：对原始数据标准化处理，将各指标值转化为标准化指标，有： 其中：即为第个指标的样本均值和样本标准差。对应地称 标准化指标变量。（2）计算相关系数矩阵:相关系数矩阵，有 其中：是第个指标与第个指标的相关系数。（3）计算特征值与特征向量计算相关系数矩阵的特征值及对应的标准化特征向量，其中，由特征向量组成3个新的指标变量 其中：是第1主成分，是第2主成分，,是第6主成分。（4）选择个主成分，计算综合评价值。计算特征值的信息贡献率和累积贡献率。称 为主成分的信息贡献率；并且称 为主成分的累积贡献率。当接近于1时，选择前个指标变量作为个主成分，代替原来的指标变量，从而对个主成分进行综合评判。计算综合得分： 其中为第个主成分的信息贡献率，根据综合得分值就可进行评价。经MATLAB计算后，以四个主成分的贡献率为权重，构建主成分综合评价模型： ，把各区的四个主成分值代入上式，可以得到各区的排名和综合评价结果，如下表所示：不合理度排名CEFDAB综合评价值1.19311.09320.3389-0.1788-0.9783-1.4681表4由上表可知，C、E两区交巡警平台设置数目较不合理。对交巡警平台设置地理位置的合理性分析：本模型沿用问题一第三问的模型，分别对六个区进行合理性评价：计算各交巡警服务平台工作量方差及出警时间： 其中：区交巡警服务平台工作量方差； ：区交巡警服务平台编号； ：区非交巡警服务平台编号； ：编号的交巡警服务平台所管辖节点的案发率； ：区每个节点（路口）平均案发率； ：区交巡警服务平台个数。对于：当对应唯一一个点时，则；当对应多个点时，；当没有对应的点时，采取就近原则，。经MATLAB计算后得： 区号评价指标ABCDEF方差8.431415.456732.1398512.76515.198330.0042工作量均值5.88758.311.011767.53333310.077788.811111出警时间3的点数6443122934表5 由上表可知C、E、F、B四区工作量较大，C、E、F三个区有较多的路口节点无法满足出警时间尽可能小于三分钟的条件。52.2解决方案针对工作量较大、出警时间较长、交巡警服务平台设置较少等问题，参照问题一第二问的解决方案，在某些路口节点增设交巡警服务平台，使得各区每个交巡警服务平台工作量均值减小、方差减小，同时保证出警时间减短。沿用问题一第二问的模型，现得出解决方案如下表： 各区编号项目ABCDEF增加点数5312365改进前工作量方差8.4315.4632.1412.7715.2030.00改进后工作量方差2.877.435411.1998.114.73337.16改进前工作量均值5.898.3011.017.5310.088.81改进后工作量均值4.985.5083334.4666675.656.2166675.783333改进前大于3点数6.004.0043.0012.0029.0034.00改进后大于3点数2212597表6新增加的点对应原图中的编号为：改进后前后对比折线图如下：其中横坐标分别代表六个区图4图5图6围堵方案52.1模型的建立沿用第一问的程序，求出嫌疑犯在三分钟之后仍在区内。设编号为的交巡警平台到达围捕节点的时间为，凶犯到达点的时间为，建立0-1变量，当调动点交巡警时，反之为0；当嫌疑犯到达点时，反之为0可建立模型如下： 经（暂未求出）6模型的评价与推广评价：评价交巡警平台设置是否合理主要有“质”“量”两个指标。“质”又分为两个小指标，其一为出警时间，其二为工作量均衡；“量”即交巡警服务平台的数量是否与该区面积人口相适宜。我们在建立模型的过程中全面参考了题目中给出的数据，以最短路径Floyd算法解决出警时间问题，以方差来衡量各区工作量是否均衡的问题，用主层次分析交巡警服务平台数目设置是否合理。针对出警时间问题，由图中给出的路口节点数据可以得知总有一些节点距离其他点较远，无法实现出警时间小于三分钟的要求；使用方差衡量工作量不均衡时，每当增加一个交巡警服务平台就会使方差减小一定数值，在计算过程中我们没有排除数量增加导致的方差减小的干扰因素；在对整个市区交巡警服务平台设置是否合理进行评价时，我们参考了改进后的区工作量均值，而没有给出实际应该参考的理论值。推广： 本题解决了城市规划中关于站点设置的问题，在实际生活中，该模型也可以用于其他规划问题。7参考文献1 2 数学建模算法与应用，司守奎、孙玺菁，国防工业出版社8.附录81附录清单811求解问题一第一问的MATLAB程序；812求解问题一第二问的MATLAB程序；812求解问题一第二问的MATLAB程序；813求解问题二第一问的MATLAB程序；814求解问题二第二问的MATLAB程序；82附录正文821.1求解问题一第一问的MATLAB程序；clc,clearx=413.0000 403.0000 383.5000 381.0000 339.0000 335.0000 317.0000 334.5000 333.0000. 282.0000 247.0000 219.0000 225.0000 280.0000 290.0000 337.0000 415.0000 432.0000. 418.0000 444.0000 251.0000 234.0000 225.0000 212.0000 227.0000 256.0000 250.5000. 243.0000 246.0000 314.0000 315.0000 326.0000 327.0000 328.0000 336.0000 336.0000. 331.0000 371.0000 371.0000 388.5000 411.0000 419.0000 411.0000 394.0000 342.0000 . 342.0000 325.0000 315.0000 342.0000 345.0000 348.5000 351.0000 348.0000 370.0000 . 371.0000 354.0000 363.0000 357.0000 351.0000 369.0000 335.0000 381.0000 391.0000 . 392.0000 395.0000 398.0000 401.0000 405.0000 410.0000 408.0000 415.0000 418.0000 . 422.0000 418.5000 405.5000 405.0000 409.0000 417.0000 420.0000 424.0000 438.0000 . 438.5000 434.0000 438.0000 440.0000 447.0000 448.0000 444.5000 441.0000 440.5000 . 445.0000 444.0000;y= 359.0000 343.0000 351.0000 377.5000 376.0000 383.0000 362.0000 353.5000 342.0000 . 325.0000 301.0000 316.0000 270.0000 292.0000 335.0000 328.0000 335.0000 371.0000 . 374.0000 394.0000 277.0000 271.0000 265.0000 290.0000 300.0000 301.0000 306.0000 . 328.0000 337.0000 367.0000 351.0000 355.0000 350.0000 342.5000 339.0000 334.0000 . 335.0000 330.0000 333.0000 330.5000 327.5000 344.0000 343.0000 346.0000 342.0000 . 348.0000 372.0000 374.0000 372.0000 382.0000 380.5000 377.0000 369.0000 363.0000 . 353.0000 374.0000 382.5000 387.0000 382.0000 388.0000 395.0000 381.0000 375.0000 . 366.0000 361.0000 362.0000 359.0000 360.0000 355.0000 350.0000 351.0000 347.0000 . 354.0000 356.0000 364.5000 368.0000 370.0000 364.0000 370.0000 372.0000 368.0000 . 373.0000 376.0000 385.0000 392.0000 392.0000 381.0000 383.0000 385.0000 381.5000 . 380.0000 360.0000;n=1.72.12.21.72.12.52.42.42.11.62.62.42.22.52.12.62.51.91.81.91.41.42.41.11.61.20.81.31.42.11.61.51.41.71.41.10.11.21.41.71.41.41.71.11.41.21.61.41.21.10.80.61.40.910.50.81.10.90.70.61.21.40.80.70.80.80.91.10.91.10.80.91.10.81.10.80.80.80.81.41.10.911.21.41.10.91.40.90.90.8;for i=1:92 for j=1:92 d(i,j)=sqrt(x(j)-x(i)2+(y(j)-y(i)2); endendn=xlsread(B题附件2_全市六区交通网路和平台设置的数据表.xls,全市交通路口的路线,A2:A144);m=xlsread(B题附件2_全市六区交通网路和平台设置的数据表.xls,全市交通路口的路线,B2:B144);s=zeros(92,92);for i=1:143 if m(i)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); end end endendt=a/10;for j=21:92 c(j-20),I(j-20)=min(t(1:20,j);%I显示的管理点，c是相应的时间；end821.2求解问题一第二问的MATLAB、LINGO程序MATLAB:clc,clearx=413.0000 403.0000 383.5000 381.0000 339.0000 335.0000 317.0000 334.5000 333.0000. 282.0000 247.0000 219.0000 225.0000 280.0000 290.0000 337.0000 415.0000 432.0000. 418.0000 444.0000 251.0000 234.0000 225.0000 212.0000 227.0000 256.0000 250.5000. 243.0000 246.0000 314.0000 315.0000 326.0000 327.0000 328.0000 336.0000 336.0000. 331.0000 371.0000 371.0000 388.5000 411.0000 419.0000 411.0000 394.0000 342.0000 . 342.0000 325.0000 315.0000 342.0000 345.0000 348.5000 351.0000 348.0000 370.0000 . 371.0000 354.0000 363.0000 357.0000 351.0000 369.0000 335.0000 381.0000 391.0000 . 392.0000 395.0000 398.0000 401.0000 405.0000 410.0000 408.0000 415.0000 418.0000 . 422.0000 418.5000 405.5000 405.0000 409.0000 417.0000 420.0000 424.0000 438.0000 . 438.5000 434.0000 438.0000 440.0000 447.0000 448.0000 444.5000 441.0000 440.5000 . 445.0000 444.0000; y= 359.0000 343.0000 351.0000 377.5000 376.0000 383.0000 362.0000 353.5000 342.0000 . 325.0000 301.0000 316.0000 270.0000 292.0000 335.0000 328.0000 335.0000 371.0000 . 374.0000 394.0000 277.0000 271.0000 265.0000 290.0000 300.0000 301.0000 306.0000 . 328.0000 337.0000 367.0000 351.0000 355.0000 350.0000 342.5000 339.0000 334.0000 . 335.0000 330.0000 333.0000 330.5000 327.5000 344.0000 343.0000 346.0000 342.0000 . 348.0000 372.0000 374.0000 372.0000 382.0000 380.5000 377.0000 369.0000 363.0000 . 353.0000 374.0000 382.5000 387.0000 382.0000 388.0000 395.0000 381.0000 375.0000 . 366.0000 361.0000 362.0000 359.0000 360.0000 355.0000 350.0000 351.0000 347.0000 . 354.0000 356.0000 364.5000 368.0000 370.0000 364.0000 370.0000 372.0000 368.0000 . 373.0000 376.0000 385.0000 392.0000 392.0000 381.0000 383.0000 385.0000 381.5000 . 380.0000 360.0000;for i=1:92 for j=1:92 d(i,j)=sqrt(x(j)-x(i)2+(y(j)-y(i)2); endendn=xlsread(B题附件2_全市六区交通网路和平台设置的数据表.xls,全市交通路口的路线,A2:A144);m=xlsread(B题附件2_全市六区交通网路和平台设置的数据表.xls,全市交通路口的路线,B2:B144);s=zeros(92,92);for i=1:143 if m(i)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); end end endendt=a/10;zz=12 14 16 21 22 23 24 28 29 30 38 48 62;for i=1:20 for j=1:13 z(i,j)=t(i,zz(j) endendzzLINGO：模型一：model :title 封锁路径最快问题;sets:plot/1.13/:a;plot2/1.20/:b;links(plot2,plot):c,d;endsetsdata:c=22.2362 16.0285 9.2868 19.2934 21.0962 22.5018 22.8932 19.0012 19.5158 12.0834 5.8809 11.8501 4.8852 20.4639 14.1297 7.3881 17.3947 19.1975 20.6030 21.1210 17.2289 17.7436 10.3112 3.9822 10.3095 6.0351 18.3523 12.7672 6.0256 16.0322 17.8350 19.2405 19.0093 15.1173 15.6319 8.1996 6.0938 8.1979 4.3934 21.9974 15.0085 8.2669