大型客運樞紐行人室內導航實時路徑規劃方法

雷定猷，余文文，張英貴，洪舒華

大型客運樞紐行人室內導航實時路徑規劃方法

雷定猷1, 2，余文文1，張英貴1, 2，洪舒華1

(1. 中南大學 交通運輸工程學院，湖南 長沙 410075；2. 中南大學 交通運輸工程學院，智慧交通湖南省重點實驗室，湖南 長沙 410075)

大型客運樞紐的結構復雜、客流分布不均勻，樞紐內的引導標志不能有效解決行人對用時最短路徑的需求，基于此提出科學合理的路徑規劃方法。構建行人走行路徑網絡，采用均值聚類改進算法確定實時速度，分析路段擁擠度，以實際用時最短為目標，建立行人室內導航路徑模型，提出一種客運樞紐行人室內導航實時路徑規劃方法。以長沙南站為背景，給出具體的應用實例，其計算結果表明：所提出的方法能減少行人13.9%的時間消耗，提高樞紐內行人流通率。

大型客運樞紐；室內導航；路徑實時規劃；均值聚類；擁擠度

大型客運樞紐實現了不同方向和不同運輸方式間乘客運輸的連續性，樞紐內的乘客具有很明顯的移動目的，如進站、出站和換乘等，所以目的地相同的行人在通往目的地的過程中很容易集中起來而形成乘客流，這就會導致客流分布不均勻，沒有充分利用樞紐內的設施，不利于樞紐內行人的流通，樞紐內結構復雜，靜態導向標識為行人提供路徑的大致方向，不能合理地為行人規劃用時最短路徑，因此，本文提出大型客運樞紐行人室內導航實時路徑規劃方法。近年來，大型公共建筑物室內導航已成為熱點話題之一，常用的定位技術包括WiFi[1]，藍牙[2?3]，RFID[4]以及超寬帶[5]等技術。在定位精度、定位時間和應用場景等方面，藍牙與超寬帶定位技術明顯優于其他兩者，但考慮到超寬帶技術定位成本高，且手機不支持超寬帶技術等原因，本文采用藍牙定位技術。在室內導航方面，LI等[6]以大型公共建筑物為研究對象，采用一種改進的實時A*算法，將時間較優指標引入評價指標中。Czogalla等[7]以機場、火車站為研究對象，采用PDR算法更新用戶位置，通過動態屏幕和語音引導，將路徑方向實時傳遞給用戶。張騰[8]用建筑物平面圖構建三維路徑網絡圖，實現基于耗時最短的室內三維路徑規劃。Tardieu等[9]提出通過聽覺信息為行人解決在樞紐內迷失方向的情況，提高行人換乘效率。XU等[10]采用用戶個人設備獲取的店面圖像中的高級視覺信息，提出基于空間距離的室內購物中心定位導航方法。既有研究中，在室內導航路徑規劃方面，主要考慮路徑長度最短或通過該段路徑耗時最少，未考慮實時速度對最短路徑的影響，本文以大型客運樞紐為研究對象，提出大型客運樞紐行人室內導航實時路徑規劃方法，旨在為行人提供用時最短的路徑，提高樞紐內行人流通率。通過抽象化樞紐內行人走行網絡，利用基于指紋識別法的藍牙4.0技術獲取行人起點、路段上各樣本實時位置，計算各樣本速度，通過-means聚類改進算法得出各路段實時速度，分析路段擁擠度，尋找擁堵點，建立行人室內導航路徑模型，采用Dijksta算法搜尋最短路。

1 客運樞紐內行人位置識別方法

1.1 室內行人走行路徑網絡構建

用圖論的知識抽象化客運樞紐內行人的走行路徑網絡，即抽象為節點與弧的集合。其中，室內導航節點包括行人的起點、終點；不同設施分界點；不同設施交匯點?；∈侵腹濣c與節點之間的有向線段，在連接節點時應注意：只允許相鄰的節點連接；當平行位置出現樓梯或扶梯時，以樓梯與扶梯的分界線作為公共?。桓鶕嶋H情況標定弧的方向。

圖1 路經網絡示意圖

1.2 室內行人位置識別方法

確定性位置指紋識別法[11]指使用室內藍牙基站接入點的RSSI序列對客運樞紐內的環境特征進行抽象和形式化描述，匯集這些RSSI序列構成位置指紋數據庫，利用K近鄰法，將待測點RSSI和指紋數據庫中的數據匹配，得出待測點位置。

基于確定性位置指紋的藍牙定位算法，分為2個階段，即離線采集階段和在線定位階段。離線采集階段，有個采集點，個藍牙RSSI的指紋數據庫：

2 行人路段實時速度估算方法

在樞紐內，路段上的行人走行方向包括單一、混合方向?；旌戏较虻穆范紊希斈骋环较虻男腥溯^多時，會影響對向行人走行速度，因此本文路段實時速度指在某一時刻在該路段上所有方向行人平均走行速度。本章通過獲取路段樣本速度，利用-means聚類改進算法，確定行人路段實時速度。

2.1 客運樞紐內樣本速度獲取方法

