Identification Method for Key Nodes in En-Route Network

多模式交通系统将不同的出行方式连接在一起，通过结合每种方式的优点，既满足了乘客不同的出行需求和偏好，又提高了便捷性，具有较大提升潜力^[1]. 国内外许多学者对多模式交通多目标路径规划的模型及求解算法开展了大量研究. 陈海鹏等^[2]从时间、费用角度出发，构建了实时环境下多目标的路径选择模型. 付旻^[3]利用不同公交模式的交通特性和网络结构特点，构建了公交超级网络模型. 黄明华等^[4]考虑高峰时段乘客聚集的影响，基于非线性规划方法，构建了以网络总换乘等车时间最短为目标的数学模型. 张瑞兵^[5]考虑城际多模式出行的多个影响因素，提出了一种基于历史订单数据的个体出行偏好挖掘方法，用于计算不同出行个体的权系数. Idri等^[6]提出了一种基于时刻表的多模式交通最短路径算法. Dib等^[7]设计可变邻域-遗传算法求解多模式交通多目标路径规划问题. 赵婷等^[8]研究了换乘次数等3种约束条件下，以实际出行成本最少为优化目标的多模式交通路径决策问题，并提出了基于模拟退火-遗传算法的4种求解策略. 李浩楠等^[9]考虑到时间的波动性与突发事件的影响，建立了基于马尔可夫决策过程的多模式交通路线决策模型与算法. 赖元文等^[10]设计模拟退火-自适应布谷鸟算法求解基于不同利益方权重下的公交调度问题.

综上，国内外学者在多模式交通路网模型的构建上，考虑到了实际路网的时变特性，但时刻表的建立基于固定发车时刻、固定运行速度等方式，无法准确地计算行程时间. 在数学模型的构建上，以约束条件的形式将多目标求解转化为单目标求解问题，可能会导致计算结果出现无解的情况. 在求解算法的研究上，目前主要集中于将几种元启发式算法组合到一起来解决单一目标的优化问题，无法为具有多个出行需求的乘客提供个性化的出行方案. 因此，本文利用IC卡数据建立了一个多模式公交路网模型，并提出一种基于乘客多种出行需求的评价值模型，将真实的路网数据应用到上述模型中，同时，设计一个改进遗传算法对模型进行求解，并与使用较广的模拟退火-遗传算法（simulated annealing-genetic algorithm，GA-SA）进行对比分析. 结果表明本文算法在所得出行方案的质量、寻优效率和迭代次数上更优.

1.   建模方法

1.1   城市多模式交通网络

本文利用包含交通站点、交通站台、交通线路和多组旅程的图对多模式交通网络进行建模，该方法建模的关键是将每一种交通方式表示为一个独立的有向图，然后将所有的子图集成到一个统一的图中. 对于一个有向网络N = (S, P, J, M) ，其中：S为站点集，用于乘客换乘；P为站台集，用于乘客等候车辆，每个站台和所对应的站点相连；J为旅程集，是某种交通线路在特定的时间沿着特定的路线访问站台的车辆集；M为交通线路集. 图1所示为一个包含4个站点、7个站台、8组旅程以及2种交通线路的小型多模式交通网络.

图  1  城市多模式交通网络

Figure  1.  Urban multimodal transit network

下载: 全尺寸图片 幻灯片

1.2   模拟公交时刻表

公交系统的运行易受到道路网络的时变特性影响，无法通过传统时刻表准确地计算行程时间. 因此，为提高路径规划方案对应的时间计算精度，本文利用IC卡刷卡数据模拟公交时刻表. 具体步骤如下：

步骤1　首先对刷卡时间进行升序排列，设卡号为b的公交司机在站台编号为Q的第i次刷卡时间为D_bQ,i，V为这位司机单次运行的刷卡总次数. 则站台Q的刷卡时间间隔集T_bQ为

步骤2　 对刷卡时间进行聚类，当两个刷卡时间间隔$D_{{b{Q,i + 1}}}^{} - D_{{b{Q,i}}}^{} \leqslant 72$ s时，保留$D_{{b{Q,i}}}^{}$，否则剔除. 设n为保留的时间点个数.

步骤3　 计算公交车在站台Q的离站时刻t_Q，如式（2）所示.

步骤4　 如果$n \leqslant 3$，则通过站点间距和公交车运行速度来估计离站时刻.

