基于客流需求的列车时刻表和车底调度协同优化

第３３卷第２期２０２０年４月出版

Ｖｏｌ.３３Ｎｏ.２Ａｐｒ.２０２０

ＳＨＡＮＤＯＮＧＳＣＩＥＮＣＥ

ＤＯＩ:１０.３９７６/ｊ.ｉｓｓｎ.１００２￣４０２６.２０２０.０２.０１０

【交通运输】基于客流需求的列车时刻表和车底调度协同优化

林禹童ꎬ曹成铉∗ꎬ柳雨彤ꎬ冯紫嫣

(北京交通大学轨道交通控制与安全国家重点实验室ꎬ北京１０００４４)

摘要:随着城市规模的扩大ꎬ对城市轨道交通的需求日渐增长ꎬ对城市轨道交通的运营服务质量提出了较高要求ꎮ根据乘客需求ꎬ以最小乘客总等待时间和城市轨道交通系统运营成本为综合目标ꎬ建立混合整数规划模型ꎮ通过模拟退火算法ꎬ设计给出了某一线路的列车时刻表和车底调度方案ꎬ并通过算例分析验证其可行性ꎮ结果表明ꎬ该模型可以根据乘客需求设计出一个合适的列车时刻表和车底调度协同优化方案ꎮ

关键词:城市轨道交通ꎻ列车时刻表ꎻ车底调度ꎻ模拟退火算法ꎻ混合整数规划ꎻ乘客总等待时间ꎻ运营成本中图分类号:Ｕ２３９.５　　　文献标志码:Ａ　　　文章编号:１００２￣４０２６(２０２０)０２￣００６３￣０８开放科学(资源服务)标识码(ＯＳＩＤ):

Ｃｏｌｌａｂｏｒａｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｏｆｔｒａｉｎｔｉｍｅｔａｂｌｉｎｇａｎｄｒｏｌｌｉｎｇｓｔｏｃｋｂａｓｅｄ

ｏｎｐａｓｓｅｎｇｅｒｄｅｍａｎｄ

(ＳｔａｔｅＫｅｙＬａｂｏｆＲａｉｌＴｒａｆｆｉｃＣｏｎｔｒｏｌａｎｄＳａｆｅｔｙꎬＢｅｉｊｉｎｇＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙꎬＢｅｉｊｉｎｇ１０００４４ꎬＣｈｉｎａ)

ＬＩＮＹｕ￣ｔｏｎｇꎬＣＡＯＣｈｅｎｇ￣ｘｕａｎ∗ꎬＬＩＵＹｕ￣ｔｏｎｇꎬＦＥＮＧＺｉ￣ｙａｎ

Ａｂｓｔｒａｃｔ∶Ｔｈｅｄｅｍａｎｄｆｏｒｕｒｂａｎｒａｉｌｗａｙｓｉｓｉｎｃｒｅａｓｉｎｇｗｉｔｈｔｈｅｅｘｐａｎｓｉｏｎｏｆｔｈｅｓｃａｌｅｏｆｕｒｂａｎｒａｉｌｔｒａｎｓｉｔꎬｒｅｓｕｌｔｉｎｇｉｎａｈｉｇｈｒｅｑｕｉｒｅｍｅｎｔｗｉｔｈｒｅｓｐｅｃｔｔｏｔｈｅｏｐｅｒａｔｉｏｎｑｕａｌｉｔｙｏｆｕｒｂａｎｒａｉｌｔｒａｎｓｉｔｓｅｒｖｉｃｅｓ.Ｇｉｖｅｎｔｈｅｄｅｍａｎｄｏｆｐａｓｓｅｎｇｅｒｓꎬｔｈｉｓｓｔｕｄｙｅｓｔａｂｌｉｓｈｅｓａｍｉｘｅｄｉｎｔｅｇｅｒｍｏｄｅｌｔｏｍｉｎｉｍｉｚｅｔｈｅｔｏｔａｌｐａｓｓｅｎｇｅｒｗａｉｔｉｎｇｔｉｍｅａｎｄｏｐｅｒａｔｉｏｎａｌｃｏｓｔｏｆｔｈｅｕｒｂａｎｒａｉｌｓｙｓｔｅｍ.Ａｎａｎｎｅａｌｉｎｇａｌｇｏｒｉｔｈｍｉｓｓｉｍｕｌａｔｅｄｔｏｄｅｓｉｇｎｔｈｅｔｒａｉｎｔｉｍｅｔａｂｌｅａｎｄｒｏｌｌｉｎｇｓｔｏｃｋｓｃｈｅｄｕｌｅｆｏｒａｃｅｒｔａｉｎｒｏｕｔｅꎬａｎｄｃａｌｃｕｌａｔｉｏｎｓａｎｄｅｘａｍｐｌｅｓａｒｅｕｓｅｄｔｏａｎａｌｙｚｅｔｈｅｉｒｆｅａｓｉｂｉｌｉｔｙ.Ｔｈｅｒｅｓｕｌｔｓｄｅｎｏｔｅｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｍｏｄｅｌｃａｎｂｅｕｓｅｄｔｏｄｅｓｉｇｎａｐｒｏｐｅｒｔｒａｉｎｔｉｍｅｔａｂｌｉｎｇａｎｄｒｏｌｌｉｎｇｓｔｏｃｋｓｃｈｅｄｕｌｉｎｇｐｌａｎｂａｓｅｄｏｎｔｈｅｐａｓｓｅｎｇｅｒｄｅｍａｎｄ.

