基于Dijkstra算法的開放小區(qū)對周圍道路的影響研究

牟菡子，王加慧，張宇恒，吳宇航

(1. 華北理工大學(xué)理學(xué)院，河北 唐山 063009；2. 華北理工大學(xué)以升創(chuàng)新教育基地，河北 唐山 063009；3. 華北理工大學(xué)信息工程學(xué)院，河北 唐山 063009；4. 河北省數(shù)據(jù)科學(xué)與應(yīng)用重點實驗室，河北 唐山 063009；5. 唐山市數(shù)據(jù)科學(xué)重點實驗室 河北唐山 063009；6. 華北理工大學(xué) 數(shù)學(xué)建模創(chuàng)新實驗室，河北 唐山 063009)

0 引言

建立合理的評價指標(biāo)體系用來評價開放小區(qū)對周邊道路通行的影響。首先分析出可以衡量道路通行狀況的指標(biāo)，得到道路車流量、道路行人量、自由流速度、紅綠燈數(shù)量、路網(wǎng)密度、排隊長度和通過平均時間七個評價指標(biāo)，對初步選定的評價指標(biāo)采用條件廣義方差極小法選取在評價過程中作用較大的評價指標(biāo)建立評價指標(biāo)體系，方差大于域值的指標(biāo)為道路車流量、道路行人量、通過平均時間即為最終確定的指標(biāo)。

建立模型研究小區(qū)開放對周邊道路交通的影響，通過建立改進的Dijkstra模型，將小區(qū)或周圍處理作為節(jié)點，利用上一步得到的評價指標(biāo)將有向邊賦與時間有關(guān)的權(quán)值，通過路網(wǎng)的被選擇通過率加權(quán)求和到一條有向邊上，求得開放小區(qū)前后的任意兩目標(biāo)點的最短時間，用于反應(yīng)其對交通狀況的影響。對研究的十個小區(qū)按不同情況分兩類，得到兩類小區(qū)權(quán)值求解公式為：

在以上模型的基礎(chǔ)上，將小區(qū)分為環(huán)形直形兩類，結(jié)合實際情況考慮小區(qū)進出口數(shù)量及主干道結(jié)構(gòu)，通過分析其對車流的疏散或匯集情況以及擁擠度這一概念，根據(jù)第二問求出權(quán)值公式，賦予不同權(quán)值，對開放小區(qū)前的普通時段及高峰時段，開放小區(qū)后的普通時段及高峰時段分別進行求解，得到高峰時段環(huán)形小區(qū)改善道路通行條件好，普通時段直行小區(qū)改道路通行條件較好。

通過所建立的模型，分析一天之內(nèi)不同時段開放或關(guān)閉小區(qū)對交通道路情況的影響，建立以優(yōu)化時間，路徑為目標(biāo)的雙目標(biāo)優(yōu)化模型。對比結(jié)果建立以時間路徑為對象的雙目標(biāo)優(yōu)化模型，并得到動態(tài)優(yōu)化方案，據(jù)此提出針對性可操作性建議。

1 條件廣義方差極小法確定評價指標(biāo)

1.1 評價指標(biāo)的初步確定

選取合適的評價指標(biāo)，建立合適的評價指標(biāo)體系，用以評價開放封閉式小區(qū)對周邊道路通行的影響。

選取評價指標(biāo)關(guān)鍵在于評價指標(biāo)在評價過程中的作用大小。假定要從N個指標(biāo)中選取一個指標(biāo)來評價某事物，則應(yīng)該選取其中最具有代表性的指標(biāo)，但一個指標(biāo)絕不能把N個指標(biāo)的評價信息都反映出來，故可以采用條件廣義方差極小法，反應(yīng)不完全的部分就是這個指標(biāo)作為代表產(chǎn)生的誤差，選取的指標(biāo)越具有代表性，誤差就越小，重復(fù)這一過程，即可選擇出若干個代表性指標(biāo)。

首先分析出能夠評價周圍道路通行情況的因素，通過查詢文獻[8]和分析，得到七個評價周圍道路通行能力的指標(biāo)，分別為道路車流量，道路行人量，自由流速度，紅綠燈數(shù)量，路網(wǎng)密度，排隊長度，通過平均時間。給定p個指標(biāo)的組觀察數(shù)據(jù)：

其中給定17~xx的指標(biāo)分別為：道路車流量，道路行人量，自由流速度，紅綠燈數(shù)量，路網(wǎng)密度，排隊長度，通過平均時間。

其中道路車流量為單位時間內(nèi)通過某段路的車輛數(shù)量，自由流速度為路段在低交通量，低密度情況下機動車所能達到的行程速度；路網(wǎng)密度為在一定區(qū)域內(nèi)，道路網(wǎng)的總里程與該區(qū)域的面積的比值[7]，排隊長度為在道路通行不暢的條件下，車輛等待隊伍長度。通過查找數(shù)據(jù)[5]，以北京市內(nèi)十個小區(qū)為例，分析開放封閉式小區(qū)對周邊道路通行的影響。