在計算路段樣本速度時，應注意某行人定位的前后位置是否在同一條路段上，分2種情況討論。采集樣本的時間間隔為，定為10 s。通過1.2節中確定的各路段上的樣本行人，進行如下計算：

1) 樣本行人多個定位點分布在同一條路段上

圖2 多個定位點在同一路段的分布示意圖

該情況下行人的速度為：

其中：12為位置①與位置②的距離，m；為路段樣本速度，m/s。

2) 相鄰定位點分布在不同路段上

圖3 相鄰定位點在2條路段上分布示意圖

該情況下的行人速度為，以瞬時速度v作為取值進行分配：

設

2.2 基于k均值的路段實時速度估算方法

本文采用-means聚類[12?13]改進算法對行人路段實時速度進行估計，模型的核心思想是利用-means聚類算法將同路段同時段的行人速度種類預先設為，然后采用頻數加權法對不同類的數據進行加權融合，得到路段的平均速度。具體步驟 如下。

步驟3：路段速度樣本數據的融合。

2) 確定樣本在各個區間內的個數，計算各類所占權重：

（2）黏層油灑布：灑布黏層油前，應對原路面的雜草等進行清除，選用的黏層用乳化瀝青應與微表處用乳化瀝青相一致，并確保黏層完全凝固。

在本文中，將擁擠度劃分為3個等級[14]，分別為擁擠、一般擁擠和暢通，≥1.22 m/s為暢通；0.77~1.22 m/s為一般擁擠；≤0.77 m/s為擁擠。

3 室內導航行人最短路徑規劃方法

3.1 模型構建

為了更好地給行人規劃出最短路徑，考慮樞紐站路段實時速度對最短路徑的影響，建立室內導航行人最短路徑模型，為了合理分配資源，當行人為一般群體時，通道、自動扶梯或樓梯權值表達式為式(10)，電梯路段權值表達式為式(11)：

當行人為特殊群體時，自動扶梯或樓梯路段權值表達式為式(11)，通道、電梯路段權值表達式為式(10)。

目標函數為：

s.t

3.2 算法設計

通過建立行人走行路徑網絡、位置識別方法，獲取各路段行人位置坐標，對比前后時刻位置坐標的變化，確定各路段行人速度，利用-means聚類改進算法，獲取各路段行人平均速度，即路段實時速度，最后，通過Dijkstra算法，確定最短路徑。

具體算法設計如下：

Step 1 在大型客運樞紐內，收集采集點上的RSSI建立指紋數據庫。

Step 2 建立行人走行路徑網絡。

Step 3 用戶在起始點接收到的藍牙RSSI為[12… rssi]，與藍牙指紋數據庫對比，通過近鄰法，確定起始點1。

Step 4 輸入目標點。

Step 5 保存樞紐站內部在此刻各路段上的行人樣本坐標。

Step 6 確定各路段實時速度：

3) 判斷h是否為目標節點，若是，則轉至1)步，否則，轉至下一步。

Step 7當服務對象是特殊群體時，通道、自動扶梯或樓梯表達式為式(10)，電梯路段權值表達式為式(11)；當服務對象是特殊群體時，自動扶梯或樓梯路段權值表達式為式(11)，通道、電梯路段權值表達式為式(10)。利用Dijkstra算法，尋找最短路徑，輸出最短路徑，1，2和3。

4 實例

長沙南站站房包括候車大廳、站臺、出站和地鐵層4層。長沙南站正在實施智能車站建設，以實現高鐵車站設備設施管理智能化，已經部署好藍牙基站，為本文的研究提供了基礎。在長沙南站，地鐵站至候車大廳的路徑較為復雜，在地鐵層，行人通常能根據引導標志到達出站層(地鐵出入口)，因此本文研究出站層(地鐵出入口)至候車大廳層的行人路徑。不妨取行人在樓梯處的速度為0.42 m/s[15]。根據長沙南站的出站層(地鐵出入口)至候車大廳層的結構以及本文1.1節構建室內行人走行路徑網絡，設西進站口左側門為(0,0,0)，則起始點與目的點的走行路徑網絡如圖4所示。

圖4 走行路徑網絡圖

根據本文第2節，以某工作日某時段采集的由出站層(地鐵出入口，不包括地鐵層)至候車大廳層的行人藍牙位置數據為例，樣本采集間隔為10 s。獲取各路段行人樣本速度(包括不同方向的行人速度)，如圖5所示。

圖5 各路段行人樣本速度

根據-means聚類改進算法，根據2.2節步驟2，獲得各路段的聚類中心，如表1。

表1 各路段聚類中心

根據2.2節步驟3數據融合，獲取各路段的實時速度，如表2。

表2 路段實時速度

圖6 各路段擁擠度等級

圖7 最短路徑展示圖

5 結論

1) 本文提出的室內導航方法研究，相對于基于空間距離的室內導航，能夠提供一條實際用時最短路徑，避免傳統室內導航路徑一致性的情況，使行人流在一定程度上得到合理分配，緩解擁擠，對各路段擁擠度分析，為車站運營管理提供一定的理論依據。

