基于大數據的動態出行管理平臺研究

朱中毅　王家珂　孫晨熙

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

?

基于大數據的動態出行管理平臺研究

朱中毅王家珂孫晨熙

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

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

關鍵詞：共享出行；路徑規劃；大數據；云計算

1　研究背景

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

2　設計思路

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

3　項目目標

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

4　項目內容

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

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

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

5　技術路線

5.1技術流程

本項目組從系統角度出發，以PHP編程語言作為服務器動態執行腳本編寫語言，以Apache作為服務器端軟件腳本服務發布環境，以Eclipse作為Android手機端（用戶APP）開發編譯環境，以Xcode作為IOS手機端（用戶APP）開發編譯環境，以云計算技術作為系統后臺數據處理手段，實現大數據環境下私家車的智能調度。其技術流程圖如圖1所示。

5.2相關技術及算法

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

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

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

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

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

5.2.2Dijkstra算法的創新。Dijkstra算法的復雜度為O（n2），若Dijkstra邊數遠小于n2，就可以使用子集數據結構對其進行優化，降低算法的復雜度［4］。

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

Dijkstra算法創新的流程圖如圖2所示。

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

圖1　平臺技術流程

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

5.2.3.1路徑直接匹配法

根據用戶提供的起點和終點生成k條路徑，這k條路徑會依照用戶側重的優先級排序。在此，設匹配函數：

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

5.2.3.2節點與路徑相匹配的方式

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

圖2　算法創新流程圖

圖3　最好匹配情況

圖4　最壞匹配情況

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

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

6　結語

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

參考文獻：

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

［2］張靚.基于子集優化的Dijkstra算法的交通最短路徑查詢系統的設計與實現［D］.長春：吉林大學，2015.

［3］田智勇.基于Android平臺的實時拼車系統的設計和實現［D］.武漢：華中科技大學，2007.

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

［5］雷東升，諸彤宇.一種基于實時路況信息的動態路徑規劃算法［J］.計算機科學，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