Ｋｅｙｗｏｒｄｓ∶ｕｒｂａｎｒａｉｌｔｒａｎｓｉｔꎻｔｒａｉｎｔｉｍｅｔａｂｌｉｎｇꎻｒｏｌｌｉｎｇｓｔｏｃｋｓｃｈｅｄｕｌｉｎｇꎻｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｌｇｏｒｉｔｈｍꎻｍｉｘｅｄｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇꎻｔｏｔａｌｐａｓｓｅｎｇｅｒｗａｉｔｉｎｇｔｉｍｅꎻｃｏｓｔｏｆｕｒｂａｎｒａｉｌｓｙｓｔｅｍ

　　城市轨道交通为市民提供了便利的出行方式ꎬ具有运行速度稳定、运输量大的特点ꎮ随着交通需求量的

增加ꎬ城市轨道交通也面临着较大的运营压力ꎮ因此ꎬ设计一个与客流需求相匹配的列车时刻表和车底调度

收稿日期:２０１９￣０９￣１７

基金项目:轨道交通控制与安全国家重点实验室(北京交通大学)自主研究课题(ＲＣＳ２０１９ＺＴ００３)作者简介:林禹童(１９９３—)ꎬ男ꎬ硕士研究生ꎬ研究方向为城市轨道交通ꎮＥ￣ｍａｉｌ:１７１２０７５１＠ｂｊｔｕ.ｃｏｍ∗通信作者ꎬ曹成铉(１９６３—)ꎬ男ꎬ博士ꎬ研究方向为轨道交通ꎮＴｅｌ:１３１６７３１８３５６ꎬＥ￣ｍａｉｌ:ｃｘｃａｏ＠ｂｊｔｕ.ｃｏｍ.ｃｎ

６４山　东　科　学２０２０年

计划ꎬ对提高城市轨道交通的服务质量具有重要的现实意义ꎮ

在城市轨道交通列车调度问题的相关领域ꎬ国内外学者已经取得了很多研究成果ꎬ这些成果多以列车时刻表和客流需求匹配为目标ꎮＳｃｈöｂｅｌ[１]以乘客满意度为目标ꎬ将路线规划、时刻表制定和列车调度三个规划阶段整合进行综合规划ꎮＷａｎｇ等[２]提出了以客流需求为目标的混合整数非线性规划模型ꎬ求解和客流需求匹配的列车运行时刻表ꎮＳｈｉ等[３]提出了以乘客满意度为目标的模型ꎬ该模型主要讨论在过饱和客流情形下ꎬ如何给出最优的列车时刻表和精确的客流控制策略ꎮＲｏｂｅｎｅｋ等[４]以乘客满意度为核心建立求解最优列车时刻表的混合整数线性规划模型ꎮＲｏｂｅｎｅｋ等[５]又对文献[４]的模型进行改进ꎬ引入乘客的随机需求要素ꎬ建立弹性需求模型ꎮ国内学者在相关研究领域也取得了一些成果ꎮＹｕ等[６]和王世峰[７]提出了动态客流需求双层规划模型ꎬ并通过模型求解给出较优的列车时刻表和车底调度计划ꎮ薛彤[８]应用ＢＰ(ｂａｃｋｐｒｏｐａｇａｔｉｏｎ)神经网络算法预测客流需求ꎬ对根据客流需求制定列车调度方案具有很大的参考价值ꎮ以上研究主要基于乘客需求建立模型ꎬ并进行求解ꎬ但未考虑城市轨道交通运行成本ꎮ

文献[９￣１１]以列车的最小运行时间为目标建立优化模型ꎬ得出最优列车车底调度方案ꎬ并对列车运行图的编制进行优化ꎮ周翔翔等[１２]运用遗传算法ꎬ解决了轨道交通列车系统在以成本最低为目标时的最优列车开行方案ꎮ以上研究都是以城市轨道交通运营成本最小为目标给出解决方案ꎮ

