基于改进遗传算法的旅客列车席位分配组合优化

刘华森，程文明，张铭奎

(西南交通大学 机械工程学院，四川 成都　610031)

铁路车票票额的分配是根据预测的客流、历史的经验以及限售条件等因素，为各车站分配所停靠旅客列车的车票票额并对各种指标进行计算。分配给各车站的车票票额会影响到旅客在各车站购票的公平性以及旅客出行的方便性。同时，车票票额的分配也直接影响到铁路客运收入的高低。由于旅客通过各个车站出行的需求是随机的和实时变化的，从而使得车票票额的分配变得更为复杂。铁路部门采取票额共用、席位共用以及票额预分等销售策略强化旅客列车的营销和提高客运收入水平。为了提高旅客列车的收入和客座利用率(客座利用率=旅客周转量/客座公里总数)，席位拼接以及席位控制等方法逐步成为铁路运营管理的热点研究内容。

国内外众多的学者对票额的分配优化进行了大量的研究，并在收益管理、阶梯票价、随机需求、长途客流保护等领域取得了重要的研究成果。使铁路客票收入最大化，是铁路运输企业关心的重要课题。Hetrakul等[1]将旅客潜在的选择模型和需求函数纳入1个收入优化问题，共同考虑定价和席位分配；研究发现在相同的容量情况下将短途旅客的需求纳入收入管理中会获得更多的收入。Peng-Sheng[2]研究阶梯票价对席位分配的影响，通过将票价分为全票价段和折扣票价段2个阶段并用约束的非线性整数规划模型，解决席位分配的问题。Crevier等[3]提出1种涵盖定价和网络运行规划的双层数学模型，并采用基于混合整数规划的思路求解旅客列车的收入。

从保障旅客购票的票源以及购票机会均等性等角度出发，基于客流预测的票额分配方法也得到了广泛的研究。文献[4]以时间序列分析方法建立客流预测模型，以旅客列车全程的客座利用率、收入以及整体效益最大化为目标，构建铁路车票票额智能预分系统。包云等[5-7]将单列车的客运需求划分为具有趋势规律的确定需求和具有分布规律的随机需求两部分，进而构成单列车的客流量预测模型并嵌入随机票额分配模型中，实现随机需求与随机票额分配有效结合的单列车票额分配。

在列车席位的分配与安排上，短途客流需求与长途客流保护是一个矛盾的统一体。王洪业等[8]综合考虑票额裂解因素、票额保护因素和客流培养因素，建立站间票额数量调配模型，以站间的票额分配数裂解票额时所使用的长途票额最少为目标函数，建立了席位占用优化模型。史峰等[9]提出以旅客出行费用和票额分配计划的人公里数2项指标组成的评价方法，设计基于票额分配计划的换乘网络。文献[10]提出了拼接策略启动时机的建议方案，利用余票信息设计了拼接票搜索流程，将拼接票的存在性与售票环节相分离。Sumalee等[11]提出了1种动态席位分配模型，研究不同类型的旅客在车站等待的概率对旅客出行方式和出发时间的影响。Clausen等[12]将二维背包问题用于列车席位的分配，分别讨论了当列车席位一定时如何满足尽量多的旅客乘车需求，以及在乘车需求一定时如何用尽量少的列车完成运输任务。Boyar等[13]讨论了在允许旅客交换席位的情况下，以旅客移动位置最少为目标安排旅客的席位。

以上的文献从宏观的客票收入、客流预测以及席位的具体分配等三方面研究铁路车票的分配问题。但这些研究仍存在列车座位虚糜、客座利用率不高等问题。因此，本文以列车的席位分配为切入点，根据实际的售票情况提出改进的遗传算法，用于迭代求解和优化车票的分配方案，使得旅客列车的客座利用率最大。优化的结果不仅是得到为各个车站分配的票额，而且也同时完成了对应各种出行需求的席位分配与组合优化，实现旅客列车席位资源的有效利用。

1　席位的数学模型

根据旅客列车停靠多站的实际情况，以列车上的席位与对应的车票为研究对象，讨论分配给各个车站的票额。

1.1　车票总数

假设某列车的席位以及沿途停靠的车站如图1所示。图中，S1为列车的始发站，SN为列车的终点站；N为该列车停靠车站的数目，且N≥2；该列车中途停靠车站的次序为S2,S3,…,SN-1；A和B分别为席位号；1和0分别表示席位在行车区间被占用和未被占用的2种状态。

以该列车的某个具体席位为研究对象，当列车的停站数目为N时针对该席位最多可发售的车票总数目TN为

(1)

1.2　席位的状态

