基于單向循環列表的公交自動報站算法

彭 可，陽 領，郭啟明，馮 準，鄭懷朋

(湖南師范大學 工程與設計學院，湖南 長沙 410081)

表1 站點數據單向循環列表

基于單向循環列表的公交自動報站算法

彭 可，陽 領，郭啟明，馮 準，鄭懷朋

(湖南師范大學 工程與設計學院，湖南 長沙 410081)

針對當前公交自動報站算法大多需要人工確認公交車輛上下行方向以及車輛突然跨站或調頭導致的報站錯誤等問題，設計了一種基于單向循環列表的新型公交車輛全自動判定及報站算法。該算法充分考慮了公交車輛往復運行的規律，結合了各公交站點之間按前后順序排列的內在聯系，去除了傳統公交車自動報站算法中的上下行概念。該算法無需依賴定位信息中的方位角信息，采用單向循環列表存儲公交往返線路的全部站點信息，并結合周期性的全局搜索定位方式進行公交站點的匹配計算。該算法可以實現全自動公交車輛進出站預報和報站，無需人工判斷公交車輛行駛方向，極端情況下出現站點信息錯報或漏報時能夠快速自動恢復至正常報站狀態，且不會出現累積報站誤差。

自動報站；單向循環列表；全局搜索；站點匹配；進站判定；出站預報

0 引 言

隨著城市公交車智能化[1]需求的日益增長，國內各城市的公交車自動報站系統進入了快速研發和應用的階段，然而目前的自動報站設備及各類自動報站算法[2]依然存在著諸多缺陷。各類現有的自動報站算法大多需要依賴于人工確認車輛行駛方向，采用連續上行和連續下行[3]計數的判斷方法進行報站，但是這類算法對系統控制器處理能力要求較高。目前，GPS技術仍是國內各城市的公交車自動報站設備[4]應用最廣泛的定位技術。一些算法利用GPS數據攜帶方位角信息這一特性來判斷車輛行駛方向，在一定程度上降低了自動報站的誤報率。但是GPS模塊發送數據的穩定性有限，某些情況下定位數據中并不攜帶[5]方位角信息，這就導致依賴方位角信息來判讀車輛行駛方向的算法容易發生誤判。

針對上述公交報站設備終端算法存在的缺陷[6]，文中設計了基于單向循環列表的公交自動報站算法。該算法只依賴于經緯度數據[7]并且不涉及方位角等的計算，從而減少了算法的時間復雜度[8]。另外，文中提出的算法利用單向循環列表存儲站點信息，從而摒棄了車輛上下行[9]概念，并解決了因車輛突然跨站或調頭而造成的誤報問題。該算法適用基于北斗系統或者其他實時定位技術的全自動判定及報站。

1 自動報站算法設計與分析

文中提出的公交全自動報站算法的主要特點在于摒棄了傳統的公交車上下行概念，采用了單向循環列表來依次存儲上下行全部站點信息，并采用全局搜索[10]進行站點匹配計算。文中自動報站算法需要解決的關鍵問題包括：線路站點信息配置、可能到達站點匹配、進站判定及報站、出站判定及預報。

1.1 線路站點信息配置

根據車輛只能靠右行駛(某些國家為靠左行駛)的原則，由于公交車輛運行具有往復[11]的特征，往返路線中任意一個獨立的站點都可以看成另一個站點的前站或后站。文中所提算法中將傳統的公交車輛上行和下行的概念轉化為單向循環的方式，即按照公交車輛實際正常行駛所經過的站點次序，將公交線路上所有站點依次編號[12]排列形成一個單向循環列表，公交車實際路線情況如圖1所示。

圖1 公交車實際路線情況

單向循環列表中包含了各個站點對應的站號、站點名稱、站點經緯度等信息，將上述站點數據存儲在報站設備終端的存儲模塊內，其在存儲設備中的組織形式構成單向循環列表，如表1所示。實際運行過程中，公交車的站點路線為形成單向循環的A→B→C→D→E→F→A。

表1 站點數據單向循環列表

文中所提算法采用本地配置和遠程配置[13]相結合的數據列表來實現信息配置：當公交車報站設備終端初始化時，使用本地配置方式來存儲包含公交線路各站點信息的單向循環列表；在公交車輛運行過程中突發路線變更時，則采用遠程配置的方式來更新報站設備終端中的單向循環列表。

1.2 可能到達站點匹配