2) 通過對長沙南站的實例分析可知，采用路段實時速度尋找最短路徑，與基于空間距離的最短路徑相比，可以為行人節省13.9%的時間。

3) 本文采用的方法，使行人流在一定程度上得到合理分配，但是未考慮同一時刻行人流分配問題，在接下來的工作中會從行人流分配和個體最短路徑2個方面綜合分析。

[1] Papapostolou A, Chaouchi H. WIFE: Wireless indoor positioning based on fingerprint evaluation[C]// Networking, International Ifip-tc 6 Networking Conference, Aachen, Germany, 2010.

[2] Dickinson P, Cielniak G, Szymanezyk O, et al. Indoor positioning of shoppers using a network of bluetooth low energy beacons[C]// International Conference on Indoor Positioning & Indoor Navigation, 2016.

[3] GAO Zhe, SHEN Jie, TANG Zhenhua, et al. Study of hospital indoor localization and navigation system and hospital wireless information broadcasting system based on iBeacon[J]. China Medical Devices, 2018, 33(4): 122? 125.

[4] XU H, DING Y, LI P, et al. An RFID indoor positioning algorithm based on Bayesian probability and-nearest neighbor[J]. Sensors, 2017, 17(8):1806.

[5] 解延春, 唐佳, 倪榮霈, 等. 基于DW1000的超寬帶室內定位系統設計[J]. 數字技術與應用, 2016(4): 187? 190. XIE Yanchun, TANG Jia, NI Rongpei, et al. Design of UWB indoor positioning system based on DW1000[J]. Digital Technology and Application, 2016(4): 187?190.

[6] LI Meng, JING Y, S Xinru. Development of the indoor navigation system in large public buildings[J]. Journal of Tianjin Chengjian University, 2016, 22(6): 460?464.

[7] Czogalla O, Naumann S. Pedestrian indoor navigation for complex public facilities[C]// International Conference on Indoor Positioning & Indoor Navigation. IEEE, 2016.

[8] 張騰. 室內三維路徑規劃及多模式導航研究[D]. 濟南:山東科技大學, 2013. ZHANG Teng. Research on indoor 3D path planning and multi-mode navigation[D]. Jinan: Shandong University of Science and Technology, 2013.

[9] Tardieu J, Susini P, Poisson F, et al. The design and evaluation of an auditory way-finding system in a train station[J]. Applied Acoustics, 2009, 70(9): 1183?1193.

[10] XU Z, ZHENG H, PANG M, et al. Utilizing high-level visual feature for indoor shopping mall navigation[J]. arXiv Preprint arXiv: 1610.01906, 2016.

[11] 王海熔. 基于BLE的大型商場室內定位導航系統的設計與實現[D]. 杭州: 浙江工業大學, 2015. WANG Hairong. Design and implementation of indoor positioning navigation system for large shopping malls based on BLE[D]. Hangzhou: Zhejiang University of Technology, 2015.

[12] XIA Changhui. An improved-means clustering algorithm[J]. China Computer & Communication, 2017(14): 40?42.

[13] Terada Y. Strong consistency of reduced-means clustering[J]. Scandinavian Journal of Statistics, 2015, 41(4): 913?931.

[14] 美國交通運輸研究委員會. 公共交通通行能力和服務質量手冊[M]. 北京: 中國建筑工業出版社, 2010. American Transportation Research Board. Handbook of public transportation capacity and service quality[M]. Beijing: China Building Industry Press, 2010.

[15] Fujiyama T, Tyler N. Free walking speeds on stairs: Effects of stair gradients and obesity of pedestrians[M]. Pedestrian and Evacuation Dynamics. Springer US, 2011: 95?106.

Real–time planning method of indoor navigation path for large passenger transport hubs

LEI Dingyou1, 2, YU Wenwen1, ZHANG Yinggui1, 2, HONG Shuhua1

(1. School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China; 2. School of Traffic & Transportation Engineering, Central South University, Smart Transport Key Laboratory of Hunan Province, Changsha 410075, China)

The structure of large passenger hub is complex and the passenger flow is not evenly distributed. The guide signs in the hub can not effectively meet the demand of pedestrians for the shortest path in use. In order to solve this problem, this paper proposed a scientific and reasonable path planning method. In this paper, a pedestrian walking path network was constructed, the real-time speed was determined by the improved-means clustering algorithm, section congestion was analyzed, and the indoor navigation path model of pedestrian was established with the objective of minimizing the actual time, a real-time path planning method for indoor navigation of passenger transport hub was proposed. Taking Changsha South Railway Station as the background, the concrete application example is given, and the calculation results show that the proposed method can reduce the time consumption of pedestrians by 13.9%, improve the pedestrian circulation rate in the junction.

large passenger transport hubs; indoor navigation; path real-time planning;-means clustering; crowded degree

U115；C811

A

1672 ? 7029(2019)09? 2345 ? 07

10.19713/j.cnki.43?1423/u.2019.09.029

2018?12?25

國家自然科學基金資助項目(71501190，71771218)

雷定猷(1958?)，男，湖南瀏陽人，教授，博士，從事區域綜合交通規劃研究；E?mail：ding@csu.edu.cn

(編輯 陽麗霞)