交巡警最短路径模型的建立*



交巡警最短路径模型的建立*

0引言

【研究意义】最短路径问题是计算机科学、运筹学、地理信息科学等学科的一个研究热点[1]。因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高该算法的求解效率具有重大的现实意义，而优化切入点不同，其效果也有所区别。【前人研究进展】经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现，到1974年为止，就已经有100多篇论文和几十种算法提出[2]。关于单源最短路径的算法，目前最经典的算法是Dijkstra算法，它的时间复杂度是O(n2)(文献[3-6])。1974年，Wagner[7]采用桶分类得出一个O(e)的算法，但该算法必须在边的权值是小的整数才适用。关于每一对顶点之间的最短路径算法，公认Floyed算法最佳，其时间复杂度为(n3)(参考文献[8])。文献[9-10]对最短路径问题提出一种新的快速算法——SPFA(Shortest Path Faster Algorithm)，SPFA算法的时间复杂度为O(e)，对边的权值没有特殊的限制，适合于任意有向图。当e≪n2时，SPFA算法表现出时间复杂度上的优越。此外，最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他度量上，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径、最低费用等问题[11]。同时，最短路径问题也是资源分配、路线设计及分析等优化问题的基础[12-13]。【本研究切入点】由于最短路径问题在实际中常用于汽车导航系统、110 报警、119 火警以及医疗救护系统等各种应急系统上，这就决定最短路径问题的实现应该是高效率的。现实中，通常采用最短路径问题求解交巡警问题，但有可能在公路上任意一点报警，却未能找到最快的岗亭，造成这种缺陷的主要原因是把道路上某点报警直接归结到更近的路口。因此，本文将最短路径在出警问题上的离散化作为切入点，研究算法的优化问题。【拟解决的关键问题】采用离散化道路来优化辖区分配策略，在道路上设置虚拟路口，把每条道路离散成若干个点，然后把这些新增加的点作为新的路口，由此得到新的道路地图，可提高一般SPFA算法的效率，缩短出警时间。

1交巡警问题

交巡警问题就是在交通网络和现有交巡警服务平台的基础上，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，交巡警尽量能在3 min内(警车时速为60 km/h)到达事发地。设计一个服务平台模拟系统，主要包括报警、辖区的信息管理功能，其具体的功能模块如图1所示。

图1交巡警服务平台功能模块

Fig.1The function of the traffic patrol service platform

解决交巡警问题的评价指标主要有如下3种：(1)平均警车到达时间，该值越小，出现突发情况时多数路口警车将会更快到达，方案也就越优；(2)最长警车到达时间：区域内警车开到所有路口耗时间中的最长时间，它指出在遇到紧急情况时警车赶到离服务平台最远的路口所需时间，该值越小越好；(3)任务均衡度：各交巡警服务平台辖区内各路路口和的均方偏差，该值越小，表明各服务平台所承担的任务量越均衡。

1.1算法的选择

要解决实际的交巡警问题，常常需要计算图中从某个源点到其余各顶点的最短路径或各顶点之间的最短路径，相当于找寻一个图中的最短路径。相较于经典的Dijkstra算法，SPFA的时间复杂度为O(e)，而Dijkstra算法的时间复杂度为O(n2)，显然当图为稀疏时，SPFA算法更有优势[14-15]。

SPFA算法是Bellman-Ford算法的改进版,该算法以三角不等式为基础，实现时借助队列堆栈不断进行迭代以求得最优解，具有效率高、实现简洁、扩展性强等优点。三角不等式的普适性及其类似搜索的实现方式，使得SPFA 算法的应用并不只局限于图论中的最短路径，更可以在动态规划、迭代法解方程中发挥出巨大的作用，解决一些非常规问题；还可根据具体问题进行各种各样的优化。正是基于上述优势，本文采用SPFA 算法，把无向图转化成有向图来分配各交巡警服务平台的管辖范围。

1.2模型的建立与求解

本次算法的应用所涉及的对象可分为两类：一类是包括路口及交巡警服务平台的结点；另一类是包括公路的边数。因此，它们可以使用图论模型进行统一描述。设图G(V，E)表示本次建模所涉及的公路网，vi∈V代表公路的一个路口。由于交巡警服务平台总在路口处，故其组成的集合Vs⊆V。(vi，vj)∈E代表vi到vj之间有一条公路，用wij表示它的边权，用来表示该段公路的长度(下文中简写为(vi，vj，wij)∈E)，本次建模的所有模型都是在图G的基础上进行描述。

当路口有事件发生时，估计一个交巡警服务平台可能到达的时间，再乘以速度，得到距离；再以该路口为圆心，距离为半径画圆，求出符合的岗亭，缩小范围。在实际情况中，路与路之间存在折点，无法转化成圆的问题，所以我们要考虑的覆盖不是圆，但基本原理大致相同。因此得到的解并不是最优解，而是一个可行解，需进一步处理，再根据最短路径算法得出最优解。