如图1(a)所示，因为席位A在行车区间S1→S2的车票已经售出，即席位A在该区间处于被占用状态，故记为1；而在行车区间S2→S3，因为席位A的车票没有售出，即席位A在行车区间S2→S3没有被占用，则记为0。每个席位对于任一行车区间均只有0或1(未占用或者已经占用)2种状态。当旅客列车停靠N个车站时，则共有N-1个行车区间，故某个席位的状态在整个行车区间中可能出现2N-1次变化。

图1　列车席位及站点示意图

1.3　车票组合

在席位的占用中，会出现席位被若干个短途区间车票组合占用的情况。例如，席位B被组合占用的2种情况如图1(b)所示。情况1，席位B在S1→S2区间未被占用而在S2→S3和S3→S4区间分别被2张短途车票占用，可记为011；情况2，席位B在S1→S2区间未被占用而在S2→S4被1张长途车票占用，同样可记为011。同理，110代表席位B也有2种组合占用情况，111代表席位B则可能有4种组合占用的情况，再加上000, 001, 010, 100和101所代表的席位占用情况，故经停4个车站的席位B共有13种组合占用情况。由占用席位的短途车票所经过的短途区间可以拼接成该席位在多个相邻短途区间被占用的长途区间，长途区间也可以裂解为若干个相邻的短途区间，因此席位对应的车票组合比席位的占用更复杂。

本文采用递推法计算某席位的车票组合数目，如图2所示。设有N-1个停车站时，某席位的车票组合数目为ZN-1，用图2中的第1行表示ZN-1中所有可能的车票组合，其中×表示非0即1。当增加1个停车站使得总停车站的数目为N时，记该席位上的车票组合数目为ZN。若在SN-1→SN区间该席位的占用状态为0，则该席位上的车票组合数目仍为ZN-1；若在SN-1→SN区间该席位的占用状态为1，则由于可能出现短途区间与长途区间的转换，故需要分以下情况讨论该席位的车票组合数目。

图2　递推求解示意图

情况1：如果在第N-1区间该席位的占用状态恰好为0，则该席位的车票组合如第2行所示。情况2：如果在第N-1区间该席位的占用状态恰好为1，则需要进一步讨论在第N-2区间该席位的占用状态。依次类推直到图2中的最后一行所表示的车票组合。按照这种递推方法，图2恰好被1条取值为0的右斜对角线分成2个部分：左上角部分为列车停靠的车站数量从2个车站到前N-1个车站时的车票组合数目Z2，Z3，…,ZN-1；右下角部分为取值1的席位连续占用情况。以图2中第3行最后2位为例，2个连续取值1表示该席位在SN-2→SN-1和SN-1→SN这2个区间连续被占用。与前面的分析类似，也有可能出现2种情况，即被2个短途区间车票占用和或被1个长途区间车票占用，故自动形成1个系数21；其他情况依此类推，图2中右侧的系数则是根据右下角为1的矩阵推算而来的。

根据以上分析可得

ZN=ZN-1+20ZN-2+21ZN-3+…+2N-3+2N-2

(2)

同理可得

ZN-1=ZN-2+20ZN-3+…+2N-4+2N-3

(3)

将式(3)代入式(2)中，可得

ZN=3ZN-1-ZN-2

(4)

式(4)属于线性常系数齐次递推关系，其特征方程为

x2-3x+1=0

(5)

(6)

ZN随着列车停站数目的增加而成指数倍增长。由于旅客列车特别是长途旅客列车停靠的车站数量一般较多，当停靠的车站数目增加到一定程度时，按照传统的方法已经很难为各个车站分配较为合理的票额，而对席位的安排则更困难。列车某席位的席位状态、可发售的车票总数以及车票组合数目随着停车站的增加而变化的情况见表1。

表1　列车某席位3个参数随停车站数目的变化

2　席位预分策略

2.1　改进遗传算法与车票组合

遗传算法是解决搜索问题的一种通用算法，其共同特征为：首先从初始种群中随机选择1组候选解，依据某些适应性条件测算这些候选解的适应度，根据适应度保留某些候选解，放弃其他候选解。对保留候选解进行交叉操作，生成新的候选解。新的一代将重复他们父母所进行的繁衍过程，一代又一代演化下去，直到达到期望的解为止。