1.2 計算廣義方差

所查詢到的10個樣本數(shù)據(jù)，相應(yīng)用矩陣X表示，即：

計算均值：

計算方差：

協(xié)方差：

根據(jù)Matlab計算得到八個指標(biāo)的條件廣義方差如下：

表1 指標(biāo)對應(yīng)條件廣義方差Tab.1 Index corresponds to conditional generalized variance

其中自由流速度、紅綠燈數(shù)量、路網(wǎng)密度、排隊長度的條件廣義方差小于設(shè)定的閾值 1.50E-25，所以選擇忽略，故而第一問選取的指標(biāo)在不考慮小區(qū)內(nèi)部結(jié)構(gòu)的情況下為道路車流量，道路行人量，通過平均時間。

2 迪杰斯特拉算法求解

要求建立車輛通行的數(shù)學(xué)模型，研究開放小區(qū)對周圍道路同行的影響，在此使用改進的 Dijkstra算法求解。確定研究對象為北京某區(qū)域，具體數(shù)據(jù)根據(jù)文獻[6]得到，其中包括十個小區(qū)及路網(wǎng)如下。

圖1 研究對象分布圖Fig.1 Distribution map of research objects

圖2 主權(quán)邊副權(quán)變關(guān)系Fig.2 The relation of sovereignty side and sub – contingency

將每一個小區(qū)抽象為節(jié)點，小區(qū)關(guān)閉后將小區(qū)周圍的路口抽象為節(jié)點；將周圍可通行的道路抽象為連接道路上各小區(qū)的有向邊，查詢地圖能夠發(fā)現(xiàn)每兩個小區(qū)之間有多條道路可通行，為了求得更為準(zhǔn)確的權(quán)邊，以第一步得到的指標(biāo)為基礎(chǔ)對每一條可通行道路賦值，將這些道路以車輛選擇通過率為權(quán)重加權(quán)求和，得到有向邊的最終賦值。由于路徑不能體現(xiàn)改變前后的準(zhǔn)確情況，因為賦值與時間有關(guān)，可視化過程如下：

其中，s1、s2表示任意兩小區(qū)或路口，Pi表示有向邊權(quán)值，pi表示每一條通行道路的權(quán)值，車輛選擇通過率為li，公式如下：

對于每一段的權(quán)值賦值，基于篩選得到的指標(biāo)，得到其與通行時間的關(guān)系，由于每條路徑之間的通行規(guī)則不同，例如路徑間存在學(xué)校，學(xué)校附近路段限速等問題，所以會存在異常值情況，因此將所得值進行分類，并按照分類分別進行模型求解。

對于第一類數(shù)據(jù)，通過對散點圖的擬合確定第一種分類為：京華豪園，雙龍小區(qū)，安慧里，頤源居，水清木華，擬合結(jié)果如下：

圖3 散點擬合圖Fig.3 Scatter plot

其中，擬合度達到0.9899，SSE值為4.625e-05，結(jié)果可靠。

公式如下：

得到的第二類數(shù)據(jù)為：方星園，華騰園，九龍山家園，回龍觀，豐益花園。擬合結(jié)果如下：

圖4 散點擬合圖Fig.4 Scatter plot

其中，擬合度達到0.9839，SSE為400.6，結(jié)果可靠。

公式如下：

其中：

通過以上計算公式，對不同小區(qū)之間的道路進行加權(quán)求和，得到權(quán)邊賦值，結(jié)果如下，通過Matlab賦值求解：

圖5 抽象節(jié)點圖Fig.5 Abstracts the node diagram

3 小區(qū)開放結(jié)果模型建立與求解

3.1 思維導(dǎo)圖

圖6 流程圖Fig.6 Flow chart

3.2 模型的建立與求解

基于得到的模型，考慮不同類型的小區(qū),包括單入口單出口，多入口多出口，單入口多出口，單出口多入口對分散周圍道路車流以及對交通路網(wǎng)的影響；主干道為環(huán)形結(jié)構(gòu)以及直行結(jié)構(gòu)對擁擠度進而對通行速度的影響和車流量分散效果。

對于前者，引入等價節(jié)點[3]這一概念，通過與時間相關(guān)的權(quán)值的相應(yīng)減少或增加表示對車流量的分散和集中效果；

對于后者，由于在周圍道路車流量不高時，直行結(jié)構(gòu)小區(qū)的單位時間通過率要高于圓形結(jié)構(gòu)小區(qū),由于直行結(jié)構(gòu)小區(qū)主干道為直線，在相同速度的情況下，單位時間內(nèi)通過的車輛數(shù)量多，所以單位時間內(nèi)停留在小區(qū)內(nèi)的車輛少，故擁擠度較低，環(huán)形小區(qū)主干道為環(huán)形，在交通量高時有疏散車流的效果，故擁擠度低。

