城市交警服务平台站点选址优化设计

摘 要：收集了长沙市各主要道路信息并进行检验，构造了计算机可识别的长沙市道路交通图；利用图论中的最短路算法，定义了服务平台的服务半径；分析了长沙市的路网结构和道路通行效率，找到了适宜作为快速路的道路，并以此设计了基于快速路的选址方案；在分析了湘江、京广铁路等对城市交通影响之后，提出了以二环线为界的分区域平台设计；分析了结点流量，找到了流量不平衡的结点并分析了原因.最终结合三个方面，对长沙市交警服务平台的选址进行优化设计，再对平台效率低的区域适当添加平台数量，得到了总设计方案。

关键词：最短路算法；交警服务平台；选址问题；图论

引言

随着我国社会经济的发展以及城市化进程的加快，城市迅速的扩大，交通量也急剧上升，很多大城市现有的交通设施已经不能满足日益增长的交通需求，经常会发生交通拥挤和堵塞的情况，为了缓解城市的交通压力，适应城市的发展，越来越多的大城市在城市道路建设中采取各种各样的方法以增加道路的服务能力与容量[1]。

针对大城市日益紧张的道路交通情况，如何提高交警的出警效率将在疏导交通、事故处理等方面的效率有着至关重要的影响。

文章的选题背景来自重庆交巡警服务平台，在对交巡警服务平台的功能进行归纳提炼以后，选择了交警层面的职能进行研究[2]，在文献[3]的基础上，以长沙市作为研究对象，采用便于在计算机实现的、基于全局的路网结构分析，并结合长沙市道路结构的实际情况，选择通行效率高的道路作为快速路，对城市进行适当的分区域，结合实际模拟出交警服务平台的选址设计方案。

1 城市交通图的构造

道路交通图可以分为有向图和无向图。考虑到实际城市中存在单行线、限行道路等，为了更真实模拟城市的道路结构，采用有向图[4]。以路口作为结点，通过每条道路来确定结点之间是否直接连通.两个连通结点之间的距离用两点间直线距离计算。文章数学模型中所涉及的城市道路考虑了道路的通行能力，选择了主次干道、国省道等，排除了小街小巷、步行街等，所选择道路至少两个车道以上，以利于模型中的方案在实际路况中能够实现。

1.1 数据收集方式

1.1.1 结点坐标收集

2 交警平台数量与效率分析

2.1 交警平台数量

在进行交警服务平台站点的优化设计过程中，首先考虑的因素就是平台数量，任意两个平台之间的最短路程可能影响到效率，因此首先要求出任意两结点之间的最短路程和最短路程所经过的路径。

在计算结点之间的最短路程时，一般采用的是Floyd算法[6]，其算法的核心是对不能直接连通的A、C两点，搜索是否存在点B，使得AB连通，且BC连通，通过点B以实现A、C两点的连通；若存在点B，使得ABC的路程小于当前AC的路程，则通过点B实现A、C两点的路程更短。

2.2 数量效率关系计算

交警服务平台的数量与效率之间存在着一定的关系，下面将要讨论如何来对服务平台的效率进行量化衡量。

2.2.1 交警服务平台效率量化指标

设某个结点到平台i的最短路程为di，该结点到所有交警服务平台的路程最小值min{d1，d2，……，dn}所对应的k即所属服务平台，在得到了所有结点的所属平台以后，即构建了服务平台与结点路口之间的对应关系。

定义交警服务平台的服务半径r，假设平台到所辖路口i的最短路程为li，平台到各路口最短路程最大值max{l1，l2，…，ln}，则服务半径r=max{l1，l2，…，ln}，如图2所示。

由于服务半径越大，所花费的时间越长，因此服务效率越低，不妨用服务半径r来作为交警服务平台效率的衡量指标。

2.2.2 快速选址算法

基于以上分析，或者固定平台服务半径，以达到最少平台数；或者固定平台数，使得最大服务路程最短。在没有目标的前提下，可以考虑优先分析和计算平台数与平台的服务效率之间的关系。

采用快速选址算法，平台数在每一次循环过程中递减，每一次剔除效率最低的平台，以此减少优化过程的计算时间，其算法原理如图3所示。

2.2.3 平台数与效率的关系

图4给出了平台个数与服务半径的关系的E，以及对E做差分得到的得到的相应变化量E'，其中X轴为平台数，Y轴为服务半径。

由E可以知道，数量与效率的关系是：平台数量越多，平台的服务半径越小，效率越高；反之数量越少，服务半径越大，效率越低。同时由x发现，存在低效率的平台，由于与相邻平台距离过近，完全发挥不了应有的作用。

2.3 数量效率关系近似函数

3 长沙市道路通行状况分析