目前的研究一般都是以乘客满意度或城市轨道交通运营成本最小为目标ꎮ本文在此基础上ꎬ在建模时综合考虑了乘客满意度和城市轨道交通成本两个要素ꎬ将两者结合构建目标函数ꎮ在模型求解上ꎬ运用模拟退火算法ꎬ设计出列车时刻表和车底调度方案ꎬ并通过数值算例验证模型的可行性ꎮ

１　模型建立

１.１　问题描述

在一个线状的线路中ꎬ有ｍ个车站ꎬ车辆段位于线路的起终点站ꎬ线路如图１所示ꎮ列车运行路线有两

个方向ꎬ分别是方向ｂ１和ｂ２ꎬ两个方向经过的车站完全相同ꎬ在线路中所有的站都需要停靠ꎬ其中ꎬ车站１为起点站ꎬ车站ｍ为终点站ꎮ

列车运行方式为列车开始从某车辆段出发ꎬ到达某方向ｂｉ的起点站１站ꎬ然后沿方向ｂｉ出发ꎬ到达终点站ｍ后ꎬ再进入对面的车辆段ꎬ从相反方向ｂ３－ｉ的起点站１站出发ꎬ执行新的运输任务(在该问题中有两个方向ｂ１和ｂ２ꎬｂ１的相反方向为ｂ２ꎬｂ２的相反方向为ｂ１ꎬ因此在一般性的描述中ꎬ用ｂ３－ｉ表示某方向ｂｉ的相反方向)ꎮ

图１　城市轨道线路图

１.２　模型假设

Ｆｉｇ.１　Ｕｒｂａｎｒａｉｌｔｒａｎｓｉｔｌｉｎｅ

(１)两个方向的列车在各自的线路上ꎬ互不干扰ꎮ(３)车底不属于特定的车辆段ꎮ

(２)列车在所有中间车站均停车ꎬ且停车时间为定值ꎮ(４)列车到达中间站的下车率为定值ꎮ

第１期林禹童ꎬ等:基于客流需求的列车时刻表和车底调度协同优化

１.３　符号说明

(５)列车从某个车站发车到达另一个车站的时间为定值ꎮ

模型中所使用的符号集合见表１ꎬ模型参数在表２中给出ꎬ模型变量见表３ꎮ

表１　符号集合

Ｔａｂｌｅ１　Ｓｅｔｓｓｙｍｂｏｌａｎｄｄｅｆｉｎｉｔｉｏｎ集合ＳＢ~~６５定义及说明车站的集合列车运行方向的集合集合Ｋｂ~定义及说明列车运行方向ｂ的列车服务车次的集合表２　模型参数Ｔａｂｌｅ２　Ｐａｒａｍｅｔｅｒｓｏｆｍｏｄｅｌ参数ｔ∈[０ꎬｔｍａｘ]ｔｍａｘＫｂＭｂｉ∈Ｓｋｂ∈ＢＵ~~定义及说明列车运行计划期中的某一时刻最大时刻列车运行方向ｂ的最大可能列车服务次数开始服务前ꎬ列车运行方向ｂ端总的车底数目列车停靠的车站ꎬ取值为１~ｍꎬ其中１是起点站ꎬｍ是终点站列车发车的车次ꎬ取值为１~Ｋｂ列车运行的方向列车的最大运能ꎬ即最大载客量参数Ｃｈｍｉｎｄｍｉｎμｉｂｐｋｉｂｒｉｂλｉｂ定义及说明列车完成一个方向的服务所需要的成本列车间最小安全运行间隔时间列车到达终点站后的最短转轨时间运行方向ｂ的第ｉ站上乘客的下车率列车ｋ在ｉ站ꎬｂ方向停车时间运行方向ｂ的第ｉ站与第ｉ＋１站间路段上的列车运行时间运行方向ｂ的第ｉ站上乘客的到达率表３　模型变量Ｔａｂｌｅ３　Ｖａｒｉａｂｌｅｓｉｎｍｏｄｅｌ参数ｘｔｋｂ∈{０ꎬ１}ｆｋｉｂｄｋｉｂｎｋｉｂ定义及说明等于１表示列车ｋ在１站ꎬｔ时刻ꎬｂ方向发车ꎬ否则等于０列车ｋ在ｉ站ꎬｂ方向发车时的车刚上车的乘客数量列车ｋ在ｉ站ꎬｂ方向发车的发车时刻列车ｋ在ｉ站ꎬｂ方向发车后ꎬ在车厢内的旅客数参数ｗｋｉｂφｋｉｂθｋｉｂ定义及说明列车ｋ在ｉ站ꎬｂ方向发车后ꎬ未能上车的旅客数在时间段[ｄｋꎬｉꎬｂꎬｄｋ＋１ꎬｉꎬｂ]车站ｉ到达的乘客数ꎬ其中列车ｋ＋１在ｉ站ꎬｂ方向停车时的等待上车人数φ０ｉｂ表示在时间段[０ꎬｄ１ꎬｉꎬｂ]内ꎬ车站ｉ到达的乘客数１.４　模型构建

