城市交警服務(wù)平臺站點(diǎn)選址優(yōu)化設(shè)計(jì)

摘 要：收集了長沙市各主要道路信息并進(jìn)行檢驗(yàn)，構(gòu)造了計(jì)算機(jī)可識別的長沙市道路交通圖；利用圖論中的最短路算法，定義了服務(wù)平臺的服務(wù)半徑；分析了長沙市的路網(wǎng)結(jié)構(gòu)和道路通行效率，找到了適宜作為快速路的道路，并以此設(shè)計(jì)了基于快速路的選址方案；在分析了湘江、京廣鐵路等對城市交通影響之后，提出了以二環(huán)線為界的分區(qū)域平臺設(shè)計(jì)；分析了結(jié)點(diǎn)流量，找到了流量不平衡的結(jié)點(diǎn)并分析了原因.最終結(jié)合三個(gè)方面，對長沙市交警服務(wù)平臺的選址進(jìn)行優(yōu)化設(shè)計(jì)，再對平臺效率低的區(qū)域適當(dāng)添加平臺數(shù)量，得到了總設(shè)計(jì)方案。

關(guān)鍵詞：最短路算法；交警服務(wù)平臺；選址問題；圖論

引言

隨著我國社會(huì)經(jīng)濟(jì)的發(fā)展以及城市化進(jìn)程的加快，城市迅速的擴(kuò)大，交通量也急劇上升，很多大城市現(xiàn)有的交通設(shè)施已經(jīng)不能滿足日益增長的交通需求，經(jīng)常會(huì)發(fā)生交通擁擠和堵塞的情況，為了緩解城市的交通壓力，適應(yīng)城市的發(fā)展，越來越多的大城市在城市道路建設(shè)中采取各種各樣的方法以增加道路的服務(wù)能力與容量[1]。

針對大城市日益緊張的道路交通情況，如何提高交警的出警效率將在疏導(dǎo)交通、事故處理等方面的效率有著至關(guān)重要的影響。

文章的選題背景來自重慶交巡警服務(wù)平臺，在對交巡警服務(wù)平臺的功能進(jìn)行歸納提煉以后，選擇了交警層面的職能進(jìn)行研究[2]，在文獻(xiàn)[3]的基礎(chǔ)上，以長沙市作為研究對象，采用便于在計(jì)算機(jī)實(shí)現(xiàn)的、基于全局的路網(wǎng)結(jié)構(gòu)分析，并結(jié)合長沙市道路結(jié)構(gòu)的實(shí)際情況，選擇通行效率高的道路作為快速路，對城市進(jìn)行適當(dāng)?shù)姆謪^(qū)域，結(jié)合實(shí)際模擬出交警服務(wù)平臺的選址設(shè)計(jì)方案。

1 城市交通圖的構(gòu)造

道路交通圖可以分為有向圖和無向圖。考慮到實(shí)際城市中存在單行線、限行道路等，為了更真實(shí)模擬城市的道路結(jié)構(gòu)，采用有向圖[4]。以路口作為結(jié)點(diǎn)，通過每條道路來確定結(jié)點(diǎn)之間是否直接連通.兩個(gè)連通結(jié)點(diǎn)之間的距離用兩點(diǎn)間直線距離計(jì)算。文章數(shù)學(xué)模型中所涉及的城市道路考慮了道路的通行能力，選擇了主次干道、國省道等，排除了小街小巷、步行街等，所選擇道路至少兩個(gè)車道以上，以利于模型中的方案在實(shí)際路況中能夠?qū)崿F(xiàn)。

1.1 數(shù)據(jù)收集方式

1.1.1 結(jié)點(diǎn)坐標(biāo)收集

2 交警平臺數(shù)量與效率分析

2.1 交警平臺數(shù)量

在進(jìn)行交警服務(wù)平臺站點(diǎn)的優(yōu)化設(shè)計(jì)過程中，首先考慮的因素就是平臺數(shù)量，任意兩個(gè)平臺之間的最短路程可能影響到效率，因此首先要求出任意兩結(jié)點(diǎn)之間的最短路程和最短路程所經(jīng)過的路徑。

