徐秀娟，　趙小薇，　許真珍，　馬瑞新，　賈　棋

(大連理工大學(xué) 軟件學(xué)院， 遼寧 大連 116620)

0　引　言

大學(xué)生創(chuàng)新項目是國家為了進一步促進人才培養(yǎng)模式改革而提出的本科生項目，旨在強化創(chuàng)新創(chuàng)業(yè)能力訓(xùn)練，增強學(xué)生的創(chuàng)新能力和在創(chuàng)新基礎(chǔ)上的創(chuàng)業(yè)能力[1-2]。學(xué)生可以自主選題或者選擇教師從科研項目中抽取出的前沿課題形成一個項目進行研究，從項目選題開始跟隨教師的指導(dǎo)，由學(xué)生進行項目背景調(diào)研和分析、設(shè)計項目的解決思路、分析與處理實驗數(shù)據(jù)，最終完成整個項目的開發(fā)[3]。參與學(xué)生對科研有濃厚興趣、學(xué)有余力、具備初步科研和動手能力，學(xué)校鼓勵學(xué)科交叉融合，鼓勵學(xué)生跨學(xué)科、跨學(xué)院申報大學(xué)生創(chuàng)新項目。通過開展大學(xué)生創(chuàng)新項目，重點培養(yǎng)學(xué)生將課本知識應(yīng)用到實踐的能力，從而提高大學(xué)生的創(chuàng)新能力[4-5]。

數(shù)據(jù)分析與處理是軟件工程教學(xué)中不可缺少的實驗，具有傳統(tǒng)軟件工程教學(xué)的局限性。城市交通軌跡作為近年來新產(chǎn)生的一類流數(shù)據(jù)，其數(shù)據(jù)特性與傳統(tǒng)小數(shù)據(jù)有較大差異[6]。本城市交通軌跡方面的科研課題，引導(dǎo)本科生提出自己的想法，在老師指導(dǎo)下完成了5項大學(xué)生創(chuàng)新項目，本文將結(jié)合城市交通軌跡數(shù)據(jù)處理項目分析大學(xué)生在創(chuàng)新項目的學(xué)習過程中如何提高分析問題和解決問題的創(chuàng)新能力。

1　交通數(shù)據(jù)處理設(shè)計概念

目前國內(nèi)大部分城市的出租車都已裝備GPS，用來記錄出租車的行駛軌跡。出租車是大城市覆蓋范圍較廣、常用的交通工具，出租車軌跡數(shù)據(jù)具有定位精度高、連續(xù)性強的特點，且沒有手機數(shù)據(jù)涉及的隱私問題，因此不僅在學(xué)術(shù)界還是在工業(yè)界，正成為一種相當重要的城市交通軌跡數(shù)據(jù)源[7]。

針對城市交通軌跡數(shù)據(jù)處理相關(guān)項目背景和研究意義與前景[8-9]，初期在獲取了幾個城市的出租車數(shù)據(jù)后進行了簡單的統(tǒng)計和查詢處理，為后續(xù)的具體計算與分析奠定基礎(chǔ)。同時為了對數(shù)據(jù)進行更好地處理，學(xué)生需要接觸并學(xué)習SQL Server，通過數(shù)據(jù)庫對大量數(shù)據(jù)進行分析與提取。借助某城市出租車GPS數(shù)據(jù)[10]提供的行車軌跡，學(xué)生繪制了城市主要的交通路線圖，如圖1所示；并且根據(jù)圖示路線的深淺大致推測出各條道路的車流量；隨后學(xué)生又進一步對每個小時的數(shù)據(jù)進行了相應(yīng)的分析，給出每個小時出租車走過的路線圖，觀察不同的時間段出租車分布地域的不同。

圖1　某市一天的交通軌跡圖

在此基礎(chǔ)上，圖2展示了城市交通軌跡數(shù)據(jù)處理流程圖。在獲取軌跡數(shù)據(jù)后，首先進行數(shù)據(jù)的采集和預(yù)處理；然后進行基本的數(shù)據(jù)挖掘操作，獲取頻繁路徑；最后進行交通擁堵的檢測，以及可視化程序結(jié)果。

