雷定猷,余文文,張英貴,洪舒華
大型客運(yùn)樞紐行人室內(nèi)導(dǎo)航實(shí)時(shí)路徑規(guī)劃方法
雷定猷1, 2,余文文1,張英貴1, 2,洪舒華1
(1. 中南大學(xué) 交通運(yùn)輸工程學(xué)院,湖南 長(zhǎng)沙 410075;2. 中南大學(xué) 交通運(yùn)輸工程學(xué)院,智慧交通湖南省重點(diǎn)實(shí)驗(yàn)室,湖南 長(zhǎng)沙 410075)
大型客運(yùn)樞紐的結(jié)構(gòu)復(fù)雜、客流分布不均勻,樞紐內(nèi)的引導(dǎo)標(biāo)志不能有效解決行人對(duì)用時(shí)最短路徑的需求,基于此提出科學(xué)合理的路徑規(guī)劃方法。構(gòu)建行人走行路徑網(wǎng)絡(luò),采用均值聚類改進(jìn)算法確定實(shí)時(shí)速度,分析路段擁擠度,以實(shí)際用時(shí)最短為目標(biāo),建立行人室內(nèi)導(dǎo)航路徑模型,提出一種客運(yùn)樞紐行人室內(nèi)導(dǎo)航實(shí)時(shí)路徑規(guī)劃方法。以長(zhǎng)沙南站為背景,給出具體的應(yīng)用實(shí)例,其計(jì)算結(jié)果表明:所提出的方法能減少行人13.9%的時(shí)間消耗,提高樞紐內(nèi)行人流通率。
大型客運(yùn)樞紐;室內(nèi)導(dǎo)航;路徑實(shí)時(shí)規(guī)劃;均值聚類;擁擠度
大型客運(yùn)樞紐實(shí)現(xiàn)了不同方向和不同運(yùn)輸方式間乘客運(yùn)輸?shù)倪B續(xù)性,樞紐內(nèi)的乘客具有很明顯的移動(dòng)目的,如進(jìn)站、出站和換乘等,所以目的地相同的行人在通往目的地的過(guò)程中很容易集中起來(lái)而形成乘客流,這就會(huì)導(dǎo)致客流分布不均勻,沒(méi)有充分利用樞紐內(nèi)的設(shè)施,不利于樞紐內(nèi)行人的流通,樞紐內(nèi)結(jié)構(gòu)復(fù)雜,靜態(tài)導(dǎo)向標(biāo)識(shí)為行人提供路徑的大致方向,不能合理地為行人規(guī)劃用時(shí)最短路徑,因此,本文提出大型客運(yùn)樞紐行人室內(nèi)導(dǎo)航實(shí)時(shí)路徑規(guī)劃方法。近年來(lái),大型公共建筑物室內(nèi)導(dǎo)航已成為熱點(diǎn)話題之一,常用的定位技術(shù)包括WiFi[1],藍(lán)牙[2?3],RFID[4]以及超寬帶[5]等技術(shù)。在定位精度、定位時(shí)間和應(yīng)用場(chǎng)景等方面,藍(lán)牙與超寬帶定位技術(shù)明顯優(yōu)于其他兩者,但考慮到超寬帶技術(shù)定位成本高,且手機(jī)不支持超寬帶技術(shù)等原因,本文采用藍(lán)牙定位技術(shù)。在室內(nèi)導(dǎo)航方面,LI等[6]以大型公共建筑物為研究對(duì)象,采用一種改進(jìn)的實(shí)時(shí)A*算法,將時(shí)間較優(yōu)指標(biāo)引入評(píng)價(jià)指標(biāo)中。Czogalla等[7]以機(jī)場(chǎng)、火車站為研究對(duì)象,采用PDR算法更新用戶位置,通過(guò)動(dòng)態(tài)屏幕和語(yǔ)音引導(dǎo),將路徑方向?qū)崟r(shí)傳遞給用戶。張騰[8]用建筑物平面圖構(gòu)建三維路徑網(wǎng)絡(luò)圖,實(shí)現(xiàn)基于耗時(shí)最短的室內(nèi)三維路徑規(guī)劃。Tardieu等[9]提出通過(guò)聽(tīng)覺(jué)信息為行人解決在樞紐內(nèi)迷失方向的情況,提高行人換乘效率。XU等[10]采用用戶個(gè)人設(shè)備獲取的店面圖像中的高級(jí)視覺(jué)信息,提出基于空間距離的室內(nèi)購(gòu)物中心定位導(dǎo)航方法。既有研究中,在室內(nèi)導(dǎo)航路徑規(guī)劃方面,主要考慮路徑長(zhǎng)度最短或通過(guò)該段路徑耗時(shí)最少,未考慮實(shí)時(shí)速度對(duì)最短路徑的影響,本文以大型客運(yùn)樞紐為研究對(duì)象,提出大型客運(yùn)樞紐行人室內(nèi)導(dǎo)航實(shí)時(shí)路徑規(guī)劃方法,旨在為行人提供用時(shí)最短的路徑,提高樞紐內(nèi)行人流通率。通過(guò)抽象化樞紐內(nèi)行人走行網(wǎng)絡(luò),利用基于指紋識(shí)別法的藍(lán)牙4.0技術(shù)獲取行人起點(diǎn)、路段上各樣本實(shí)時(shí)位置,計(jì)算各樣本速度,通過(guò)-means聚類改進(jìn)算法得出各路段實(shí)時(shí)速度,分析路段擁擠度,尋找擁堵點(diǎn),建立行人室內(nèi)導(dǎo)航路徑模型,采用Dijksta算法搜尋最短路。
用圖論的知識(shí)抽象化客運(yùn)樞紐內(nèi)行人的走行路徑網(wǎng)絡(luò),即抽象為節(jié)點(diǎn)與弧的集合。其中,室內(nèi)導(dǎo)航節(jié)點(diǎn)包括行人的起點(diǎn)、終點(diǎn);不同設(shè)施分界點(diǎn);不同設(shè)施交匯點(diǎn)?;∈侵腹?jié)點(diǎn)與節(jié)點(diǎn)之間的有向線段,在連接節(jié)點(diǎn)時(shí)應(yīng)注意:只允許相鄰的節(jié)點(diǎn)連接;當(dāng)平行位置出現(xiàn)樓梯或扶梯時(shí),以樓梯與扶梯的分界線作為公共??;根據(jù)實(shí)際情況標(biāo)定弧的方向。
圖1 路經(jīng)網(wǎng)絡(luò)示意圖
確定性位置指紋識(shí)別法[11]指使用室內(nèi)藍(lán)牙基站接入點(diǎn)的RSSI序列對(duì)客運(yùn)樞紐內(nèi)的環(huán)境特征進(jìn)行抽象和形式化描述,匯集這些RSSI序列構(gòu)成位置指紋數(shù)據(jù)庫(kù),利用K近鄰法,將待測(cè)點(diǎn)RSSI和指紋數(shù)據(jù)庫(kù)中的數(shù)據(jù)匹配,得出待測(cè)點(diǎn)位置。
基于確定性位置指紋的藍(lán)牙定位算法,分為2個(gè)階段,即離線采集階段和在線定位階段。離線采集階段,有個(gè)采集點(diǎn),個(gè)藍(lán)牙RSSI的指紋數(shù)據(jù)庫(kù):
在樞紐內(nèi),路段上的行人走行方向包括單一、混合方向?;旌戏较虻穆范紊?,當(dāng)某一方向的行人較多時(shí),會(huì)影響對(duì)向行人走行速度,因此本文路段實(shí)時(shí)速度指在某一時(shí)刻在該路段上所有方向行人平均走行速度。本章通過(guò)獲取路段樣本速度,利用-means聚類改進(jìn)算法,確定行人路段實(shí)時(shí)速度。
在計(jì)算路段樣本速度時(shí),應(yīng)注意某行人定位的前后位置是否在同一條路段上,分2種情況討論。采集樣本的時(shí)間間隔為,定為10 s。通過(guò)1.2節(jié)中確定的各路段上的樣本行人,進(jìn)行如下計(jì)算:
1) 樣本行人多個(gè)定位點(diǎn)分布在同一條路段上
圖2 多個(gè)定位點(diǎn)在同一路段的分布示意圖
該情況下行人的速度為:
其中:12為位置①與位置②的距離,m;為路段樣本速度,m/s。
2) 相鄰定位點(diǎn)分布在不同路段上
圖3 相鄰定位點(diǎn)在2條路段上分布示意圖
該情況下的行人速度為,以瞬時(shí)速度v作為取值進(jìn)行分配:
設(shè)
本文采用-means聚類[12?13]改進(jìn)算法對(duì)行人路段實(shí)時(shí)速度進(jìn)行估計(jì),模型的核心思想是利用-means聚類算法將同路段同時(shí)段的行人速度種類預(yù)先設(shè)為,然后采用頻數(shù)加權(quán)法對(duì)不同類的數(shù)據(jù)進(jìn)行加權(quán)融合,得到路段的平均速度。具體步驟 如下。
步驟3:路段速度樣本數(shù)據(jù)的融合。
2) 確定樣本在各個(gè)區(qū)間內(nèi)的個(gè)數(shù),計(jì)算各類所占權(quán)重:
(2)黏層油灑布:灑布黏層油前,應(yīng)對(duì)原路面的雜草等進(jìn)行清除,選用的黏層用乳化瀝青應(yīng)與微表處用乳化瀝青相一致,并確保黏層完全凝固。
在本文中,將擁擠度劃分為3個(gè)等級(jí)[14],分別為擁擠、一般擁擠和暢通,≥1.22 m/s為暢通;0.77~1.22 m/s為一般擁擠;≤0.77 m/s為擁擠。
為了更好地給行人規(guī)劃出最短路徑,考慮樞紐站路段實(shí)時(shí)速度對(duì)最短路徑的影響,建立室內(nèi)導(dǎo)航行人最短路徑模型,為了合理分配資源,當(dāng)行人為一般群體時(shí),通道、自動(dòng)扶梯或樓梯權(quán)值表達(dá)式為式(10),電梯路段權(quán)值表達(dá)式為式(11):
當(dāng)行人為特殊群體時(shí),自動(dòng)扶梯或樓梯路段權(quán)值表達(dá)式為式(11),通道、電梯路段權(quán)值表達(dá)式為式(10)。
目標(biāo)函數(shù)為:
s.t
通過(guò)建立行人走行路徑網(wǎng)絡(luò)、位置識(shí)別方法,獲取各路段行人位置坐標(biāo),對(duì)比前后時(shí)刻位置坐標(biāo)的變化,確定各路段行人速度,利用-means聚類改進(jìn)算法,獲取各路段行人平均速度,即路段實(shí)時(shí)速度,最后,通過(guò)Dijkstra算法,確定最短路徑。
具體算法設(shè)計(jì)如下:
Step 1 在大型客運(yùn)樞紐內(nèi),收集采集點(diǎn)上的RSSI建立指紋數(shù)據(jù)庫(kù)。
Step 2 建立行人走行路徑網(wǎng)絡(luò)。
Step 3 用戶在起始點(diǎn)接收到的藍(lán)牙RSSI為[12… rssi],與藍(lán)牙指紋數(shù)據(jù)庫(kù)對(duì)比,通過(guò)近鄰法,確定起始點(diǎn)1。
Step 4 輸入目標(biāo)點(diǎn)。
Step 5 保存樞紐站內(nèi)部在此刻各路段上的行人樣本坐標(biāo)。
Step 6 確定各路段實(shí)時(shí)速度:
3) 判斷h是否為目標(biāo)節(jié)點(diǎn),若是,則轉(zhuǎn)至1)步,否則,轉(zhuǎn)至下一步。
Step 7當(dāng)服務(wù)對(duì)象是特殊群體時(shí),通道、自動(dòng)扶梯或樓梯表達(dá)式為式(10),電梯路段權(quán)值表達(dá)式為式(11);當(dāng)服務(wù)對(duì)象是特殊群體時(shí),自動(dòng)扶梯或樓梯路段權(quán)值表達(dá)式為式(11),通道、電梯路段權(quán)值表達(dá)式為式(10)。利用Dijkstra算法,尋找最短路徑,輸出最短路徑,1,2和3。
長(zhǎng)沙南站站房包括候車大廳、站臺(tái)、出站和地鐵層4層。長(zhǎng)沙南站正在實(shí)施智能車站建設(shè),以實(shí)現(xiàn)高鐵車站設(shè)備設(shè)施管理智能化,已經(jīng)部署好藍(lán)牙基站,為本文的研究提供了基礎(chǔ)。在長(zhǎng)沙南站,地鐵站至候車大廳的路徑較為復(fù)雜,在地鐵層,行人通常能根據(jù)引導(dǎo)標(biāo)志到達(dá)出站層(地鐵出入口),因此本文研究出站層(地鐵出入口)至候車大廳層的行人路徑。不妨取行人在樓梯處的速度為0.42 m/s[15]。根據(jù)長(zhǎng)沙南站的出站層(地鐵出入口)至候車大廳層的結(jié)構(gòu)以及本文1.1節(jié)構(gòu)建室內(nèi)行人走行路徑網(wǎng)絡(luò),設(shè)西進(jìn)站口左側(cè)門為(0,0,0),則起始點(diǎn)與目的點(diǎn)的走行路徑網(wǎng)絡(luò)如圖4所示。
圖4 走行路徑網(wǎng)絡(luò)圖
根據(jù)本文第2節(jié),以某工作日某時(shí)段采集的由出站層(地鐵出入口,不包括地鐵層)至候車大廳層的行人藍(lán)牙位置數(shù)據(jù)為例,樣本采集間隔為10 s。獲取各路段行人樣本速度(包括不同方向的行人速度),如圖5所示。
圖5 各路段行人樣本速度
根據(jù)-means聚類改進(jìn)算法,根據(jù)2.2節(jié)步驟2,獲得各路段的聚類中心,如表1。
表1 各路段聚類中心
根據(jù)2.2節(jié)步驟3數(shù)據(jù)融合,獲取各路段的實(shí)時(shí)速度,如表2。
表2 路段實(shí)時(shí)速度
圖6 各路段擁擠度等級(jí)
圖7 最短路徑展示圖
1) 本文提出的室內(nèi)導(dǎo)航方法研究,相對(duì)于基于空間距離的室內(nèi)導(dǎo)航,能夠提供一條實(shí)際用時(shí)最短路徑,避免傳統(tǒng)室內(nèi)導(dǎo)航路徑一致性的情況,使行人流在一定程度上得到合理分配,緩解擁擠,對(duì)各路段擁擠度分析,為車站運(yùn)營(yíng)管理提供一定的理論依據(jù)。
2) 通過(guò)對(duì)長(zhǎng)沙南站的實(shí)例分析可知,采用路段實(shí)時(shí)速度尋找最短路徑,與基于空間距離的最短路徑相比,可以為行人節(jié)省13.9%的時(shí)間。
3) 本文采用的方法,使行人流在一定程度上得到合理分配,但是未考慮同一時(shí)刻行人流分配問(wèn)題,在接下來(lái)的工作中會(huì)從行人流分配和個(gè)體最短路徑2個(gè)方面綜合分析。
[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的超寬帶室內(nèi)定位系統(tǒng)設(shè)計(jì)[J]. 數(shù)字技術(shù)與應(yīng)用, 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] 張騰. 室內(nèi)三維路徑規(guī)劃及多模式導(dǎo)航研究[D]. 濟(jì)南:山東科技大學(xué), 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的大型商場(chǎng)室內(nèi)定位導(dǎo)航系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 杭州: 浙江工業(yè)大學(xué), 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] 美國(guó)交通運(yùn)輸研究委員會(huì). 公共交通通行能力和服務(wù)質(zhì)量手冊(cè)[M]. 北京: 中國(guó)建筑工業(yè)出版社, 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
國(guó)家自然科學(xué)基金資助項(xiàng)目(71501190,71771218)
雷定猷(1958?),男,湖南瀏陽(yáng)人,教授,博士,從事區(qū)域綜合交通規(guī)劃研究;E?mail:ding@csu.edu.cn
(編輯 陽(yáng)麗霞)