朱中毅　王家珂　孫晨熙

（西南交通大學(xué)交通運輸與物流學(xué)院，四川　成都　611756）

?

基于大數(shù)據(jù)的動態(tài)出行管理平臺研究

朱中毅王家珂孫晨熙

（西南交通大學(xué)交通運輸與物流學(xué)院，四川成都611756）

摘要：隨著居民生活水平的提高，近幾年我國城市私家車的數(shù)量大幅度增加，但與此同時也產(chǎn)生了許多社會問題，如嚴重的大氣污染、大面積的交通擁堵、日益加劇的能源消耗等。針對以上問題，本項目組設(shè)計了基于大數(shù)據(jù)的動態(tài)出行管理平臺。該平臺通過路線匹配算法、自動撮合算法和云計算模型等技術(shù)手段，結(jié)合實時的路網(wǎng)流量數(shù)據(jù)，為出行者智能地規(guī)劃最優(yōu)路徑，并將起訖點相同或相近的出行者匹配在同一次出行當(dāng)中，建議其共享出行，進而在滿足人們出行需求的同時降低私家車的出行數(shù)量，也為城市居民普及一種綠色出行理念。本文將從設(shè)計思路及技術(shù)路線對系統(tǒng)的構(gòu)建進行相關(guān)闡述。

關(guān)鍵詞：共享出行；路徑規(guī)劃；大數(shù)據(jù)；云計算

1　研究背景

隨著我國居民生活水平的提升，私家車數(shù)量也在不斷增多，但與此同時也產(chǎn)生了很多社會問題。機動車尾氣的排放是大氣污染的主要來源，尤其對霧霾天氣的影響最大；私家車的增加也導(dǎo)致了嚴重的交通擁堵，降低人們的生活品質(zhì)，浪費人們的出行時間。以北京市為例，中國科學(xué)院可持續(xù)發(fā)展戰(zhàn)略研究組發(fā)表《2012中國新型城市化報告》顯示，由于交通擁堵，2010年北京市居民出行受影響的人數(shù)平均每天達1381.8萬人次，平均每日每人次延誤66min，由此造成的時間價值損失每天高達32386.2萬元；此外，汽車行駛時間的增加必然增加燃料消耗，每年僅汽車燃料北京市就浪費722.9萬L，經(jīng)濟損失高達201.1億元。不僅如此，車輛的閑置現(xiàn)象也十分嚴重。據(jù)統(tǒng)計，2012年北京的出租車空載率為30%，“一人一車”現(xiàn)象十分嚴重。如果能夠通過拼車而使“一人一車”現(xiàn)象得到改善，那么在道路上行駛的汽車數(shù)量將得到有效減少，機動車尾氣的排放量也將會減少。因此，基于這樣的思想—滿足人們出行需求的同時降低機動車出行率，拼車出行的方式不僅能夠在一定程度上緩解交通擁堵，減少汽車尾氣排放等社會和環(huán)境問題，還同時具有節(jié)約出行成本和擴大社交等好處。

2　設(shè)計思路

本項目小組擬根據(jù)云計算理論，建立私家車交通資源和出行需求的合理配對模型（招標與投標的自動撮合模型），并研發(fā)一款結(jié)合網(wǎng)頁端與手機端的軟件，將車、數(shù)據(jù)庫、服務(wù)器和用戶手機終端進行組網(wǎng)，司機通過GPS模塊定位出租車位置，傳感層模塊采集車內(nèi)溫度等信息上傳到遠程服務(wù)器，實現(xiàn)信息共享［1］。乘客方面，可以通過網(wǎng)頁地圖信息查看周邊街道空車的分布情況以及車內(nèi)環(huán)境、車型等基本信息，從而選擇合適的車輛。用戶通過軟件提供的車主信息向車主發(fā)送打車請求，收到打車請求的車主可發(fā)回確認信息。同時，該軟件依據(jù)現(xiàn)今城市交通大數(shù)據(jù)，以Dijkstra算法為基礎(chǔ)，通過對相關(guān)理論文獻進行研究，對原有算法進行創(chuàng)新，結(jié)合城市路網(wǎng)車流量的動態(tài)數(shù)據(jù)，實現(xiàn)多人拼車時的最優(yōu)路徑規(guī)劃選擇，從而實現(xiàn)以用戶最優(yōu)為目標的路徑起訖點規(guī)劃方案，節(jié)約用戶的出行時間。與此同時，這樣一種新型的融合交通出行理論的拼車模式能夠在保證居民安全出行的同時，逐漸培養(yǎng)人與人之間的信任感，并樹立綠色環(huán)保的出行理念。

