鄭州市交通實時監(jiān)測及

1、2016年全國統(tǒng)計建模大賽參賽論文鄭州市交通實時監(jiān)測及誘導(dǎo)系統(tǒng)探索性研究 基于出租車GPS數(shù)據(jù)的分析彭 霄 徐 端 徐委喬河南省統(tǒng)計局目 錄一、研究背景和目標1（一）研究背景1（二）預(yù)期目標3（三）實現(xiàn)方法和思路3二、相關(guān)理論研究和應(yīng)用綜述4三、數(shù)據(jù)預(yù)處理和模型構(gòu)建5（一）數(shù)據(jù)來源和數(shù)據(jù)選擇5（二）數(shù)據(jù)預(yù)處理6（三）數(shù)據(jù)探索性分析8（四）模型選擇和構(gòu)建11四、模型結(jié)果解讀和結(jié)論15（一）模型結(jié)果解讀15（二）結(jié)論18五、創(chuàng)新點和研究展望18（一）創(chuàng)新點18（二）研究展望19參考文獻20附錄21圖表目錄圖1 滴滴研究院2016上半年平均擁堵延時指數(shù)排名前10位2圖2 文章研究架構(gòu)4圖3 市區(qū)三環(huán)

2、以內(nèi)道路節(jié)點的拾取和編號7圖4 GPS經(jīng)緯度高密度散點圖與市區(qū)地圖對比9圖5 出租車上午7:008:00瞬時速度頻次直方圖9圖6 出租車GPS經(jīng)緯度散點圖及其擁堵區(qū)域二維等高圖10圖7 V1至V6六個變量散點圖矩陣10圖8 V2、V3、V4、V5相關(guān)圖矩陣11圖9 距離最短路徑16圖10 用時最少路徑17圖11 信息素最優(yōu)路徑18表1 鄭州與東京交通環(huán)境對比2表2 出租車GPS原始數(shù)據(jù)5表3 機動車出行的外在影響因素及分類6表4 道路節(jié)點信息7表5 道路節(jié)點的通達數(shù)據(jù)集7鄭州市交通實時監(jiān)測及誘導(dǎo)系統(tǒng)探索性研究基于出租車GPS數(shù)據(jù)的分析摘要：隨著經(jīng)濟快速發(fā)展，機動車保有量迅速增多，城市擁堵日益嚴

3、重。蟻群算法和dijkstra最短路徑算法是路徑規(guī)劃中的經(jīng)典算法，能夠有效的提高城市交通出行效率。本文利用出租車GPS數(shù)據(jù)，取兩種算法的優(yōu)勢，分別以距離最短、用時最少、信息素最優(yōu)為約束條件，規(guī)劃最優(yōu)出行路徑。在計算用時最少路徑時，本文創(chuàng)造性地結(jié)合歷史數(shù)據(jù)和短期內(nèi)道路狀況變化趨勢，構(gòu)建和對比了支持向量機、隨機森林和單指數(shù)平滑等三種未來道路狀況預(yù)測模型，對用時最少算法進行了改良優(yōu)化。最終實現(xiàn)了不同交通出行主體的路徑優(yōu)化選擇，從而提高城市道路整體通行效率，緩解城市交通壓力。關(guān)鍵詞：出租車GPS數(shù)據(jù) 蟻群算法 Dijkstra最短距離算法 路徑規(guī)劃一、研究背景和目標經(jīng)濟中占主導(dǎo)地位的產(chǎn)業(yè)形態(tài)的不同，決

4、定社會經(jīng)濟形態(tài)的不同。當(dāng)前我國經(jīng)濟進入新常態(tài)，新業(yè)態(tài)不斷涌現(xiàn)，特別是大數(shù)據(jù)時代的到來，不斷加速新業(yè)態(tài)的產(chǎn)生。大數(shù)據(jù)的使用不但能夠提供更多元的信息獲得途徑，同時通過對其分析、研究和使用，能夠帶來新的產(chǎn)業(yè)和新的發(fā)展模式，降低各種要素的消耗，提高要素的使用效率。本文正是在這種思維框架下確定了初步的研究方向，沿著這個思維方向，結(jié)合生活中的現(xiàn)實問題，形成了整個研究的框架。通過對城市交通出行效率的探索性研究，推薦出行路徑，有助于滿足不同出行人群需求，提升道路通行效率，降低城市污染，提高城市智慧程度，使城市居民獲得更多幸福感。（一）研究背景近年來，由于經(jīng)濟的快速發(fā)展，人們的生產(chǎn)和生活方式不斷變化，城市機動車

5、保有量和增長速度遠遠超出了現(xiàn)有基礎(chǔ)設(shè)施的承載能力。機動車的快速增長與道路交通設(shè)施的增長不同步，城市規(guī)劃水平和管理水平相對滯后，導(dǎo)致鄭州市城區(qū)交通壓力不斷加大，城市交通日益擁堵，嚴重影響了人們的日常工作和生活。2016年7月，滴滴媒體研究院發(fā)布了2016上半年中國城市交通出行報告 注：該報告引自于互聯(lián)網(wǎng)。報告顯示，2016年上半年，全國400個城市平均擁堵延時指數(shù)（高峰期道路平均通過時間與凌晨通暢時刻通行時間的比值）為1.58，平均時速為24.8km/h。報告還顯示，全國最堵的地方其實并非一線城市，多個二、三線城市的擁堵狀況比北京、上海、廣州等一線城市更加嚴重。上半年，全國最擁堵的城市是石家莊，