　　注:表中只有ｘｔｋｂ是决策变量ꎬ其余的变量都是中间变量

该模型的目标为综合目标ꎬ总共分为两个子目标ꎬ如下:(１)降低运营成本

成本的衡量方式为对每一次列车发车引发的成本进行求和ꎮ若决策变量ｘｔｋｂ＝１ꎬ表示方向ｂ的第ｋ次列

车发车ꎬ其成本为Ｃꎻ若决策变量为０ꎬ表示未发车ꎬ成本为０ꎮ

(２)降低乘客总等待时间

总乘客等待时间的计算方式ꎬ将总时间段分割成相等的离散时间段ꎬ对在每一个小的离散时间段内车站等待的乘客数进行计数ꎬ将每一个时间段内的乘客数相加ꎬ乘以离散时间段的时间单位得到总乘客等待时间ꎮ

设在方向ｂꎬ车站ｉ上的车次ｋ和ｋ＋１的发车间隔为ｌꎬ其中ꎬ

单位时间段为Δｔꎬ到达率定义为Δｔ内到站人数为λｉｂꎬ设将时间间隔分割成ｎ个时间段ꎬ在ｋ次列车发

ｌ＝ｄｋ＋１ꎬｉꎬｂ－ｄｋꎬｉꎬｂꎮ

(１)

６６山　东　科　学２０２０年

车后ꎬ有人数为ｗｋｉｂ的乘客滞留在ｉ站ꎮ其中ꎬ滞留的乘客在车次ｋ和ｋ＋１之间的等待时间

计算车次ｋ和ｋ＋１次之间进站的乘客等待时间ꎮ由于乘客进站率为定值ꎬ每一个小时间段人数都增加ｌλｉｂ/ｎꎬ则进站乘客的等待时间

ｔ２＝

ｌ２ｌｎｌ１１λｉｂΔｔ＋λｉｂΔｔ＋􀆺＋λｉｂΔｔ＝λｉｂｌ２＋λｌΔｔꎮｎｎｎ２２ｉｂ

ｌｉｍｔ２＝

１

λｉｂｌ２ꎮ２

１

λｉｂｌ２ꎮ２

ｔ１＝ｗｋｉｂｌꎮ

(２)

(３)

在乘客达到率为定值的情形下ꎬ可以视为连续到达ꎬ则取极限

Δｔ→０

(４)

则有在该时间区间内ꎬ乘客总等待时间ｔ总

ｔ总＝ｔ１＋ｔ２＝ｗｋｉｂｌ＋

２

ｍ

(５)

在初始发车前的时间ꎬ滞留乘客数为０ꎬ所以乘客总等待时间为

ｔ总

１æö

＝∑∑∑∑çｗｋｉｂ＋φｋｉｂ÷􀅰(ｄｋ＋１ꎬｉꎬｂ－ｄｋｉｂ)􀅰ｘｔｋｂ＋

２~~èøｂ＝１ｉ＝１

ｔ∈Ｔｋ∈Ｋ

ｂ

∑∑ｂ＝１ｉ＝１

２

ｍ

１

λｉｂ􀅰ｄ２１ｉｂꎮ２

(６)

将两个目标乘以一定的系数求和后形成一个综合目标ꎬ并以该目标函数最小化为最优目标ꎮ

在约束条件中ꎬ需要充分考虑要素:客流的分布情况ꎻ可调用的车底数量ꎻ列车乘客容量ꎻ最小停车间隔ꎻ客流状态平衡的约束ꎬ其中起点站乘客下车率为０ꎬ终点站为１００％ꎮ

该模型的综合表述如下:

２ｍ１２１é２ｍæöｔ２ùú－＋＋－çｗｋｉｂ＋÷()()ｍｉｎＺ＝αê∑∑∑∑φ􀅰ｄｄ􀅰ｘ∑∑λ􀅰ｄ１α∑∑∑ｘｔｋｂ􀅰Ｃꎬ(７)ｋｉｂｋ＋１ꎬｉꎬｂｋｉｂｋｂｉｂ１ｉｂúê~~~＝＝＝＝＝ｂ１ｉ１２ｂ１~２ëｂ１ｉ１ｔ∈Ｔｋ∈Ｋｂèøûｔ∈Ｔｋ∈Ｋｂ

~

ｓ.ｔ.

~ｔ′∈[ｔꎬｔ＋ｈｍｉｎ]

ｋ∈Ｋｂ

∑∑

~