單位時間內(nèi)停留在小區(qū)的車輛數(shù)量少，故而在某一周圍道路車流量閾值之前，圓形結(jié)構(gòu)的小區(qū)擁擠率高于直行結(jié)構(gòu)小區(qū)，在某一閾值[1]之后，隨著周圍道路車流量增大，圓形結(jié)構(gòu)小區(qū)作為通過道路起到了分流疏散的效果，類似于路口轉(zhuǎn)盤，此時圓形結(jié)構(gòu)小區(qū)的擁擠率低于直行結(jié)構(gòu)小區(qū)的擁擠率。

圖7 等價節(jié)點表示圖Fig.7 Equivalent Node Representation Graph

圖8 環(huán)形結(jié)構(gòu)示意圖Fig.8 Schematic diagram of ring structure

圖9 直行結(jié)構(gòu)示意圖Fig.9 Straight line structure diagram

根據(jù)道路通行規(guī)則、小區(qū)內(nèi)道路寬度、小區(qū)內(nèi)車流量及周邊道路車流量進行定性分析得出的關(guān)于環(huán)形小區(qū)與直行小區(qū)擁擠度公式：

圖10 小區(qū)內(nèi)擁擠度與外部車流量關(guān)系圖Fig.10 Diagram of the relationship between the crowding degree in the community and the external traffic flow

公式定性分析結(jié)果可視化：

結(jié)合上述方法，對查詢[2]到的不同類型的小區(qū)信息數(shù)據(jù)進行處理，分析各小區(qū)信息如下表所示：

表1 小區(qū)信息表Tab.1 Cell information table

3.3 模型的結(jié)果分析

通過上述賦值方法，結(jié)合數(shù)據(jù)[4]對研究對象分高峰時段與普通時段對小區(qū)開放前后進行求解，并對Matlab求解的量化時間結(jié)果進行可視化表出，結(jié)果如下：

由圖分析，在交通量較低，路面情況良好的普通時段下，小區(qū)的開放提高了路網(wǎng)密度，緩解了交通壓力，提高了行駛效率，故而普遍開放小區(qū)時行駛時間較短。

由圖分析，部分小區(qū)由于結(jié)構(gòu)不夠，例如多入口單出口結(jié)構(gòu)小區(qū)，會造成車輛堵塞，在交通量高的情況下開放此類型的小區(qū)起到了反效果，但大多數(shù)的小區(qū)表現(xiàn)出了疏散車流，提高路網(wǎng)密度，緩解交通壓力提高行駛速度的效果，故而大部分情況下開放小區(qū)會使得交通路況在高峰時段壓力緩解。

圖11 普通時段開放關(guān)閉小區(qū)效果Fig.11 General period of time to open and close the community effect

圖12 高峰時段開放關(guān)閉小區(qū)效果Fig.12 Opening and closing the community during peak hours

4 小區(qū)開放的合理化建議

基于第三問的求解結(jié)果，建立以優(yōu)化時間，路徑為目標(biāo)的雙目標(biāo)優(yōu)化模型。其中：

基于第三問的啟發(fā)，重點分析一天之內(nèi)不同時段開放或關(guān)閉小區(qū)對交通道路情況的影響，可視化結(jié)果如下：

圖13 一天內(nèi)不同時段開放關(guān)閉小區(qū)效果Fig.13 The effect of opening and closing the community at different times of the day

據(jù)圖分析，由于不同類型小區(qū)的構(gòu)造，例如多入口單出口類型在高峰期會起到反效果，故而不宜選擇在高峰期開放，但在大體上開放小區(qū)對交通道路情況的影響利大于弊，故而需要在一天內(nèi)根據(jù)不同的時段有選擇的開放和關(guān)閉不同類型的小區(qū)。針對此種情況得到如下優(yōu)化建議：

（1）在高峰時段，可以選擇定時開放環(huán)形結(jié)構(gòu)小區(qū)，多進出口或者單進多出結(jié)構(gòu)的小區(qū)，達到疏散車流，提高路網(wǎng)密集度，降低擁擠度，以提升通行效率避免堵車情況的發(fā)生。同時限制開放多進單出小區(qū)，以防在小區(qū)出口處堵塞。

（2）在普通時段，道路通行狀況良好，可以選擇開放單進單出小區(qū)或者直行結(jié)構(gòu)小區(qū)在提升路網(wǎng)密度的條件下，提高通行車輛效率。

（3）對于多進單出結(jié)構(gòu)的小區(qū)，由于其可以匯聚車流，且在數(shù)值上表現(xiàn)出對交通運行的負面情況，應(yīng)盡量關(guān)閉此類結(jié)構(gòu)小區(qū)或者在此小區(qū)路口加強管制和監(jiān)督。