創(chuàng)新實驗項目組成員通過筆者給予的國內(nèi)外相關(guān)資料，初步掌握了城市交通軌跡數(shù)據(jù)的特點，在一般數(shù) 據(jù)挖掘知識的基礎(chǔ)上，認識到了軌跡數(shù)據(jù)流的特性，擴展了視野。相關(guān)的大學(xué)生創(chuàng)新項目采取漸進式教學(xué)方法[11]，主要進行了如下的實驗：基于軌跡數(shù)據(jù)的打車時間計算實驗；基于軌跡數(shù)據(jù)的擁堵檢測實驗；以及基于軌跡數(shù)據(jù)的擁堵可視化實驗。

圖2　城市交通軌跡數(shù)據(jù)處理流程圖

2　大學(xué)生交通數(shù)據(jù)處理創(chuàng)新實驗

2.1　基于城市交通軌跡數(shù)據(jù)處理的打車時間計算實驗

本項目主要研究大規(guī)模的GPS數(shù)據(jù)的壓縮和轉(zhuǎn)換，以期望得到一個供動態(tài)查詢所用的離線模型[12]。首先對數(shù)據(jù)進行預(yù)處理，得到某天的軌跡圖。在實時動態(tài)查詢過程中，利用離線模型計算打車概率與等待時間。本項目的研究內(nèi)容分為三大模塊：離線預(yù)處理模塊、離線圖模型和在線處理模塊。

離線預(yù)處理包括文件分塊、熱點掃描、偏好軌跡處理3個步驟。① 針對輸入文件進行分塊處理：首先按照一周中的每天將文件分為7塊，其次根據(jù)每天的數(shù)據(jù)計算差異度，最后根據(jù)差異度進行文件分塊并用差值法存儲文件。② 根據(jù)每輛出租車的行駛路線提取掃描熱點區(qū)域；將打車概率的計算問題轉(zhuǎn)化為一條軌跡上在這個時間段恰好會有幾條有效軌跡覆蓋到查詢地點上。在預(yù)處理軌跡時，將軌跡抽象成由地點和時間拼接成的模式串作為算法使用的數(shù)據(jù)結(jié)構(gòu)。對于數(shù)據(jù)分析時還要掃描出大量出租車都會經(jīng)過的熱門地區(qū)。③ 研究快速偏好軌跡處理算法。需要將對應(yīng)每輛車的數(shù)據(jù)點映射到熱點上，以求解得到全部的軌跡模式串。

離線圖模塊構(gòu)造部分處理出在線查詢時參考的頻繁軌跡圖模型。該模塊主要研究頻繁軌跡圖模型構(gòu)建與相關(guān)數(shù)據(jù)結(jié)構(gòu)的設(shè)計與存儲。根據(jù)離線預(yù)處理的結(jié)果，離線得到軌跡模式串的頻繁模式子串。由于需要計算某一時間某一地點的打車概率以及等待時間，因此需要根據(jù)有效軌跡圖的數(shù)據(jù)特征，設(shè)計一個能夠有效地壓縮存儲空間的數(shù)據(jù)結(jié)構(gòu)，如按時間分層的多重鄰接表。多重鄰接表將構(gòu)造的有效軌跡圖存儲起來建立成一個圖。頻繁軌跡圖得到的是一個圖模型所轉(zhuǎn)化成的離線參考數(shù)據(jù)模型，這個離線模型的大小需要有效壓縮數(shù)據(jù)，并且在壓縮過程中保證有效數(shù)據(jù)不丟失。

在線處理模塊中針對每次查詢輸入，搜索軌跡圖模型，進行打車概率與等待時間計算。首先根據(jù)用戶提供的查詢地點，定位到離線模型對應(yīng)的熱點區(qū)域。其次根據(jù)用戶提供的時間信息，運用搜索算法求出這段時間內(nèi)可以到達查詢點的軌跡數(shù)。再次經(jīng)過分析可知，打車概率是符合泊松分布的概率，可根據(jù)軌跡數(shù)對泊松分布進行參數(shù)估計。最后，通過泊松分布計算出打車概率，并根據(jù)幾何分布計算出等待時間。

2.2　基于交通數(shù)據(jù)處理的交通流預(yù)測實驗