ｘｔ′ｋｂ≤１ꎬ∀ｔ∈[０ꎬｔｍａｘ]ꎬｂ∈Ｂꎬ

~

~

(８)(９)(１０)

∑

ｔ∈Ｔ

ｘｔｋｂ≤１ꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬ

ｄｋ１ｂ＝

ｄｋꎬｉ＋１ꎬｂ＝ｄｋꎬｉꎬｂ＋ｒｉｂ＋ｐｋꎬｉ＋１ꎬｂꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｉ∈Ｓꎬｄｋ＋１ꎬｉꎬｂ－ｄｋꎬｉꎬｂ≥ｈｍｉｎꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｉ∈Ｓꎬθｋｉｂ＝ｗｋｉｂ＋φｋｉｂꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｉ∈Ｓꎬ

~

~

~

~

~

~

~

~

∑ｔｘｔｋｂꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬ

~

~

ｔ<Ｔ

~

~~

(１１)(１２)

~

φｋｉｂ＝(ｄｋ＋１ꎬｉꎬｂ－ｄｋꎬｉꎬｂ)􀅰λｉｂꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂ/{１}ꎬｉ∈Ｓꎬｆｋｉｂ≤Ｕ－ｎｋꎬｉ－１ꎬｂ􀅰(１－μｉｂ)ꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｉ∈Ｓ/{１}ꎬ

ｆｋｉｂ≤θｋ－１ꎬｉꎬｂ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｉ∈Ｓꎬ

ｆｋ１ｂ≤Ｕꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬ

~~

~

~

~

~

~

~

~

(１３)(１４)(１５)(１６)(１７)(１８)(１９)(２０)(２１)

φ１１ｂ＝ｄ１１ｂ􀅰λ１ｂꎬ∀ｂ∈Ｂꎬ

~

~

~~

ｎｋｉｂ＝ｎｋꎬｉ－１ꎬｂ(１－μｉｂ)＋ｆｋｉｂꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｉ∈Ｓ/{１}ꎬ

ｗｋｉｂ＝θｋ－１ꎬｉꎬｂ－ｆｋｉｂꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｉ∈Ｓꎬ

ｎｋ１ｂ＝ｆｋ１ｂꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬ

~

~

~

~

第１期林禹童ꎬ等:基于客流需求的列车时刻表和车底调度协同优化

６７(２２)(２３)

ｄＭｂ＋ｋꎬ１ꎬｂ≥ｄｋꎬｍꎬ３－ｂ＋ｒｍꎬ３－ｂ＋ｄｍｉｎꎬ∀ｂ∈Ｂꎬｋ∈Ｋｂꎬｘｔｋｂ∈{０ꎬ１}ꎬ∀ｔ∈[０ꎬｔｍａｘ]ꎬｂ∈Ｂꎬｋ∈Ｋｂꎬ

~

~

~~

其中ꎬ目标函数第一项表示服务质量ꎬ衡量指标是总服务时间ꎬ第二项表示列车运营成本ꎮ其中ꎬα(０<α<１)表示目标函数的权重ꎬ决策者可以根据乘客总等待时间和列车的总运行成本对整个运营管理影响的大小来决定目标函数权重α的取值ꎮ公式(８)表示在规定时间间隔ｈｍｉｎ内只能发一次列车ꎮ公式(９)表示对于方向ｂꎬ车次ｋ发车的时间点是唯一的ꎮ公式(１０)将发车的决策变量ｘｔｋｂ转化成某列车对应的车次ｋ在第１站发车的时刻ｄｋ１ｂꎮ公式(１１)表示对方向ｂꎬ车次ｋꎬ根据第ｉ站的发车时间ꎬ计算列车在第ｉ＋１站发车时间ꎮ公式(１２)表示在列车发车后ꎬ方向ｂꎬ两个车次第ｋ次和ｋ＋１次在车站ｉ站的发车间隔要大于最小时间间隔ｈｍｉｎꎮ公式(１３)用于确定在第ｋ＋１车次于ｂ方向ꎬ第ｉ站发车时等待上车的乘客数ꎮ公式(１４)和(１５)用于确定到达车站的乘客数ꎮ公式(１６)~(１８)是刚上车的乘客数量的约束ꎮ公式(１９)和(２０)表示车厢内的旅客数ꎮ公式(２１)表示未能上车的旅客数量ꎮ公式(２２)表示列车循环运营约束ꎮ公式(２３)表示决策变量ｘｔｋｂ是０￣１变量ꎮ

２　算法设计