在計(jì)算結(jié)點(diǎn)之間的最短路程時(shí)，一般采用的是Floyd算法[6]，其算法的核心是對不能直接連通的A、C兩點(diǎn)，搜索是否存在點(diǎn)B，使得A→B連通，且B→C連通，通過點(diǎn)B以實(shí)現(xiàn)A、C兩點(diǎn)的連通；若存在點(diǎn)B，使得A→B→C的路程小于當(dāng)前A→C的路程，則通過點(diǎn)B實(shí)現(xiàn)A、C兩點(diǎn)的路程更短。

2.2 數(shù)量效率關(guān)系計(jì)算

交警服務(wù)平臺的數(shù)量與效率之間存在著一定的關(guān)系，下面將要討論如何來對服務(wù)平臺的效率進(jìn)行量化衡量。

2.2.1 交警服務(wù)平臺效率量化指標(biāo)

設(shè)某個(gè)結(jié)點(diǎn)到平臺i的最短路程為di，該結(jié)點(diǎn)到所有交警服務(wù)平臺的路程最小值min{d1，d2，……，dn}所對應(yīng)的k即所屬服務(wù)平臺，在得到了所有結(jié)點(diǎn)的所屬平臺以后，即構(gòu)建了服務(wù)平臺與結(jié)點(diǎn)路口之間的對應(yīng)關(guān)系。

定義交警服務(wù)平臺的服務(wù)半徑r，假設(shè)平臺到所轄路口i的最短路程為li，平臺到各路口最短路程最大值max{l1，l2，…，ln}，則服務(wù)半徑r=max{l1，l2，…，ln}，如圖2所示。

由于服務(wù)半徑越大，所花費(fèi)的時(shí)間越長，因此服務(wù)效率越低，不妨用服務(wù)半徑r來作為交警服務(wù)平臺效率的衡量指標(biāo)。

2.2.2 快速選址算法

基于以上分析，或者固定平臺服務(wù)半徑，以達(dá)到最少平臺數(shù)；或者固定平臺數(shù)，使得最大服務(wù)路程最短。在沒有目標(biāo)的前提下，可以考慮優(yōu)先分析和計(jì)算平臺數(shù)與平臺的服務(wù)效率之間的關(guān)系。

采用快速選址算法，平臺數(shù)在每一次循環(huán)過程中遞減，每一次剔除效率最低的平臺，以此減少優(yōu)化過程的計(jì)算時(shí)間，其算法原理如圖3所示。

2.2.3 平臺數(shù)與效率的關(guān)系

圖4給出了平臺個(gè)數(shù)與服務(wù)半徑的關(guān)系的E，以及對E做差分得到的得到的相應(yīng)變化量E'，其中X軸為平臺數(shù)，Y軸為服務(wù)半徑。

由E可以知道，數(shù)量與效率的關(guān)系是：平臺數(shù)量越多，平臺的服務(wù)半徑越小，效率越高；反之?dāng)?shù)量越少，服務(wù)半徑越大，效率越低。同時(shí)由x發(fā)現(xiàn)，存在低效率的平臺，由于與相鄰平臺距離過近，完全發(fā)揮不了應(yīng)有的作用。

2.3 數(shù)量效率關(guān)系近似函數(shù)

3 長沙市道路通行狀況分析

對長沙市進(jìn)行交警服務(wù)平臺的設(shè)計(jì)，不能不考慮各條道路的通行效率對交通流量的影響。

3.1影響通行效率的因素

影響道路通行效率的因素，除了本身的路網(wǎng)結(jié)構(gòu)以外，還有很重要的一點(diǎn)就是路口的等待。

影響等待次數(shù)的主要因素是經(jīng)過的路口數(shù)，但是還要考慮幾種特殊情況：

右轉(zhuǎn)彎：在一般的交通規(guī)定中，右轉(zhuǎn)彎是可以不受紅綠燈限制的，某些路口對右轉(zhuǎn)彎有特殊限制，屬于特殊情況，文章不予考慮。

立交系統(tǒng)：立交系統(tǒng)是提升城市道路通行效率的重要手段，因此文章在數(shù)據(jù)收集階段特意收集了長沙市重要的立交系統(tǒng)。

3.2 道路通行效率分析

4 長沙市交警服務(wù)平臺設(shè)計(jì)

4.1基于快速路的交警服務(wù)平臺設(shè)計(jì)

由表1知道，長沙市通行效率達(dá)到100%的道路只有：東二環(huán)、西二環(huán)、南二環(huán)、北二環(huán)、長沙大道，因此討論基于快速路的交警服務(wù)平臺設(shè)計(jì)時(shí)僅考慮上述道路。