隨著城市化進程的推進，城市人口增加、道路增長率遠低于汽車增長率等因素均造成了一系列交通問題，其中最為突出問題是交通擁堵問題。交通擁堵已經(jīng)成為制約社會發(fā)展和城市經(jīng)濟的瓶頸，它直接影響了城市的整體運轉(zhuǎn)效率，在城市發(fā)展過程中的短板效應(yīng)日益明顯。該問題與學(xué)生日常生活非常接近，學(xué)生對此類問題興趣濃厚。經(jīng)過調(diào)研后，學(xué)生發(fā)現(xiàn)要研究交通擁堵問題，首先應(yīng)該做好交通擁堵的預(yù)防，即本項目期待能夠根據(jù)道路數(shù)據(jù)中路段一段時間的交通狀況預(yù)測分析出未來一段時間的該路段交通擁堵情況。在此基礎(chǔ)上，對可能出現(xiàn)的擁堵情況通過媒體宣傳或交通廣播進行預(yù)警，來避免一定的擁堵情況。

本項目中從交通數(shù)據(jù)處理(即離線數(shù)據(jù)處理)和交通擁堵識別判斷(即在線監(jiān)控)兩方面進行設(shè)計交通擁堵算法[13]。交通數(shù)據(jù)處理中，通過分離空間數(shù)據(jù)和實時數(shù)據(jù)分別采用不同方式壓縮來提高壓縮率和準確率。交通擁堵識別判斷中，選取交通擁堵的特征參數(shù)(平均車速、密度、交通流量)，構(gòu)造公式根據(jù)交通數(shù)據(jù)分別計算參數(shù)值。在大部分系統(tǒng)處理過程中，并不需要所有的數(shù)據(jù)都參與處理，所以，如何選取適應(yīng)量軌跡數(shù)據(jù)也是離線數(shù)據(jù)處理中比較重要的部分。因此，對數(shù)據(jù)采集中收集到的數(shù)據(jù)進行預(yù)處理，即對離線數(shù)據(jù)處理，才能更高效地實現(xiàn)交通信息化。

擁堵識別包括地圖信息分塊、軌跡信息壓縮、交通擁堵識別3個模塊。① 地圖信息分塊：由于實際地圖中所收集到的數(shù)據(jù)數(shù)量比較大，不適合進行算法實現(xiàn)結(jié)果測試。在不改變數(shù)據(jù)真實性的前提下，可對實際地圖數(shù)據(jù)進行分塊處理，形成相對較小的數(shù)據(jù)集，來進行調(diào)用并實現(xiàn)相應(yīng)測試功能。② 軌跡信息壓縮：對于交通擁堵處理、判斷，除地圖數(shù)據(jù)之外，還需車輛軌跡信息。對于軌跡來說，某些點是多余的點，增加了軌跡應(yīng)用系統(tǒng)的負荷同時也提高了數(shù)據(jù)存儲的代價。這些點完全可以選取特征點來替代表示。通過有效的軌跡數(shù)據(jù)壓縮，能夠減少數(shù)據(jù)存儲成本，并且能夠保持軌跡的效用。值得注意，車輛GPS軌跡信息中包含了實時信息和空間路徑，兩個數(shù)據(jù)具有不同的特性，所以本文采取的壓縮方法包括：無損空間數(shù)據(jù)壓縮和有限誤差實時數(shù)據(jù)壓縮。③ 交通擁堵識別：在描述道路交通狀況時，根據(jù)數(shù)據(jù)分析，對特征參數(shù)的影響程度進行權(quán)值分析。選取特征參數(shù)速度、密度、流量，即每路段每小時行駛多少千米、每千米行駛多少輛車及平均每小時有多少輛車來測算道路通行狀況，判斷路況信息。其中，速度低、密度大、流量小的路段設(shè)定為擁堵路段。

