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

　　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所示，用户上一时刻的到达站点也是下一时刻的出发站点。