在传统遗传算法中，遗传个体以一定的概率变异，父代的交叉点也具有一定的随机性。这是因为传统遗传算法中原始变量的取值范围一般为连续区间，遗传变异以及随机交叉产生的新个体始终都在这个范围内，而且同时还会加快产生新个体的速度，从而尽快收敛到目标函数值。但传统遗传算法在有整数约束的组合优化算法中却有一些缺点，比如变异新个体以及随机交叉产生的新个体很可能是无意义的个体，而且会改变组合优化的原始乘车区间车票需求数目。因此，结合铁路车票票额的实际情况，本文对传统的遗传算法进行改进，使得在车票组合优化算法中始终保持对原始乘车区间车票的需求不变。

2.2　车票编码与组合

设某旅客列车停靠车站的集合S={Si|i=1,2,…，N}；从停车站Si到其他各停车站Sj(j=2,3,…，N；j>i)的预测客流对应的车票的需求为Pij。图3是以列车上某个具体席位对应不同车票需求的车票编码示意图。为了保证原始乘车区间车票的需求(原始基因组)在运算过程中不改变，改进后的车票编码分为行车区间编码以及判别符号编码两部分。如1.2节所定义，对于某席位的状态在任何1个区间都只有0或1(未占用或者已近占用)2种情况，以此作为车票编码中的行车区间编码。判别符号编码是在各个区间位置增加符号判别位，“*”代表此位置可以进行交叉运算，“#”代表此位置不可以进行交叉运算。例如图3中第1行代表所有的行车区间均被占满，是一张全程的长途车票，并且行车区间内不可以进行交叉运算；图3中最后一行代表最后一个行车区间被占用，是一张SN-1→SN的短途车票，所有的行车区间可以进行交叉运算。通过此种编码方法，可以将所有客流对应的车票需求进行唯一编码。

图3　某席位对应不同车票需求的车票编码示意图

加入判别符号位后，可对某席位车票的组合情况进行区分。对于由交叉产生的新子代，在对应的交叉点用“&”标记，代表2个父代在此点的连接处可以再次进行交叉计算。以2个8车站的编码交叉为例，若F1和F2为父代，且F1表示S2→S5站的短途车票需求，F2表示S5→S7站的短途车票需求，对应的车票编码分别为

F1=* 0 * 1 # 1 # 1 * 0 * 0 * 0

F2=* 0 * 0 * 0 * 0 * 1 # 1 * 0

本文发展的TOPSIS算法与现有的R-IGTA算法相比，在优化目标和对模块划分方案的后处理方面存在明显的先进性。

根据编码与交叉的规则，父代F1和F2可以在S5进行交叉运算。得到子代f1和f2为

f1=* 0 * 1 # 1 # 1 & 1 # 1 * 0

f2=* 0 * 0 * 0 * 0 & 0 * 0 * 0

子代f1是由父代F1和F2在S5站交叉得到，故f1在S5站的判别符号记为&。当新个体f1作为父代进行下一次交叉运算时，可以一定的概率在S5站解散开，从而保证最大限度的交叉组合。子代f2由于不再包含任何有意义的乘车区间，所以子代f2将被淘汰。在以上定义的车票编码以及组合交叉运算过程中，原始的乘车区间车票需求始终被完整的保留和继承到了下一代个体中，并且没有产生多余的乘车区间车票需求。这是车票组合优化算法的重要前提和保障。

2.3　空间多背包问题与车票组合

多背包问题(Multiple Knapsack Problem, MKP)[14-15]是指从1个物品集合中选出1个物品子集分别装入M个背包中, 在不超出每个包限制容量的条件下, 使选出的全部物品的总价值最大。传统的多背包问题只考虑物体的体积，并没有考虑物体所处的空间位置，而车票的组合问题是一个更为复杂的多背包问题，同样的乘坐区间数由于起始车站的不同而形成不同的车票需求。

对于属多背包问题且有空间位置的车票组合问题，对应其收入和客座利用率的多目标函数为

(7)

s.t

(8)

(9)

(10)

式(8)—式(10)分别为空间位置约束、列车定员约束、票额的上下限约束。

2.4　席位预分策略

每位旅客对其乘车区间的车票需求(原始基因组)具有空间性，这使得车票组合问题更为复杂。同时，为了保持在运算过程中原始乘车区间车票的需求不减少也不增加，本文采用改进的遗传组合算法求解这种多维多背包的车票组合优化问题。图4是列车席位预分的车票组合优化算法流程。

Step1：车票编码。以0与1表示席位在某个行车区间是否被占用；同时加入符号判别位，对遗传交叉点的组合情况进行区分。

Step2：父代选择。父代个体由随机选取产生，即在车票种类范围内智能产生，并且父代所包含的基因组数目为一定值。