3　項目目標

該管理平臺旨在實現(xiàn)用戶快速便捷地找到同路的乘車伴侶，在減少機動車出行數(shù)量的同時，幫助車主以自由民主的市場方式完成交通搭乘的選擇。在實現(xiàn)合理拼車出行的同時，能夠大大減少由于機動車尾氣排放而引起的環(huán)境污染及交通擁堵等社會問題的出現(xiàn)。

4　項目內(nèi)容

該管理平臺建立了能夠融合多終端設(shè)備數(shù)據(jù)的云計算模型，以城市路網(wǎng)車流量的動態(tài)數(shù)據(jù)作為規(guī)劃拼車路線的首要影響因子；同時，以社區(qū)為單位，通過人脈重合度智能推選算法，以人脈重合度的高低值作為次要影響因子，在考慮社區(qū)單元因素的同時，優(yōu)先推選人脈相識度更高的招標人與投標人的信息至用戶終端，最終實現(xiàn)在一人或多人，單組起訖點或多組起訖點情況下的最優(yōu)拼車路徑規(guī)劃［2］。

使用該平臺的用戶分為二類：①系統(tǒng)游客，只可以瀏覽該軟件的招標信息和投標信息，但無法進行選擇和操作，只具備瀏覽的權(quán)限，也不為該類客戶提供個性化服務(wù)，該類客戶無需注冊；②正式用戶，必須在該動態(tài)管理平臺注冊，登錄系統(tǒng)后，這類客戶可以瀏覽已注冊私家車的拼車信息，可以實時在線拼車，也可享受該管理平臺提供的個性化服務(wù)及其他服務(wù)等。

該平臺通過統(tǒng)計城市所有接入本系統(tǒng)服務(wù)的車主用戶實時發(fā)布的車輛信息，可以幫助用戶以最便捷的方式找到附近有空座位且有相同或相近出行路線的車輛，并支持提前預(yù)定車位、最優(yōu)路徑規(guī)劃以及語音消息提醒等實用功能。而該平臺由于軟實體占主要開發(fā)和維護部分，因此具有廉價實用的特性，并且能夠有效解決當(dāng)前車主的私家車空座位信息處于信息孤島的難題；同時，依據(jù)城市路網(wǎng)車流量的實時數(shù)據(jù)為用戶選擇最優(yōu)路徑，從而降低車輛尾氣污染，緩解交通擁堵，提升出行效率。由此可以預(yù)見，基于城市交通大數(shù)據(jù)的以私家車為主體的管理平臺將有望成為居民出行必不可少的輔助決策工具。

5　技術(shù)路線

5.1技術(shù)流程

本項目組從系統(tǒng)角度出發(fā)，以PHP編程語言作為服務(wù)器動態(tài)執(zhí)行腳本編寫語言，以Apache作為服務(wù)器端軟件腳本服務(wù)發(fā)布環(huán)境，以Eclipse作為Android手機端（用戶APP）開發(fā)編譯環(huán)境，以Xcode作為IOS手機端（用戶APP）開發(fā)編譯環(huán)境，以云計算技術(shù)作為系統(tǒng)后臺數(shù)據(jù)處理手段，實現(xiàn)大數(shù)據(jù)環(huán)境下私家車的智能調(diào)度。其技術(shù)流程圖如圖1所示。

5.2相關(guān)技術(shù)及算法

5.2.1Dijkstra算法介紹分析。目前，常用的計算最短路徑的算法主要有Dijkstra算法、Floyd算法和A*算法等。當(dāng)路網(wǎng)規(guī)模不大時，A*算法和Dijkstra算法效率相近，而Floyd算法復(fù)雜度為O（n3），在求單源點最短路徑時效率較低；而Dijkstra算法復(fù)雜度為O（n2），在求解單源點最短路徑時，效率比較高?？紤]到該管理平臺使用的都是單源點路徑規(guī)劃，故采用Dijkstra算法。

在求解最短路徑問題時，多使用有向圖或無向圖來描述問題，即在G=（V，E）中，邊E［i］的距離權(quán)值設(shè)為w［i］，并找出從頂點V1到路網(wǎng)中其他各節(jié)點的最短距離。