在大规模问题中ꎬ找到较优列车调度方案的方法是先根据总的客流需求情况找到一个初始的运行方案ꎬ再根据每一时刻具体的客流状况沿着一定路径进行调整ꎬ逐渐找到较优的运行方案ꎮ由于该问题的混合整数规划模型由０￣１决策变量组成ꎬ理论上可以使用枚举法找到最优解ꎮ但如果模型规模较大ꎬ则枚举法并不可行ꎬ而模拟退火算法可以提高寻找最优解的效率且可有效避免陷入局部最优解的困境ꎬ因此该模型的求解应用模拟退火算法ꎮ算法流程图如图２所示ꎬ应用该算法的具体步骤如下:终止温度Ｔｆꎬ以及迭代次数ｎꎬ第一步令Ｔ＝Ｔ０ꎬｎ＝０ꎬ转步骤２ꎮ

步骤１:初始化ꎮ给出初始温度Ｔ０、

步骤２:随机生成一个优化方案Ｘ′ꎮ

判断此方案能否满足约束ꎬ若满足ꎬ则Ｘ′是可行的ꎬ令Ｘ′＝Ｘ０ꎬ转步骤３继续迭代ꎻ若不满足ꎬ则对未满足约束条件的方案进行随机调整ꎬ直到生成一个可行方案ꎬ得到初始可行解ꎬ转至步骤３ꎮ

步骤３:对该方案进行随机扰动ꎬ直到得到一个符合约束的新方案Ｘꎬ并计算该方案和原可行方案Ｘ０的目标函数的增量Δｆ＝ｆ(Ｘ)－ｆ(Ｘ０)ꎬ转至步骤４ꎮ

图２　算法流程图Ｆｉｇ.２　Ｆｌｏｗｃｈａｒｔｏｆａｌｇｏｒｉｔｈｍ

６８山　东　科　学２０２０年

大于(０ꎬ１)的随机数ꎬ令Ｘ＝Ｘ０ꎬ让Ｘ成为新路径ꎬ转至步骤５ꎬ否则转至步骤３ꎮ

步骤４:若Δｆ<０ꎬ则令Ｘ＝Ｘ０ꎬ即接受路径Ｘ为新的路径ꎻ若Δｆ≥０ꎬ计算ｐ＝ｅｘｐ(－Δｆ/Ｔ０)ꎬ若ｐ为步骤５:进行终止条件判断ꎬ满足则给出可行方案ꎬ结束迭代ꎻ否则更新Ｔ０ꎬ令ｎ＝ｎ＋１转至步骤３ꎮ

３　数值案例

本文以图３所示的列车线路图进行案例分析ꎮ图３的城市轨道交通线路图为线状线路ꎬ有３个车站ꎬ分成ｂ１和ｂ２两个方向ꎬ两个方向互为相反方向ꎬ图示共有６个车站ꎮ方向ｂ１和ｂ２的站１和站３分别为起点站和终点站ꎬ站２为中间站ꎬ列车从车辆段出发ꎬ到起点站站１ꎬ然后沿某方向出发ꎬ途经中间站站２ꎬ到达终点站站３ꎬ进入对面车辆段ꎬ进行休整ꎬ向相反方向的起点站站１发车ꎮ案例中的列车发车时间范围８:００ａｍ—８:３０ａｍꎮ单位时间段为３０ｓꎬ一共分成６０个时间段ꎮ其参数和符号表示及数值设定如表４所示ꎬ乘客的进站情况如表５所示ꎮ

图３　数值案例线路图Ｆｉｇ.３　Ｔｒａｎｓｉｔｌｉｎｅｉｎｎｕｍｅｒｉｃａｌｃａｓｅ

表４　算例参数

Ｔａｂｌｅ４　Ｐａｒａｍｅｔｅｒｓｉｎｎｕｍｅｒｉｃａｌｃａｓｅ名称乘客容量Ｕ/人最小发车间隔ｈｍｉｎ/ｍｉｎ列车停站时间ｐｋｉｂ/ｍｉｎ

车站下车率μｉｂ

总乘客等待时间的权重α单位车次发车成本Ｃ/元相邻车站间运行时间ｒｉｂ/ｍｉｎｂ１方向车辆段初始列车数/辆ｂ２方向车辆段初始列车数/辆最短转轨时间ｄｍｉｎ/ｍｉｎ最大发车车次Ｋｂ/次

值１６００１.５０.５０.５０.５１６００２７３１２０

表５　乘客需求Ｔａｂｌｅ５　Ｐａｓｓｅｎｇｅｒｄｅｍａｎｄ方向ｂ１ｂ２

车站１２１２

每０.５ｍｉｎ进站人数/人１００１５０５０５０

第１期林禹童ꎬ等:基于客流需求的列车时刻表和车底调度协同优化

　　根据表４算例参数和表５乘客需求状况ꎬ应用模拟退火算法ꎬ得到的较优解对应的时刻表如表６所示ꎮ城市轨道交通列车运行图如图４所示ꎮ