本項目的實驗數(shù)據(jù)來源于2011年1月新加坡最大出租車公司通過車載GPS所記錄的數(shù)據(jù)[14]。總數(shù)據(jù)包括46.5萬條道路軌跡，約1.5萬輛出租車，總數(shù)據(jù)共9.26 GB。在線監(jiān)控部分通過平均車速、交通流量、交通密度3個特征參數(shù)實現(xiàn)了交通擁堵模式判別。利用VISSIM軟件，仿真一條長為1.2 km的單行單車道路段，分別在400 m、800 m及1 200 m處放置檢測器，路段分為A、B和C段，方向由A駛向C。設(shè)定初始流量為2 000pcu/h，期望車速為60 km/h，由檢測器分別檢測0～2、2～4、4～6、6～8 min內(nèi)的車輛平均速度、密度及交通流量，結(jié)果如表1所示。

表1　各路段平均車速、密度、交通流量

從表中可見，路段A從2～4 min開始出現(xiàn)一般擁堵狀況；6 min時交通擁堵現(xiàn)象最為明顯；8 min時，交通擁堵現(xiàn)象出現(xiàn)好轉(zhuǎn)，道路狀況有所改善。路段B在4～6 min開始出現(xiàn)一般擁堵狀況；8 min時交通擁堵現(xiàn)象最為明顯；0～8 min過程中，道路狀況由暢通逐漸擁堵。路段C在6 min出現(xiàn)擁堵現(xiàn)象，且該時刻擁堵現(xiàn)象最為明顯，一直持續(xù)到8 min。交通擁堵流從路段A逐步蔓延到路段B、C；6 min時，由于路段A擁堵明顯，而路段B車輛大部分已經(jīng)駛?cè)肼范蜟，故在此時刻，路段A、C擁堵現(xiàn)象最為明顯；6～8 min時，由于路段A擁堵現(xiàn)象好轉(zhuǎn)，路段C擁堵持續(xù)，故路段B駛?cè)胲囋隽看笥隈偝鲕囋隽?，出現(xiàn)擁堵現(xiàn)象較為明顯。綜合路段A、B和C，該仿真路段交通狀況由通暢、一般擁堵到較擁堵變化，如圖3所示。

輸入監(jiān)控時間段，獲取該時段按時分類軌跡數(shù)據(jù)， 根據(jù)數(shù)據(jù)中車輛軌跡判斷所經(jīng)過的道路，并將數(shù)據(jù)存儲到道路集中。由公式分別計算出道路集中各道路的平均車速、密度、交通流量，再計算出綜合測度值。如果綜合測度值屬于較擁堵、一般擁堵或者非常擁堵，則在地圖中表示出該路段；否則不做處理。最后可視化的圖形如圖4所示。

圖3路段A、B、C綜合閾值

圖4　交通擁堵識別模式應(yīng)用

2.3　基于城市交通擁堵系統(tǒng)的可視化實驗

基于獲取的城市交通軌跡數(shù)據(jù)，學(xué)生開發(fā)了城市交通擁堵系統(tǒng)，從而更好地理解城市交通軌跡數(shù)據(jù)的意義，從多個角度圖形化展示城市的交通狀況，提高了學(xué)生分析問題的能力。

通過折線圖的形式展示北京市全路網(wǎng)全天的交通指數(shù)走勢。學(xué)生將道路交通指數(shù)劃分為5個級別，取值范圍為[0,10]，指數(shù)越大表示擁堵的程度越嚴重，各級別分別為暢通(0～2)、基本暢通(2～4)、輕度擁堵(4～6)、中度擁堵(6～8)和嚴重擁堵(8～10)，同時用綠、黃、橘、紅、深紅5種不同顏色對應(yīng)5種不同級別擁堵等級，使結(jié)果更加直觀。圖5大致反映當天北京市全路網(wǎng)的交通情況，在0：00～6：00這一時間段內(nèi)北京市路網(wǎng)交通狀況處于暢通的狀態(tài)，而在9：00～18：00之間北京市路網(wǎng)交通狀況大部分處于基本暢通的狀態(tài)。同時可以明顯看出，在早上7：00前后和下午19：00前后北京市出現(xiàn)兩個交通擁堵高峰期，全市的交通狀況基本處于輕度擁堵和中度擁堵的狀態(tài)。

路網(wǎng)概況主要分析全路網(wǎng)以及各環(huán)路、各級別道路的交通擁堵情況。用戶自選時間段點擊查詢，系統(tǒng)用過擁堵檢測算法，將分析結(jié)果通過地圖庫顯示在地 圖上，主要道路的擁堵程度通過對應(yīng)顏色顯示出來。

