雷定猷，余文文，张英贵，洪舒华

大型客运枢纽行人室内导航实时路径规划方法

雷定猷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 室内行人走行路径网络构建

用图论的知识抽象化客运枢纽内行人的走行路径网络，即抽象为节点与弧的集合。其中，室内导航节点包括行人的起点、终点；不同设施分界点；不同设施交汇点。弧是指节点与节点之间的有向线段，在连接节点时应注意：只允许相邻的节点连接；当平行位置出现楼梯或扶梯时，以楼梯与扶梯的分界线作为公共弧；根据实际情况标定弧的方向。

图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

(编辑 阳丽霞)