表６　列车运行时刻表Ｔａｂｌｅ６　Ｔｉｍｅｔａｂｌｅｏｆｔｒａｉｎ方向ｂ１车次１２３４５６７８１０１１１２１３１４１５９发车时间８:００:３０８:０２:３０８:０４:３０８:０６:３０８:０８:３０８:１０:３０８:１２:３０８:１４:３０８:１６:３０８:１８:３０８:２０:３０８:２２:３０８:２４:３０８:２６:３０８:２８:３０车次１２３４５６７８１０１１１２９方向ｂ２发车时间８:００:３０８:０３:００８:０５:３０８:０８:００８:１０:３０８:１３:００８:１５:３０８:１８:００８:２０:３０８:２３:００８:２５:３０８:２８:００６９图４　城市轨道交通列车运行图

　　在该时间段内ꎬ由于方向ｂ１的乘客需求大ꎬ因此和方向ｂ２比ꎬ发车频率较高ꎮ在目标函数中考虑降低乘客总等待时间和列车运行成本后ꎬ其发车频率更加合理ꎮ若仅考虑降低乘客总等待时间ꎬ则成本的增加量高于乘客总等待时间的降低量后ꎬ目标函数值会增加ꎮ在建立目标函数时ꎬ综合考虑乘客等待时间和运营成本ꎬ可得到一个和客流需求匹配ꎬ且能够节约成本的列车运行计划ꎮ

Ｆｉｇ.４　Ｄｉａｇｒａｍｏｆｔｉｍｅｔａｂｌｅｐｌａｎｎｉｎｇｉｎｕｒｂａｎｔｒａｎｓｉｔｌｉｎｅ

４　结论

本文根据乘客需求ꎬ以最小化乘客总等待时间和城市轨道交通系统运营成本为综合目标ꎬ建立混合整数规划模型ꎮ在模型求解时ꎬ运用模拟退火算法得到较优的列车时刻表和车底调度方案ꎬ并通过算例分析对模型进行验证ꎬ结果证明该较优解是符合客流需求的ꎮ

７０山　东　科　学２０２０年

本文数值算例的计算结果与预期一致ꎮ相比目标函数中仅考虑单一要素ꎬ本文考虑综合要素后给出的列车调度方案ꎬ发车频率保持在一个合理的范围ꎬ且和客流需求更加匹配ꎬ不会出现列车发车频率过高或者过低的情况ꎮ而保持一个合理的发车频率ꎬ既可以降低乘客等待时间ꎬ提高乘客满意度ꎬ又可以降低列车运营成本ꎮ

但是该模型是在列车停站时间及客流下车率为定值的假设下提出的ꎬ缺乏灵活性ꎬ如果乘客下车率在不同车站不同时段是变动的ꎬ则对于该优化问题中模型提出了更多的改进要求ꎬ这也是下一步的工作方向ꎮ

参考文献:

[１]ＳＣＨÖＢＥＬＡ.Ａｎｅｉｇｅｎｍｏｄｅｌｆｏｒｉｔｅｒａｔｉｖｅｌｉｎｅｐｌａｎｎｉｎｇꎬｔｉｍｅｔａｂｌｉｎｇａｎｄｖｅｈｉｃｌｅｓｃｈｅｄｕｌｉｎｇｉｎｐｕｂｌｉｃｔｒａｎｓｐｏｒｔａｔｉｏｎ[Ｊ].[２]ＷＡＮＧＹＨꎬＤ’ＡＲＩＡＮＯＡꎬＹＩＮＪＴꎬｅｔａｌ.Ｐａｓｓｅｎｇｅｒｄｅｍａｎｄｏｒｉｅｎｔｅｄｔｒａｉｎｓｃｈｅｄｕｌｉｎｇａｎｄｒｏｌｌｉｎｇｓｔｏｃｋｃｉｒｃｕｌａｔｉｏｎｐｌａｎｎｉｎｇｆｏｒａｎ[３]ＳＨＩＪＧꎬＹＡＮＧＬＸꎬＹＡＮＧＪꎬｅｔａｌ.Ｓｅｒｖｉｃｅ￣ｏｒｉｅｎｔｅｄｔｒａｉｎｔｉｍｅｔａｂｌｉｎｇｗｉｔｈｃｏｌｌａｂｏｒａｔｉｖｅｐａｓｓｅｎｇｅｒｆｌｏｗｃｏｎｔｒｏｌｏｎａｎ

１１０:２６￣５９.ＤＯＩ:１０.１０１６/ｊ.ｔｒｂ.２０１８.０２.００３.Ｂ:Ｍｅｔｈｏｄｏｌｏｇｉｃａｌꎬ２０１６ꎬ８９:１０７￣１２６.