現(xiàn)假設(shè)通過快速路，位于快速路上兩結(jié)點(diǎn)之間通行時(shí)間可以控制在20分鐘；普通道路的理論路口間距為500米，路口等待時(shí)間為3分鐘，行駛速度為30km/h，因此普通道路通行效率為25%，現(xiàn)要求通過快速路的傳遞能夠在1小時(shí)內(nèi)達(dá)到，快速路上時(shí)間不超過20分鐘，則上快速路和離開快速路行駛時(shí)間小于20分鐘。考慮上述假設(shè)的行駛速度和通行效率，到達(dá)快速路上最近的結(jié)點(diǎn)時(shí)間小于20分鐘的結(jié)點(diǎn)，則認(rèn)為該結(jié)點(diǎn)是快速路可以覆蓋的結(jié)點(diǎn)。

通過對快速路覆蓋區(qū)域的篩選，得到了集合Qp，假設(shè)全部結(jié)點(diǎn)集合為P，則存在快速路不能覆蓋的區(qū)域P-QP，有快速路覆蓋區(qū)域的定義可以知道，集合QP結(jié)點(diǎn)的交通狀況要好于集合P-QP的結(jié)點(diǎn)，因此單獨(dú)考慮為區(qū)域P-QP設(shè)置平臺。

圖6給出了快速路不能覆蓋的區(qū)域。

現(xiàn)已知總結(jié)點(diǎn)數(shù)389，快速路不能覆蓋的結(jié)點(diǎn)數(shù)202，因此快速路不能覆蓋的結(jié)點(diǎn)所占比重0.519280，現(xiàn)單獨(dú)取P-QP進(jìn)行設(shè)計(jì)，設(shè)置10個(gè)交警服務(wù)平臺，按照快速選址算法得到了如圖7的方案，設(shè)置的結(jié)點(diǎn)信息見表3。

4.2 分區(qū)域的交警服務(wù)平臺設(shè)計(jì)

由于城市人口不是平均分布，有些區(qū)域人口密集，有些區(qū)域人口稀疏，因此交通狀況也存在差異.城市交通狀況的總體趨勢是：越接近城中心區(qū)域，道路越擁堵，通行效率越低，平均行駛速度越慢；越遠(yuǎn)離城中心區(qū)域，通行效率越高，平均行駛速度越快.因此考慮到這個(gè)因素，可以對城市區(qū)域按照交通狀況進(jìn)行劃分。

對于設(shè)置了環(huán)線的城市而言，每個(gè)環(huán)線的編號k越大，距離城市中心越遠(yuǎn)，因而通行效率越高。因此對于相同的路程，不同區(qū)域所花費(fèi)的時(shí)間也是不同的。長沙市有三個(gè)環(huán)線，其中并無單獨(dú)的一環(huán)線，而是選擇若干道路作為一環(huán)線；三環(huán)線為繞城高速，并未在文章考慮范圍，因此適合于進(jìn)行分區(qū)的環(huán)線只有二環(huán)線。

由于鐵路、河流的影響，長沙市被分為了內(nèi)城和外城，內(nèi)城與外城之間通過若干條道路、橋梁連接，造成了出入瓶頸，而二環(huán)線緊鄰鐵路，因此二環(huán)線實(shí)際上也反映出了這種現(xiàn)象。

要判斷結(jié)點(diǎn)屬于區(qū)域內(nèi)外，首先需要得到區(qū)域的邊界，用結(jié)點(diǎn)集合LE、LW、LN、LS分別代表東二環(huán)、西二環(huán)、北二環(huán)、南二環(huán)。

如圖8所示，判斷坐標(biāo)（x，y）是否處于區(qū)域之內(nèi)，只需要檢驗(yàn)是否處于以下四個(gè)集合的交集。

由于邊界可能不是一段構(gòu)成，假設(shè)有n個(gè)結(jié)點(diǎn)，則必有n-1條邊，如圖9所示，要判斷是否滿足集合，只需要計(jì)算各條邊是否符合，然后取交集。

通過上述步驟篩選得到了區(qū)域內(nèi)結(jié)點(diǎn)，區(qū)域上結(jié)點(diǎn)可以直接得到，余下的屬于區(qū)域外結(jié)點(diǎn)。