文中算法設定報站設備終端按固定時間周期T接收實時定位數據信息，并從中篩選出有效的數據信息進行拆解。也就是說，公交報站設備終端的默認狀態是周期性的站點匹配判定狀態。當公交車輛速度V≠0時，設備終端保存位置信息從而獲取公交車輛的當前位置。周期T、距離值L、公交車輛行駛速度V應當滿足：V×T≤2L，即確保公交車輛經過任意站點時以設定周期T進行計算和判定。為了準確匹配可能到達的站點，該算法規定任意時刻公交車當前位置與單向循環列表中站點位置之間線性距離為Ld，當有至少連續周期的兩次判定均能滿足Ld

按周期T對所獲取的Ld進行測算，根據站點實際分布狀況，大部分匹配結果都只有一個站點符合要求，而當往返路線對應站點距離較近時則可能出現兩個滿足條件的站點。進一步計算并記錄單向循環列表中該可能到達站點的下一站點與所述公交車輛的當前位置之間的線性距離，設為Ld+1。

1.3 進站判定及報站

上一節中提到，公交車在行駛過程中可能匹配到1個或2個擬到達站點。當只匹配到1個站點時，該站點即為當前進站站點。當匹配到2個站點時，其中有一個點為對應往返路線站點，那么在公交車行駛過程中，其單向循環列表中的下一站點與當前車輛位置距離Ld+1值在連續兩個周期T內將呈增長趨勢，而當前進站站點的Ld+1應該呈遞減趨勢。所以，在匹配到2個站點的情況下，對滿足Ld

從上述分析可知，每個周期的站點匹配計算可能存在多種結果，并且需要排除車輛突然跨站或掉頭而導致的誤差。因此，在當前進站站點求取過程中，必須判定和丟棄不符合單向循環排列的逆向[14]或虛假站點。

由于前、后兩個周期所求取匹配的可能到達站點都可為1個或2個，文中算法設置了fro_1、fro_2分別存儲上一周期站點匹配所得的第一個和第二個可能到達站點的站號；D_fro_1、D_fro_2分別存儲上一周期的公交車輛位置與這兩個可能到達站點在單向循環列表中下一站點之間的線性距離；cur_1、cur_2分別存儲當前周期的站點匹配所得第一個和第二個可能到達站點的站號；D_cur_1、D_cur_2分別存儲當前周期的公交車輛位置與可能到達站點在單向循環列表中下一站點之間的線性距離。因此總共可能存在四種不同情況，對其是否符合單向循環排列的判定如下：

(1)前后兩個周期都只匹配到一個可能到達站點。此時，比較匹配站號是否相同；若相同且前后周期距離滿足遞減規律，則認為該匹配站號所對應的站點為車輛當前進站站點。即比較fro_1與cur_1是否相同；若相同且滿足距離D_cur_1小于D_fro_1，則認為fro_1所對應的站點為車輛當前進站站點。其搜索流程如圖2所示。

圖2 站點搜索情況1流程圖

(2)前一周期匹配到一個可能到達站點，后一周期匹配到兩個可能到達站點。后一周期中的兩個可能到達站點中必有一個與前一周期匹配站點一致，此時若前后兩個周期中所得Ld+1值呈遞減趨勢，則該一致站點即為車輛當前進站站點，否則認為后一周期的另一匹配站點為當前進站點。即先比較fro_1與cur_1是否相同，若相同則比較距離D_cur_1與D_fro_1的大小，若D_cur_1小于D_fro_1則認為cur_1所對應的站點為車輛當前進站站點，否則認為cur_2所對應的站點為車輛當前進站站點；若fro_1與cur_1所記錄的站號不同，則再比較距離D_cur_2與D_fro_1的大小，D_cur_2小于D_fro_1則認為cur_2所對應的站點為車輛當前進站站點，否則認為cur_1所對應的站點為車輛當前進站站點。其搜索流程如圖3所示。

圖3 站點搜索情況2流程圖

(3)前一周期匹配到兩個可能到達站點，后一周期匹配到一個可能到達站點。前一周期中的兩個可能到達站點中必有一個與后一周期匹配站點一致，此時若前后兩個周期中所得Ld+1值呈遞減趨勢，則該一致站點即為車輛當前進站站點，否則認為前一周期的另一匹配站號為當前進站點。即先比較fro_1與cur_1是否相同，若相同則比較距離D_cur_1與D_fro_1的大小，D_cur_1小于D_fro_1則認為fro_1所對應的站點為車輛當前進站站點，否則認為fro_2所對應的站點為車輛當前進站站點；若fro_1與cur_1所記錄的站號不同，則再比較距離D_fro_2與D_cur_1的大小，若D_cur_1小于D_fro_2則認為fro_2所對應的站點為車輛當前進站站點，否則認為fro_1所對應的站點為車輛當前進站站點。其搜索流程如圖4所示。