圖5　路網(wǎng)指數(shù)

圖6展示的是北京市某天8：30～8：35這5 min內(nèi)北京市各個主要路段的交通擁堵情況，這里主要使用的是基于行程時間比算法來檢測交通擁堵程度，可以看出，在8：30這個時間段北京各主要路段基本還是處于暢通狀態(tài)，而各別的路段處于不同程度的擁堵，但大部分擁堵的路段還是位于四環(huán)以內(nèi)。

圖6　一天內(nèi)路網(wǎng)概況

路網(wǎng)評估模塊負責分析全路網(wǎng)的交通擁堵程度，而道路評估模塊負責對特定道路的擁堵分析，主要有道路路況、速度評估、密度評估、流量評估和道路指數(shù)這5個功能。

其中，流量評估是對特定道路全天各時段的流量分析，并通過柱狀圖呈現(xiàn)結(jié)果。本系統(tǒng)將根據(jù)道路流量(輛/車道)不同劃分道路服務(wù)水平為5個級別，分別為1級(0～84)、2級(84～157)、3級(157～262)、4級(262～336)和5級(大于336)，其中1級代表道路服務(wù)水平處理最理想狀態(tài)，而5級表示道路服務(wù)水平處于不理想狀態(tài)。如圖7所示流量評估，用戶選擇查詢北四環(huán)中路的流量評估，系統(tǒng)通過統(tǒng)計數(shù)據(jù)庫中各個時段北四環(huán)中路通過的浮動車數(shù)量得出結(jié)果，并通 過柱狀圖展示結(jié)果?？梢钥闯鲈摰缆吩?：00～21：00

圖7　北京市北四環(huán)中路交通流量評估

這段時間服務(wù)水平一直處于不太理想的狀態(tài)，而凌晨7：00前該道路通過的車流量則較少。

對于檢測道路擁堵程度所采用的基于行程時間比的道路交通指數(shù)，實際上可以理解為擁堵時延指數(shù)，其意義為在擁堵狀態(tài)下車輛出行所耗費的時間比在非擁堵狀態(tài)下車輛出行所耗費時間的倍數(shù)。如圖8道路指數(shù)所示，用戶選擇查詢北四環(huán)東路的交通指數(shù)，系統(tǒng)通過計算各個時段北四環(huán)東路的交通指數(shù)，并把結(jié)果用折線圖展示出來。從圖中可以看出，北四環(huán)東路在8：30和17：30出現(xiàn)兩個交通指數(shù)高峰，意味著在這兩個時間段該道路的大多數(shù)路段處于嚴重擁堵狀態(tài)，車輛的實際行駛速度會比理想狀態(tài)下慢很多。

圖8　道路指數(shù)

3　創(chuàng)新實驗效果

近3年來，獲國家級大學(xué)生創(chuàng)新項目2項(基于移動軌跡數(shù)據(jù)的推薦算法，基于城市交通數(shù)據(jù)的擁堵算法設(shè)計與實現(xiàn))和校級大學(xué)生創(chuàng)新項目3項(T-Catching基于移動軌跡的全局最優(yōu)路線檢索工具，大規(guī)模移動數(shù)據(jù)的打車推薦算法研究，基于移動數(shù)據(jù)的擁堵信息預(yù)測算法)。其中，國家級大學(xué)生創(chuàng)新項目發(fā)表1篇期刊學(xué)術(shù)論文“Taxi-RS: Taxi-Hunting Recommendation System Based on Taxi GPS Data”[13]，并且其中一位成員通過推免清華大學(xué)研究生；校級大學(xué)生創(chuàng)新項目發(fā)表1篇會議論文“A Novel Algorithm for Urban Traffic Congestion Detection Based on GPS Data Compression”[15]。相關(guān)軟件著作權(quán)7項?？傆?0余位學(xué)生受益。