其中v1，v2為相應(yīng)區(qū)域的權(quán)值，其權(quán)重參照相應(yīng)區(qū)域的交通狀況或者所要研究問題的附屬條件，文章給定v1=2，v2=1、進(jìn)行模擬，再次進(jìn)行最短路計(jì)算，取結(jié)點(diǎn)總數(shù)的1/4作為交警服務(wù)平臺數(shù)，通過平臺設(shè)置的快速算法，得到了如圖10所示的設(shè)計(jì)方案。表4給出了平臺所在結(jié)點(diǎn)。

對距離分區(qū)域加權(quán)后，計(jì)算得總共有222個(gè)路口與相鄰路口距離不足500m，路口距離過近對道路的通行效率有影響。

4.3 基于結(jié)點(diǎn)的交警服務(wù)平臺設(shè)計(jì)

在圖論中，結(jié)點(diǎn)的度反映出該結(jié)點(diǎn)與其他結(jié)點(diǎn)的連通性。對于有向圖而言，定義了出度與入度，若將度作為流量來看，則對于無向圖，流量是平衡的，而有向圖可能會(huì)出現(xiàn)不平衡的現(xiàn)象，假設(shè)每個(gè)路口都會(huì)發(fā)生阻滯，而通過立交、右轉(zhuǎn)彎等，路口可能存在某些路線不需要等待，這些不需要等待的路線在經(jīng)過當(dāng)前路口之后，會(huì)在下一個(gè)結(jié)點(diǎn)發(fā)生阻滯。

經(jīng)過對長沙市各路口進(jìn)行了分析篩選計(jì)算，總共有50個(gè)點(diǎn)交通流量易發(fā)生堆積.對交警服務(wù)平臺的設(shè)置，也應(yīng)重點(diǎn)放在這一類路口，選擇以上所有結(jié)點(diǎn)設(shè)置交警服務(wù)平臺。表5給出了交通流量容易發(fā)生堆積的結(jié)點(diǎn)，圖11畫出了相應(yīng)的結(jié)點(diǎn)位置。

經(jīng)觀察可以發(fā)現(xiàn)，除了單行線，丁字路口也容易發(fā)生流量堆積的現(xiàn)象。在流量模型中，每個(gè)路口的流量將會(huì)影響到下一個(gè)路口，由于右轉(zhuǎn)彎不需要等待紅燈，直接影響到了下一個(gè)路口。現(xiàn)在長沙市已經(jīng)對某些路口右轉(zhuǎn)彎設(shè)置了紅綠燈，以此控制轉(zhuǎn)彎車流量對路口通行的影響。文章以長沙市為藍(lán)本進(jìn)行模擬分析，所收集的數(shù)據(jù)并未能有效反映出這一類情況。

實(shí)際上分析道路的流量還應(yīng)考慮到每條道路的車道數(shù)，在車道數(shù)減少的情況下容易因并道引起擁堵，影響流量的因素還包括大多數(shù)司機(jī)的習(xí)慣行駛路線，最后這個(gè)因素有較大的主觀成分，超出了文章所考慮的范圍。

4.4 長沙市交警服務(wù)平臺優(yōu)化設(shè)計(jì)

由于長沙市的路口數(shù)多，直接采用優(yōu)化選址的算法，其運(yùn)算量規(guī)模難以想象，因此先要對交警服務(wù)平臺進(jìn)行初選，確定主要的路口，然后根據(jù)所選擇方案進(jìn)行適當(dāng)?shù)奶砑樱懊娣謩e就快速路、城市區(qū)域劃分、結(jié)點(diǎn)流量三個(gè)方面對交警服務(wù)平臺選址進(jìn)行了設(shè)計(jì)。現(xiàn)將按以下步驟進(jìn)行綜合：（1）按區(qū)域?qū)Y(jié)點(diǎn)之間距離進(jìn)行加權(quán)；（2）計(jì)算出距離加權(quán)后的最短路矩陣；（3）計(jì)算快速路不能覆蓋區(qū)域；（4）對指定區(qū)域進(jìn)行設(shè)計(jì)，獲取結(jié)點(diǎn)集合；（5）進(jìn)行結(jié)點(diǎn)分析，得到集合；（6）對集合取并，得到初選的結(jié)點(diǎn)集合。

對快速路不能覆蓋區(qū)域按1/4的結(jié)點(diǎn)數(shù)取點(diǎn)，共設(shè)計(jì)了32個(gè)平臺。在獲得當(dāng)前方案后，與基于結(jié)點(diǎn)分析的選址方案取并集。