对长沙市进行交警服务平台的设计，不能不考虑各条道路的通行效率对交通流量的影响。

3.1影响通行效率的因素

影响道路通行效率的因素，除了本身的路网结构以外，还有很重要的一点就是路口的等待。

影响等待次数的主要因素是经过的路口数，但是还要考虑几种特殊情况：

右转弯：在一般的交通规定中，右转弯是可以不受红绿灯限制的，某些路口对右转弯有特殊限制，属于特殊情况，文章不予考虑。

立交系统：立交系统是提升城市道路通行效率的重要手段，因此文章在数据收集阶段特意收集了长沙市重要的立交系统。

3.2 道路通行效率分析

4 长沙市交警服务平台设计

4.1基于快速路的交警服务平台设计

由表1知道，长沙市通行效率达到100%的道路只有：东二环、西二环、南二环、北二环、长沙大道，因此讨论基于快速路的交警服务平台设计时仅考虑上述道路。

现假设通过快速路，位于快速路上两结点之间通行时间可以控制在20分钟；普通道路的理论路口间距为500米，路口等待时间为3分钟，行驶速度为30km/h，因此普通道路通行效率为25%，现要求通过快速路的传递能够在1小时内达到，快速路上时间不超过20分钟，则上快速路和离开快速路行驶时间小于20分钟。考虑上述假设的行驶速度和通行效率，到达快速路上最近的结点时间小于20分钟的结点，则认为该结点是快速路可以覆盖的结点。

通过对快速路覆盖区域的筛选，得到了集合Qp，假设全部结点集合为P，则存在快速路不能覆盖的区域P-QP，有快速路覆盖区域的定义可以知道，集合QP结点的交通状况要好于集合P-QP的结点，因此单独考虑为区域P-QP设置平台。

图6给出了快速路不能覆盖的区域。

现已知总结点数389，快速路不能覆盖的结点数202，因此快速路不能覆盖的结点所占比重0.519280，现单独取P-QP进行设计，设置10个交警服务平台，按照快速选址算法得到了如图7的方案，设置的结点信息见表3。

4.2 分区域的交警服务平台设计

由于城市人口不是平均分布，有些区域人口密集，有些区域人口稀疏，因此交通状况也存在差异.城市交通状况的总体趋势是：越接近城中心区域，道路越拥堵，通行效率越低，平均行驶速度越慢；越远离城中心区域，通行效率越高，平均行驶速度越快.因此考虑到这个因素，可以对城市区域按照交通状况进行划分。

对于设置了环线的城市而言，每个环线的编号k越大，距离城市中心越远，因而通行效率越高。因此对于相同的路程，不同区域所花费的时间也是不同的。长沙市有三个环线，其中并无单独的一环线，而是选择若干道路作为一环线；三环线为绕城高速，并未在文章考虑范围，因此适合于进行分区的环线只有二环线。

由于铁路、河流的影响，长沙市被分为了内城和外城，内城与外城之间通过若干条道路、桥梁连接，造成了出入瓶颈，而二环线紧邻铁路，因此二环线实际上也反映出了这种现象。

要判断结点属于区域内外，首先需要得到区域的边界，用结点集合LE、LW、LN、LS分别代表东二环、西二环、北二环、南二环。

如图8所示，判断坐标（x，y）是否处于区域之内，只需要检验是否处于以下四个集合的交集。

由于边界可能不是一段构成，假设有n个结点，则必有n-1条边，如图9所示，要判断是否满足集合，只需要计算各条边是否符合，然后取交集。

通过上述步骤筛选得到了区域内结点，区域上结点可以直接得到，余下的属于区域外结点。

其中v1，v2为相应区域的权值，其权重参照相应区域的交通状况或者所要研究问题的附属条件，文章给定v1=2，v2=1、进行模拟，再次进行最短路计算，取结点总数的1/4作为交警服务平台数，通过平台设置的快速算法，得到了如图10所示的设计方案。表4给出了平台所在结点。

对距离分区域加权后，计算得总共有222个路口与相邻路口距离不足500m，路口距离过近对道路的通行效率有影响。

4.3 基于结点的交警服务平台设计

在图论中，结点的度反映出该结点与其他结点的连通性。对于有向图而言，定义了出度与入度，若将度作为流量来看，则对于无向图，流量是平衡的，而有向图可能会出现不平衡的现象，假设每个路口都会发生阻滞，而通过立交、右转弯等，路口可能存在某些路线不需要等待，这些不需要等待的路线在经过当前路口之后，会在下一个结点发生阻滞。

经过对长沙市各路口进行了分析筛选计算，总共有50个点交通流量易发生堆积.对交警服务平台的设置，也应重点放在这一类路口，选择以上所有结点设置交警服务平台。表5给出了交通流量容易发生堆积的结点，图11画出了相应的结点位置。