圖4 站點搜索情況3流程圖

(4)前一周期匹配到了兩個可能到達站點，后一周期也匹配到了兩個可能到達站點。這種情況下，前后兩周期匹配到的兩個站號應互相對應。首先比較其中一個對應匹配站點在前后兩個周期中所得Ld+1值，若呈遞減趨勢則認為該匹配站點為當前進站站點，否則認為另一對應匹配站點為當前進站站點。即先比較fro_1與cur_1是否相同，若相同則比較距離D_cur_1與D_fro_1的大小，D_cur_1小于D_fro_1則認為cur_1所對應的站點為車輛當前進站站點，否則認為cur_2所對應站點為車輛當前進站站點；若fro_1與cur_1所記錄的站號不同，則再比較距離D_cur_1與D_fro_2的大小，若D_cur_1小于D_fro_2則認為fro_2所對應站點為車輛當前進站站點，否則認為站號為fro_1所對應站點為車輛當前進站站點。其搜索流程如圖5所示。

圖5 站點搜索情況4流程圖

如果上述(1)～(4)情況中的判定條件均不滿足，則所求取的可能到達站點是逆向或虛假站點，不進行進站報站。

1.4 出站判定及預報

文中所提算法規定，通過進站判定確定當前進站站點之后，繼續以設定周期T計算所接收到的公交車輛當前位置與已確定的當前進站站點之間的線性距離。當所計算的距離不再小于設定距離值L時，將單向循環列表中的下一站點設置為預報站點，進行出站預報。為避免下一次的進站站點誤判，還需將前后兩次記錄的滿足小于設定距離值L的可能到達站點及下一站點與公交車輛當前位置之間的線性距離清除。將公交線路所有站點按照所述單向循環列表方式存儲后，公交車輛出站的預報站點必將是當前進站站點在單向循環列表中的下一個站點。

2 實驗結果分析

為了驗證文中公交自動報站算法的可行性和有效性，利用基于北斗定位模塊UM220和3G通信模塊EM770W的嵌入式智能公交信息發布系統進行實際公交路線報站測試，系統終端主控MCU為STM32F107VCT6，采用VS1003音頻解碼模塊進行相應站點的語音播報。截取某實際公交路線的一段作為公交報站測試路線，裝載了嵌入式智能公交信息發布系統終端的車輛依次經過1號至12號實際公交站點。其中1號和12號站點、2號和11號站點、3號和10號站點互為實際公交路線對應往返站點。測試環境變量設置如下：車輛運行速度V=40km/h，距離值L=50m，周期T=2s。

目前階段的自動報站算法大多需要在人工確認車輛行駛方向后才能較好工作，且基本無法自行修復公交車任意調頭和跨站后產生的報站問題，對文中所提公交自動報站算法的測試主要集中驗證是否能夠解決上述車輛上下行、調頭跨站相關問題：

首先假定1號站點為實際公交路線端站點，此時可默認12號站點與1號站點為同一站點。現有的公交自動報站算法在未經人工確認車輛上下行方向的前提下，GPS數據匹配到端站點位置信息后系統可能默認此次線路運行結束，導致車輛開往2號站點時，系統無法準確尋址存儲模塊內的站點信息從而無法正確報站。文中所提出的算法采用單向循環列表方式存儲往返全部站點信息，不存在無法準確尋址的問題。測試車輛從1號站點開往2號站點過程中，由于2號站點與11號站點十分接近，北斗定位數據在兩次搜索周期內匹配到兩個站點信息，此時算法按照1.3小節中第四種情況進行站點搜索，測試結果顯示該算法能夠有效解決上下行問題并準確對2號站點進行報站。

測試車輛從4號站點出站后不按原路線行駛，而是調頭返回運行，此時車輛并未抵達終點站，跨站的情況也包含其中。在有上下行概念的現有公交自動報站算法中，這種情況下只會去匹配原有方向的其他站點，而無法匹配到返向的站點，從而導致誤報或者不報站。文中所提出的算法不僅采用循環列表存儲全部站點信息，且采用實時全局搜索方式進行站點匹配計算，全匹配的站點搜索方式對以前的報站狀態是無關聯性的，車輛的位置狀態信息的刷新速度要遠快于車輛的運行速度。也就是說，該算法在匹配10號站點時只依賴連續兩次實時接收的車輛位置數據，在站點匹配過程中將公交車輛的實際位置與預存的所有站點進行全匹配，測試結果顯示該算法能夠在車輛突然調頭的情況下對10號站點進行準確報站。后續的站點判斷則與正常行駛過程中的報站判斷一致。