划定平台管辖范围的主要依据是做到快速出警，即任一地区出现突发事件，警察应能在最快的时间内赶到(尽量在3 min之内)。下面采用SPFA算法进行建模求解。

要找出到达路口v路径最短的岗亭，以v为圆心，R为半径画圆，找出圆内的岗亭，街道口和公路，记新得到的公路网为无向图G(V，E)，vi∈V代表各街道口，ei=(vj，vk，wjk)∈E表示从vi到vj的一条路径。那么，从vi到vj的最短路径Lmin(vi，vj)可以表示为

Lmin(vi，vj)=min{L(Rij)}=min{wt0t1+…+wtn-1tn},

(1)

记第i个交巡警平台为vis∈V，那么在此种划分策略下，若第j个路口划分给了第m个平台管辖，则必有

Lmin(vj，vms)=min1≤i≤M{Lmin(vj，vis)},

(2)

式中M为交巡警平台个数。

求解上式的关键是求解所有路口和服务平台间的最短路径Lmin(vj，vis)。求解最短路径SPFA算法可以一次性地求解某个结点vi到其他所有结点vj的最短路径长度。

变量说明：

Dist[i]是vk到其他节点v1的距离，显然Dist[k]=0；que是一个队列，用于缓存算法的节点。vt指队列的队尾元素，vp是vt在公路网的邻接节点；wtp是vp到vt的公路距离。求vk到其他各结点最短路径的算法流程如下所示：

Step2：判断队列que是否为空，如果为空，则跳至Step4。否则从que的队首弹出一个元素，记为t。

Step3：遍历所有与vt相邻的结点vp，如果dist[p]>dist[t]+wtp，则将dist[p]更新为dist[p]+wtp，同时将p压入que的队尾，跳至Step2继续执行。

Step4：输出dist，dist的第i项即为vk到vi的最短距离。

求出所有结点之间的最短路径之后，代入式(2)，便可找到各路口对应的服务平台，其详细结果如表1所示。

所以1～20号岗亭的管辖范围如表2所示(根据表1，得出离路口距离最短的平台)。

表1路口编号

Table 1Crossing number

路口编号Crossingnumber平台编号Platformnumber路口编号Crossingnumber平台编号Platformnumber路口编号Crossingnumber平台编号Platformnumber路口编号Crossingnumber平台编号Platformnumber路口编号Crossingnumber平台编号Platformnumber路口编号Crossingnumber平台编号Platformnumber1117173384956538118221818349505663821833191935951567183184420203616525681842055211337165356918520662213381654370286207723133925537118720882413402565722882099251241175747318920101026114217585741902011112711432595751912012122815442604761922013132915459617771914143074686247811515319477634791916163274876448018

表2管辖范围表

Table 2Jurisdiction table

平台编号Platformnumber路口编号Crossingnumber辖区路口数Thenumberofcrossing平台编号Platformnumber路口编号Crossingnumber辖区路口数Thenumberofcrossing11,68,69,71,73,74,75,76,7891111,26,27322,39,40,43,44,70,7271212,25233,54,55,65,6651313,21,22,23,24544,57,60,62,63,6461414155,49,50,51,52,53,56,58,5991515,28,2936611616,36,37,38477,30,32,47,48,6161717,41,42388,33,4631818,80,81,82,83599,31,34,35,4551919,77,793101012020,84,85,86,87,88,89,90,91,9210

由于本文假设案发率和路口数成正比，为衡量此种策略下各交巡警平台工作量的大小，本文将平台辖区内的所有路口进行加和，以此作为交巡警平台工作量的度量。

对表1、表2的数据进行统计,得到服务平台的指标(图2)，计算出警车平均到达时间为0.97 min，平均最晚到达时间为2.16 min，任务均衡度为4.6。

图2服务平台的统计指标

Fig.2Statistical indicators of the service platform

1.3模型的评价

由上面的结果可以看出(图2)，警车平均到达时间为0.97 min，因此该平均到达时间非常优秀，平均仅需1 min左右便可到达现场。然而，各服务平台的任务均匀度并不好，有些任务很重，如1号、5号、20号，需要管辖8个以上的路口，另一些任务却较少，如6号、10号、14号，仅仅管辖一个路口，这对资源条件相同的服务平台来说明显不合理。

另外，我们注意到即使是在此种策略下，有些路口也是不能在3 min之内到达，这样的结点有6个(表3)。

表36个路口的坐标位置及最短到达时间表

Table 3The location and the shortest arrival schedule of six crossing