6、擁堵延時指數(shù)達1.87，意味著早晚高峰期的通行時間要比凌晨多出87%。重慶、西安、濟南分列二至四位，而鄭州、哈爾濱、青島和武漢等多個二、三線城市的擁堵程度與一線城市中最擁堵的北京和廣州相當(dāng)。圖1 滴滴研究院2016上半年平均擁堵延時指數(shù)排名前10位注：高峰擁堵延時指數(shù)=自由流（暢通）車速/早晚高峰平均車速，其中早晚高峰時間段為7:0010:00和17:0020:00，自由流（暢通）車速是指0:006:00的平均車速，延時指數(shù)越大表明越擁堵。眾所周知，日本首都東京交通狀況良好，在城市交通中有“東京模式”之稱，一直是城市交通出行效率的典范。通過對比鄭州和東京的人口集聚水平和機動車保有量密度，可以看

7、出，鄭州市交通出行效率有很大改善和提升空間，通過對相關(guān)交通主體的研究、分析、設(shè)計和規(guī)劃，應(yīng)能提升道路網(wǎng)絡(luò)的通行效率。表1 鄭州與東京交通環(huán)境對比人口密度（人/平方公里）機動車保有量密度（輛/平方公里）交通擁堵情況鄭州12853540高峰期快速路平均時速小于20km東京60163653資料來源：鄭州市交管部門、鄭州市統(tǒng)計年鑒、互聯(lián)網(wǎng)（二）預(yù)期目標本文旨在通過路徑規(guī)劃，改善鄭州市交通出行效率。這主要基于以下兩點原因：一是部分交通主體GPS數(shù)據(jù)的易取得性。隨著GPS定位系統(tǒng)的普及，當(dāng)前城市營運車輛都裝有GPS衛(wèi)星定位系統(tǒng)，實時上傳車輛的運行狀態(tài)和位置信息等數(shù)據(jù)，這些數(shù)據(jù)保存在交通管理部門的服務(wù)器中。

8、二是GPS數(shù)據(jù)自身的特性。GPS數(shù)據(jù)具有大數(shù)據(jù)的基本特性：數(shù)據(jù)體量巨大，相對客觀，沒有人為干擾等。同時，GPS精準度高，數(shù)據(jù)產(chǎn)生頻率高，能夠?qū)崟r反映車輛狀態(tài)和交通網(wǎng)絡(luò)狀況，是進行路徑規(guī)劃的優(yōu)質(zhì)數(shù)據(jù)。本文研究的目標是：實時更新路況信息；通過對未來一段時間交通網(wǎng)絡(luò)狀況的預(yù)測，實時規(guī)劃最優(yōu)路徑；結(jié)合出行主體的不同要求，為出行主體提供更多選擇方案，從而減少交通主體出行時間，提高道路使用效率，降低城市擁堵程度。（三）實現(xiàn)方法和思路出租車司機每天都作業(yè)于城市大大小小的道路上，由于職業(yè)的特殊性，其積累了豐富的行車經(jīng)驗。每一個出租車司機都具有個體的獨立性，其行為和特點與蟻群類似。為了更加詳細準確的了解出租車司

9、機路徑選擇的考慮因素，我們隨機走訪了十幾位出租車司機，通過交流討論，發(fā)現(xiàn)出租車司機群體在出行路線的選擇上，基本是客觀理性的。因此，本文利用出租車GPS數(shù)據(jù)相關(guān)信息，進行最優(yōu)路徑的規(guī)劃和預(yù)測問題研究。具體思路見圖2。圖2 文章研究架構(gòu)二、相關(guān)理論研究和應(yīng)用綜述國內(nèi)的專家學(xué)者利用出租車GPS數(shù)據(jù)進行數(shù)據(jù)挖掘，主要從4個方面進行：對道路狀態(tài)進行估計、對出租車出行行為進行研究、建立出租車調(diào)度系統(tǒng)和改善交通線路規(guī)劃等。目前，單純的利用出租車GPS數(shù)據(jù)對交通出行線路進行規(guī)劃的研究還不多，具有代表性的有以下幾個研究方向和算法模型。唐爐亮將城市道路按功能劃分等級，計算出各路段出租車通行頻率，將之作為必要信息素

10、，綜合考慮路徑通行時間、通行距離、路徑信息素等多個因素，提出了基于蟻群算法的公眾出行路徑規(guī)劃優(yōu)化算法。但是，由于蟻群算法思想的本質(zhì)在于逐步收斂出最優(yōu)路徑，在一定的約束條件下并不能夠保證結(jié)果最優(yōu)。姚鵬使用Oracle 數(shù)據(jù)庫和 MATLAB 軟件對出租車 GPS 軌跡數(shù)據(jù)進行運算和處理，建立了以出租車歷史 GPS 軌跡數(shù)據(jù)和運行軌跡數(shù)據(jù)相結(jié)合的當(dāng)前最優(yōu)路徑推薦算法。但是，道路交通網(wǎng)絡(luò)的狀況時時刻刻發(fā)生著變化，僅僅考慮歷史數(shù)據(jù)和當(dāng)前狀況，對處于快速變化的交通網(wǎng)絡(luò)未必適用。許國淼根據(jù)城市道路交通流的基本特性，分析了不同情況下的路段平均行程速度和交叉口平均行程延誤時間估計算法。最后基于模糊評價的理論，

11、建立以路段平均行程速度和交叉口平均行程延誤作為度量指標的道路交通運行狀態(tài)判別方法，從而實現(xiàn)對城市道路運行狀態(tài)的監(jiān)測。但是，由于GPS數(shù)據(jù)的離散性，導(dǎo)致不同的道路運行狀態(tài)評價體系在一定條件下都具有局限性。譚衛(wèi)針在蟻群算法的基礎(chǔ)上做了改進，他認為不同出租車公司所屬的出租車組處于相互競爭狀態(tài)，通過不同出租車公司信息的不同反饋，來實現(xiàn)交通資源合理分配的規(guī)劃算法。楊建峰在蟻群算法的基礎(chǔ)上，總結(jié)出了一種回溯螞蟻系統(tǒng)，提出了多重蟻群算法。并對蟻群優(yōu)化算法可能使用的相關(guān)領(lǐng)域進行了分析和解讀，其中就包括路徑選擇問題。國外基于機動車GPS數(shù)據(jù)（非僅限出租車）進行道路規(guī)劃的研究起步較早，比較有代表性的有Bullnh