经观察可以发现，除了单行线，丁字路口也容易发生流量堆积的现象。在流量模型中，每个路口的流量将会影响到下一个路口，由于右转弯不需要等待红灯，直接影响到了下一个路口。现在长沙市已经对某些路口右转弯设置了红绿灯，以此控制转弯车流量对路口通行的影响。文章以长沙市为蓝本进行模拟分析，所收集的数据并未能有效反映出这一类情况。

实际上分析道路的流量还应考虑到每条道路的车道数，在车道数减少的情况下容易因并道引起拥堵，影响流量的因素还包括大多数司机的习惯行驶路线，最后这个因素有较大的主观成分，超出了文章所考虑的范围。

4.4 长沙市交警服务平台优化设计

由于长沙市的路口数多，直接采用优化选址的算法，其运算量规模难以想象，因此先要对交警服务平台进行初选，确定主要的路口，然后根据所选择方案进行适当的添加，前面分别就快速路、城市区域划分、结点流量三个方面对交警服务平台选址进行了设计。现将按以下步骤进行综合：（1）按区域对结点之间距离进行加权；（2）计算出距离加权后的最短路矩阵；（3）计算快速路不能覆盖区域；（4）对指定区域进行设计，获取结点集合；（5）进行结点分析，得到集合；（6）对集合取并，得到初选的结点集合。

对快速路不能覆盖区域按1/4的结点数取点，共设计了32个平台。在获得当前方案后，与基于结点分析的选址方案取并集。

在对平台选择的路口进行了初选之后，还需要对平台选址进行分析，对覆盖薄弱的地区进行服务平台的适当添加。为了对路口是否在覆盖区域范围，现定义平台的最大服务半径r=max{ri}，其中ri代表平台i的服务半径。由于每个平台的服务半径不同，现取其最大值作为统一的衡量标准。为了便于计算，还需要将最大服务半径r适当转化为平台之间的最短路程lij。对所有平台进行讨论，考虑对区域进行分块，各平台进行聚类划分，平台服务的区域也就减小到相应聚类所在区域，划分的依据是按照最近的路程进行归类，划分算法借用图论的连通性，得到平台与最近距离平台之间的联系。通过最短路程导出的聚类，每一个聚类最少有两个元素，因而每个聚类都存在最大服务半径rc。只需要令最大服务半径r=max{rc}，最终平台选址和平台聚类的划分如图12所示。

此时最大服务半径限制为4238.3m，服务平台不能覆盖的路口有：

（云栖路，绕城高速），（潇湘路，南三环），（三一大道，汽配城路）。

5 结束语

文章通过图论中最短路算法定义了交警服务平台的服务半径，并以此作为选址方案的基础，在贴近真实的基础上，对长沙市道路结构进行了分析，并以此选定了长沙市的快速路，确定了基于快速路的交警服务平台设计。在分析了湘江、京广铁路等对城市交通影响以后，确定了以二环线为基础的分区域的服务平台设计方案。在单独对结点进行分析以后，得到了基于结点的设计方案，最终在综合了三个方面因素以后，对长沙市交警服务平台进行了总设计，得到总设计方案。

城市交通模型应用前景广，对于加油站设置、保险公司快赔处理点设置都有参考价值，甚至可以扩展到整个国家物流运输网络的规划。对模型改进以后还可以对道路的通行能力进行逐一分析，得到更贴近实际的方案。

参考文献

[1]杨晓娟，李嘉.快速路设计在城市道路设计中的应用分析[J].城市建设理论研究，2012，7：1-3.

[2]李阳，杨东.重庆市交巡警的胜任特征研究[J].人力资源管理，2011，3：184-185.

[3]张妲，王小凡，徐国兵.旧城区城市道路的有机更新--以长沙市红旗区支路网规划为例[J].规划师，2006，22（1）：40-42.

[4]孙登文.一种有向图中道路的识别方法[J].清华大学学报（自然科学版）， 2001，41（11） ：127-128.

[5]张维琪.坐标变换在规划设计中的应用[J].城市建设理论研究，2011（17）：1-4.

[6]Stefan Hougardy.The Floyd-Warshall algorithm on graphs with negative cycles [J].Information processing letters， 2010， 110（8）：24-27.

[7]代西武.快速排序与递归[J].北京建筑工程学院学报，2006，22（1）：52-54.

[8]戴建国，曹传东，郭理.递归算法应用分析[J].电脑知识与技术，2008，4（28）：107-110.

作者简介：张逵（1973-），男，湖南祁阳人，长沙学院信息与计算科学系讲师。