ｕｒｂａｎｒａｉｌｔｒａｎｓｉｔｌｉｎｅ[Ｊ].ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅｓｅａｒｃｈＰａｒｔＢ:Ｍｅｔｈｏｄｏｌｏｇｉｃａｌꎬ２０１８ꎬ１１８:１９３￣２２７.ＤＯＩ:１０.１０１６/ｊ.ｔｒｂ.２０１８.１０.００６.ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅｓｅａｒｃｈＰａｒｔＣ:ＥｍｅｒｇｉｎｇＴｅｃｈｎｏｌｏｇｉｅｓꎬ２０１７ꎬ７４:３４８￣３６５.ＤＯＩ:１０.１０１６/ｊ.ｔｒｃ.２０１６.１１.０１８.

ｏｖｅｒｓａｔｕｒａｔｅｄｍｅｔｒｏｌｉｎｅ:ａｎｉｎｔｅｇｅｒｌｉｎｅａｒｏｐｔｉｍｉｚａｔｉｏｎａｐｐｒｏａｃｈ[Ｊ].ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅｓｅａｒｃｈＰａｒｔＢ:Ｍｅｔｈｏｄｏｌｏｇｉｃａｌꎬ２０１８ꎬ

[４]ＲＯＢＥＮＥＫＴꎬＡＺＡＤＥＨＳＳꎬＭＡＫＮＯＯＮＹꎬｅｔａｌ.Ｐａｓｓｅｎｇｅｒｃｅｎｔｒｉｃｔｒａｉｎｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ[Ｊ].ＴｒａｎｓｐｏｒｔａｔｉｏｎＲｅｓｅａｒｃｈＰａｒｔ[５]ＲＯＢＥＮＥＫＴꎬＡＺＡＤＥＨＳＳꎬＭＡＫＮＯＯＮＹꎬｅｔａｌ.Ｔｒａｉｎｔｉｍｅｔａｂｌｅｄｅｓｉｇｎｕｎｄｅｒｅｌａｓｔｉｃｐａｓｓｅｎｇｅｒｄｅｍａｎｄ[Ｊ].Ｔｒａｎｓｐｏｒｔａｔｉｏｎ[６]ＹＵＥＹＸꎬＨＡＮＪＴꎬＷＡＮＧＳＦꎬｅｔａｌ.Ｉｎｔｅｇｒａｔｅｄｔｒａｉｎｔｉｍｅｔａｂｌｉｎｇａｎｄｒｏｌｌｉｎｇｓｔｏｃｋｓｃｈｅｄｕｌｉｎｇｍｏｄｅｌｂａｓｅｄｏｎｔｉｍｅ￣ｄｅｐｅｎｄｅｎｔ

ｄｅｍａｎｄｆｏｒｕｒｂａｎｒａｉｌｔｒａｎｓｉｔ[Ｊ].Ｃｏｍｐｕｔｅｒ￣ＡｉｄｅｄＣｉｖｉｌａｎｄＩｎｆｒａｓｔｒｕｃｔｕｒｅＥｎｇｉｎｅｅｒｉｎｇꎬ２０１７ꎬ３２(１０):８５６￣８７３.ＤＯＩ:１０.１１１１/ｍｉｃｅ.１２３００.

ＲｅｓｅａｒｃｈＰａｒｔＢ:Ｍｅｔｈｏｄｏｌｏｇｉｃａｌꎬ２０１８ꎬ１１１:１９￣３８.ＤＯＩ:１０.１０１６/ｊ.ｔｒｂ.２０１８.０３.００２.

[７]王世峰.基于动态客流的城市轨道交通列车时刻表与车底运用一体化优化模型和算法研究[Ｄ].北京:北京交通大学ꎬ２０１６.[８]薛彤.城市轨道交通列车开行计划调整优化方法研究[Ｄ].成都:西南交通大学ꎬ２０１８.[９]李峰.网络环境下单线列车运行图编制的优化算法研究[Ｄ].北京:北京交通大学ꎬ２０１０.

[１０]黎新华.单线区段列车运行图铺划与运行调整优化方法研究[Ｄ].长沙:中南大学ꎬ２００５.

[１１]史峰ꎬ黎新华ꎬ秦进ꎬ等.单线列车运行图铺划的时间循环迭代优化方法[Ｊ].铁道学报ꎬ２００５ꎬ２７(１):１￣５.

２１(１２):６７￣７０.ＤＯＩ:１０.１６０３７/ｊ.１００７￣８６９ｘ.２０１８.１２.０１５.

[１２]周翔翔ꎬ刘鑫荣ꎬ张永ꎬ等.基于遗传优化算法的城市轨道交通多列车运行节能计算方[Ｊ].城市轨道交通研究ꎬ２０１８ꎬ