12、eimer,Hart&Strauss基于AS-VRP 算法，Gambadella,Tailrd&Agazzi 基于HAS-VRP算法和Reimann,Stummer&Doerner 基于SbAS-VRP算法的研究等。 注：“AS”即螞蟻系統(tǒng)，該介紹出自于楊建峰蟻群算法以及應(yīng)用研究。綜上，國內(nèi)外對路徑規(guī)劃的研究，從研究方向上看，主要集中在規(guī)劃城市路網(wǎng)最短距離路徑和最短時間路徑。從算法模型上看，國外在蟻群算法和最短路徑算法上已經(jīng)比較成熟，國內(nèi)研究與國外的差距在不斷縮小，但國內(nèi)對不同路徑算法的對比研究較少，對不同算法的結(jié)合使用較少。不同的算法和模型對現(xiàn)實路徑規(guī)劃問題都有很好的

13、啟示作用，但具體到路徑的計算上還需要進一步完善。三、數(shù)據(jù)預(yù)處理和模型構(gòu)建（一）數(shù)據(jù)來源和數(shù)據(jù)選擇鄭州市交通運管局下屬的城市公共交通客運管理處，掌握著全市10800多輛出租車的GPS數(shù)據(jù)。通過協(xié)調(diào)，我們對鄭州市出租車GPS數(shù)據(jù)進行了收集，每天的數(shù)據(jù)量大約是3000萬條，數(shù)據(jù)格式見表2。表2 出租車GPS原始數(shù)據(jù)V1V2V3V4V5V6V71TN727034.7674113.626192016/6/13 0:002562TX053134.72142113.658172016/6/13 0:007693TV256134.72125113.6508122016/6/13 0:007684TQ66803

14、4.7656113.6506322016/6/13 0:002565TY072034.76189113.6075252016/6/13 0:002566TW911134.77805113.6759162016/6/13 0:007687數(shù)據(jù)指標分別為：V1代表車牌號信息，V2代表車輛載客狀態(tài)，V3代表車輛所在緯度，V4代表車輛所在經(jīng)度，V5代表車輛瞬時速度，V6代表數(shù)據(jù)上傳時間，V7信息未知。對于數(shù)據(jù)時間范圍的選擇。本文假定不同情況會對交通主體的行為產(chǎn)生不同影響，對交通網(wǎng)絡(luò)狀況產(chǎn)生影響的主要因素見表3。表3 機動車出行的外在影響因素及分類影響因素分類原因天氣晴天（多云）、嚴重霧霾、雨雪天不同天

15、氣對交通工具和出行路線有較大影響作息時間調(diào)整5月1日-10月1日、其他時間鄭州在此期間，下午作息時間由14:3017:30調(diào)整到15:0018:00季節(jié)因素春、夏、秋、冬季節(jié)變化會影響出行交通工具的選擇擁堵程度早高峰（6:009:00）、晚高峰（17:0020:00）、其他時間早高峰和晚高峰對出行的影響較大，且早高峰和晚高峰的擁堵路段會有所不同出行規(guī)律周一、周二周三周四、周五、周六周日根據(jù)經(jīng)驗周一和周五擁堵程度較其他工作日嚴重，周末擁堵程度相對較低，周二、周三、周四差別不大法定節(jié)假日前后五一、十一、中秋、春節(jié)等法定節(jié)假日前后都會造成不同程度的擁堵為了達到對特定時間段路徑優(yōu)化的研究目的，必須嚴格

16、限制研究條件，以便能從歷史數(shù)據(jù)中采集出所需要的信息，這對優(yōu)化模型、預(yù)測未來短期內(nèi)的交通擁堵情況提供了必要的歷史信息。結(jié)合已有數(shù)據(jù)資源，為了使研究更具代表性，本文選取時間為6月13日上午7:008:00（其特征為：周一、晴天、夏季、早高峰時段、5月1日10月1日期間、不是法定節(jié)假日）的出租車GPS信息作為基礎(chǔ)研究數(shù)據(jù)。在后續(xù)研究中，關(guān)于歷史數(shù)據(jù)的選取，按照上述影響因素及其分類進行篩選。（二）數(shù)據(jù)預(yù)處理1.數(shù)據(jù)篩選。一是收集到的原始數(shù)據(jù)共7個指標，其中V7的信息未知，對本文的研究沒有意義，選擇刪去。二是選擇合適的研究區(qū)域。根據(jù)隨訪的出租車司機和出行經(jīng)驗判斷，交通擁堵的路段主要集中在三環(huán)以內(nèi)，因此，

17、將三環(huán)以內(nèi)出租車GPS數(shù)據(jù)作為主要研究對象，通過經(jīng)度和緯度坐標進行定位，將三環(huán)以外數(shù)據(jù)進行刪除。2.剔除異常值，保證數(shù)據(jù)代表性。一是剔除當(dāng)期數(shù)據(jù)異常值。根據(jù)數(shù)據(jù)上傳時間間隔信息，刪除長期處于非運行狀態(tài)的出租車GPS數(shù)據(jù)；結(jié)合三環(huán)內(nèi)道路實際情況，刪除瞬時速度大于120km/h的GPS數(shù)據(jù)。二是剔除歷史數(shù)據(jù)異常值。通過對歷史數(shù)據(jù)進行分析和觀察，刪除明顯的異常值，比如同一時間段同一路段上，某車車速明顯區(qū)別于其他車速，則認為該數(shù)據(jù)不具有參考性，不能參與歷史平均時間和速度的計算。3.通達節(jié)點定位及編號。結(jié)合谷歌地圖，為方便實際操作，將鄭州市三環(huán)以內(nèi)區(qū)域以農(nóng)業(yè)路、隴海路、花園路為分界線劃分為六部分，通過坐