此外，基于創(chuàng)新項目開發(fā)的“基于城市交通軌跡數(shù)據(jù)的信息可視化軟件”獲得了遼寧省教育廳第二十屆教育教學(xué)信息化大獎賽二等獎，該可視化軟件應(yīng)用到課程的設(shè)計中，作為教學(xué)課件豐富了課程的教學(xué)案例，展示給學(xué)生從而激發(fā)更多的學(xué)生參與到創(chuàng)新項目中。

4　結(jié)　語

通過參與城市交通軌跡數(shù)據(jù)處理相關(guān)的創(chuàng)新實驗，項目組成員的創(chuàng)新思維、設(shè)計思維、實踐思維和溝通能力都得到了有效地提升，同時也加深了學(xué)生將理論知識應(yīng)用到實際的能力。同時，城市交通軌跡數(shù)據(jù)處理創(chuàng)新實驗也將筆者的科研項目很好地融合到課程教學(xué)中，解決了進行數(shù)據(jù)挖掘、軟件工程等課程實驗時學(xué)生對于科研理論理解與實際脫節(jié)的問題。這些項目對于培養(yǎng)解決實際社會需求的工程人才進行了一次有效的探索。

參考文獻(References)：

[1]吳遠征, 倪杰, 董玉婷. 基于多維動態(tài)創(chuàng)新模型的大學(xué)生創(chuàng)新創(chuàng)業(yè)提升策略[J].實驗室研究與探索, 2016, 35(2): 205-210, 240.

[2]賈棋,王祎,許真珍,等.以大學(xué)生科技競賽為牽引的創(chuàng)新實驗班建設(shè)[J]. 實驗技術(shù)與管理, 2015, 32(4): 29-32.

[3]劉清,高金東,何原野. 基于創(chuàng)新試驗培養(yǎng)大學(xué)生綜合能力[J]. 實驗室研究與探索, 2016, 35(1): 141-145.

[4]張運楚, 姜愛民, 徐紅東, 等. 高校實驗教學(xué)中創(chuàng)新教育現(xiàn)狀與對策[J].實驗室研究與探索, 2016, 35(2): 224-228, 240.

[5]湯佳樂, 程放, 黃春輝, 等. 素質(zhì)教育模式下大學(xué)生實踐能力與創(chuàng)新能力培養(yǎng)[J].實驗室研究與探索, 2013, 32(1): 88-89, 135.

[6]陳寶權(quán),曾瓊.大數(shù)據(jù)時代的城市計算[J].中國計算機學(xué)會通訊, 2016, 12(6): 8-12.

[7]杜龍兵, 徐書克. 淺析大學(xué)生創(chuàng)新性實驗計劃項目[J].實驗室研究與探索, 2012，31(2): 82-84.

[8]禹曉輝,于自強,陳勐.城市時空大數(shù)據(jù)的研究與應(yīng)用現(xiàn)狀[J].中國計算機學(xué)會通訊, 2016, 12(6): 20-26.

[9]陸旻,王祖超,袁曉如,等. 城市移動數(shù)據(jù)知微探秘[J].中國計算機學(xué)會通訊, 2016, 12(6): 32-39.

[10]Yuan Nicholas Jing, Zheng Yu, Xie Xing,etal. T-drive: Enhancing driving directions with taxi drivers’ intelligence[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 220-232.

[11]張博. 基于云計算的出租車軌跡數(shù)據(jù)挖掘研究[D]. 西安: 西安電子科技大學(xué). 2014.

[12]趙小薇,許真珍,田琳琳,等. 漸進式教學(xué)在軟件工程建模課程中的應(yīng)用探索[J]. 計算機教育, 2015(20): 49-52.

[13]Xu Xiujuan, Zhou Jianyu, Liu Yu,etal. Taxi-RS: Taxi-hunting recommendation system based on taxi GPS data[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4): 1716-1727.

[14]Song Renchu, Sun Weiwei, Zheng Baihua,etal. PRESS: A novel framework of trajectory compression in road networks [C]∥In Proceeding of the 40th International Conference on Very Large Data Bases, 2014, 7(9):661-672.

[15]Xu Xiujuan, Gao Xiaobo, Zhao Xiaowei,etal. A novel algorithm for urban traffic congestion detection based on GPS data compression [C]∥In Proceeding of 2016 IEEE International Conference on Service Operations and Logistics, and Informatics, 2016: 107-112.