DOI: 10.11817/j.issn.1672-7207.2017.08.036
基于旅客类别的列车服务网络客流分配
王文宪，潘金山，吕红霞，张瑞婷
(1. 西南交通大学 交通运输与物流学院，四川 成都，610031；
2. 西南交通大学 全国铁路列车运行图编制研发培训中心，四川 成都，610031)
摘 要：
络客流分配模型复杂、求解困难的特点，采用旅客类别划分的简化策略，以旅客主体特性为分析参数，运用近邻传播算法对其进行聚类。在此基础上，构造列车开行方案形成的服务网络，提出不同类别旅客乘车方案弧段阻抗的计算方法，建立基于类别划分的旅客乘车方案概率选择模型，并设计相应的网络流量加载算法。以宝成线为实例，根据客流调查结果，进行旅客类别聚类划分与流量加载验证。研究结果表明：将铁路出行旅客划分为6个类别时，具有最好的聚类效果；在此基础上客流分配准确率在80%以上。基于旅客类别划分的流量分配方法能够得到准确的流量分配结果，从而为列车开行方案的调整提供合理依据。
关键词：
旅客列车开行方案；客流分配；旅客类别划分；近邻传播聚类；列车服务网络；
中图分类号：U268.6 文献标志码：A 文章编号：1672-7207(2017)08-2245-06
Train service network flow assignment based on passenger classification
WANG Wenxian, PAN Jinshan, L
Hongxia, ZHANG Ruiting
(1. School of Traffic and Transportation, Southwest Jiaotong University, Chengdu 610031, China;
2. National Railway Train Diagram Research and Training Center, Southwest Jiaotong University, Chengdu 610031, China)
Abstract: According to the railway network multi-flow path optimization problem of passenger train plan. The simplifying method of passenger classification was firstly adopted, which takes individual feature of passengers as analyzing parameter. And affinity propagation algorithm is used for the cluster of passengers. On that basis, service network constructed by train plan is built, together with the network impedance of different passengers. Then the passenger flow assignment model of train service network reflecting passenger category was established, and relevant strengthening algorithm is designed. Taking Baoji-Chengdu Railway as an example, its cluster partitioning on passenger categories and traffic load verification was analyzed according to passenger survey results. Cluster analysis results show that when the railway travel passengers are divided into six categories, the clustering effect is the best, and on this basis, the passenger flow distribution also shows that the accuracy is above 80%. The flow distribution method based on the classification of passenger categories can get accurate flow distribution results, so as to provide a reasonable basis for the adjustment of train operation plan.
Key words: passenger train plan; flow assignment; passenger classification; affinity propagation cluster; train service network
在旅客列车开行方案所形成的复杂网络上进行客流分配，研究旅客在列车上的分布状况，对旅客列车开行方案评价与优化调整具有重要意义。GOOSSENS[1-2]将IC，IR和AR 3类铁路网叠加，构造基于开行方案备选集的“模式路网”，将旅客路径选择行为衍化为多商品流问题。何宇强等[3]基于旅客出行方便效用最大化，建立不同类型列车客流量分配的非线性双层规划模型，利用混沌算法进行求解。曾鸣凯等[4]建立了不同列车等级、不同停站方案下旅客出行成本最小的客流分配多目标线性模型。聂磊等[5]在分析客流不同出行距离、不同层次以及运输组织对旅客乘车选择的影响基础上，构建列车开行方案服务网络及改进F-W客流分配方法。佟璐等[6]根据旅客出行过程计算列车服务网络的弧段阻抗，设计融合改进蚁群搜索机制以及Frank-Wolfe加载规则的混合求解算法。上述研究主要通过建立各种客流分配模型，设计不同启发式算法实现客流在不同列车上的加载，其中，旅客乘车选择机理是客流分配算法设计的理论依据。但由于旅客对乘车方案的选择具有主观偏好性，不同类型的旅客具有不同的主观乘车方案广义费用。而且，铁路出行旅客数量众多，乘车选择行为受到的众多因素的影响，不同旅客的乘车选择各不相同，要实现对每个旅客的乘车选择行为进行分析是一个规模庞大的问题。对铁路出行旅客进行类别划分，根据旅客的自身特性及出行情况，将具有相似选择行为的旅客进行归并，是简化列车服务网络多层次客流分配问题的重要策略之一。目前国内外对铁路出行旅客类别划分尚无统一方法。胡小风等[7-8]根据出行需求差异性旅客属性，将旅客分为时间型、经济型、舒适型3种基本类型，但该方法主要依靠经验，采用人为划分方式，效率和精度低，不能很好地反映客观情况。曾鸣凯等[4-6]在其构建的客流分配模型中引入时间价值，作为旅客层次划分的依据，但相关研究与调查结论显示，铁路出行旅客的出行选择行为不完全依赖于旅客的收入水平和消费水平，旅客属性诸如年龄、性别、出行目的以及出行费用来源都与其乘车选择行为有较大的关联。聚类分析可以较好地解决这一问题，其本质是根据对象在某些属性上的相似性，将模式空间中有限数据集划分成若干个相互无交集的非空子集，能在没有先验知识的情况下，将样本数据按事物性质的内在联系进行分类[9]。本文作者在前人研究的基础上，先将铁路出行旅客类别划分的依据作为个体描述的变量，然后采用近邻传播的方法对旅客进行划分，针对不同类型旅客提出其乘车广义费用计算方法，在此基础上建立基于旅客类别分类的乘车方案选择概率选择模型，设计列车服务网络流量分配方法，最后通过宝成铁路实际客流和列车开行方案数据对模型和算法进行分析验证。
1 铁路旅客类别划分
铁路旅客的主体特性包括：年龄、性别、月收入、出行目的、出行费用来源等因素，各类属性对其乘车选择均会产生较大的影响[3]。将上述属性进行量化或定性描述，可作为用于旅客聚类分析的属性参数。
近邻传播算法(简称AP)是由FREY等[10]提出来的一种聚类算法，因其不受初始类代表点选择的限制，聚类结果较为稳定，而且在处理大规模多类数据时收敛速度更快，聚类结果更准确，故本文选择AP算法对出行旅客进行类别划分。
AP算法的原理：1) 将数据集的所有N个旅客样本都视为候选的类代表，为每个旅客建立与其他旅客的吸引程度的信息，即任意2个旅客xi和xk之间的相似度，存储在N×N相似度矩阵S中。2) 用s(i，k)表示旅客xk在多大程度上适合作为旅客xi的类代表，初始假设所有旅客样本被选中成为类代表的可能性相同，即设定所有s(k，k)为相同值p。3) 算法引入了2个重要的信息量参数—可信度矩阵R和可用度矩阵A，r(i，k)是从xi指向xk，用来表示xk适合作为xi的类代表的代表程度；a(i，k)是从xk指向xi，用来表示xi选择xk作为类代表的合适程度。对于任意旅客样本xi，计算所有样本的可信度r(i，k)和可用度a(i，k)之和，则两者之和最大的样本xk为类代表，AP算法的迭代为上述2个信息量交替更新的过程。
算法基本步骤如下。
Step 1 初始化。
计算样本相似度矩阵元素s(i，k)，矩阵采用欧式距离为测度，即
(1)
设置对角线元素s(i，k)为相同的吸引度中值：
(2)
设置可信度矩阵R和可用度矩阵A的初始值为0。
Step 2 迭代。
1) 更新可用度和可信度。可信度矩阵元素r(i，k)更新计算公式为
(3)
可用度矩阵元素a(i，k)更新计算公式为
(4)
2) 对所有样本求可信度与可用度之和，根据
找到每个样本的类中心样本。
Step 3 结果输出。
判断信息迭代过程是否达到设置的最大迭代次数，是则算法终止，否则返回Step 2。
2 列车服务网络构造与阻抗确定
2.1 列车服务网络构造
给定铁路客运线路拓扑结构图G=(V，E)以及开行旅客列车L(其中：V为客运站集，E为连接客运站的区段集)。图1所示为6个车站和5个区间构成的铁路线路及相应的旅客列车开行方案。
图2所示为图1所示方案形成的复杂列车服务网络
，由网络节点V和服务弧段E′组成。
图1 铁路线路及其列车开行方案示意图
Fig. 1 Railway line and train plan
图2 复杂列车服务网络示意图
Fig. 2 Complex train service network
本文所涉及的服务网络是由旅客列车开行方案形成，用于不同类型旅客乘车选择的虚拟网络。在进行客流分配时，根据建立的旅客乘车方式规则(如换乘次数等规则)，缩小旅客乘车备选方案搜索范围，从而降低问题的规模。
2.2 网络阻抗确定
不同类型的旅客具有不同的主观乘车方案广义费用，所有OD需求中旅客类型数量为N，列车服务网络中的某OD对r-s间的第n类旅客而言，其可以选择的备选乘车方案集合为
，其选择第k种乘车方案的广义费用为
，即
(5)
式中：
为OD对r-s间第n类旅客对第k种乘车方案出行费用的确定项；
为对应的随机误差项。
现有研究中乘车方案的广义费用包括票价支出、旅行时间以及列车舒适度，即
(6)
式中：αn，βn和γn为第n类旅客的广义费用指标权重；
，
和
为第k种乘车方式的票价支出、旅行时间、以及乘车舒适度；
为第n类旅客的平均时间价值。
但在实际乘车中，旅客往往会考虑出行列车在始发终到时间上的方便程度，但由于该因素没有量纲，本文引入方便系数的概念，对式(6)改进如下：
(7)
式中：δ为旅客乘车方便系数，其取值参照文献[11]中所采用的旅客SP问卷调查统计得出。
舒适度参照文献[12]的成果，采用旅行疲劳恢复时间来描述：
(8)
式中：Tmax为恢复疲劳所需的最长时间参数，通常取14~15 h；φk为选择k种乘车方式的疲劳恢复时间的最小值(即乘车时间为0时的疲劳恢复时间)；fk为单位出行时间的疲劳恢复时间。
参数取值如表1所示。
表1 φk和
k的取值
Table 1 Values of φk and k
3 乘车概率选择模型与算法
3.1 备选乘车方案的确定
由于列车时刻表本身包含路径信息，在确定旅客乘车方案集合时，可由列车时刻表的站点序列得到多个可行的旅客乘车方案，为便于计算，取最大换乘次数为1。
某OD对r-s而言，首先在列车集合L={li|i=1，2，…，N}中，分别找出经过r站及s站的列车集合，并分别记为Lr和Ls。
直达方案求解思路：设
，则列车
经过r站及s站，若列车li从r站的发车时刻trf(li)早于到达s站的时刻tsd(li)，即trf(li)＜tsd(li)，则从r站乘坐列车li可到达s站。
换乘方案求解思路：设Lj=Lr-Ls，则列车
只经过r站，设Lk=Ls-Lr，则列车
只经过s站，若列车lj在r站以后的车站与列车lk在s站以前的车站可以换乘，即
，且
，
，则表示从r站乘坐列车lj在h站可以换乘列车lk到达s站，从而到一个换乘的出行乘车方案。
假定方案广义费用中的随机误差项相互独立，且服从Gumbel分布，则某OD间第n类旅客选择第k种乘车方案的概率为
(9)
3.2 网络流量加载算法设计
根据各类旅客的乘车广义费用，由Logit模型计算其对各种乘车方案的选择比例，在列车开行方案形成的乘车服务网络依次进行流量加载，然后根据乘车方案与开行列车的关联性进行流量累加，得到旅客在各列车上的流量分配结果。具体计算过程如下。
步骤1 采用AP算法将所有OD间旅客进行类别划分，OD对r-s间第n类旅客流量为
。
步骤2 确定列车服务网络中每个OD对r-s间的备选乘车方案集合
。
步骤3 根据式(7)计算OD对r-s间每类旅客的各备选乘车方案广义费用。
步骤4 根据式(9)计算OD对r-s间各备选乘车方案的选择比例
。
步骤5 根据对每种备选方案进行流量分配，计算式为
(10)
步骤6 判断各OD间每类旅客都是否完成分配，是则转步骤7；否则转步骤2。
步骤7 根据
，计算乘车方案与列车流量，计算公式如下：
(11)
(12)
其中：
为0-1变量，表示列车服务网络中OD对r-s间的乘车方案k与列车a的关联系数，若r-s间的乘车方案k由列车a形成，取值为1，否则为0。
4 实例验证与结果分析
以2014年底宝成线开行方案及客流统计数据为基础，进行旅客列车开行方案的客流分配案例分析，相关客流数据由铁路总公司列车运行图编制研发培训中心调查所得。为简化案例，将该线路上流量过小的站点客流归并至相邻三等站以上站点，共计10个客流节点。
线路车站的编号为1~10，依次为成都、德阳、绵阳、江油、广元、阳平关、略阳、徽县、凤县、宝鸡。宝成线上共有3个列车始发终到车站，分别是成都、广元、宝鸡。跨线列车起讫点包括北京、拉萨、佳木斯、乌鲁木齐、西宁、西安、昆明、郑州、兰州、上海、沈阳、扬州、福州、天津、青岛、巴中、呼和浩特、太原等。开行方案包含32对本线及跨线旅客列车，其中，城际快速列车8对/d，特快列车2对/d，快速列车19对/d，普速列车3对/d，具体开行方案如表2所示。开行旅客列车具体参数诸如票价、运行时间、出发时间、列车定员均可由12 306铁路客票系统查询。
表2 宝成线列车开行方案
Table 2 Line plan of Baoji-Chengdu railway
根据2.2节类别划分方法，采用AP聚类法对旅客进行类别划分。AP算法进行样本聚类时会输出多种聚类结果，这些结果具有不同的聚类数，故需对其进行有效性评价。聚类有效性评价是采用相关指标来确定聚类算法产生的哪个聚类结果为最优，其对应的聚类数目即为最佳聚类数。常用的最佳聚类有效性指标为：Calinski-Harabasz指标、Hartigan指标和In-Group Proportion指标等，其计算方法见文献[13]。
对AP算法获得的聚类结果，分别运用上述3种指标进行计算，结果如表3所示。由表3可知：CH指标、Hart指标以及IGP指标得到的最佳聚类数均为6。根据问卷统计结果，不同类别旅客对乘车费用指标各因素的主观权重以及平均时间价值如表4所示。
运用Matlab软件，运用4.2节流量加载算法进行列车服务网络流量分配，得到列车在各个运行区段上座率如表5所示，运算共耗时25.7 s。
从表4可以发现：根据基于旅客类别的列车服务网络配流得到的列车上座率的准确率较高，均在80%以上。根据表5配流结果，可以对列车开行方案进行调整，对于上座率较低列车，可采用调整列车停站方案的策略；对于上座率过高列车，可在该车发车时间域内加开追踪列车，从而对列车服务网络进行综合优化。例如，对于C6302，C6304，C630和C6308，由于其出发时间域处于8:30—12:30，旅客方便系数高，故旅客集中选择这几趟列车，因而可采取加开相同运行区段的城际列车用以分摊客流；而6064列车的上座率不理想，建议取消，同时增加1486在徽县与凤县的停靠站点，以输送原6064列车的客流。
表3 不同聚类数的有效性指标值
Table 3 Validity index of different clusters
表4 不同类别旅客的乘车选择参数
Table 4 Boarding choice parameters of different travelers
表5 列车客流分配结果
Table 5 Result of train flow assignment
5 结论
1) 在既定旅客列车开行方案所形成的服务网络上，对客流分配进行了研究。以年龄、性别、月收入等主体特性为属性参数，采用近邻传播算法对铁路旅客进行聚类分析，通过CH，Hart以及IGP指标确定其最佳聚类数。在此基础上，提出了基于不同类别旅客的网络阻抗值计算方法，构建体现不同层次需求的客流分配模型，并对备选乘车方案以及客流加载规则进行设计。
2) 以2014年宝成线为实例进行客流分配验算，结果显示算法能在较短时间内获得结果，且各列车配流上座率的准确率均在80%以上。
3) 本文提出的客流分配理论方法为铁路客运管理部门根据旅客出行需求，对列车开行方案进行适应性调整提供理论依据。
参考文献：
[1] GOOSSENS W. Models and algorithms for railway line planning problems[D]. Maastricht, Netherlands: University of Maastricht, 2004: 1-46.
[2] GOOSSENS W, HOESEL S, KROON L. On solving multi-type railway line planning problems[J]. European Journal of Operational Research, 2006, 168(2): 403-424.
[3] 何宇强, 张好智, 毛保华, 等. 客运专线旅客列车开行方案的多目标双层规划模型[J]. 铁道学报, 2006, 28(5): 6-10.
HE Yuqiang, ZHANG Haozhi, MAO Baohua, et al. Multi objective Bi-level programming model of making train working plan for passenger-only line[J]. Journal of the China Railway Society, 2006, 28(5): 6-10.
[4] 曾凯鸣, 黄鉴, 彭其渊. 客运专线旅客列车开行方案的客流分配方法[J]. 西南交通大学学报, 2006, 41(5): 571-574.
ZENG Kaiming, HUANG Jian, PENG Qiyuan. Research on assignment of passenger train plan for dedicated passenger traffic lines[J]. Journal of Southwest Jiaotong University, 2006, 41(5): 571-574.
[5] 聂磊, 胡小风, 佟璐, 等. 基于旅客列车开行方案的客流分配方法研究[J]. 交通运输系统工程与信息, 2011, 11(3): 87-92.
NIE Lei, HU Xiaofeng, TONG Lu, et al. Research of passenger flow assignment based on passenger train plan[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(3): 87-92.
[6] 佟璐, 聂磊, 付慧伶. 基于复杂列车服务网络的客流分配方法研究[J]. 铁道学报, 2012, 34(10): 7-15.
TONG Lu, NIE Lei, FU Huiling. Research on passenger flow assignment method based on complex train service network[J]. Journal of the China Railway Society, 2012, 34(10): 7-15.
[7] 胡小风. 混合铁路客运服务网中多层次客流分配技术研究[D]. 北京: 北京交通大学交通运输学院, 2012: 28-34.
HU Xiaofeng. Research on technologies of mutli-level passenger flow assignment in the mixed-train service network[D]. Beijing: Beijing Jiaotong University, 2012: 28-34.
[8] 柳健. 高速铁路多层次客流分配方法及系统设计[D]. 北京: 北京交通大学交通运输学院, 2013: 28-32.
LIU Jian. Multilevel passenger flow assignment method in high speed railways and the computer system design[D]. Beijing: Beijing Jiaotong University, 2013: 28-32.
[9] 何晓群. 现代统计分析方法与应用[M]. 北京: 中国人民大学出版社, 1999: 215-216.
HE Xiaoqun. Modern statistical methods and applications[M]. Beijing: Chinese People University Press, 1999: 215-216.
[10] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.
[11] 史峰, 邓连波, 霍亮. 铁路旅客乘车选择行为及其效用[J]. 中国铁道科学, 2007, 28(6): 117-121.
SHI Feng, DENG Lianbo, HUO Liang. Boarding choice behavior and its utility of railway passengers[J]. China Railway Science, 2007, 28(6): 117-121.
[12] 杨信丰, 刘兰芬, 李引珍, 等. 多目标铁路旅客乘车方案优化模型及算法研究[J]. 交通运输系统工程与信息, 2013, 13(5): 72-78.
YANG Xinfeng, LIU Lanfen, LI Yinzhen, et al. Route selection for railway passengers: a multi-objective model and optimization algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(5): 72-78.
[13] 周世兵, 徐振源, 唐旭清. 基于近邻传播算法的最佳聚类数确定方法比较研究[J]. 计算机科学, 2011, 38(2): 225-228.
ZHOU Shibing, XU Zhenyuan, TANG Xuqing. Comparative study on method for determining optimal number of clusters based on affinity propagation clustering[J]. Computer Science, 2011, 38(2): 225-228.
(编辑 陈爱华)
收稿日期：2016-09-30；修回日期：2016-12-02
基金项目(Foundation item)：国家自然科学基金资助项目(61273242，61403317，71403225); 中国铁路总公司科技研究计划项目(2014X004-D，2015X008-B)(Projects(61273242, 61403317, 71403225) supported by the National Natural Science Foundation of China; Projects(2014X004-D, 2015X008-B) supported by Science and Technology Plan of China Railway Corporation)
通信作者：王文宪，博士，从事交通运输规划与管理研究；E-mail：wwx530@163.com
摘要：针对列车服务网络客流分配模型复杂、求解困难的特点，采用旅客类别划分的简化策略，以旅客主体特性为分析参数，运用近邻传播算法对其进行聚类。在此基础上，构造列车开行方案形成的服务网络，提出不同类别旅客乘车方案弧段阻抗的计算方法，建立基于类别划分的旅客乘车方案概率选择模型，并设计相应的网络流量加载算法。以宝成线为实例，根据客流调查结果，进行旅客类别聚类划分与流量加载验证。研究结果表明：将铁路出行旅客划分为6个类别时，具有最好的聚类效果；在此基础上客流分配准确率在80%以上。基于旅客类别划分的流量分配方法能够得到准确的流量分配结果，从而为列车开行方案的调整提供合理依据。
[3] 何宇强, 张好智, 毛保华, 等. 客运专线旅客列车开行方案的多目标双层规划模型[J]. 铁道学报, 2006, 28(5): 6-10.
[4] 曾凯鸣, 黄鉴, 彭其渊. 客运专线旅客列车开行方案的客流分配方法[J]. 西南交通大学学报, 2006, 41(5): 571-574.
[5] 聂磊, 胡小风, 佟璐, 等. 基于旅客列车开行方案的客流分配方法研究[J]. 交通运输系统工程与信息, 2011, 11(3): 87-92.
[6] 佟璐, 聂磊, 付慧伶. 基于复杂列车服务网络的客流分配方法研究[J]. 铁道学报, 2012, 34(10): 7-15.
[7] 胡小风. 混合铁路客运服务网中多层次客流分配技术研究[D]. 北京: 北京交通大学交通运输学院, 2012: 28-34.
[8] 柳健. 高速铁路多层次客流分配方法及系统设计[D]. 北京: 北京交通大学交通运输学院, 2013: 28-32.
[9] 何晓群. 现代统计分析方法与应用[M]. 北京: 中国人民大学出版社, 1999: 215-216.
[11] 史峰, 邓连波, 霍亮. 铁路旅客乘车选择行为及其效用[J]. 中国铁道科学, 2007, 28(6): 117-121.
[12] 杨信丰, 刘兰芬, 李引珍, 等. 多目标铁路旅客乘车方案优化模型及算法研究[J]. 交通运输系统工程与信息, 2013, 13(5): 72-78.
[13] 周世兵, 徐振源, 唐旭清. 基于近邻传播算法的最佳聚类数确定方法比较研究[J]. 计算机科学, 2011, 38(2): 225-228.