18、標拾取器對其范圍內(nèi)的所有道路節(jié)點（道路交叉口）的GPS坐標進行拾取，分別以A、B、C、D、E、F作為編號開頭，按照統(tǒng)一規(guī)則命名，并記錄節(jié)點名稱等。最終獲得862個節(jié)點信息。圖3 市區(qū)三環(huán)以內(nèi)道路節(jié)點的拾取和編號表4 道路節(jié)點信息經(jīng)緯度節(jié)點號節(jié)點名稱34.7317058131,113.6815492809F0201豫筑路二里崗街34.7384011109,113.6847370863F0202南倉街城東路34.7384980945,113.6904340982F0203貨站街貨站北街34.7385554027,113.6940202117F0204貨站街東明路34.7386127109,113.

19、6981078982F0205貨站街未來路34.7302233771,113.6816015840F0206二里崗南街二里崗街4.建立道路節(jié)點通達數(shù)據(jù)集。作為道路節(jié)點，每個節(jié)點必然至少可通達一個節(jié)點，也必然至少有一個節(jié)點可通達至該節(jié)點。在綜合考慮道路單行、路中央護欄等特殊情況下，結(jié)合谷歌地圖，把每個節(jié)點所能通達的節(jié)點一一找出，建立節(jié)點通達數(shù)據(jù)集。表5 道路節(jié)點的通達數(shù)據(jù)集經(jīng)緯度節(jié)點號節(jié)點名稱通達節(jié)點34.7317058131,113.6815492809F0201豫筑路二里崗街F0201,F0206,F023834.7384011109,113.6847370863F0202南倉街城東路F02

20、02,B9966,F0203,C9974，F(xiàn)023834.7384980945,113.6904340982F0203貨站街貨站北街F0203,F0202,F0204,C997334.7385554027,113.6940202117F0204貨站街東明路F0204,F0203,F0205,C997234.7386127109,113.6981078982F0205貨站街未來路F0205,F0204,C9971,C997034.7302233771,113.6816015840F0206二里崗南街二里崗街F0206,B9963,F0207，F(xiàn)0208，F(xiàn)02015.通達性校驗。為了避免人工選擇

21、通達節(jié)點時可能會出現(xiàn)的錯誤，建立通達節(jié)點兩兩匹配檢驗，一般情況下通達節(jié)點都應(yīng)為成對出現(xiàn)，如存在獨立通達節(jié)點則該節(jié)點通達信息有可能是錯誤的，需進行校驗、核實和修改。6.GPS數(shù)據(jù)位置判別。為了較準確的判斷出租車GPS數(shù)據(jù)所處位置位于路口或道路，結(jié)合節(jié)點GPS坐標，以坐標為原點，以50米為半徑劃定范圍，在此范圍內(nèi)的GPS數(shù)據(jù)認定為處于節(jié)點的數(shù)據(jù)，不在此范圍內(nèi)則認定為處于路徑上。7.路段距離的計算。根據(jù)節(jié)點信息及其通達信息，可以計算出路段長度。如，節(jié)點A（x1,y1）可通達節(jié)點B(x2,y2)，x、y分別表示經(jīng)度和緯度，則通達路段AB的距離為：（注：單位為米，6371004為地球平均半徑）通過校驗和

22、計算，三環(huán)以內(nèi)共獲得2825條路段及其距離信息。8.路段通行平均時間及平均速度指標計算。在確定出租車所處位置后，對特定時間段內(nèi)的所有車輛按照車牌號和時間進行排序，即可得到出租車駛?cè)?、駛出某一路段的時間；將該時間相減即為出租車在該路段上的行駛時間，對經(jīng)過該路段的所有出租車行駛時間進行算術(shù)平均，就可得到該路段的通行平均時間；用路段的長度除以通行平均時間，即可得到某時段內(nèi)該路段的平均速度。（三）數(shù)據(jù)探索性分析為了更好的研究出租車路徑規(guī)劃問題，本文對選取的120萬余條研究數(shù)據(jù)（6月13日上午7:008:00）進行分析，探索、總結(jié)出租車出行的基本特征。1鄭州市出租車主要分布在城區(qū)以出租車的經(jīng)緯度數(shù)據(jù)為基

