基于開放街區(qū)的車輛行駛最優(yōu)路徑設(shè)計(jì)

潘福全，邢 英，魏金麗，楊金順，張麗霞，劉尊民

青島理工大學(xué)機(jī)械與汽車工程學(xué)院，山東青島266520

近年來(lái)，住宅從傳統(tǒng)鄰里開發(fā)(traditional neighborhood development, TND)模式和以公共交通為導(dǎo)向的開發(fā)(transit-oriented development, TOD)模式等新城市主義到中高密度住區(qū)，都提倡了開放性、混合性、多樣性和可持續(xù)性發(fā)展．如美國(guó)紐約巴特利公園城街道采取方格形網(wǎng)狀的形式，將地塊劃分成小面積街區(qū)，使公共空間更加方便[1]；日本的新城建設(shè)模式采用了“沿道中庭型住棟”形式，在空間規(guī)劃方面體現(xiàn)了開放型的空間結(jié)構(gòu)街區(qū)和公共空間整體設(shè)計(jì)，如幕張濱城住宅區(qū)；新加坡2l世紀(jì)住宅的開放網(wǎng)絡(luò)結(jié)構(gòu)，以Punggol新鎮(zhèn)為典型模式代表，采用了棋盤式的住宅模式，區(qū)塊作為基本單元，注重公共交通與空間的整合[2]．隨著居民日益多樣化的居住生活追求，當(dāng)前中國(guó)也出現(xiàn)了很多新類型、新模式的住區(qū)建設(shè)．北京建外SOHO是一個(gè)開放式混合型街區(qū)，通過多種功能的混合和空間層次上的設(shè)計(jì)，將道路與城市路網(wǎng)銜接，并設(shè)置中央公園，形成開放的空間結(jié)構(gòu)，極大地改善了交通環(huán)境．上海創(chuàng)智坊以圍合式的住宅街區(qū)作為基本單元，在空間形態(tài)上形成私密的庭院空間和開放的公共空間，采用較小的街區(qū)和較密的住宅區(qū)路網(wǎng)，形成舒適便捷的城市交通環(huán)境[3]．

關(guān)于小區(qū)開放對(duì)交通影響方向也有相關(guān)研究．LIN等[4]研究了在居住社區(qū)開放后對(duì)周邊道路交通的影響；QIU等[5]基于小區(qū)開放的條件下對(duì)周邊交通進(jìn)行了研究；肖旭[6]在社區(qū)開放的條件下，分析了周邊路網(wǎng)的通行能力；李良[7]通過研究小區(qū)開放對(duì)周邊道路通行能力的影響，證明了開放街區(qū)可以有效緩解周邊道路交通壓力．2016年，《中共中央國(guó)務(wù)院關(guān)于進(jìn)一步加強(qiáng)城市規(guī)劃建設(shè)管理工作的若干意見》提出“新建住宅要推廣街區(qū)制，原則上不再建設(shè)封閉住宅小區(qū)”的政策原則，旨在實(shí)現(xiàn)住宅小區(qū)內(nèi)部道路的公共化利用和解決交通路網(wǎng)布局產(chǎn)生的問題，促進(jìn)人們節(jié)約利用緊張的城市用地，樹立“窄馬路、密路網(wǎng)”的城市道路布局理念，打造方便快捷生活圈．

因此，通過改進(jìn)Floyd算法，提高算法的求解速度，并應(yīng)用到基于開放街區(qū)條件下的車輛行駛路線時(shí)間最優(yōu)路徑的計(jì)算，對(duì)實(shí)現(xiàn)道路資源的共享，緩解交通壓力，具有重要意義．

1 最優(yōu)路徑方法分析

目前比較常用的最短路徑算法包括Dijkstra、Bellman-Ford和Floyd算法，它們各有不同的適用范圍，需根據(jù)所規(guī)劃的路徑特點(diǎn)選擇適合的最短路算法．Floyd算法是一種動(dòng)態(tài)路徑規(guī)劃算法，其主要的適用范圍是：① 所有結(jié)點(diǎn)對(duì)的最短路徑問題(all-pairs shortest paths, APSP)；② 在起訖點(diǎn)(origin-destination, OD)和線路密集的圖上顯示效果最好；③ 網(wǎng)絡(luò)圖上各線路的邊權(quán)可正可負(fù)．所以，F(xiàn)loyd算法是針對(duì)在多源點(diǎn)之間尋找最優(yōu)路徑的外賣送餐類實(shí)際生活問題的較佳方法．

