基于改进PageRank算法的城市轨道交通站点选址规划

【摘 要】为了解决轨道交通选址规划根据静态要素进行选点的问题，提出基于改进PageRank算法来选择城市轨道交通站点。基于移动用户出行数据构建有向带权值的用户出行网络，采用改进PageRank算法识别网络的关键节点，以此作为轨道交通规划的核心站点，根据与核心站点相连的节点的拓扑结构判断轨道交通的“桥接”站点位置，以确定轨道交通的路径走向。实验结果表明，基于改进PageRank算法的城市轨道交通站点选址规划方法能够高效、科学地识别轨道交通规划的核心站点和“中转”站点，提高了城市轨道交通站点选址的准确性。

【关键词】PageRank算法 轨道交通 站点选址

doi：10.3969/j.issn.1006-1010.2016.14.013 中图分类号：TP391.4 文献标志码：A 文章编号：1006-1010（2016）14-0060-06

引用格式：杜翠凤，王俊. 基于改进PageRank算法的城市轨道交通站点选址规划[J]. 移动通信， 2016，40（14）： 60-65.

[Abstract] In order to address the issue of urban track traffic site planning based on static factors， the paper proposed site location selection based on improved PageRank algorithm. User travel network construction with directed weighted value was based on mobile user travel data， key node of the network was identified by improved PageRank algorithm， which was used as a core site in rail transit planning， according to the topology of the site and the core node connected， rail transportation“bridge”site location was decided， and the path of the rail strike was thus determined. Experimental results showed that this planning approach can identify core sites and“transit”sites effectively and scientifically， improving site location selection accuracy.

[Key words]PageRank algorithm track traffic site location

1 引言

由于轨道交通体系具有运输量大、准时高效、方便快捷的优点，且不占用地面资源，能够很大程度地缓解交通拥堵和环境污染，因此越来越多的大城市开始打造轨道交通体系。但轨道交通建设是一个非常巨大的投资，如何针对用户的实际出行集聚的需求打造运输效率高、出行方便快捷的轨道交通体系成为轨道交通规划的一个重要问题。

目前大多数研究者以人口数量、土地利用情况、出行时间、站间距、系统等影响轨道交通规划重要因素，采用运筹学的最优理论、阈值函数模型或者仿真等方式进行轨道交通站点的选址，但是这些研究大多采用相对静态的因素作为轨道交通站点选址进行建模，没有考虑用户出行的方向以及用户出行而形成的动态的、复杂网络的链接关系对站点规划的影响。文献[1]根据对轨道交通点客流量分布特征与站点服务能力的关系，建立轨道交通站点的服务能力评价模型，利用该模型得出轨道交通服务能力的综合评价分值，给相关的部门提出改善的建议。该研究仅考虑客流分布特征与站点规划的影响，没有考虑到用户出行的方向以及用户换乘的需求，不能很好地满足用户总体出行的需求。文献[2]综合考虑步行速度和行人密度等影响因素，通过社会力模型来优化两条地铁线的平均传输时间，以此来有效地缓解交通堵塞和优化地铁线路。该研究仅考虑用户出行的距离，但是并没有考虑随着城市的发展，用户出行的需求量也是轨道交通考虑的重要因素。文献[3]从一对起点和终点之间的轨道乘客出行综合费用来优化轨道交通的规划，通过旅客的出行费用、旅客数量以及两点间轨道站点的数量，以综合费用最低来进行线网的总体规划。该研究仅通过乘客自适应选择多条路径实现客流的均衡分布，并没有从乘客实际出行需求出发，高效满足乘客需求。针对上述研究的特点，本文利用运营商的移动用户出行数据构建有向带权值的动态、真实的用户出行网络，采用改进PageRank算法识别出行网络中的每一个基站的重要性，通过该重要性排序进行核心站点和“中转”站点的识别，从而有效地提升站点选址的可用性和实用性。我国大中型城市的城区基站距离一般为200～300 m，郊区基站的距离一般为500～1000 m，而城市的轨道站点间隔一般为1～2 km，因此以运营商的数据的轨道交通选址方法能够广泛应用于我国大中城市的轨道交通选址领域。

2 PageRank算法研究

2.1 问题定义

选址问题中一个重要的研究领域是站点选址问题。站点选址是通过覆盖度量、中心点度量、最短路径等方法来衡量站点的重要性，以重要的站点作为选址的优先点。本文结合移动用户的O-D（Origin-Destination）数据（本文是指移动用户从一个基站到达另一个基站的数据，也称来源去向数据），采用改进PageRank算法来评价以移动用户来源去向的出行行为为基础构建的复杂网络各个节点的重要性，以此实现城市轨道交通站点的选址规划。

2.2 PageRank算法

PageRank算法应用于轨道交通网络节点重要性的评价，其主要思想是：

（1）构建以移动用户出行的O-D数据为基础的复杂网络来模拟现实世界的用户出行的网络。

（2）把评判用户出行的集散点的问题转化为评判每一个基站PageRank值（即基站重要性排名）。某个基站的PageRank值具体算法如下：