下面對Dijkstra算法的計算步驟進行描述：①假設(shè)在某個路網(wǎng)中有n個節(jié)點，在初始時刻，令集合S={V1}，T= {V2，V3，V4，……，Vn}；②在集合T中選取距離V0權(quán)值最小的頂點且該頂點不在集合S中，選取后將該點加入到集合S中；③修改集合T中余下各頂點的距離權(quán)值；④修改此距離權(quán)值，使V0到Vi的距離權(quán)值縮短；⑤直到集合S中包含所有集合T中的節(jié)點，算法結(jié)束。

根據(jù)上述步驟的描述可知，Dijkstra算法的主要特點是在路網(wǎng)中設(shè)置一個起點，并以該點為中心，向外進行擴展，直到該路網(wǎng)中的所有節(jié)點都被囊括為止。Dijkstra算法的運行時間為搜索路網(wǎng)中所有節(jié)點的集合中最小元素的運算時間，其時間是路網(wǎng)中節(jié)點數(shù)n和邊數(shù)m的函數(shù)。

盡管如此，現(xiàn)階段Dijkstra算法仍然存在不足：①當(dāng)從集合T中選定一個節(jié)點k作為中轉(zhuǎn)點時，需要掃描集合T中的其他節(jié)點j并更新其距離權(quán)值，而在集合T中還存在著大量與中轉(zhuǎn)節(jié)點k不直接相連的節(jié)點i（即w［i］=∞）；②Dijkstra算法是由單一方向遍歷所有節(jié)點，求出以任意一個節(jié)點作為起點時到其余各節(jié)點的最短路徑［3］。對于節(jié)點較多，路況復(fù)雜的路網(wǎng)，該算法的實時性較差，因此有對其進行創(chuàng)新的需要。

5.2.2Dijkstra算法的創(chuàng)新。Dijkstra算法的復(fù)雜度為O（n2），若Dijkstra邊數(shù)遠小于n2，就可以使用子集數(shù)據(jù)結(jié)構(gòu)對其進行優(yōu)化，降低算法的復(fù)雜度［4］。

算法優(yōu)化方法：①將與路網(wǎng)源點相連的點加入子集；②選出子集元素u，并對子集進行調(diào)整；③處理未被使用的、與u相鄰的路網(wǎng)節(jié)點；④更新各節(jié)點距離，并修改該元素在子集中的位置；⑤直到u為終點時，結(jié)束算法。否則，繼續(xù)重復(fù)②③④步驟。

Dijkstra算法創(chuàng)新的流程圖如圖2所示。

5.2.3路徑匹配算法。在基于大數(shù)據(jù)的動態(tài)出行管理平臺中，當(dāng)有用戶發(fā)出拼車請求，并提供了起訖點的地理位置時，需要在其他用戶所發(fā)布的路徑信息中選擇一條合適的路徑與其匹配。若該用戶為乘客，則需要根據(jù)車主的出行路徑進行匹配；若該用戶為車主，則需要根據(jù)乘客的出行路徑進行匹配。因此，本項目組使用了路徑匹配算法，使該平臺能夠根據(jù)起訖點以及路徑的要求為有需求的用戶進行適當(dāng)?shù)钠ヅ洹?/p>

圖1　平臺技術(shù)流程

當(dāng)有用戶發(fā)布拼車請求時，路線匹配算法將根據(jù)此用戶所選擇的起訖點在數(shù)據(jù)庫中規(guī)劃出合適的拼車路徑。在此，提供以下2種路徑匹配方式。

5.2.3.1路徑直接匹配法

根據(jù)用戶提供的起點和終點生成k條路徑，這k條路徑會依照用戶側(cè)重的優(yōu)先級排序。在此，設(shè)匹配函數(shù)：

其中，λ為匹配系數(shù)；pathm表示用戶所選擇的第i條路徑與系統(tǒng)給出的第m條路徑中完全相同的子路徑；di為第i條路徑的長度。

5.2.3.2節(jié)點與路徑相匹配的方式

這種方法分為2種情況：①最好情況（見圖3），其起點和終點都在已知的某條路徑上，如起點A和終點B都在線路2上，此時不需要修正原來的行車路徑，在系統(tǒng)數(shù)據(jù)庫已有的路徑數(shù)據(jù)足夠多的情況下，這種情況出現(xiàn)的概率最高；②最差情況（見圖4），其起點和終點都不在已知路徑上，即起點A和終點B都不在線路2上，這時需要修改原有的行車路徑，這種條件下若需滿足拼車需求，則車主必須要繞路接送乘客，或者乘客步行一段距離到達乘車地點。這種情況雖然有些不合理，但只要乘客和車主能夠溝通協(xié)調(diào)，仍然可以使問題得到解決［5］。

圖2　算法創(chuàng)新流程圖