地铁线路运行比较独立，运行时不受干扰，因此，根据地铁运营公司给出的时刻表便可准确地计算行程时间.

1.3   数学模型

基于乘客的4种出行需求，分别建立各单一目标下的数学模型.

以出行时间为目标函数的数学模型如式（3）所示.

式中：${T_{{\text{jnl}}}}$为出行总时间；t_j为乘客在站台j处的等待时间，$j\in{P}$；${t_{(j,k),{\lambda }}}(a)$为乘客在时刻a从站台j出发选择交通线路${\lambda }$到达站台k所花费的行程时间，$k\in{P}$，${\lambda }\in{M}$；${t_{j,({\lambda },{\theta })}}$为乘客在站台j处由交通线路${\lambda }$换乘交通线路${\theta }$所花费的换乘时间，${\theta }\in{M}$；${x_{(j,k),{\lambda }}}$为站台$j$到站台k是否选择交通线路${\lambda }$，若是，则${x_{(j,k),{\lambda }}}{\text{ = 1}}$，否则，${x_{(j,k),{\lambda }}} = {\text{0}}$；${x_{j,({\lambda },{\theta })}}$表示是否在站台j处由交通线路，${\lambda }$换乘交通线路${\theta }$，若是，则${x_{j,({\lambda },{\theta })}} = {\text{1}}$，否则，${x_{j,({\lambda },{\theta })}} = {\text{0}}$.

以出行成本为目标函数的数学模型如式（4）和式（5）所示.

式中：${C_{{\text{jnl}}}}$为出行总成本;${C_{(j,k),{\lambda }}}\left( f \right)$为乘客从站台j到站台k采用交通线路${\lambda }$经过里程数f所花费的票价；${C_q}$为第q段里程（里程数区间为(f_q−1，f_q] ）所花费的票价.

以换乘次数为目标函数的数学模型如式（6）所示.

式中：${N_{{\text{jnl}}}}$为出行总换乘次数.

以步行距离为目标函数的数学模型如式（7）所示.

式中：${D_{{\text{jnl}}}}$为出行总步行距离；${d_{j,k}}$为站台j到站台k的步行距离.

2.   算法设计

遗传算法是模拟生物进化过程的计算模型，以其评价值简单、随机性强、可群体搜索等特点，应用于大量多目标最优化的问题中. 但其计算结果对初始种群具有一定的依赖性，并且易陷入局部最优解. 深度优先搜索算法^[11]可遍历到包含自身的所有起终点路径，且不会重复访问相同节点，二者的结合可在确保初始种群可行性的前提下，提高寻优能力，使得算法跳出局部最优解. 因此，本文提出了深度优先搜索-遗传组合算法（depth first search-genetic algorithm，GA-DFS）来实现多模式公交多目标的路径规划.

2.1   算法步骤

算法的具体步骤如下：

步骤1　将路网中所有多模式公交站台进行编码；

步骤2　应用深度优先搜索算法随机产生初始种群；

步骤3　计算各个单一目标下，种群中所有方案对应的函数值；

步骤4　把同一方案不同出行目标下的函数值进行无量纲化处理，并基于用户的出行需求赋予权重，通过线性加权法得到出行总评价值；

步骤5　判断是否收敛或达到迭代次数，是则输出最优值，否则转步骤6；

步骤6　进行父代选择、单点交叉和基于深度优先搜索算法的变异操作，生成子代种群. 再次判断是否收敛或达到迭代次数，是则输出最优解，否则转步骤6，直至满足终止条件.

2.2   编码设计

遗传算法中的每个染色体表示起、终点间一个潜在的出行方案，针对本文建立的多模式公交网络，对染色体分两层进行编码，现以一个起点站台为1，终点站台为7的出行方案为例进行阐述，如图2所示. 第一层编码{1, 2, 3, 4, 5, 6, 7}表示公交网络中的站台编号，第二层编码{1, 1, 1, 1, 1, 1}表示各个站台间是否连通，若连通，则编码为1，否则，编码为0.

图  2  编码示意

Figure  2.  Coding schematic

下载: 全尺寸图片 幻灯片

2.3   初始种群

初始种群中的每个出行方案应避免出现回路和无效路径. 为解决上述问题，本文采用深度优先搜索算法进行初始种群的生成. 方法如下：