路口编号CrossingnumberXY最短到达时间Theshortesttimeofarrival(min)282433284.70292463375.70383713303.40393713333.70613353955.30924444444.30

2SPFA算法的优化设计

在前面我们讨论的是假设所有事件都在路口发生，在道路上发生的就把它作为靠近一点的路口发生，但是该算法仍然有缺陷。如果在公路上任意一点报警，比如在40号公路(12-27)的P1点(236，310)处报警，由于离27号路口更近，本文用11号岗亭为其服务，总计用时3.10 min，路线如图3中的11-26-27-P1；如在40号公路(12-27)的P2点(234，311)处报警，由于离12号路口更近，本文用12号岗亭为其服务，总计用时1.58 min，路线如图3中的12-P2。

图3第11，12号岗亭报警图

Fig.3The alarming figure of No.11,12

P1点(236，310)和P2点(234，311)之间的距离为0.24 km，历时0.24 min；另外，如果点(275，350)报警，让12号岗亭为其服务显然比11号岗亭快(3.10-1.58-0.24=1.28 min)。造成这种缺陷的原因主要是直接把道路上某点报警直接归结到更近的路口。

基于上述模型的不足，本文提出离散化道路的思想，在道路上设置虚拟路口，把每条道路离散成若干个点，然后把这些新增加的点作为新的路口，由此得到新的道路地图。假设将离散逐步细化后，误差可以忽略不计，路口报警的模拟情况则越来越逼近真实的情况。在满足精度的条件下，将问题的规模降维，进而难度大大降低。

比如道路A-B，距离为9 km，本来只有两个路口，如果以3 km为路口最大距离，则可以增加2个虚拟路口(C、D表示)，离散化后，变成A-C、C-D、D-B 3条道路。

优化核心代码如下:

void CPDSPView::partition(int RouteID, int &topND, int &topRT)

{//划分第RouteID号道路, 增加路口和路段。每增加一个路口就要增加一个路段

if ((nd1.fX-nd2.fX)*(nd1.fY-nd2.fY)>=0)//斜率非负

{

nd0.fX=min(nd1.fX,nd2.fX)+p*(fabs(nd1.fX-nd2.fX));

nd0.fY=min(nd1.fY,nd2.fY)+p*(fabs(nd1.fY-nd2.fY));

}

else

{

nd0.fX=min(nd1.fX,nd2.fX)+p*(fabs(nd1.fX-nd2.fX));

nd0.fY=max(nd1.fY,nd2.fY)-p*(fabs(nd1.fY-nd2.fY));

}

//开始增加节点,增加坐标值

m_pNode[topND].fX=nd0.fX;

m_pNode[topND].fY=nd0.fY;

m_pNode[topND].nID=nd0.nID;

//增加道路

m_pEdge[topRT].nIDP1=tmpNd1.nID;

m_pEdge[topRT].nIDP2=nd0.nID;

m_pEdge[topRT].weight=ComputeDistance(tmpNd1,nd0);

}

void CPDSPView::addRoute(int &topND, int &topRT)

{//划分新的道路图

topND=NNode-ADD,topRT=NROUTE-ADD;

for(index=1;index <=NROUTE-ADD;index++)partition(index,topND,topRT);

}

3模型测试

经过二次划分后，新增加26个节点(编号为93～118)、26条道路(编号为141～166)，测试如图4所示：

图4优化测试图

Fig.4Optimization test pattern

报警测试一：如图5所示，在点(236，311)处报警，警车到达时间原来为3.13 min，优化后为1.77 min，提高1.36 min。

报警测试二：如图6所示，在点(304，345)处报警，警车到达时间原来为3.45 min，优化后为1.65 min，提高1.80 min。

图5　在点(236，311)处报警的对比情况

图6在点(304，345)处报警的对比情况

Fig.6Compares alarm at (304，345)

4讨论

本文采用SPFA算法求解交巡警问题，完成数学模型的建立和求解，并采用MFC开发交巡警的服务平台。在做模拟平台时，采用面向对象的方法，并基于MFC框架，用C++语言开发出交巡警服务平台，对本文提出的模型进行很好的验证。

本文使用图论模型的相关知识解决警力资源的评价、优化和调度问题。图论建模方法有两种作用：一是图论提供了将具体问题抽象为数学模型的形式化描述工具；二是图论中的经典模型和SPFA算法可直接用到模型求解的过程中。这些作用不仅仅可以体现在本文研究的交巡警服务平台中，而且可以很方便地移植到其他类似领域中。

MFC的仿真功能非常灵活，可以直观地展示报警效果，并生成软件，方便验证。

优化时，将道路合理离散化，每条道路离散成若干个点，然后把这些新增加的点作为新的路口，由此得到新的道路地图，从而完成第二类岗亭管辖范围的划分，达到预期目的。对于优化的角度，也可以尝试从增加岗亭的角度来优化，对于任务量大的岗亭指派更多的警力资源等都是我们可以深入探讨的问题。