根據實際測試結果可知，文中所提出的算法適用于基于北斗或者其他實時定位技術的全自動判定及報站，能夠較好地解決公交車自動上下行判斷的問題，且在公交車臨時調頭的情況下能夠實現報站恢復，具備較好的糾錯能力。

3 結束語

結合公交車輛往復運行的規律，文中提出一種基于單向循環列表的新型公交全自動報站算法。算法采用單向循環列表存儲公交往返路線全部站點信息，從而達到了無需判斷公交車輛行駛方向的效果，減少了公交司機的工作量；通過周期性的全局搜索進行站點匹配計算，解決了公交車輛突然調頭或跨站后出現的自動報站問題，避免了累積誤報。該算法經過理論分析和實驗驗證，具有一定的可行性和有效性。

[1] 楊再龍,趙仁冉,肖 明,等.基于GPS的公交自動報站系統設計[J].科技信息,2010(12):236-237.

[2] 彭 可，周 敏，邵 添，等.一種公交全自動報站方法:CN,201410077708.7[P].2014-03-05.

[3] 張國華,黎 明,王靜霞.智能公共交通系統在中國城市的應用及發展趨勢[J].交通運輸系統工程與信息,2007,7(5):24-30.

[4]EzellS.ExplaininginternationalITapplicationleadership:intelligenttransportationsystems[C]//ProceedingsofIOPconferenceseries:materialsscienceandengineering.[s.l.]:[s.n.],2010.

[5] 李 耀,昂志敏,李敏杰,等.基于3G車載移動終端的GPS定位系統設計[J].微型機與應用,2012,31(23):51-54.

[6] 王 波.基于GPS/BD2和行駛記錄信息的車輛監控終端設計與實現[D].杭州：浙江工業大學,2012.

[7] 馬麗芳.基于北斗和GPRS車載終端的設計與研究[D].西安：西安科技大學,2013.

[8]SenatoreS.Specialissueonknowledge-intensivefusionforcontextawareness[J].JournalofAmbientIntelligence&HumanizedComputing,2013,4(4):409-410.

[9]KawaiK,McdonaldDT.Computer-implementedsystemandmethodforidentifyingduplicateandnearduplicatemessages:US,US8914331[P].2014.

[10] 劉前剛.GPS定位算法及其在智能公交中的應用[D].長沙：湖南大學,2009.

[11] 張 偉.基于GPS和移動互聯網的城市公交監管系統設計與研發[D].長沙：湖南師范大學,2012.

[12] 彭 勇.基于GPS的公交自動報站算法研究[J].通信技術,2009,42(11):211-213.

[13]RazzaqueMA,AhmadSS,CheraghiSM.Securityandprivacyinvehicularad-hocnetworks:surveyandtheroadahead[M]//Wirelessnetworksandsecurity.Berlin:Springer,2013:107-132.

[14] 薛盛可,徐晉鴻,徐曉霞,等.基于GPS的校車自動報站系統設計[J].電子技術與軟件工程,2014(10):132.

Algorithm of Automatic Bus-station Broadcasting System Based on Unidirectional Circular List

PENG Ke,YANG Ling,GUO Qi-ming,FENG Zhun,ZHENG Huai-peng

(College of Engineering and Design,Hunan Normal University,Changsha 410081,China)

A new algorithm for automatic bus-station broadcasting system based on unidirectional circular list is proposed to solve the problems such as the determination of bus direction and the station skip or unexpected U-turn in current automatic broadcasting algorithms.Both the reciprocating operation pattern of buses and the internal unidirectional cyclic sequence of bus stations are taken into consideration.So the concept of bus up and down direction is replaced by the unidirectional circular list,which stores the bus stations information.Also the periodic global search is adopted in the new algorithm to match the correct bus station.This algorithm is applied to realize bus automatic station forecasting and broadcasting without direction determination.The bus-station broadcasting recovers to normal status rapidly even in malfunction cases,and there is no accumulated error.

automatic station broadcasting;unidirectional circular list;global search;station matching;approaching judgment;departure forecasting

2016-01-14

2016-04-20

時間：2016-09-19

湖南省自然科學基金資助項目(11JJ3080)；湖南省高校產業化培育項目(11CY012)

彭 可(1973-)，男，教授，博士后，研究方向為網絡化控制、實時嵌入系統、DSP控制系統等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0842.060.html

TP301.6

A

1673-629X(2016)12-0148-05

10.3969/j.issn.1673-629X.2016.12.032