步骤1　基于城市公共交通网络建立邻接矩阵；

步骤2　把起始站台放入数组中，设为当前站台；

步骤3　扩展当前的站台，产生一个新的邻近站台放入数组，同时把新产生的站台设为当前站台；

步骤4　判断当前站台是否与数组中的站台相重复，如果重复则返回上一个站台，产生它的另一个邻近站台；

步骤5　判断当前站台是否为目标站台，如果是，则找到一个初始个体，结束算法，否则，转步骤3.

2.4   评价与选择

路径规划方案的选择操作选用出行总评价值 ${{\boldsymbol{A}}_{{\text{sum}}}}$描述候选个体的适应值，由于初始种群以及迭代过程中的每一代种群是否包含最优个体是未知的，因此，本文采用动态阈值化法进行无量纲化处理，如式（8） ~ （11）所示.

s.t.：

式中：${{\boldsymbol{A}}_{{\text{single}}}}$为无量纲化后的指标评价值；${o_{\max }}$为种群中每一代单一指标下的最大值；${o_{\min }}$为种群中每一代单一指标下的最小值；${r_{{\text{real}}}}$为指标的实际值；${A_{uv}}$为出行需求为u的第v个个体经无量纲化处理的结果，u = 1, 2, 3, 4， v = $1, 2, \cdots , H$，为种群中个体的总数；${\xi }_{\text{T}}、{\xi }_{\text{C}}、{\xi }_{\text{N}}、{\xi }_{\text{D}}$分别为出行时间、出行成本、换乘次数、步行距离对应的权重系数.

乘客可根据自己的个性化需求进行选择，且每个出行需求之间为平行目标，选择方式为轮盘赌.

2.5   交叉操作

本文采用具有相同站台的单点交叉方法，如图3所示. 现以两个起点站台为1，终点站台为13的出行方案为例进行阐述. 具体的操作步骤为：随机选择两个父代个体P₁、P₂作为交叉个体；遍历搜索父代个体中的相同站台9、10、11，若存在多个相同的站台，则随机选择一个站台作为交叉点进行交叉操作，本例中选择站台11；保持P₁中交叉点11之前的序列{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}不变，将P₂中交叉点11之后的序列{33, 34, 35, 36, 13}与之相组合形成子代S₁；保持P₂中交叉点11之前的序列{1, 28, 29, 9, 10, 11}不变，将P₁中交叉点11之后的序列{12, 13}与之组合形成子代S₂.

图  3  交叉操作

Figure  3.  Cross operation

下载: 全尺寸图片 幻灯片

若在进行交叉操作后，子代个体出现了重复的基因或片段，这表明新产生的子代个体出现了回路，应当予以消除，同时将父代个体保留至子代.

2.6   变异操作

经交叉操作产生的子代个体与未发生交叉操作的父代个体组成一个新的种群，再进行变异操作. 由于交叉操作可能产生退化种群，由此导致算法陷入局部最优解. 因此，为了跳出局部最优解，寻找全局最优，本文提出了一种新的变异方法，基于深度优先搜索算法的两点变异方法，让变异定向地向着乘客出行需求的方向进行变异，如图4所示.

图  4  变异操作

Figure  4.  Mutation operation

下载: 全尺寸图片 幻灯片

具体的变异过程为：在父代的个体P₁中随机产生两个不同的站台作为变异点，本例中为站台1和站台9；将变异点1、变异点9分别设置为起、终点，利用深度优先搜索算法寻找两变异点间所有的路径片段{1, 28, 29, 9}、{1, 2, 3, 4, 5, 6, 7, 8, 9}、{1, 37, 38, 39, 5, 14, 15, 16, 17, 18, 19, 20, 9}，分别计算所有路径片段的基于乘客个性化需求的出行总评价值V₁ = 0.91、V₂ = 0.83、V₃ = 0.75，将评价值最大的路径片段{1, 28, 29, 9}作为两变异点之间的新路径片段，与父代P₁变异点9之后的序列{10, 11, 33, 34, 35, 36, 13}相组合后形成子代个体S₁.

3.   数值实验

本文实验基于某市区的真实路网数据对GA-DFS算法进行验证，并将GA-DFS算法与GA-SA算法^[8]进行比较. 数据由区交通委提供，路网实例如图5所示，图中数字所示为站点编号. 数据包括两种交通方式（公交、地铁）的地理位置信息以及对应的IC卡刷卡数据信息. 更准确地说，数据包括2条地铁线路、4条公交线路、48个站台、321条起终点路线、1110组旅程.