23、礎(chǔ)繪制高密度散點圖，可以看到，顏色較深的區(qū)域主要覆蓋了鄭州市三環(huán)內(nèi)區(qū)域，這與區(qū)域內(nèi)經(jīng)濟社會發(fā)展?fàn)顟B(tài)相匹配，同時也說明本文選擇三環(huán)內(nèi)出租車數(shù)據(jù)進行研究有實用性，見圖4。 圖4 GPS經(jīng)緯度高密度散點圖與市區(qū)地圖對比2.鄭州市超過60%的出租車行駛速度都在20km/h以內(nèi)刪除出租車瞬時速度大于120km/h的數(shù)據(jù)，繪制出租車瞬時速度直方圖，可以看到，出租車行駛速度一般在80km/h以內(nèi)，其中，行駛速度在0,10區(qū)間的，占比49.0%，在(10,20區(qū)間的，占比13.5%，按照國際上約定俗成的“20km/h”擁堵分界線來看，在上午7:008:00內(nèi)鄭州市出租車有62.5%的時間都處于擁堵狀態(tài)，這說明

24、優(yōu)化出行路徑，提高交通通行效率的必要性和緊迫性，見圖5。圖5 出租車上午7:008:00瞬時速度頻次直方圖3.擁堵路段集中在三環(huán)以內(nèi)對出租車GPS經(jīng)緯度數(shù)據(jù)作散點圖，可以看到，經(jīng)緯度散點勾勒出鄭州市交通網(wǎng)路脈絡(luò)，說明GPS經(jīng)緯度數(shù)據(jù)準確度較高，能夠滿足路徑規(guī)劃需要。對瞬時速度在0,20區(qū)間的數(shù)據(jù)，作基于經(jīng)緯度的二維等高圖，可以看到，市區(qū)最擁堵的區(qū)域分布在東經(jīng)113.65度和北緯34.75度附近，該區(qū)域是鄭州市火車站，其實際擁堵情況與圖中顯示一致。大部分擁堵區(qū)域則集中在東經(jīng)113.6113.7度和北緯34.734.8度之間，該區(qū)域恰好與鄭州市三環(huán)邊界相重疊，表明三環(huán)以內(nèi)是解決鄭州市交通擁堵問題的

25、核心區(qū)域，見圖6。圖6 出租車GPS經(jīng)緯度散點圖及其擁堵區(qū)域二維等高圖4.變量間關(guān)聯(lián)性不大對V1至V6六個變量繪制散點圖矩陣，可以看到，各個指標間相關(guān)性不大，見圖7。圖7 V1至V6六個變量散點圖矩陣剔除字符型變量V1和V6，對剩余的四個變量繪制相關(guān)圖，可以看到，相關(guān)性最大的指標為V2（載客狀態(tài)）和V5（瞬時車速），但即便如此，其相關(guān)系數(shù)也僅為0.25，見圖8。圖8 V2、V3、V4、V5相關(guān)圖矩陣（四）模型選擇和構(gòu)建1.模型介紹（1）蟻群算法基本思想仿生學(xué)家長期研究發(fā)現(xiàn)，螞蟻在尋找路徑時會在路徑上釋放出一種特殊的物質(zhì)信息素，當(dāng)它們碰到一個還沒有經(jīng)過的路口時，就隨機地挑選一條路徑前行，同時釋放

26、出一定的信息素。隨著信息素的不斷揮發(fā)，路徑越長，其釋放的信息素濃度會越低。后來的螞蟻到這個路口的時候，會根據(jù)之前路徑上存在的信息素來選擇道路，信息素濃度較高的路徑被選擇的概率相對較大，這樣形成一個正反饋，最優(yōu)路徑上信息素的濃度越來越大，而其它路徑上激素的濃度卻會隨著時間的流逝而消減，最終整個蟻群會找出最優(yōu)路徑。（2）Dijkstra最短距離算法 注：引自張怡復(fù)雜環(huán)境下車輛導(dǎo)航系統(tǒng)最優(yōu)路徑規(guī)劃算法研究.導(dǎo)彈與制導(dǎo)學(xué)報.2005年第1期 給定帶權(quán)有向圖，其中是包含n個頂點的頂點集，設(shè)是包含m條弧的弧集，是中從至的弧，是的非負權(quán)值，設(shè)和為中的頂點，為中由到的一條路徑，則路徑的權(quán)值總和可表示為：所謂最

27、短路徑問題就是指在帶權(quán)有向圖中，尋找從指定起點到終點的一條具有最小權(quán)值總和的路徑問題。如果把權(quán)值看成是弧的長度屬性（距離），那么目標路徑就是從起點到終點的最短路徑，這也是其名稱的由來。如果把路徑規(guī)劃中的優(yōu)化標準量化為道路的旅行代價，則最優(yōu)路徑規(guī)劃就可以歸結(jié)為在特定道路網(wǎng)中尋找具有最小旅行代價總和的最優(yōu)路徑問題，顯然這與最短路徑問題是等價的。2.模型構(gòu)建和優(yōu)化以往學(xué)者對蟻群算法的考慮僅限于以下幾個因素：即，式中R(Ei,t)為根據(jù)出租車路徑行駛信息規(guī)劃的出行路徑；S(t)為時段t內(nèi)路段Ei的通行距離，顯然，該數(shù)據(jù)一般是固定不變的；N(t)為時段t內(nèi)路段Ei的實時通行時間；P(t)為在時段t內(nèi)路段

28、Ei的信息素大小。本文認為基于出租車GPS數(shù)據(jù)的路徑優(yōu)化模型還應(yīng)該考慮另外兩個因素。一個是歷史因素，出租車的出行行為是多次蟻群覓食行為的循環(huán)，而不是簡單的一次性的覓食活動，因此，歷史因素（數(shù)據(jù)）可以為路徑選擇提供較好的對未來路徑狀態(tài)的預(yù)測，本文使用H(t)代表這一因素；另一個要考慮的因素，是當(dāng)前狀態(tài)下車速的變化情況，這對預(yù)測較短時期內(nèi)道路的變化情況有較強的參考價值，本文使用未來預(yù)測數(shù)據(jù)F(t)代表這一因素。為了規(guī)劃出距離最短、用時最少、信息素最優(yōu)的路徑，建立模型如下：對時間、距離、頻次等路徑信息的傾向，通常需要出行主體根據(jù)個體偏好進行自主決策。模型中的目標決策函數(shù)是對出行路徑距離、通行時間以及

29、出租車司機路徑選擇信息素進行綜合考慮，制定的決策函數(shù)表達式為：即，S、N、P、H和F分別為S(t)、N(t)、P(t)、H(t)、F(t)標準化后的值；分別為S、N、P、H和F的權(quán)重。3.模型運算（1）最短距離算法通過數(shù)據(jù)預(yù)處理，計算出鄭州市三環(huán)以內(nèi)每個路段的長度，使用Dijkstra算法，以道路長度為變量，計算出所有可達路徑的最短距離，共有862*861=742182條計算結(jié)果。（2）最少用時算法計算各個路段各個時間切片的通行時間均值。出租車通過某一路段所用時間的長短，是出租車選擇路徑的重要參考依據(jù)。本文利用6月13日上午7:008:00的GPS數(shù)據(jù)計算路徑通行時間。首先，計算各個時間切片通

30、行均值。以出租車駛出某一路段的時間點（t2）為標準，上溯至出租車駛?cè)朐撀范蔚臅r間點（），定義該出租車通過此路段的通行時間為。將上午7:008:00的時間按照2分鐘進行切片，劃分為30個時間切片，對駛出時間點進行分類，再以路段為分類指標，計算各個時間切片中的出租車通行時間均值，即獲得各個路段各個時間切片的通行時間均值（）。其次，融合歷史數(shù)據(jù)和預(yù)測數(shù)據(jù)。將各個路段各個時間切片的通行時間均值（）作為自變量建立模型，即使用實時道路網(wǎng)絡(luò)擁堵狀況規(guī)劃路徑，但由于道路網(wǎng)絡(luò)擁堵狀況每時每刻都在發(fā)生變化，僅僅考慮實時狀況，隨著時間的推移，原先規(guī)劃的最優(yōu)路徑可能會逐漸變得非最優(yōu)，尤其是在進入和退出高峰期過程中，道