(1)

Floyd算法計(jì)算任意兩點(diǎn)之間的最短路徑長(zhǎng)度是將初始矩陣D(0)依次插入多個(gè)中間節(jié)點(diǎn)數(shù)次迭代后計(jì)算得到的．將第k-1個(gè)距離矩陣D(k-1)的最短路徑長(zhǎng)度與基于D(k-1)插入新節(jié)點(diǎn)后得到的最短路徑長(zhǎng)度進(jìn)行比較，最小值為D(k)的最短路徑長(zhǎng)度．多次迭代至無(wú)新數(shù)據(jù)[8]，即從所有可通過路徑的長(zhǎng)度中選出最小值作為兩點(diǎn)之間的最短路徑值．

1.1 改進(jìn)的 Floyd算法

傳統(tǒng)的Floyd算法在節(jié)點(diǎn)較多時(shí)，迭代次數(shù)會(huì)很多，增大了算法復(fù)雜度．本研究針對(duì)多頂點(diǎn)的最短路徑問題，采用改進(jìn)的Floyd算法降低計(jì)算量，通過計(jì)算不含負(fù)回路的路網(wǎng)中任意起訖點(diǎn)之間的最短路徑，找到各頂點(diǎn)之間的最優(yōu)路徑．

1.1.1 算法思想

1.1.2 算法步驟

步驟1：由有向網(wǎng)絡(luò)圖構(gòu)建的初始距離矩陣(k=0)為

i=1, 2, …,n，j=1, 2, …,n

(2)

步驟3：比較D(k-1)與基于D(k-1)插入后的最短路徑長(zhǎng)，若D(k)=D(k-1)， 則輸出為最短路徑值；否則，令k加1，并跳轉(zhuǎn)到步驟2繼續(xù)迭代[10]．

1.1.3 算法分析

1.2 應(yīng)用分析

對(duì)于車輛行駛尋找最優(yōu)路徑問題，需要算出任意兩節(jié)點(diǎn)之間的最短距離．改進(jìn)的Floyd算法計(jì)算復(fù)雜度降低，計(jì)算效率高，且容易理解，代碼編寫也更簡(jiǎn)單．將改進(jìn)Floyd算法應(yīng)用于小區(qū)開放后車輛行駛路徑優(yōu)化模型的流程圖如圖1．

圖1 路徑優(yōu)化模型的算法流程圖Fig.1 Algorithm flow chart of path optimization model

2 青西新區(qū)CBD外賣送餐路徑調(diào)查及優(yōu)化

本研究調(diào)查的中國(guó)青島市西海岸新區(qū)(青西新區(qū))中央商務(wù)區(qū)(central business district, CBD)，包括黃島區(qū)全部行政區(qū)域的青島西海岸新區(qū)的中央商務(wù)區(qū)(北至嘉陵江路，南至濱海大道，西至太行山路，東至衡山路)，詳圖請(qǐng)掃描論文末頁(yè)右下角二維碼見圖S1．該范圍內(nèi)現(xiàn)存在小區(qū)封閉和街區(qū)隔離的現(xiàn)象，因城市公共道路與住宅小區(qū)內(nèi)部的道路沒有打通，導(dǎo)致區(qū)域交通擁堵嚴(yán)重，同時(shí)公交線路與站點(diǎn)覆蓋不全，城市道路交通效率低下．為響應(yīng)國(guó)家政策，解決城市交通公共道路網(wǎng)絡(luò)覆蓋率不高的問題，青西新區(qū)CBD也將逐步建設(shè)開放小區(qū)，并開放已建封閉住宅．在基于開放街區(qū)下，以青西新區(qū)CBD范圍內(nèi)的外賣送餐車輛行駛為例來(lái)設(shè)計(jì)最優(yōu)路徑．

2.1 青西新區(qū)CBD現(xiàn)狀調(diào)查

2.1.1 路網(wǎng)現(xiàn)狀調(diào)查