Step3：裂解。根据列车席位预分的特点，改进裂解的定义为：处于连接状态的组合，以一定的概率拆散原始组合以便生成新的个体，从而寻找最优解。2个交叉的父代根据适应度大小分成父体和母体。适应度较小的父体在交叉过程中首先分解为独立的原始乘车区间车票需求。适应度按列车客座利用率和客票收入计算。

Step4：吸收交叉。基因组具有空间位置，必须按顺序进行对应点的交叉组合。为了保证每次交叉都朝着结果更优的方向前进，采用适应度较大的母体和在交叉过程中吸收接纳父体独立基因组的方式实现交叉。不能成功吸收接纳的基因组则独立成为子代，等待下一次的遗传交叉。

Step5：选择与排序。按适应度大小筛选最优的车票组合，未被选取的客流需求也放入子代内等待下一次的组合配对。

Step6：优化准则判断。对于完成1次循环交叉的子代，按照适应度大小进行排序，判断交叉得到的子代是否满足优化准则条件。不满足条件时则再次进入下一次吸收交叉循环，满足条件达到优化的要求时则停止计算。

图4　组合优化算法流程

3　算例分析

以1条包含8个客运站(S1，S2，…，S8)的运输线路为例进行算例分析。旅客的车票需求以及相关的约束见表2所示的矩阵[6]。该矩阵包含各客流对应的车票需求值、最低票额保障值以及相应票价。如该矩阵第1行第2列中的数值(80,10,40)表示从S1站到S2站的车票需求为80张，最低票额保障为10张，对应的车票价格为40元·张-1。

表2　车票需求、最低票额保障值和票价矩阵

采用Matlab编程求解，遗传种群的规模随着遗传迭代次数变化的情况如图5所示。初始种群包含的基因组个数(乘车区间车票需求)约为2 000，优化迭代结束后种群包含的基因组个数约为1 400。由于本文对遗传算法进行了改进，因此由2.4节中的第2步以及第3步可保证在种群规模减小的过程中遗传交叉不会变异产生新的基因组；同时通过吸收交叉的方式也能保证原有的初始基因组不会减少。由于在迭代运算的初期存在大量的短途车票需求，故在迭代的开始阶段，短途车票会迅速组合交叉而拼接为长途席位，使得进入下一步迭代的父代数量急剧减少，而父代所包含的原始车票需求却不变。在迭代的后期，因为短途车票逐步拼接为长途席位，交叉产生新子代的概率逐步降低，所以种群的规模随着遗传迭代次数变化的曲线逐步收敛平缓。

图5　遗传种群规模随迭代次数的变化

列车定员分别按600和1 200人情况下列车的客座利用率以及客票总收入如图6所示。由图6可知，与图5类似，在迭代初期客座利用率以及客票总收入均迅速增加；而在迭代的后期，这2项指标却逐步收敛。当列车定员为1 200人时，由于列车的席位数增加，使得列车的客票收入也相应增加，但是客票总收入低于列车定员为600人时的2倍。客座利用率也低于列车定员为600人时的。依本文例，定员为600人的列车，其最大收入为26.718 5万元，客座利用率为92.57%；定员为1 200人的列车，其最大收入为47.057 0万元，客座利用率为82.04%。客座利用率以及客票总收入2项指标可以为是否增开或重联旅客列车提供参考依据。

图6　客票总收入和客座利用率随迭代次数的变化

迭代结束后种群中基因组包含的乘车区间数以及其对应的客票收入情况如图7所示。由图7可知，种群中基因组个数(乘车区间数)对应的客票收入也成阶梯状排列。在同样的乘车区间数下客票的收入有略微的波动，这是因为不同乘车区间组合对应的原始票价有所差别所致。

图7迭代后种群中基因组包含的客票总收入以及乘车区间数

优化后按照列车定员600人和列车定员1 200人时的车票票额分配方案见表3。表3中，分子表示列车定员为600人时的票额分配方案；分母表示列车定员为1 200人时的票额分配方案。

表3　各车站最终车票分配方案　张

4　结　语

本文根据铁路客流的特点，对遗传算法进行改进，在车票编码中增加判别符号，同时对遗传的交叉点位置进行重新定义，从而保证在遗传运算中原始的乘车区间车票需求不会发生改变。在此基础上，以列车的客票收入和客座利用率最大为优化目标，迭代逆向求解属于多维多背包问题的各车站车票分配数额的优化方案。采用本文方法得到不同列车定员情况下的列车客座利用率以及客票总收入，而且当列车定员为600人时，列车的客座利用率可达92%以上，有效改善了列车座位虚弥问题，使得列车的客座利用率以及客票总收入都得到增加，验证了本文方法的有效性。另外，优化后的结果还直接反映出各个原始乘车区间车票需求的组合情况，有利于售票时席位的安排与各站车票票额分配，可为增开列车或列车重联提供决策依据。

