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

青島理工大學機械與汽車工程學院，山東青島266520

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

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

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

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

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

(1)

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

1.1 改進的 Floyd算法

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

1.1.1 算法思想

1.1.2 算法步驟

步驟1：由有向網絡圖構建的初始距離矩陣(k=0)為

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

(2)

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

1.1.3 算法分析

1.2 應用分析

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

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

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

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

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

2.1.1 路網現(xiàn)狀調查

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 方案評價

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

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

3 結 論

基于小區(qū)開放的國家政策導向，將改進Floyd算法應用到車輛行駛路線的最優(yōu)設計中，并以青島西海岸新區(qū)CBD內外賣送餐為例，分析算法對駕駛人選擇車輛行駛路線參考價值，得到以下結論：

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

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