~~对于i：K~， 即；对于 即K(x?j,y?j)?K(xj,yj)。 j：K~?KK(x,y)?K(x,y)?Kj，??iiiiiij其中，K?xi,yi?表示第i个交叉路口坐标(xi?(0,500),yi?(0,600))；K(xi,yi)表示第i个交叉路口的邻接路口集合，坐标表示(xi?(0,500),yi?(0,600))。
可以得到各个路径之间的距离，再用Matlab编程使之在地图的道路上标出各自的76距离。 13.1529106.70823.5355 64截取第3661个交巡警服务平台周围设置点的图形以示说明：9.21953645.831362663.1623654.24263606735815.23983566935435214.76485.38526.40316.1033754.5277684.12317.0711789.300516.918919.72316.40314.472181156.265744.031173 ?100m） 71图 2 第1个交巡警服务平台的设置点距离图（单位：8.062370在点3501和点69之间道路的距离显示为5，加上单位即两点之间的距离为500米。
400405410米；415420之间的距离为425同样的，点1和点74之间的距离为626.5点15和点78640.31米；点11.62971和点75之间的距离为930.05米。以此类推，可以得到市中心区域A的各道路间的距
72离示意图（具体的图形见附录 1）。 7.61588.6023445.2 问题一
8.06235.2.1 A区各交巡警服务平台管辖范围合理的分配方案 9.48684246.31688.06231. Dijkstra算法
2843在分配A区各交巡警服务平台的管辖范围时，要遵守这样的原则和义务：交巡警服务平台在其所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。由此，我们给出了一个连接若干个交叉路口的节点的网络，在
9.8489这个网络的两个指定的节点间，找出一条最短路径。下面以交巡警服务平台设置点1为例。
G，以交叉路口的节点为图G的顶点,这些顶点包括交巡警服务平台设置点给定图19.144240.22441(记为u1)和不设交巡警服务平台的交叉路口的节点(依次记为v1~vn,n?1,?,i,?72)。
17各节点间的距离为图G相应两顶点间的边。对G的每一边e，赋与一个实数w(e)，称为
26.8794边e 的权，得到赋权图?G,E?。
8.5本文中我们规定边e的权为任意相邻两个交叉路口间的距离，记为l(i,40.07841
6
j)。下面我
们需要求得指定两点间的最小权，即最短路径。将u1,vi间路程的权记作d(u1,vi)。
为了计算出u1 到G的其余各顶点的最短路径和路程d(u1,vi)。首先我们构造出一个赋权临接矩阵W??wij?92?92，其中分量定义如下：
(1). 若交叉路口vi和vj之间有直接的道路连接，那么定义其边的权值为：w(e)i,j?l(i,j)。(2). 若交叉路口vi和vj之间没有直接的道路连接，那么定义其边上的权值为w(e)i,j??。 根据上面的定义我们可以得到：
??w?e?i,jwij?????ei,j?E;else。
其次，求最短路径本文采用众所周知的Dijkstra算法，该算法的基本思想分别从图G中的顶点ui出发，找出到其他各交叉路口间的最短距离，构成一个最小生成树。现将该算法叙述如下:
设u1直至vi前，会经过多个交叉路口，在选择哪一条路径前，我们先将各个有相邻边的交叉路口之间的距离可以按从大到小排列如下：
0?l1???lj???li,，
从而在算法实现中我们将点的排序与代换法解方程同时进行。下面是该算法的具体
步骤。
第一步：置l1?0，lj?w(e)1j,j?2,3,?,i，P?{1},S?{2,3?,i}，
第二步：对S??，使得lk?min{uj}。置P?P?{k},S?S?{k}。若S??，终止；
j?S否则,继续循环第二步。
第三步：对?j?S,置lj?min{lj,lk?w(e)kj}，然后返回第二步。
1这个算法经过n?1次循环后必结束。整个算法过程中，第2步要做(n?1)?(n?2)次
211比较，而第3步则分别要做(n?1)(n?2)次加法和(n?1)(n?2)次比较。因此，总的
22计算量O(n3)，依次求得u1 到G的各顶点的最短路径和距离（其具体的算法程序见附录 2）。
2. 各交巡警服务平台的管辖范围的分配
基于5.2.1中提到的原则，即当出现突发事件时，巡警车的时速为60km/h，并且要求尽量能在3分钟内到达事发地。也就是说，巡警车从各自的交巡警服务平台出发，到达事发地至多经过60km/h?3min?3km的路程。那么，在这个过程当中巡警车所经过的节点就属于各自的交巡警服务平台的管辖范围，而对超出这个范围的节点，将进一步
7
进行讨论。根据Dijkstra算法并且利用Matlab软件得到A区1-20号平台各自以3km为管辖范围所能管辖到的交叉路口的节点情况见附录 5，从中可以知道：在Q1~20平台以3km为管辖范围内A区仍旧有几个节点不能被包括。经过整理后可以知道这些不能到达的节点共有6个，序号分别为：28,29,38,39,61,92。现将不能到达的道路交叉口分别命名为：Q28、Q29、Q38、Q39、Q61、Q92。
为了处理这几个节点，本文采用最短路径优先原则找到与这些节点距离最近的平
7.5297.8102台，使这些节点属于离它最近的交巡警平台所管辖。以节点Q28为例，将图1 区域A6 16.0312575059的交通网络示意图中第28节点的图像扩大后得到下图 3。 37036074.32368.139413.89243.80792.9155625118.68153.58.48534.301212.379414.866110.4403410.35254.242664810.19814.560255647498.5447.07116.708295324.18683012.806222.803565.8315420.79667350340293309.486828103201247.51841511.401810.049945.60981532811.70475512.6595.0998.27653139.300529.42793338.183830.4138114611.597415.532242.46477.5664629.6816345.02499454.24266.7082355375.0993649.216435.01433917.677736.0828403834.0588416 从图
35.383633.0492m） 31067.4166图 3 节点Q28的局部图（单位：?10017.8885272602202402803003203407.4333中我们可以看到QQ15和Q7，其余的服务平台离119附近的交巡警服务平台有262820.0252518.0278节点Q28相对来说都较远。可以计算出节点Q28与节点Q15之间的路程为： 142432.695623.853721节点Q28与节点Q7之间的最短路径为28→29→30→7，所以最短的路程： 18.027822139.05545d2328?29?30?732.6497d28?15?47.5184，
?9.4868?74.3236?5.831?89.6414。
在这两条路线d28?…-m??d28?15,d28?29?30?7?min中选择较短的一条路径。此时，m取15。也就是说，节点Q28可以归类到平台Q15的管辖范围内。因此我们将交巡警服务平台Q15的管辖范围扩大到47.5184?100m?4.75184km。
由上方法类似可以得到，节点Q29距离最近平台也是Q15，将交巡警服务平台Q15的
8
管辖范围扩大至(9.4868?47.5184)?100m?5.70052km。
同理，节点Q38距离最近的平台是Q16，将交巡警服务平台Q16的管辖范围扩大至
3.40588km后能够将Q38管辖进去。距离Q39最近的平台是Q2，因此再继续将Q2的管辖
范围扩大至3.68219km。距离Q61最近的是Q4，将Q4的管辖范围扩大至5.21055km。距离Q92最近的是Q20，将Q20的管辖范围扩大至3.60128km。
综上所述，交巡警服务平台Q1~Q20中：Q4的管辖范围是5.21055km，Q15的管辖范围是5.70052km，Q2的管辖范围是3.68219km，Q20的管辖范围是3.60128km，其余的管辖范围都是3.00km。在这种分配方案下，除去Q28、Q29、Q38、Q39、Q61、Q92这几个点外其余的都能够在3min钟之内赶到。 3. 被重复管辖节点的分配原则
以3km为管辖范围，据上述分析，很容易就发现，在节点密集的地区有很多节点属于多个平台管辖范围，也就是说这些节点“被重复管辖”，这样不利于警力工作量的均衡分配，也会造成警力资源的一定浪费。并且在实际生活中，节点被重复管辖的现象是不允许出现的，所以我们对以上给出平台管辖范围作以下修正。
本文中，我们制定了“被重复管辖节点的分配原则”。首先，我们定义警力工作量WQj为第j个平台当前管辖范围内的发案率总和，也即
WQj??wi1nQj?j?1,2,?20?，
其中，nQj为平台Qj当前所管辖的总节点数，wi为第i个节点平均每天发生报警案件的数量即发案率（次数）。
将所得的WQj无量纲化，采用归一化得无量纲化：
?Q?j?W?QjWQj?WQj26.7。
max其次，有实际生活中可以知道，路程越远，那么巡警到达的时间越迟，也就不利于交巡警平台的管辖。而根据警力工作量的定义可以知道：警力工作量越大，越不利于交巡警平台的管辖。
这里需要将d(Qj,Qk)也无量纲化，方法同上：
?(Qj,Qk)?
d(Qj,Qk)?l(i,j)?max9
?d(Qj,Qk)7.43236，
其中，d(Qj,Qk)表示节点Qj和节点Qk之间的路程，?l(i,j)?max表示任意相连交叉路口的的距离。
因此本文引入隶属度?Qj,Qk，其计算公式为
?Q,Q?jk1?j?1,2,?20;k?1,2,?92?。
?Qj?(Qj,Qk)那么很容易就得到如下结论：若节点Qk在s个平台节点的管辖范围内，那么分别求出这几个平台的隶属度?，选取隶属度最大的点作为节点Qk的服务平台(若有隶属度相同的节点则随机选取服务平台。本文中由于实际条件的约束，不存在这种情况)。
下面以具体的节点Q33来加以说明。 35635411.704735231350348346344342340320345.024994.242635325330335 图 4 节点Q33的放大图
53403456.7082455.0998.27659.30053330.413811.597415.53227.566464629.4279328 通过上图 4可以看到节点Q33被平台Q8、平台Q9同时管辖。根据前面的分析我们
375.099先来计算出Q8，Q9的当前警力工作量和距离Q33的路程，得到：
3635.0143d(Q9,Q33)?1.25913km， WQ8?22.8，d(Q8,Q33)?0.82765km，WQ9?22.5，6.0828由归一化得：
16?(Q9,Q33)?0.1694， ?Q?0.854，?(Q8,Q33)?0.1114；?Q?0.8426，
j934.0588通过隶属度的计算可以求得?Q8,Q33?10.5113，?Q9,,Q33?7.0059。显然?Q8,Q33??Q9,Q33，因此节点Q8归属于平台Q33管辖。
10
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库2024年全国数学建模获奖论文 交巡警服务平台的设置与调度(2)在线全文阅读。
相关推荐：
