基于遗传算法的大小交路开行方案优化模型研究.pdf

实验报告科技创新与应用Technology Innovation and Application2023 年 31 期基于遗传算法的大小交路开行方案优化模型研究周佳莹，周炫宇，李晓东*（佛山科学技术学院 电子信息工程学院，广东 佛山 528225）在城市轨道交通系统中，合理的运行区间和开行数量对于提高运行效率和乘客出行体验至关重要。为了尽可能减少企业运营成本和实现服务水平最大化，确定了大小交路运营模式，本文依据 OD 客流量、车站数据（包括车站能否作为折返站，车站之间的距离），以小交路区间划分和大小交路开行数量为决策变量，以企业运营成本最小化和服务水平最大化为目标函数，以大小交路比例约束、最小列车追踪间隔、最大/小列车发车间隔、最大/小交路经过车站数量和小交路起始点等作约束条件，建立列车开行方案优化模型，并将目标函数逐层剖析分解得到其数学表达式，而由于多目标优化模型难于求解，于是将 2 个目标函数转化为以成本为基本单位的单目标优化模型，并通过遗传算法求出最优解1。1列车开行方案的影响因素分析1.1乘客需求一段时间内在某区域的乘客出行需求即客流需求决定了交通的需求，交通的需求关系到交路划分及行车数量2。OD 客流量为起始点与目的地之间的客流量，在城市轨道交通系统中常使用断面客流量和 OD客流量描述一段时间内某区域的客流需求，便于后续数学模型的建立。1.2运营成本城市轨道交通运行中列车运行过程需要消耗能源的成本、企业需在列车运营中设置人力的成本，企业购置列车等硬件设备的成本均为运营成本3，可见列车的数量和列车运行的总距离可直接影响企业的运营成本。摘要：近年来，我国城市轨道交通快速发展，并成为城市公共交通的重要组成部分。城市轨道主要采用大小交路方案，即将轨道交通线路划分为 2 条大小不同的交路，可以更好地应对客流不均匀的情况，大小交路运营模式是我国城市轨道交通运用得最广泛的运营管理方式，在面对庞大的客流量和复杂的车站数据时，需要将企业的运营成本尽可能最小化和乘客服务水平尽可能最大化，在此基础上决定列车开行方案成为城市轨道交通运营的重要一环，故该文旨在解决大小交路模式下的列车开行方案问题。关键词：多目标动态规划；遗传算法；列车时刻表优化问题；大小交路；优化模型中图分类号院U239.5文献标志码院A文章编号院2095-2945渊2023冤31-0063-04Abstract:In recent years,urban rail transit in China has developed rapidly and become an important part of urban publictransport.The urban track mainly adopts the long&short routing scheme,that is,the rail transit line is divided into twointersections of different sizes,which can better deal with the uneven passenger flow.The operation mode of long&short routingsis the most widely used mode of operation and management of urban rail transit in China.In the face of huge passenger flow andcomplex station data,it is necessary to minimize the operating cost of enterprises and maximize the level of passenger service asmuch as possible.On this basis,determining the train operation plan has become an important part of urban rail transit operation,so the purpose of this paper is to solve the problem of train operation plan under long&short routing mode.Keywords:multi-objectivedynamicprogramming;geneticalgorithm;trainscheduleoptimization;long&shortrouting;optimization model基金项目：2022 年度佛山科学技术学院学生学术基金立项项目资助（xsjj202203zrb04）*通信作者：李晓东（1968-），男，硕士，副教授。研究方向为图形图像处理，机器视觉等。DOI：10.19981/j.CN23-1581/G3.2023.31.01563-2023 年 31 期实验报告科技创新与应用Technology Innovation and Application1.3轨道交通线路特点实际生活中轨道交通并非所有车站都能作为小交路的起始站、车站间距与列车行驶距离成正比、在实际生活中会制定相应的停车和发车间隔标准，限定了列车最小停站、发车时间和最大停站、发车时间，这些都作为轨道交通线路特点4。2基于遗传算法的大小交路优化模型建立与求解2.1模型假设本文根据大小交路的运营模式特点，为简化该模型的建立，故提出假设如下。假设一：假设乘客均衡到达车站等候发车，无滞留在车站的乘客。假设二：假设列车自身硬件条件相同，线路采用一条小交路的模式。假设三：所有列车采用站站停的方式且只考虑单向车程问题。假设四：所有乘客均选择直达列车出现，不出现换乘情况。假设五：列车在线路上匀速运行，速度为 45 km/h，列车定员均为 1 860 人。2.2符号说明符号说明见表 1。表 1符号说明2.3模板建立与求解2.3.1目标函数构建将乘客体验度量化为乘客出行成本，因此本文以企业运营成本最小化和乘客出行成本最小化为目标函数5。1）乘客出行成本。乘客在车时间为Z1=T1+T2+T3。本文考虑所有车辆在某个车站停留的总时间由乘客上下车所需时间构成，故第 i 个车站上下车乘客总数及第 i 个车站经过的车辆总数为在第 i 个车站未下车的乘客数量为故所有乘客停站总时间为乘客列车纯运行时间为所有乘客在列车行驶途中花费的总时间（不包括停站时间）乘客上下车花费总时间为乘客等待时间为综上所述，乘客出行成本目标函数 Z为式中：棕1为乘客在车时间成本；棕2为乘客在站候车时间成本，元/s。2）企业运营成本。企业运营成本可分为固定运营成本和可变运营成本，固定运营成本为列车数，可变运营成本为列车行车总公里。列车数为列车行车总公里为综上所述，企业运营成本目标函数为变量 说明 变量 说明 iK 第i个车站能否作为 交路起始点 1iN 第i个车站的上下车 乘客总数 n 车站总数 2iN 第i个车站的经过的 车辆总数 a、b 小交路开始、结束车站 3iN 在第i个车站停站的 乘客数量 1f、2f 单位时间内大交路、小交路列车开行数量 rl 第r个区间的站间距 C 列车定员 rD 第r个区间的断面客流量 srt 第r个区间的区间 运行时间 ijq i车站到j车站的 OD 客流量需求 it 第i个车站车辆 停留的时间 121nsrrrTD t。1avg3112nnijij iTTq 。12112111111111()21()2bbijia jianbnnnijijijijiia jbibjiZqffqqqf 。1122minZZZww，112Fff。112121nbrrrr aFflfl。1 122min,FFFqq1311iiijijNDq。12n3iiiTN t。11212111avg12,elseTniiijjiijijiiiffaibNqqNfiNtN ；。，第 个 车 站 车 辆 停 留 的 时 间 为。第 i 个车站车辆停留的时间为64-实验报告科技创新与应用Technology Innovation and Application2023 年 31 期式中：兹1为每列车投入的与行走公里无关的成本，元/列；兹2为列车每公里可变运营成本，元/km。2.3.2约束条件构建1）为使大小交路列车等间隔发车，大小交路开行数比例必须为 1颐m 或者 m颐1（m 为正整数）2）发车间隔时间约束为式中：3 600 表示 1 h。3）满足客流需求约束为4）车辆停站时间约束为式中：为最短停车时间约束，为最长停车时间约束。5）小交路端点位置约束：1臆ab臆n。6）小交路起始点约束：Ka=1，Kb=1。将多目标约束优化模型转化为单目标优化模型6。由于各优化目标均与成本有关，可将企业运营成本和乘客出行成本相加为总成本，进而将多目标规划转化为单目标规划本文将权重系数设为2.3.3算法求解本文采用遗传算法来求解该优化问题的最优解，算法步骤如下。Input:OD 客流需求，车站区间长度，最大(小)发车间隔，最大(小)停靠时间,小交路可经过车站数。Output:小交路区间a,b，大交路开行数量 f1,小交路开行数量 f2。Step 1:初始化迭代次数 ITERATION，交叉变异概率，初始种群数。Step 2:生成初始种群，开始迭代第一次 iteration=1。Step 3:目标函数计算，计算适应度并进行染色体选择、交叉和变异。Step 4:记录全局最优解，iteration=iteration+1。Step 5:若 iterationITERATION，则转入 Step 3，否则继续。Step 6:输出结果。3算例测试为验证模型和算法的有效性，本文以某城市轨道交通线路为例，选取该线路客流数据，对开行方案进行优化。使用开源数据集进行测试。该算例线路全长40.168 km，共开设车站 30 座，线路区间长度（km）和该区间断面客流量（人）、车站是否能作为折返站等数据见表 2、3。由表 4、表 5 可看出当开行数量不变，小交路区间扩大时，乘客候车时间和在车时间减少，列车行车总公里在增加，即乘客出行成本降低，企业运营成本增加。权衡服务水平和企业运营成本，寻求二者的最佳平衡点，即可实现企业与乘客的双赢7。1221fmfmZfmf。12min11max23 6003 600ffIfI，112max,max,rrDfr rarbCDffr arbC。minmax221,2,3,iItIin，1 2 3 4 5 6 7 8 9 10 区间长度/km 1.38 1.15 1.318 0.964 1.096 1.945 1.506 2.267 1.241 1.012 断面客流/人 3 169 5 613 7 331 11 179 15 802 21 502 30 650 30 939 33 990 36 824 11 12 13 14 15 16 17 18 19 20 区间长度/km 1.589 1.865 0.779 1.233 2.428 1.738 1.612 1.14 1.034 1.8 断面客流/人 45 749 36 535 45 402 46 049 33 568 32 233 31 248 30 524 30 579 30 681 21 22 23 24 25 26 27 28 29 区间长度/km 1.161 0.827 1.592 0.721 1.026 1.35 0.792 1.491 2.111 断面客流/人 30 411 30 815 10 435 10 493 9 648 9 130 8 003 6 611 459 7 表 2城市轨道交通线路区间长度与断面客流 min2I max2I11221122minGZFZZFFwwqq。12129.92,6 000,142.14wwqq。65-2023 年 31 期实验报告科技创新与应用Technology Innovation and Application表 3车站是否能作为折返站4结束语本文通过建立基于遗传算法的列车开行方案优化模型，解决我国城市轨道交通规模不断扩大的情况下合理划分小交路区间和大小交路列车开行方案，从而使企业成本和乘客出行成本最小化。参考文献院1 安志龙，马丽，崔虎，等.基于遗传算法的城市轨道交通大小交路模式列车开行方案研究J.河南科技，2022，41（18）：6-10.2 魏博超.基于大小交路的城轨列车行车间隔优化研究D.兰州：兰州交通大学，2022.3 张春田，戚建国，杨立兴，等.基于不确定旅客需求的高速铁路鲁棒列车开行方案研究J.交通运输系统工程与信息，2022，22（1）：115-123.4 宗会明，何舟，杨庆媛，等.基于 SP 方法的重庆居民轨道交通出行时间价值及影响因素分析J.现代城市研究，2014（2）：115-120.5 张海，吕苗苗，倪少权.基于非均匀发车间隔的大小交路时刻表优化模型J.交通运输系统工程与信息，2022，22（6）：224-233.6 袁家伟.基于大小交路方案的城市轨道交通列车时刻表与车底运用计划协同优化研究D.北京：北京交通大学，2021.7 肖远芯.城市轨道交通列车运行策略多目标优化研究D.成都：西南交通大学，2021.表 5对比结果渊大交路开行数量均为 18袁小交路开行数量为 9冤表 4模型最优结果 1 2 3 4 5 6 7 8 9 10 是否能作为折返站 是 是 否 否 是 否 否 是 否 是 11 12 13 14 15 16 17 18 19 20 是否能作为折返站 否 否 否 是 否 否 是 是 否 否 21 22 23 24 25 26 27 28 29 30 是否能作为折返站 是 是 否 否 是 是 是 否 否 是 结果 数值 结果 数值 小交路区间 8,17 所有乘客车站候车时间/h 2 476.037 大交路开行数量/列 18 企业使用车辆数/列 27 小交路开行数量/列 9 所有列车行驶总公里数/km 850.392 所有乘客在车总时间/h 25 495.708 1 总成本/元 542 732.231 4 小交路区间 乘客候车时间/h 乘客在车时间/h 列车数/列 列车行驶总公里/km 总成本/元 8,17 2 476.0 25 495.7 27 850.392 542 732.2 8,22 2 439.53 25 495.71 27 911.115 551 024.31 5,22 2 227.06 25 425.269 5 27 952.038 554 212.87 2,22 2 155.157 4 25 425.269 5 27 982.926 557 935.27 66-