论文部分内容阅读
【摘要】本文基于第23届全国大学生数模竞赛C题，主要研究交巡警服务平台的管辖范围的规划问题，划分区域研究，以Floyd算法为基础，给出了合理性判定参数，合理地解决了该问题。
【关键词】交巡警服务平台；划分区域；Floyd算法
一、问题背景
为了更有效地贯彻实施维护社会稳定的职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
本文就第23届全国大学生数模竞赛问题一第一小问进行探讨，详细信息可见相关网站。以达到如下目的：为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60 km/h）到达事发地。
二、问题分析
交巡警服务平台实质上是应急服务设施，应急问题中最显著的特点表现在时间的紧迫性，应急服务设施应能在最短的时间内到达进行服务，因此路径的选择至关重要。运用网络图的最短路径算法理论，给出基于最短路径的选址问题的Floyd算法，计算出任意两点的最小距离矩阵，即可确定最佳路径，在最小距离矩阵中筛选小于最大距离30的元素，即可确定交巡警服务平台的管辖范围。
三、模型假设
（1）突发事件仅在该市各个交通路口发生；
（2）相邻两个交通路口之间的道路近似认为是直线，把城市地图抽象成由点和线组成的无向网络赋权图；
（3）假设交巡警车在到达案发点的途中没有障碍，即不考虑路况和其他突发事件的影响，交巡警车按照其行驶速度匀速行驶直至到达案发点；
（4）不考虑交巡警平台的反应时间，假设接到报案的瞬间，交巡警即出警；
（5）该市交通事务各城区内自行解决，其他市区不参与交通管辖；
（6）题目中的数据真实、可靠、全面。
四、模型的建立与求解
交巡警服务平台实质上是应急服务设施，应急问题中最显著的特点表现在时间的紧迫性，应急服务设施应能在最短的时间内到达进行服务，因此在速度一定的情况下路径的选择至关重要。运用网络图的最短路径算法理论，给出了基于最短路径的选址问题的Floyd算法，计算出A区任意两个路口的最小距离矩阵。
1Floyd算法
直接在A区交通网络中的带权邻接矩阵中用插入顶点的方法依次构造出v个道路距离矩阵D(1),D(2),…,D(v)，使最后得到的矩阵D(v)成为A区交通网络的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
把每个路口之间的带权邻接矩阵W作为距离矩阵的初值，即D(0)=(d(0)ij)v×v=W。
（1）D(1)=(d(1)ij)v×v，其中(d(1)ij)v×v=min{d(0)ij,d(0)i1+d(0)1j}。
d(1)ij是从路口vi到路口vj的只允许以路口v1作为中间点的路径中最短路的长度。
（2）D(2)=(d(2)ij)v×v，其中d(2)ij=min{d(1)ij,d(1)i 2+d(1)2j}。
d(2)ij是从路口vi到路口vj的只允许以路口v1,v2作为中间点的路径中最短路的长度。
……
(v)D(v)=(d(v)ij)v×v,其中d(v)ij=min{d(v-1）ij,d(v-1)iv+d(v-1)vj}。
d(v)ij是从路口vi到路口vj的只允许以路口v1,v2,…,vv作为中间点的路径中最短路的长度，即是从路口vi到路口vj经过任意中间路口的路径中最短路的长，因此D(v)即是A区交通网络的距离矩阵。
在建立距离矩阵的同时可建立A区交通网络路径矩阵R。
R=(rij)v×v，rij的含义是从路口vi到路口vj的最短路要经过编号为rij的道路。
R(0)=(r(0)ij)v×v,r(0)ij=j。
每求得一个D(k)时，按下列方式产生相应的新的R(k):
r(k)ij=k 若d(k-1)ij>d(k-1)ik+d(k-1)kj,
r(k-1)ij否则,
（1）
即当通过路口vk的任意两路口的路径最短时，被记录在R(k)中，依次求D(v)时求得R(v),可由R(v)来查找任何路口之间最短路的路径。
若r(v)ij=p1，则路口p1是路口i到点路口j的最短路的中间点。然后用同样的方法再分头查找。若：
（1）向点i追溯得：r(v)ip=p2，r(v)ip=p3，…，r(v)ip=pk。
（2）向点j追溯得：r(v)pj=q1，r(v)qj=q2，…，r(v)qj=j。
则由路口i到路口j的最短路路径为：
i，pk，…，p2，p1，q1，q2，…，qm，j
用MATLAB求解，可得距离矩阵D，路径矩阵R。
交巡警服务平台在其所管辖的范围内出现突发事件时，要使交巡警（警车的时速为60 km/h）尽量能在3分钟内到达事发地，不考虑路况、其他突发事件以及拐弯处对交巡警速度的影响，交巡警车按照其行驶速度匀速行驶直至到达案发点，因此，最大服务距离L=60 km/h×120 h=3 km。
L在图上的距离为30 mm。
在距离矩阵中筛选小于最大服务距离30 mm(图中)的元素，整理后可得交巡警服务平台管辖范围如下：
【关键词】交巡警服务平台；划分区域；Floyd算法
一、问题背景
为了更有效地贯彻实施维护社会稳定的职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
本文就第23届全国大学生数模竞赛问题一第一小问进行探讨，详细信息可见相关网站。以达到如下目的：为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60 km/h）到达事发地。
二、问题分析
交巡警服务平台实质上是应急服务设施，应急问题中最显著的特点表现在时间的紧迫性，应急服务设施应能在最短的时间内到达进行服务，因此路径的选择至关重要。运用网络图的最短路径算法理论，给出基于最短路径的选址问题的Floyd算法，计算出任意两点的最小距离矩阵，即可确定最佳路径，在最小距离矩阵中筛选小于最大距离30的元素，即可确定交巡警服务平台的管辖范围。
三、模型假设
（1）突发事件仅在该市各个交通路口发生；
（2）相邻两个交通路口之间的道路近似认为是直线，把城市地图抽象成由点和线组成的无向网络赋权图；
（3）假设交巡警车在到达案发点的途中没有障碍，即不考虑路况和其他突发事件的影响，交巡警车按照其行驶速度匀速行驶直至到达案发点；
（4）不考虑交巡警平台的反应时间，假设接到报案的瞬间，交巡警即出警；
（5）该市交通事务各城区内自行解决，其他市区不参与交通管辖；
（6）题目中的数据真实、可靠、全面。
四、模型的建立与求解
交巡警服务平台实质上是应急服务设施，应急问题中最显著的特点表现在时间的紧迫性，应急服务设施应能在最短的时间内到达进行服务，因此在速度一定的情况下路径的选择至关重要。运用网络图的最短路径算法理论，给出了基于最短路径的选址问题的Floyd算法，计算出A区任意两个路口的最小距离矩阵。
1Floyd算法
直接在A区交通网络中的带权邻接矩阵中用插入顶点的方法依次构造出v个道路距离矩阵D(1),D(2),…,D(v)，使最后得到的矩阵D(v)成为A区交通网络的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
把每个路口之间的带权邻接矩阵W作为距离矩阵的初值，即D(0)=(d(0)ij)v×v=W。
（1）D(1)=(d(1)ij)v×v，其中(d(1)ij)v×v=min{d(0)ij,d(0)i1+d(0)1j}。
d(1)ij是从路口vi到路口vj的只允许以路口v1作为中间点的路径中最短路的长度。
（2）D(2)=(d(2)ij)v×v，其中d(2)ij=min{d(1)ij,d(1)i 2+d(1)2j}。
d(2)ij是从路口vi到路口vj的只允许以路口v1,v2作为中间点的路径中最短路的长度。
……
(v)D(v)=(d(v)ij)v×v,其中d(v)ij=min{d(v-1）ij,d(v-1)iv+d(v-1)vj}。
d(v)ij是从路口vi到路口vj的只允许以路口v1,v2,…,vv作为中间点的路径中最短路的长度，即是从路口vi到路口vj经过任意中间路口的路径中最短路的长，因此D(v)即是A区交通网络的距离矩阵。
在建立距离矩阵的同时可建立A区交通网络路径矩阵R。
R=(rij)v×v，rij的含义是从路口vi到路口vj的最短路要经过编号为rij的道路。
R(0)=(r(0)ij)v×v,r(0)ij=j。
每求得一个D(k)时，按下列方式产生相应的新的R(k):
r(k)ij=k 若d(k-1)ij>d(k-1)ik+d(k-1)kj,
r(k-1)ij否则,
（1）
即当通过路口vk的任意两路口的路径最短时，被记录在R(k)中，依次求D(v)时求得R(v),可由R(v)来查找任何路口之间最短路的路径。
若r(v)ij=p1，则路口p1是路口i到点路口j的最短路的中间点。然后用同样的方法再分头查找。若：
（1）向点i追溯得：r(v)ip=p2，r(v)ip=p3，…，r(v)ip=pk。
（2）向点j追溯得：r(v)pj=q1，r(v)qj=q2，…，r(v)qj=j。
则由路口i到路口j的最短路路径为：
i，pk，…，p2，p1，q1，q2，…，qm，j
用MATLAB求解，可得距离矩阵D，路径矩阵R。
交巡警服务平台在其所管辖的范围内出现突发事件时，要使交巡警（警车的时速为60 km/h）尽量能在3分钟内到达事发地，不考虑路况、其他突发事件以及拐弯处对交巡警速度的影响，交巡警车按照其行驶速度匀速行驶直至到达案发点，因此，最大服务距离L=60 km/h×120 h=3 km。
L在图上的距离为30 mm。
在距离矩阵中筛选小于最大服务距离30 mm(图中)的元素，整理后可得交巡警服务平台管辖范围如下：