青西新區(qū)CBD范圍內(nèi)大部分屬封閉小區(qū)，區(qū)域內(nèi)道路資源緊張，帶來(lái)了較為嚴(yán)重的交通問題．一方面，城市路網(wǎng)稀疏，干道承擔(dān)了主要交通量，缺少下一層次的路網(wǎng)，令干道交通負(fù)荷過大，特別是區(qū)域內(nèi)的路網(wǎng)交叉口供給能力不足而路段供給能力過剩，干道交通在很多交叉口發(fā)生擁堵，但在路段上卻常處于不飽和狀態(tài)，有違干道設(shè)計(jì)速度的要求，令微循環(huán)系統(tǒng)不暢．另一方面，城市交通因封閉小區(qū)切割帶來(lái)的被迫繞行，降低了路網(wǎng)結(jié)構(gòu)效率，同時(shí)交通線路與站點(diǎn)等覆蓋率較低．調(diào)查范圍內(nèi)開放小區(qū)道路資源前后的基本路網(wǎng)如圖2．

圖2 小區(qū)開放前后基本路網(wǎng)Fig.2 (Color online) The basic road network before and after the opening of the community

2.1.2 外賣送餐的起訖點(diǎn)及路線分布現(xiàn)狀調(diào)查

以青西新區(qū)CBD的澳龍花園、綠島印象和香江花園等小區(qū)作為終點(diǎn)，去掉分散的外賣點(diǎn)，僅保留外賣餐館較密集的中心地帶作為此地區(qū)的代表取餐點(diǎn)為起點(diǎn)．調(diào)查區(qū)域內(nèi)外賣點(diǎn)聚集地分布情況請(qǐng)掃描論文末頁(yè)右下角二維碼查看圖S2．

外賣送餐過程包括訂單接收、餐品處理、遞送取餐和終端送餐．送餐員接到訂單信息后抵達(dá)外賣點(diǎn)取餐，從起點(diǎn)出發(fā)，并運(yùn)送至小區(qū)終點(diǎn)為外賣送餐模式．圖3為調(diào)查區(qū)域內(nèi)OD的位置以及外賣送餐的現(xiàn)狀路線．由圖3可見，一方面，封閉小區(qū)會(huì)在周邊形成較多丁字路和斷頭路，不利于城市密集路網(wǎng)的形成，造成周邊交通堵塞．另一方面，封閉小區(qū)令街區(qū)被隔離，造成道路和土地等資源的浪費(fèi)，也破壞了城市街區(qū)的社會(huì)性．送餐員從接到訂單，到抵達(dá)外賣點(diǎn)，再到目的小區(qū)的過程中，途經(jīng)很多封閉小區(qū)，而繞行會(huì)造成人力與時(shí)間的浪費(fèi)．若全部小區(qū)都是開放的，開放街區(qū)令送餐車輛有更多可選路線．基于開放的密集新路網(wǎng)設(shè)計(jì)OD最優(yōu)路徑，則能讓外賣工作人員更加節(jié)省路上時(shí)間，大幅提高工作效率．

圖3 調(diào)查范圍內(nèi)OD及送餐現(xiàn)狀路線Fig.3 (Color online) The OD points and the current route of food delivery in the survey area

2.2 青西新區(qū)CBD外賣送餐路徑優(yōu)化

由圖3可見，在調(diào)查區(qū)域內(nèi)，已有部分已建成的封閉小區(qū)．繞行不僅增加了送餐時(shí)間，甚至常有送餐員因送餐時(shí)間的要求，為趕時(shí)間發(fā)生交通違法行為，產(chǎn)生極大的道路安全威脅隱患．目前，城市內(nèi)電動(dòng)車及摩托車行車速度一般為20～40 km/h，取最低速度，即設(shè)外賣送餐員駕車行駛所用速度為20 km/h，由此可計(jì)得在送餐現(xiàn)狀路線條件下的外賣送餐所用時(shí)間如表1．其中，A～G為店鋪外賣起點(diǎn)，1～20為小區(qū)．

按照國(guó)家政策，未來(lái)小區(qū)將逐步開放，使內(nèi)部道路公共化．一旦小區(qū)道路公共化并與周邊環(huán)境結(jié)合，就可形成有助于改善交通擁擠問題的城市布局．小區(qū)內(nèi)部道路的公共化利用，可提高城市路網(wǎng)密度，增加道路面積，減小交叉口規(guī)模，提升道路通行能力、交通網(wǎng)絡(luò)連通性和微循環(huán)系統(tǒng)性能，通過分擔(dān)干道交通量，使道路交通流均衡分布[11]，緩解了交通壓力，改善交通出行的環(huán)境，節(jié)省人們出行時(shí)間和各種社會(huì)資源．