参考文献:

[1]李阳，高艳春，全艳.最短路径理论在紧急通道设计中的应用[J].工业控制计算机，2012，25(11):91-92.

LI Y，GAO Y C，QUAN Y.Application of shortest path theory in design of emergency entrance[J].Industrial Control Computer，2012，25(11):91-92.

[2]吴鹏.赋权图上最短路径的一种简便算法[J].贵州师范大学学报:自然科学版，2012，30(5):69-72.

WU P.A simple solution to the shortest path problem of weighted graph[J].Journal of Guizhou Normal University:Natural Sciences，2012，30(5):69-72.

[3]王智广，王兴会，李妍.一种基于Dijkstra最短路径算法的改进算法[J].内蒙古师范大学学报:自然科学汉文版，2012，41(2):195-198.

WANG Z G，WANG X H，LI Y.A kind of shortest path algorithm based on Dijkstra[J].Journal of Inner Mongolia Normal University:Natural Science Edition，2012，41(2):195-198.

[4]董俊，黄传河.改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J].计算机科学，2012，39(10):245-247.

DONG J，HUANG C H.Research on shortest path search of improved Dijkstra algorithm in GIS navigation application[J].Computer Science，2012，39(10):245-247.

[5]李前进，王希武，林克成，等.一种新的穿越战场监控区域最优化路径算法[J].计算机应用与软件，2012，30(1):180-183.

LI Q J，WANG X W，LIN K C，et al.A novel algorithm of optimized path across battlefield monitoring region[J].Computer Applications and Software，2012，30(1):180-183.

[6]梁利刚，蔡莉，刘丹枫，等.基于交通方向的较优路径选路算法[J].计算机应用与软件，2012，29(6):94-96.

LIANG L G，CAI L，LIU D F，et al.Traffic direction based better path selection algorithm[J].Computer Applications and Software，2012，29(6):94-96.

[7]WAGNER R A.The Shortest Path Algorithm for Edg-

e-sparse Graphs[D].Nashville,Tennessee:Dept of Systems and Information Science,Vanderbilt University,2010:108-120.

[8]朱明，李予.基于权值抖动的误差扩散加网算法研究[J].包装工程，2013，34(7):71-75.

ZHU M，LI Y.Research on error diffusion algorithm based on weights perturbation[J].Packaging Engineering，2013，34(7):71-75.

(下转第41页Continue on page 41)

Establishment of the Shortest Path Model for Traffic Patrol

黎永壹

LI Yongyi

(钦州学院电子与信息工程学院，广西钦州535099)

(College of Electronic and Information Engineering，Qinzhou University，Qinzhou，Guangxi，535099,China)

摘要：【目的】提高一般SPFA算法(Shortest Path Faster Algorithm)的效率，缩短出警时间。【方法】用离散化道路法优化辖区分配策略，在道路上设置虚拟路口，把每条道路离散成若干个点，然后把这些新增加的点作为新的路口，由此得到新的道路地图。【结果】多次仿真实验数据显示离散化的优化策略可以缩短出警时间。【结论】基于离散化的改进SPFA算法提高了一般SPFA算法的效率，优化了服务平台，具有一定的实用价值。

关键词：交巡警最短路径出警问题离散化算法优化策略

Abstract：【Objective】To improve the efficiency of the SPFA algorithm and shorten the response time.【Methods】Discretization was proposed in this paper to optimize jurisdiction allocation strategy. In virtual crossing the roads, every road discreted into several points, and then put the new increase point as the new intersection, which resulted the new road map.【Results】After many experiments, data proved that optimized discretization strategy can shorten the response time .【Conclusion】Improved SPFA algorithm based on discretization can improve the efficiency of the SPFA algorithm and optimizes the service platform, which has certain practical value.

Key words：traffic patrol,the shortest path，police problem，discretization，algorithm，optimization strategy

中图分类号：TP391

文献标识码：A

文章编号：1002-7378(2016)01-0030-06

作者简介：黎永壹(1979-)，男，硕士，高级工程师，主要从事信息系统与知识发现方面的研究。

收稿日期：2015-11-10

网络优先数字出版时间:2016-01-27

网络优先数字出版地址:http://www.cnki.net/kcms/detail/45.1075.N.20160127.1616.010.html

*国家自然科学基金项目(51204071)，广东省科技计划项目(2012b010100019)，中央大学的基础研究基金项目(2013 zz0047)， 广西教育科学“十二五”规划课题“慕课教学模式下高校教学资源信息化建设的研究”(2015C435)和广西高校科研项目“半连续动力系统几何理论及其害虫综合治理研究”(ZD2014137)资助。