图  5  城市多模式交通网络实例

Figure  5.  Case of urban multimodal transit network

下载: 全尺寸图片 幻灯片

首先，选取路网节点中的站台38和站台39进行模拟时刻表可行性实验. IC卡刷卡信息选取的是2017年3月13日382路公交车的刷卡数据，如表1所示，其中，站台38和站台39的实际到站时刻依次为表中黑体数据，对应的传统时刻表信息和本文模拟时刻表信息如表2所示. 传统的时刻表基于固定运行速度、固定站点间距求得，受早高峰时段路网的时变特性影响，造成到站时刻不准确. 本文的模拟时刻表方法，基于实际的刷卡数据，2个站台到站时刻的精度分别提升了94%和98%.

表  1  IC卡刷卡数据

Table  1.  IC card data

线路编号	线路名称	交易日期时间
000382	382 路	2017-03-13 07：23：08
000382	382 路	2017-03-13 07：23：10
000382	382 路	2017-03-13 07：23：12
000382	382 路	2017-03-13 07：29：44
000382	382 路	2017-03-13 07：29：47
000382	382 路	2017-03-13 07：29：48
000382	382 路	2017-03-13 07：29：52
000382	382 路	2017-03-13 07：29：54
000382	382 路	2017-03-13 07：29：55
000382	382 路	2017-03-13 07：29：56

下载: 导出CSV 

| 显示表格

表  2  传统时刻表和模拟时刻表

Table  2.  Traditional timetable and simulated timetable

站台号	382 路公交车到站时刻
	传统时刻表	模拟时刻表
38	07：22：32	07：23：10
39	07：24：25	07：29：51

下载: 导出CSV 

| 显示表格

通过假设3种不同出行需求的出行场景，设置不同权重系数，得到不同的推荐路径规划方案，验证说明本文算法在乘客选择不同出行需求时提供的路径规划方案更优. 场景一，乘客为一名旅游度假人员，出行需求为：出行成本低、换乘次数少；场景二，乘客为一名上班通勤人员，出行需求为：出行时间短、换乘次数少；场景三，乘客为一名购买生活必需品的通勤人员，出行需求为：出行成本低、步行距离短.

现某名乘客在8：00从起点1出发到终点13，分别给出3种场景对应的路径规划方案.

种群规模为30，最大迭代数为50次，通过MATLAB软件编程计算，不断调整交叉概率（probability crossover，PC），变异概率（probability mutation，PM）后，连续运行10次，得到对应方案的平均出行时间（average travel time，ATT）、平均换乘次数（average travel number，ATN）、平均出行成本（average travel cost，ATC）、平均步行距离（average walk distance，AWD）和达到稳定时所需的平均迭代次数（average iteration，AI）.

在PC为0.9，PM为0.10且相同初始种群条件下，不同场景的GA-DFS、GA-SA算法迭代过程各参数结果见图6 ~ 8，相同场景下，GA-DFS算法达到稳定时所需的迭代次数更少.

图  6  场景一下相同遗传参数的算法对比

Figure  6.  Comparison of algorithms with the same parameters under scene one

下载: 全尺寸图片 幻灯片

图  7  场景二下相同遗传参数的算法对比

Figure  7.  Comparison of algorithms with the same parameters under scene two

下载: 全尺寸图片 幻灯片

改变遗传参数和出行场景，GA-DFS和GA-SA算法各参数结果见表3. 以场景一为例，当PC为0.9，PM为0.10时，GA-DFS、GA-SA算法的AI分别为17.80、30.62次，ATC分别为0.96、1.76元，ATN分别为1.2、2.2次. 与GA-SA算法相比，GA-DFS算法AI减少了42%，计算效率更高，更有效节约时间成本.

表  3  不同出行场景下的算法对比

Table  3.  Comparison of algorithms under different scenarios

遗传	参数	场景一								场景二								场景三
		GA-DFS				GA-SA				GA-DFS				GA-SA				GA-DFS				GA-SA