圖3　最好匹配情況

圖4　最壞匹配情況

路徑直接匹配法在最開始就給出了路徑，不再需要再次求路徑以及路徑長度；節(jié)點與路徑相匹配的方式還需要對現(xiàn)有路徑進行調(diào)整，規(guī)劃出新的路徑并計算路徑長度。盡管如此，路徑直接匹配法同樣存在不足，該方法只能在λ值為1的情況，即完全匹配時才能給出匹配路徑。當(dāng)存在最差情況時，用戶選擇的n條路徑與系統(tǒng)規(guī)劃的k條路徑進行匹配，不存在使得λ值為1的匹配情況，但在已知路徑足夠多的情況下，可以通過這個方法盡量滿足用戶需求。因此，在該平臺中，結(jié)合了上述的兩種匹配方法來更好地滿足用戶需求。

路徑匹配算法可以在Dijkstra算法基礎(chǔ)上設(shè)計實現(xiàn)。通過用戶對平臺的使用，系統(tǒng)數(shù)據(jù)庫可以對已有的路徑進行儲存，在有用戶提出新的拼車請求時，系統(tǒng)可以根據(jù)其提供的起訖點在數(shù)據(jù)庫中對已有數(shù)據(jù)進行檢索并提供合適的路徑規(guī)劃，然后依據(jù)匹配度從高到低的路徑排列順序給予推薦。

6　結(jié)語

基于大數(shù)據(jù)的動態(tài)出行管理平臺主要通過拼車這一方式來緩解現(xiàn)今城市中交通擁堵的問題，同時結(jié)合城市路網(wǎng)中車流量的動態(tài)數(shù)據(jù)來為出行者規(guī)劃最優(yōu)路徑。對用戶而言，該平臺可以為其出行提供優(yōu)質(zhì)的服務(wù)，節(jié)約出行時間，提高出行效率；對于城市交通部門而言，該平臺通過拼車這一方式來緩解交通壓力，減輕有關(guān)部門的管理負擔(dān)；對于政府而言，通過該平臺不僅能夠有效地宣傳綠色環(huán)保的出行理念，同時拼車也有利于拉近人與人之間的距離，為構(gòu)建和諧社會發(fā)揮積極作用。

參考文獻：

［1］李由.路徑搜索和匹配算法在交通信息服務(wù)中的應(yīng)用［J］.航空計算技術(shù)，2009，39（1）：98-106.

［2］張靚.基于子集優(yōu)化的Dijkstra算法的交通最短路徑查詢系統(tǒng)的設(shè)計與實現(xiàn)［D］.長春：吉林大學(xué)，2015.

［3］田智勇.基于Android平臺的實時拼車系統(tǒng)的設(shè)計和實現(xiàn)［D］.武漢：華中科技大學(xué)，2007.

［4］張凱杰，潘奇.基于最短路徑的求解與創(chuàng)新［J］.科技創(chuàng)新導(dǎo)報，2012（29）：38-41.

［5］雷東升，諸彤宇.一種基于實時路況信息的動態(tài)路徑規(guī)劃算法［J］.計算機科學(xué)，2008，35（4）：28-30.

中圖分類號：U491.1

文獻標識碼：A

文章編號：1003-5168（2016）01-0056-04

收稿日期：2015-12-25

作者簡介：朱中毅（1994-），男，本科在讀，研究方向：交通運輸；王家珂（1994-），男，本科在讀，研究方向;交通運輸；孫晨熙（1994-），男，本科在讀，研究方向：交通運輸。

Research on Dynamic Travel Management Platform Based on Big Data

Zhu ZhongyiWang JiakeSun Chenxi
（School of Transportation and Logistics,Southwest Jiao Tong University，Chengdu Sichuan 611756）

Abstract:With the improvement of people's living standards,the number of private cars increased significantly in re?cent years.However,at the same time it caused many social issues,such as serious air pollution,traffic congestion, increasing expenditure of energy and so on.To solve the above problems,we designed theDynamic Travel Manage?ment System based on Big Data.Using the technical means such as the line matching algorithm and automatic match?ing algorithm and cloud model,and combining with the seasonable network traffic data,this system can planning opti?mal path for traveler intelligently.And it can also match the travelers who have the same or similar begin and end point in the same trip,thus can meet the demand of people’s travel and meanwhile reduce the number of private cars in cities,which populars a kind of“green travel”concept for city dwellers.This article is related from the design ideas and technical route of system construction.

Keywords:sharing travel；ath planning；big data；cloud computing