设移动用户基站A有T1， T2， …， Tn等n个链接基站源，即移动用户从基站T1， T2， …， Tn到达基站A，基站A的PageRank值（即衡量基站的重要性程度）为PR（A），基站Ti的PageRank值为PR（Ti），Ti的正向链接（从Ti发出的链接）数据为C（Ti），基站Ti的PageRank值根据链接关系平均分配给C（Ti）个基站[4-5]。根据上述定义，则基站A的PageRank值为：

PR（A）=PR（T1）/C（T1）+PR（T2）/C（T2）+…+PR（Tn）/C（Tn）

= （1）

公式（1）表明基站PageRank值完全依赖于移动用户出行网络的链接结构，后来的研究者对公式（1）引入一个阻尼因子d（也称衰减系数）进行改进，表示移动用户有d的概率会顺着基站继续往下一个基站运动，而有1-d的概率驻留在当前基站，一般情况下d取值0.85，则得到公式如下：

PR（A）=（1-d）+d （2）

（3）算法是基于“优质网页链接过来的网页，必定还是优质网页”的回归假设[5]。这就意味着如果某个基站得到周边基站的大量移动用户的进入，那么该基站的重要性更高，更有可能成为用户出行的核心站点或者中转站点。

2.3 改进PageRank算法

公式（1）和（2）采取平均分配的方式通过链接关系传递PageRank值，有学者针对平均分配这一不合理性将正向链接节点根据链接关系赋予不同的权值，通过不均匀分配提高了优质节点的PageRank值，保证了节点重要性的计算。目前已经有很多学者借鉴优化的PageRank算法来计算有向带权值的复杂网络的节点，但是该方法并没有进一步考虑链接源节点Ti与其余节点相连的拓扑结构对A节点的影响，该指标不能发现一些重要的“桥接”节点[7]，如图1所示：

从图1可以看出，如果按照传统的PageRank算法来发现网络的核心节点，那么就意味着M2这个重要的“桥接”节点肯定被忽略掉。“桥接”节点直接关联轨道交通的路径和换乘点选择，在实际应用中“桥接”节点选择也是轨道交通选址规划不可忽略的一个大问题。因此，需要改进网络中PageRank的计算方法，更精确地衡量节点在网络中的地位。

Ti为节点A的第i个链接源，INA为节点A的链接源总数，wAi为Ti指向A的权值（也称边权值，计算方式为Ti指向A的PageRank值除以所有指向A的源节点的PageRank值），以Ti为链接源的节点包括A在内有M1， M2， …， Mm等mi个。INj为节点Mj的链接源总数，wMj为Ti指向Mj的权值，N为网络节点的数量。公式如下：

由公式（3）得出的PR（A）能够判断核心节点的位置，然后再通过来判断“桥接”节点的位置。

3 基于改进PageRank算法的城市轨道交

通站点选址规划

3.1 城市轨道交通站点选址规划流程

根据城市轨道交通站点规划选址的规范为：

（1）满足城市主干客流需求，主要研究城市客流集散点和分布情况、人口及产业的分布特征，使得轨道交通有效承担城市主干客流量和疏散城市人口聚集中心的压力。

（2）设置大型的换乘中心，保证轨道交通各线路便捷换乘。

因此，本文设计的轨道交通站点选址优先考虑用户出行需求量、客流中转需求量，通过建立模型得到相关的参数评价出行网络的核心站点和“桥接”站点。

如图2所示，本文基于改进PageRank算法的城市轨道交通站点选址规划的流程是：

（1）通过移动运营商获取移动用户在每一个基站O-D数据。

（2）基于用户来源去向的出行行为数据构建有向带权值的用户出行网络。

（3）采用改进PageRank算法处理复杂网络的链接关系并识别网络的关键节点，以关键节点作为轨道交通规划的核心站点。

（4）根据与核心站点相连的节点的拓扑结构判断轨道交通的“桥接”（或“中转”）站点位置，以确定轨道交通的路径走向。

3.2 城市轨道交通站点选址规划过程

（1）移动用户来源去向数据的提取

在提取用户的来源去向数据之前，首先需要说明切换的定义。切换是指当移动台在通话过程中从一个基站覆盖区移动到另一个基站覆盖区，或者由于外界干扰造成通话质量下降时，必须改变原有的话音信道而转接到一条新的空闲话音信道上，以继续保持通话的过程。切换通常发生在移动台从一个基站覆盖小区进入到另一个基站覆盖小区的情况下，为了保持通信的连续性，MSC（Mobile Switching Center，移动交换中心）将移动台与当前基站之间的链路转移到移动台与新的基站之间的链路，这种切换操作不仅要识别一个新的基站，而且要求将语音和控制信号分配到新基站的相关信道上[6]。

在手机用户进行移动的过程中，会发生各种手机业务或者进行小区的切换，这些信息都会记录在信令数据里面，通过手机信令采集系统可以获得手机用户的所有切换信息。移动用户的切换信息示例如表1所示：

如表1所示，用户ID为1在一段时间内的切换路径为54216-54217-54321-55452-55383。同理，其他用户的切换路径的处理方式也是一致的。