在對平臺選擇的路口進(jìn)行了初選之后，還需要對平臺選址進(jìn)行分析，對覆蓋薄弱的地區(qū)進(jìn)行服務(wù)平臺的適當(dāng)添加。為了對路口是否在覆蓋區(qū)域范圍，現(xiàn)定義平臺的最大服務(wù)半徑r=max{ri}，其中ri代表平臺i的服務(wù)半徑。由于每個(gè)平臺的服務(wù)半徑不同，現(xiàn)取其最大值作為統(tǒng)一的衡量標(biāo)準(zhǔn)。為了便于計(jì)算，還需要將最大服務(wù)半徑r適當(dāng)轉(zhuǎn)化為平臺之間的最短路程lij。對所有平臺進(jìn)行討論，考慮對區(qū)域進(jìn)行分塊，各平臺進(jìn)行聚類劃分，平臺服務(wù)的區(qū)域也就減小到相應(yīng)聚類所在區(qū)域，劃分的依據(jù)是按照最近的路程進(jìn)行歸類，劃分算法借用圖論的連通性，得到平臺與最近距離平臺之間的聯(lián)系。通過最短路程導(dǎo)出的聚類，每一個(gè)聚類最少有兩個(gè)元素，因而每個(gè)聚類都存在最大服務(wù)半徑rc。只需要令最大服務(wù)半徑r=max{rc}，最終平臺選址和平臺聚類的劃分如圖12所示。

此時(shí)最大服務(wù)半徑限制為4238.3m，服務(wù)平臺不能覆蓋的路口有：

（云棲路，繞城高速），（瀟湘路，南三環(huán)），（三一大道，汽配城路）。

5 結(jié)束語

文章通過圖論中最短路算法定義了交警服務(wù)平臺的服務(wù)半徑，并以此作為選址方案的基礎(chǔ)，在貼近真實(shí)的基礎(chǔ)上，對長沙市道路結(jié)構(gòu)進(jìn)行了分析，并以此選定了長沙市的快速路，確定了基于快速路的交警服務(wù)平臺設(shè)計(jì)。在分析了湘江、京廣鐵路等對城市交通影響以后，確定了以二環(huán)線為基礎(chǔ)的分區(qū)域的服務(wù)平臺設(shè)計(jì)方案。在單獨(dú)對結(jié)點(diǎn)進(jìn)行分析以后，得到了基于結(jié)點(diǎn)的設(shè)計(jì)方案，最終在綜合了三個(gè)方面因素以后，對長沙市交警服務(wù)平臺進(jìn)行了總設(shè)計(jì)，得到總設(shè)計(jì)方案。

城市交通模型應(yīng)用前景廣，對于加油站設(shè)置、保險(xiǎn)公司快賠處理點(diǎn)設(shè)置都有參考價(jià)值，甚至可以擴(kuò)展到整個(gè)國家物流運(yùn)輸網(wǎng)絡(luò)的規(guī)劃。對模型改進(jìn)以后還可以對道路的通行能力進(jìn)行逐一分析，得到更貼近實(shí)際的方案。

參考文獻(xiàn)

[1]楊曉娟，李嘉.快速路設(shè)計(jì)在城市道路設(shè)計(jì)中的應(yīng)用分析[J].城市建設(shè)理論研究，2012，7：1-3.

[2]李陽，楊東.重慶市交巡警的勝任特征研究[J].人力資源管理，2011，3：184-185.

[3]張妲，王小凡，徐國兵.舊城區(qū)城市道路的有機(jī)更新--以長沙市紅旗區(qū)支路網(wǎng)規(guī)劃為例[J].規(guī)劃師，2006，22（1）：40-42.

[4]孫登文.一種有向圖中道路的識別方法[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2001，41（11） ：127-128.

[5]張維琪.坐標(biāo)變換在規(guī)劃設(shè)計(jì)中的應(yīng)用[J].城市建設(shè)理論研究，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].北京建筑工程學(xué)院學(xué)報(bào)，2006，22（1）：52-54.

[8]戴建國，曹傳東，郭理.遞歸算法應(yīng)用分析[J].電腦知識與技術(shù)，2008，4（28）：107-110.

作者簡介：張逵（1973-），男，湖南祁陽人，長沙學(xué)院信息與計(jì)算科學(xué)系講師。