[1]HETRAKUL P, CIRILLO C. A Latent Class Choice Based Model System for Railway Optimal Pricing and Seat Allocation[J]. Transportation Research Part E: Logistics and Transportation Review，2014, 61: 68-83.

[2]YOU P. An Efficient Computational Approach for Railway Booking Problems[J]. European Journal of Operational Research, 2008, 185(2): 811-824.

[3]CREVIER B, CORDEAU J, SAVARD G. Integrated Operations Planning and Revenue Management for Rail Freight Transportation[J]. Transportation Research Part B: Methodological， 2012, 46(1): 100-119.

[4]单杏花，周亮瑾，吕晓艳，等. 铁路旅客列车票额智能预分研究[J]. 中国铁道科学， 2011, 32(6): 125-128.

(SHAN Xinghua，ZHOU Liangjin，LÜ Xiaoyan，et al. Research on Intelligent Pre-Assignment of Ticket Allotment for Railway Passenger Train[J]. China Railway Science, 2011, 32(6): 125-128.in Chinese)

[5]BAO Y, LIU J, MA M, et al. Seat Inventory Control Methods for Chinese Passenger Railways[J]. Journal of Central South University, 2014, 21(4): 1672-1682.

[6]包云，刘军，马敏书，等. 高速铁路嵌套式票额分配方法研究[J]. 铁道学报，2014,36(8): 1-6.

(BAO Yun，LIU Jun，MA Minshu，et al. Nested Seat Inventory Control Approach for High-Speed Train[J]. Journal of the China Railway Society，2014,36(8): 1-6. in Chinese)

[7]包云，刘军，刘江川，等. 基于随机需求的单列车票额分配方法[J]. 中国铁道科学，2015, 36(2): 96-102.

(BAO Yun，LIU Jun，LIU Jiangchuan，et al. Seat Allotment Method for Single Train Based on Stochastic Demand[J]. China Railway Science, 2015, 36(2): 96-102. in Chinese)

[8]王洪业，吕晓艳，周亮瑾，等. 基于客流预测的铁路旅客列车票额智能分配方法[J]. 中国铁道科学，2013,34(3): 128-132.

(WANG Hongye，LÜ Xiaoyan，ZHOU Liangjin，et al. Intelligent Seat Allotment Method for Railway Passenger Train Based on Passenger Flow Forecast[J]. China Railway Science，2013,34(3): 128-132. in Chinese)

[9]史峰，陈彦，周文梁，等. 基于用户平衡分析的铁路旅客列车票额分配计划制定及评价方法[J]. 中国铁道科学，2008, 29(6): 98-103.

(SHI Feng，CHEN Yan，ZHOU Wenliang，et al. Railway Passenger Train Seats Allotment Plan Establishment and Evaluation Method Based on User Equilibrium Analysis[J]. China Railway Science，2008, 29(6): 98-103. in Chinese)

[10]史峰，周俊，陈东方，等. 同一列车不同席位分段拼接售票策略[J]. 铁道科学与工程学报，2013, 10(5): 71-77.

(SHI Feng，ZHOU Jun，CHEN Dongfang，et al. A Ticketing Strategy of Segmented Stitching Seats in the Same Train[J]. Journal of Railway Science and Engineering，2013, 10(5): 71-77. in Chinese)

[11]SUMALEE A, TAN Z, LAM W H K. Dynamic Stochastic Transit Assignment with Explicit Seat Allocation Model[J]. Transportation Research Part B: Methodological，2009, 43(8/9): 895-912.

[12]CLAUSEN T, HJORTH A N, NIELSEN M, et al. The Off-Line Group Seat Reservation Problem[J]. European Journal of Operational Research，2010, 207(3): 1244-1253.

[13]BOYAR J, KRARUP S, NIELSEN M N. Seat Reservation Allowing Seat Changes[J]. Journal of Algorithms，2004, 52(2): 169-192.

[14]GOKCE E I, WILHELM W E. Valid Inequalities for the Multi-Dimensional Multiple-Choice 0-1 Knapsack Problem[J]. Discrete Optimization，2015, 17(3): 25-54.

[15]马丰宁，谢龙，郑重. 求解背包问题的基因属性保留遗传算法[J]. 天津大学学报，2010, 43(11): 1020-1024.

(MA Fengning，XIE Long，ZHENG Zhong. Attribute Gene-Reserved Genetic Algorithm for Solving Knapsack Problem[J]. Journal of Tianjin University，2010, 43(11): 1020-1024. in Chinese)