在提取用户切换路径的基础上，添加移动用户的O-D标签，可确定用户的出发时间、到达时间、出发站点、到达站点。如表2所示，用户上一时刻的到达站点也是下一时刻的出发站点。

（2）构建有向带权值的用户出行网络

对上述每个用户的每一对O-D序列点连线处理，按照时间序列把用户轨迹最终拟合点连成线，就能统计大多数用户在一段时间内的出行轨迹，通过对全部用户的O-D序列进行叠加，可以统计从一个基站到另一个基站的移动用户数量。

如图3所示，出行网络的节点是由基站构成，基站的起点和终点的连线代表网络的边，从起点到终点的人数可认为是该网络的PageRank值，边权值是通过某一个节点的拓扑结构决定。

（3）改进PageRank算法挖掘站点选址位置及“中转”站点位置

基于运营商移动用户来源去向的出行网络，判断某个基站站点A的来源基站站点Ti（i=1， 2， …， n）；INA是指向基站站点A的来源基站站点的总数；每一个来源基站到A基站的人数设为RTi-A；wAi为来源基站站点Ti指向基站站点A的权值（wAi=），以Ti为来源基站站点包括A在内有M1， M2， …， Mm等mi个基站站点。INj为基站站点Mj的来源基站站点的总数，wMj为基站站点Ti指向基站站点Mj的权值，N为整个网络基站站点的总数量。因此，A站点的重要性I（A）为：

（4）

由公式（4）得出的I（A）能够判断轨道交通核心站点的选址位置，然后再通过来判断轨道交通“中转”站点的选址位置，以确定轨道交通的路径走向。

4 实验分析

4.1 数据来源及处理工具介绍

本文采用保定某运营商提供A接口、IuCS接口2015年8月16日至30日的信令数据，该信令数据大小为874 GB，包含200多万用户发生业务的位置切换及位置更新的相关信息，其中A接口数据约为23亿条，IuCS接口数据约为37亿条。通过分析处理保定某运营商移动用户两周的来源去向出行行为数据，挖掘核心站址和“中转”站址。

4.2 结果展现

如图4所示，本文基于某运营商移动用户的来源去向数据，采用改进PageRank算法挖掘站点选址位置及“中转”站点位置。

其中，分别有3个核心站点和3个“中转”站点，整个轨道交通的建设路径如图4中的蓝色线段所示。该站点的选址位置与用户停留热力图较为吻合，能够在一定程度上满足用户的出行需求。

5 结束语

由于运营商平台积累了大量用户的来源去向数据，从这些数据提取移动用户出行信息能够比较有效地模拟乘客的实际出行行为，为轨道站点选址建设提供可靠的依据。本文通过分析用户来源去向数据所构成的出行网络，提出了改进PageRank算法挖掘城市轨道交通核心站点和“中转”站点，为城市交通的站点规划选址和交通轨道的路径选址给出了具有可行性的方案。此外，由于基站会产生一些“乒乓切换”的现象而导致用户手机在两个基站中频繁切换，这样得出的用户来源去向信息也是无效的，因此在以后的研究中需要对这类数据进行检查并将非正常数据剔除，以免误差严重偏离真实情况。

参考文献：

[1] Nabil Semaan， Terek Zayed. A Stochastic Diagnostic Model for Subway Stations[J]. Tunneling and Underground Space Technology， 2010，25（1）： 32-41.

[2] Xubin Sun， Yue Zhang， Gaoyou Qin， et al. Pedestrian Transfer Time Optimization of Urban Rail transit based on ACP Approach[A]. IEEE International Conference on Automation and Logistics[C]. 2012： 90-95.

[3] 李福志，胡思继. 城市快速轨道交通路网规划的相关问题[J]. 交通运输工程学报， 2001（1）： 39-42.

[4] 张巍. 基于PageRank算法的搜索引擎优化策略研究[D]. 成都： 四川大学， 2005.

[5] 胡满玉. 基于链接关系的有向加权复杂网络关键节点识别技术研究[D]. 南京： 南京理工大学， 2012.

[6] 杨飞，惠英. 基于手机切换变化模式的道路匹配方法[J]. 系统工程， 2007，25（11）： 6-13.

[7] 苏晓萍，宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点[J]. 物理学报， 2015，64（2）： 1-11.

[8] 孙宏飞. 城市轨道交通站点选址问题研究[D]. 兰州： 兰州交通大学， 2014.

[9] 郭晨. 面向轨道交通的灵活型接驳公交站点选址研究[D]. 济南： 山东大学， 2015.

[10] 单海燕. 面向有向赋权网络的节点重要性度量方法研究[J]. 统计与决策， 2012（24）： 29-31.

[11] 李好，陈军. 创意产业经济网络的分析与决策――基于有向节点赋权网络的测度方法[J]. 华东经济管理， 2011，25（6）： 151-154.

[12] 牟浩. 城市轨道交通网络规划综合评价研究[D]. 大连： 大连理工大学， 2013.

[13] 傅搏峰，吴娇蓉，陈小鸿. 郊区轨道站点分类方法研究[J]. 铁道学报， 2008，30（6）： 19-23.