31、路狀況變化較快且具有趨勢性。適當(dāng)?shù)目紤]未來的道路狀況進行路徑規(guī)劃，可以很好的解決這一問題。本文使用各個路段上午7:107:40之間15個時間切片的通行時間均值作為訓(xùn)練集，分別建立單指數(shù)平滑、隨機森林、支持向量機等預(yù)測模型，預(yù)測各個路段上午7:408:00之間10個時間切片的通行時間均值。由于路段總數(shù)為2825，因此，分別建立了2825個單指數(shù)平滑、隨機森林和支持向量機預(yù)測模型。使用各個路段上午7:408:00之間10個時間切片的實際通行時間均值作為驗證集，求出每個模型的MSE，對比可知：隨機森林、支持向量機分別有1683、1603個預(yù)測模型的MSE小于單指數(shù)平滑，分別占模型總數(shù)的59.6%、5

32、6.7%。支持向量機有1575個預(yù)測模型的MSE小于隨機森林，占模型總數(shù)的55.8%。綜上可知，支持向量機對道路網(wǎng)絡(luò)擁堵狀況的預(yù)測精度高于單指數(shù)平滑和隨機森林。再次，計算融合后的通行時間。本文選用支持向量機的預(yù)測結(jié)果融入路段切片通行時間，同時將與6月13日相似的歷史數(shù)據(jù)也融入路段切片通行時間，以期規(guī)劃出考慮未來道路網(wǎng)絡(luò)變化情況的優(yōu)化路徑。鑒于5月9日上午7:008:00影響機動車出行的外在因素與6月13日基本相同，本文將5月9日上午7:408:00之間10個切片通行時間的平均值作為歷史通行時間（），將6月13日上午7:387:40之間1個切片通行時間作為現(xiàn)實通行時間（），將支持向量機預(yù)測的6月

33、13日上午7:408:00之間10個切片通行時間的平均值作為未來通行時間（），構(gòu)建綜合通行時間：其中，分別為各個通行時間的權(quán)重。本文使用構(gòu)建綜合通行時間。分別將現(xiàn)實通行時間（）、綜合通行時間（）與驗證集中現(xiàn)實通行時間的真實值均值對比，求得方差，綜合通行時間有1916個方差小于現(xiàn)實通行時間，占2825個方差總數(shù)的67.8%。因此，使用綜合通行時間規(guī)劃路徑，能夠考慮未來道路網(wǎng)絡(luò)擁堵的變化情況，規(guī)劃出具有預(yù)測能力的優(yōu)化路徑。最后，建立模型及運算。路徑距離最短與時間最少算法相似，只不過路徑的大小由長度變?yōu)闀r間，因此，使用dijkstra算法，可以計算出整個道路網(wǎng)絡(luò)各個節(jié)點之間相互通達的最少用時，共86

34、2*861=742182條計算結(jié)果。（3）蟻群優(yōu)化算法首先，計算出租車時段通行頻次。出租車時段通行頻次是指在一段時間內(nèi)，某路段上產(chǎn)生的GPS數(shù)據(jù)數(shù)量，該指標既反映了路段對應(yīng)于其所處區(qū)域社會經(jīng)濟條件下的交通狀況和地位，同時也包含了司機對該路段的認知偏好。本文根據(jù)蟻群優(yōu)化算法思想，將6月13日上午7:008:00的GPS數(shù)據(jù)按照每20分鐘進行切片，并對每20分鐘時間切片內(nèi)道路上的GPS數(shù)據(jù)進行頻次統(tǒng)計。其次，計算通行頻次密度。根據(jù)上述頻次定義，其計算方法為：選取20分鐘內(nèi)所有GPS數(shù)據(jù)，將其按照車牌號和時間排序，記錄其駛?cè)肽骋宦范螘r間t1和駛出某一路段時間t2，由于出租車GPS信號每15s上傳一次

35、，因此：將經(jīng)過該路段的所有車輛頻次相加，即為該路段出租車時段通行頻次。然后計算“信息素”，即出租車時段通行頻次密度的倒數(shù)。為了消除道路長短對頻次大小的影響，本文定義一個指標“時段通行頻次密度”，其計算方法為：本文認為時段通行頻次密度的大小包含了出租車司機對于該路段通行情況的綜合考量，是出租車司機理性思量后的最優(yōu)選擇，時段通行頻次密度越大，說明越多的出租車選擇該道路，其被推薦為最優(yōu)路徑的概率也越大。在時間最短、距離最短兩個算法里選取最優(yōu)路徑時，“時間”和“距離”兩個指標的約束條件都是“最小值為優(yōu)”，為了與其保持一致，對“時段通行頻次密度”這個指標取了倒數(shù)，使用“出租車時段通行頻次密度的倒數(shù)”這個

36、指標作為引入模型的“信息素”。最后，建立模型及運算。蟻群優(yōu)化算法（ACO）在解決商旅問題(Traveling Saleman Problem,TSP)中得到了充分應(yīng)用，但其出發(fā)點和目的地為同一地點，且其初始信息素為0，而交通路徑優(yōu)化的出發(fā)點和目的地則往往不是同一地點，且存在信息素先驗概率，這是同傳統(tǒng)蟻群優(yōu)化算法不一致的地方。本文根據(jù)研究目的和實際情況，采用蟻群優(yōu)化算法思想，結(jié)合Dijkstra算法，將信息素最優(yōu)作為路徑選擇條件，計算最優(yōu)路徑。在選取的20分鐘里，存在部分路段無出租車通過的情況，即路段上無GPS數(shù)據(jù)，為了排除這些數(shù)據(jù)在計算信息素時出現(xiàn)無窮大值，對模型運行產(chǎn)生影響，本文選取20分鐘