PC	PM	ATC/ 元	ATN/ 次	AI/ 次		ATC/ 元	ATN/ 次	AI/ 次		ATT/ min	ATN/ 次	AI/ 次		ATT/ min	ATN/ 次	AI/ 次		AWD/ m	ATC/ 元	AI/ 次		AWD/ m	ATC/ 元	AI/ 次
0.9	0.10	0.96	1.2	17.80		1.76	2.2	30.62		39	1.5	18.90		47	1.9	31.85		600	0.96	19.66		900	1.80	28.95
0.9	0.05	1.24	1.3	21.70		1.88	2.1	32.10		41	1.3	23.60		52	1.9	33.50		650	1.22	24.10		950	1.96	32.70
0.8	0.10	1.32	1.4	23.20		1.96	2.2	31.43		45	1.5	22.30		54	1.8	33.61		700	1.48	22.71		1000	2.04	30.24
0.7	0.10	1.60	1.4	25.60		2.16	2.1	33.95		44	1.4	24.80		64	1.8	34.46		700	1.66	24.53		1050	2.12	31.67
0.6	0.05	1.80	1.9	26.80		2.34	2.2	35.72		50	1.4	27.60		66	1.8	38.73		850	1.88	27.47		1100	2.12	34.81

下载: 导出CSV 

| 显示表格

在场景一的背景下，PC为0.9，PM为0.10时，改变种群规模的大小，GA-DFS、GA-SA算法参数结果见表4. GA-DFS算法在种群规模为60时，基本上每次计算都可以找到最优解（ATC为0.80元，ATN为1.0次），GA-SA算法则需要种群规模达到120时才可以找到最优解，由此可见，与GA-SA算法相比，GA-DFS算法的寻优效率提高了50%，更适用于应用在实际路网中.

表  4  相同参数、不同种群规模在场景一下的算法对比

Table  4.  Comparison of algorithms with the same parameters and different population sizes under scene one

种群规模	GA-DFS			GA-SA
	ATC/元	ATN/次		ATC/元	ATN/次
60	0.88	1.10		1.04	1.30
90	0.80	1.00		0.96	1.20
120	0.80	1.00		0.80	1.00
150	0.80	1.00		0.80	1.00

下载: 导出CSV 

| 显示表格

图  8  场景三下相同遗传参数的算法对比

Figure  8.  Comparison of algorithms with the same parameters under scene three

下载: 全尺寸图片 幻灯片

根据本文多目标路径规划算法的原理分析可知，针对遗传算法对初始种群具有一定的依赖性的问题，本文采用基于深度优先搜索算法的产生策略，利用其不重复访问节点特性，保证初始种群中无回路和无效路径，有效降低了算法的平均迭代次数，节约了计算的时间成本；针对遗传算法的易陷入局部最优解的特点，本文创新地提出了基于深度优先搜索算法的两点变异法，利用深度优先搜索算法的遍历性，在进行变异操作时，产生变异点间所有可能的路径片段，通过计算路径片段的适应值，选择适应值较大的路径片段进行拼接，让变异定向地向着乘客个性化出行需求的方向进行，有效地改善了算法的全局搜索能力，使得给出的路径规划方案更优.

通过GA-DFS算法的求解，得到3种出行场景下的最优路径方案. 场景一的最优路径：1→28→29→30→31→32→33→34→35→36→13；场景二的最优路径：1→2→3→4→5→6→7→8→9→10→11→12→13；场景三的最优路径：1→28→29→30→31→32→33→34→35→36→13. 场景一与场景三所示最优路径，对应的换乘次数和步行距离均为本网络中的最小值，因此出现相同的推荐路径.

4.   结　论

1） 本文在多模式交通出行的背景下，以乘客个性化的出行需求为目标，同时考虑路网的时变特性影响，建立了基于模拟时刻表的多模式公交路网模型和数学模型，并设计了一个基于乘客多出行需求的路径规划求解算法.

2） 所提出的模型和算法，能够根据乘客的多种出行需求提供对应的路径规划方案，其有效性在以某市区为实例背景的算例中得到验证，相比已有的研究，可以提供更优的路径规划方案和更高的寻优效率，适用于规模较大的路网.

3） 未来可对算法框架进行改进，以提高求解效率；此外，还将对其他出行方式（如网约车、共享单车等）进行研究，以提供更加多样化的多模式交通路径规划方案.

致谢：北方工业大学“毓优人才”项目（213051360020XN173/013）的资助.