本研究基于調(diào)查范圍內(nèi)封閉小區(qū)全部開放的假設(shè)，通過將最短路問題的理論運(yùn)用到車輛行駛路線優(yōu)化問題中．以外賣送餐為例，將外賣中的任意起點(diǎn)與小區(qū)終點(diǎn)相對(duì)應(yīng)，利用改進(jìn)Floyd算法計(jì)算出任意OD間優(yōu)化后的最短路徑長(zhǎng)度，從而完成最優(yōu)路徑設(shè)計(jì)．

表1 現(xiàn)狀路線外賣送餐所用時(shí)間

判斷外賣起點(diǎn)到小區(qū)終點(diǎn)是否有直接相連的路線，若有直接相連的路線，則值為該路線的值；若不存在直接相連的邊，則值為∞，由此來(lái)構(gòu)建初始矩陣D(0)． 將同一小區(qū)內(nèi)所有出行頂點(diǎn)的某一集中點(diǎn)作為小區(qū)重心，即終點(diǎn)，并基于D(0)， 選擇任意外賣點(diǎn)與小區(qū)重心之間的路線依次插入交叉口頂點(diǎn)作為節(jié)點(diǎn)，利用改進(jìn)Floyd算法避免對(duì)不影響最短路徑值的中間節(jié)點(diǎn)插入后路長(zhǎng)的計(jì)算，得到距離外賣起點(diǎn)和小區(qū)終點(diǎn)之間直線的相近節(jié)點(diǎn)插入后的新路徑，并與未插入之前的路徑距離進(jìn)行對(duì)比，得到最優(yōu)路徑長(zhǎng)度，最終輸出最優(yōu)路徑矩陣D(k)． 在得到任意外賣點(diǎn)與小區(qū)之間的最短路徑后，設(shè)外賣員行車速度為20 km/h，則他在路線優(yōu)化后送餐所用的時(shí)間如表2．

表2 路線優(yōu)化后外賣送餐所用時(shí)間

采用Visual C編譯軟件實(shí)現(xiàn)改進(jìn)Floyd算法求最短路徑，尋找任意OD間的最優(yōu)路徑，實(shí)現(xiàn)優(yōu)化調(diào)查范圍內(nèi)小區(qū)開放后的外賣送餐路線網(wǎng)，結(jié)果如圖4．

圖4 小區(qū)開放后優(yōu)化外賣送餐路網(wǎng)Fig.4 (Color online) The optimized takeout delivery network after the opening of the community

2.3 方案評(píng)價(jià)

在開放街區(qū)條件下，調(diào)查范圍內(nèi)的小區(qū)內(nèi)部道路被公共化，與城市原有路網(wǎng)道路銜接，形成更高效的新城市路網(wǎng)．開放街區(qū)下的外賣員可自由通過小區(qū)內(nèi)部道路，避免不必要繞行，道路可直達(dá)性大增，送餐行駛路線長(zhǎng)度大減．與街區(qū)隔離時(shí)相比，經(jīng)改進(jìn)Floyd算法優(yōu)化的路徑，令送餐員在路上花費(fèi)的時(shí)間平均減少了30.4%．可見，小區(qū)開放可以有效緩解周邊道路的交通壓力，提高城市道路利用率，避免社會(huì)資源的浪費(fèi)，提高城市生活品質(zhì)．

但是，該方案僅假設(shè)了在車輛行駛中無(wú)因意外造成的延誤，忽略了高峰期造成的擁堵，以及因突發(fā)意外事故等因素造成的時(shí)間延誤．

3 結(jié) 論

基于小區(qū)開放的國(guó)家政策導(dǎo)向，將改進(jìn)Floyd算法應(yīng)用到車輛行駛路線的最優(yōu)設(shè)計(jì)中，并以青島西海岸新區(qū)CBD內(nèi)外賣送餐為例，分析算法對(duì)駕駛?cè)诉x擇車輛行駛路線參考價(jià)值，得到以下結(jié)論：

1)在開放街區(qū)的條件下，基于改進(jìn)的Floyd算法求解的最優(yōu)路徑可避免繞路，減少了行駛路線長(zhǎng)度，節(jié)省了行駛時(shí)間，避免了交通擁堵的同時(shí)，降低了行車途中的交通安全隱患．

2)小區(qū)開放令道路資源得以共享，提升了周邊道路通行能力，提高了直達(dá)性，促進(jìn)城市土地的高效利用．