37、內(nèi)全市所有路段上最大的信息素的數(shù)值（2031）對其進行替代。經(jīng)過程序計算，得出鄭州市三環(huán)以內(nèi)所有路口之間的信息素最優(yōu)通行路徑，共862*861=742182條計算結(jié)果。四、模型結(jié)果解讀和結(jié)論（一）模型結(jié)果解讀通過模型運算，本文可以計算出三種約束條件下的不同路徑選擇結(jié)果。距離最短的約束條件，適合步行和騎行的人群；時間最短的約束條件，適合短途且時間要求較高的人群；信息素最優(yōu)的約束條件，適合較認同出租車司機理性選擇的人群。在“最短距離”、“最少用時”、“信息素最優(yōu)”三個約束條件下，分別使用模型對2016年6月13日上午7:008:00的數(shù)據(jù)進行計算，通過結(jié)果分析可以看到，不同路徑選擇方法下推薦的路徑

38、差別較大，為了能更加清晰的進行說明，本文選取“出發(fā)點”為“中原中路桐柏北路”，“目的地”為“生產(chǎn)路南陽路”，查看三種路徑優(yōu)化算法計算出來的推薦路徑，如下：距離最短：中原中路桐柏北路-康樂街桐柏北路-協(xié)作路桐柏北路-市場街桐柏北路-建設(shè)西路桐柏北路-棉紡西路桐柏北路-西站路桐柏北路-朱屯路桐柏北路-煤倉北街桐柏北路-冉屯路桐柏北路-農(nóng)業(yè)路朱屯北路-農(nóng)業(yè)路京廣快速路-農(nóng)業(yè)路南陽路-生產(chǎn)路南陽路，其路徑長度為5796米，平均用時為31分鐘，該路徑選擇唯一，即所有路徑當(dāng)中此路徑距離最短，見圖9。圖9 距離最短路徑用時最少：中原中路桐柏北路-中原中路文化宮路-中原中路工人路-中原中路百花路-互助路百花路

39、-互助路嵩山北路-友愛路嵩山北路-建設(shè)西路嵩山北路-棉紡東路建設(shè)東路金水路-新建街金水路-金水路京廣快速路-黃河路京廣快速路-黃河路南陽路-南豐街南陽路-生產(chǎn)路南陽路，其路徑長度為7743米，平均用時為26.8分鐘。該路徑長度在三種路徑優(yōu)化方法內(nèi)為最長，但平均用時最少，原因為該路徑選擇繞行京廣快速路，因而速度最快，見圖10。圖10 用時最少路徑信息素最優(yōu)：中原中路桐柏北路-康樂街桐柏北路-協(xié)作路桐柏北路-市場街桐柏北路-建設(shè)西路桐柏北路-建設(shè)西路文化宮路-建設(shè)西路工人路-建設(shè)西路百花路-建設(shè)西路嵩山北路-棉紡西路嵩山北路-西站路嵩山北路-黃河路嵩山北路-黃河路京廣快速路-黃河路南陽路-南豐街南

40、陽路-生產(chǎn)路南陽路，其路徑長度為6577米，平均用時為37.2分鐘。該路徑的長度和時間均處于三種路徑選擇方法居中的位置，通過與出租車司機交流，出租車司機選擇該路徑的理由是：沿線所走的桐柏路、建設(shè)路、嵩山路、黃河路和京廣路均為大路，道路較寬且大部分為人車分流，紅綠燈個數(shù)相對較少，行車路況較好，安全性高，因此，雖然該路段距離不是最短，時間也不是最少，但卻為出租車司機所“鐘愛”，見圖11。圖11 信息素最優(yōu)路徑通過對上述三條路徑進行實地走訪并結(jié)合自身經(jīng)歷，三種模型推薦的路徑均符合實際情況，也都為三個約束條件下的最優(yōu)路徑。（二）結(jié)論模型運行結(jié)果顯示：本文基于出租車GPS數(shù)據(jù)建立的路徑優(yōu)化模型，包含了道

41、路網(wǎng)絡(luò)各個路段的距離、實時通行時間、歷史通行信息、未來通行預(yù)測信息和出租車司機路徑選擇等信息，可以分別提供距離最短、時間最少、信息素最優(yōu)等三種路徑優(yōu)化選擇。因此，也可以根據(jù)不同用戶的不同偏好，按照特定的權(quán)重設(shè)置距離、時間、信息素等路徑約束條件，規(guī)劃個性化出行路徑。五、創(chuàng)新點和研究展望（一）創(chuàng)新點1.實現(xiàn)算法上的創(chuàng)新。一方面，由于出租車司機作為“智能蟻群”模擬了自然螞蟻的路徑選擇規(guī)律，同時通過大腦的記憶有效的防止了信息素的揮發(fā)，因此基于出租車GPS路徑的優(yōu)化，有助于在當(dāng)前情況下規(guī)劃出最有效的路徑。但是在當(dāng)前規(guī)劃的路徑最優(yōu)，并不能完全滿足路徑最優(yōu)的出行要求，因為當(dāng)前最優(yōu)往往并不能保證整個行程最優(yōu)，

42、特別是在高峰出行時，當(dāng)前的最短時間和最短距離往往由于外部特定因素的變化而發(fā)生變化，特別是這種變化具有決定性影響的時候，會對路徑選擇形成誤導(dǎo)。這就需要優(yōu)化當(dāng)前的算法模型，本文結(jié)合蟻群優(yōu)化模型的基本思想，在蟻群優(yōu)化算法的基礎(chǔ)上增添了除傳統(tǒng)的信息素等因素之外的因素。一方面加入歷史信息，作為對路徑優(yōu)化模型約束條件的補充。另一方面，根據(jù)當(dāng)前狀態(tài)下交通網(wǎng)絡(luò)變化情況，預(yù)測未來道路通行信息，將其作為對路徑優(yōu)化模型約束條件的另一個補充。2.構(gòu)建綜合通行時間，分別計算綜合通行時間、現(xiàn)實通行時間與驗證集中的真實值對比，論證了綜合通行時間在路徑優(yōu)化模型中，能夠保證更高的精度。3.優(yōu)化蟻群算法模型，使用通行頻次模擬信息

43、素，保證了出租車司機在路徑選擇中的有效信息，結(jié)合使用dijkstra最短路徑算法，提高了蟻群算法在最優(yōu)路徑選擇中的精度。（二）研究展望1.由于相關(guān)研究并不多，特別是一些成熟的商業(yè)公司的相關(guān)研究處于保密狀態(tài)，本文收集到的資料有限，可供使用進行交叉驗證的模型并不多，因此需要更多的此類研究進行支撐和驗證。2.模型中各個參數(shù)應(yīng)進一步優(yōu)化。模型中的各個參數(shù)仍有優(yōu)化空間。比如綜合通行時間中三個時間的比例、預(yù)測未來通行時間模型中的訓(xùn)練集個數(shù)和預(yù)測長度等。但是，這些參數(shù)的優(yōu)化，不僅需要大量的歷史數(shù)據(jù)，而且需要強大的計算硬件，受限于時間和作者水平，這將是未來努力的方向。3.由于出租車的覆蓋率在有限的時間內(nèi)不能保

44、證路段全覆蓋，某些路段上會存在一定的不確定性，實時路徑規(guī)劃可能會出現(xiàn)盲點，這需要更多的機動車GPS數(shù)據(jù)的補充。4.機動車GPS數(shù)據(jù)是一個豐富的大數(shù)據(jù)庫，可供挖掘的方面還很多，比如利用GPS數(shù)據(jù)可以對城市道路規(guī)劃、紅綠燈時間和位置設(shè)置、機動車保有量的監(jiān)控和城市空氣質(zhì)量監(jiān)測等方面進行研究，均有助于緩解城市交通壓力，提高道路通行效率，改善生活和工作環(huán)境。參考文獻：1唐爐亮.常曉猛.李清泉.SHAW S L.基于蟻群優(yōu)化算法與出租車GPS 數(shù)據(jù)的公眾出行路徑優(yōu)化J.中國公路學(xué)報.2011年3月2姚鵬.基于出租車 GPS 軌跡的智能推薦系統(tǒng)D.長安大學(xué).2015年6月3許國淼基于出租車 GPS 數(shù)據(jù)的道

45、路交通運行狀態(tài)判別D.長安大學(xué).2015年6月4林泉.基于蟻群優(yōu)化的居民公交出行路徑選擇算法及仿真研究D.華南理工大學(xué)2010年6月5齊林.基于 GPS 數(shù)據(jù)的出租車交通運行特性研究及應(yīng)用D.哈爾濱工業(yè)大學(xué).2013年6月6楊建峰.蟻群算法以及應(yīng)用研究D.浙江大學(xué).2007年6月7譚衛(wèi).賴斌.基于改進蟻群算法的出租車路徑規(guī)劃算法J.信息化縱橫2009年第10期8張怡復(fù)雜環(huán)境下車輛導(dǎo)航系統(tǒng)最優(yōu)路徑規(guī)劃算法研究J.導(dǎo)彈與制導(dǎo)學(xué)報.2005年第1期9滴滴研究院2016上半年中國城市交通出行報告Z.10代小瑞，余豐茹，魏琳,鄭州市交通擁堵分析及對策研究Z.中國科技論文在線附錄：附件一 R軟件數(shù)據(jù)處理和

46、建模部分代碼指數(shù)平滑模型：d=read.csv("data.csv")d=d1:10,for(i in 1:2825)sub=which(is.na(d,i)=TRUE)dTR=d-sub,dsub,i=mean(dTR,i)write.csv(d,"05090701.csv")d=d11:20,for(i in 1:2825)sub=which(is.na(d,i)=TRUE)dTR=d-sub,dsub,i=mean(dTR,i)write.csv(d,"05090702.csv")d=d21:30,for(i in 1:2825

47、)sub=which(is.na(d,i)=TRUE)dTR=d-sub,dsub,i=mean(dTR,i)write.csv(d,"05090703.csv")td=d6:20,for(i in 1:2825)td,i=ts(td,i,frequency=1)f1=ets(td,1,model="AAN")f2=ets(td,2,model="AAN")ff1=forecast(f1,10)ff2=forecast(f2,10)fff1=as.data.frame(ff1$mean)fff2=as.data.frame(ff2$m

48、ean)r=cbind(fff1,fff2,fff2825)write.csv(r,"resultz.csv")隨機森林模型：yd=read.csv("yd.csv")pre=read.csv("pre.csv")for(i in 1:2825)prei*15-14,=ydi,1:4prei*15-0,=ydi,57:60pre1=pre1:15,pre2=pre16:30,rf1=randomForest(V4.,data=pre1,importance=TRUE)rf2=randomForest(V4.,data=pre2,imp

49、ortance=TRUE)p1=pre15,p2=pre30,p1,1:3=p1,2:4p2,1:3=p2,2:4p1p=predict(rf1,p1)p2p=predict(rf2,p2)r=cbind(p1p,p2p,p2825p)write.csv(r,"r1.csv")支持向量機模型：pre1=pre1:15,pre2=pre16:30,svm1=svm(V4.,data=pre1)svm2=svm(V4.,data=pre2)p1=pre15,p2=pre30,p1,1:3=p1,2:4p2,1:3=p2,2:4p1p=predict(svm1,p1)p2p=predict(svm2,p2)r=cbind(p1p,p2p,p2825p)write.c