高速铁路车站到发线运用实时调整复合排序模型与算法.pdf
《高速铁路车站到发线运用实时调整复合排序模型与算法.pdf》由会员分享,可在线阅读,更多相关《高速铁路车站到发线运用实时调整复合排序模型与算法.pdf(12页珍藏版)》请在咨信网上搜索。
1、第 卷 第 期 年 月铁 道 学 报 文章编号:()高速铁路车站到发线运用实时调整复合排序模型与算法张英贵,陈 元,雷定猷,高 全(中南大学 交通运输工程学院,湖南 长沙)摘 要:高速铁路车站到发线运用实时调整是列车运行调整的重要内容。运用现代排序理论,将列车视为工件,到发线、咽喉区进路和区间视为机器,将相邻若干高速铁路车站到发线运用技术作业过程视为混合流水作业过程,将实时调整优化问题抽象成一类新型复合排序问题;统筹考虑车站到发线和咽喉区进路占用最小安全间隔时间、车底周转计划等约束,以列车加权到发时刻和到发线运用方案波动性最小为优化目标函数,构建高速铁路车站到发线运用实时调整第三类多目标复合排
2、序模型;以列车运行和车站到发时刻为纽带,分别设计基于分派规则的复合排序算法和基于 的优化算法确定其规则解和优化解。算例表明:所提方法能快速制订线路级高速铁路车站到发线运用实时调整方案,有效缓解列车晚点、到发线故障对车站到发线运用的影响,满足实时调整的强时效性要求;针对不同工况宜直接采用合适的分派规则制订实时调整方案;立折列车对晚点程度的敏感性最强,终到列车最弱。关键词:高速铁路车站;到发线运用;实时调整;混合流水作业;复合排序;分派规则中图分类号:文献标志码:收稿日期:;修回日期:基金项目:国家自然科学基金();湖南省自然科学基金()作者简介:张英贵(),男,安徽金寨人,教授,博士。:,(,)
3、:,:;第 期张英贵等:高速铁路车站到发线运用实时调整复合排序模型与算法 到发线运用是高速铁路(以下简称“高铁”)车站作业组织的核心,列车晚点、到发线故障等情况发生时,调度人员会在线临时调整到发线运用方案,确保列车安全有序运行;单个车站到发线运用方案的临时调整会经由列车运行反馈至相邻若干车站;基于整体视角,高效制订相邻若干高铁车站到发线运用实时调整方案尤为重要。近年来,铁路车站到发线运用优化方面研究主要集中在计划编制和实时调整两个层面。在计划编制层面,等、等分别以列车延误程度最小和路网节点使用均衡性最强为优化目标,兼顾列车在站运行路径和到发时刻,构建混合整数线性规划模型并采用 求解;等从中观角
4、度构建时空网络和区间咽喉区到发线三段式列车运行图框架,利用拉格朗日松弛算法和交替方向乘子法对列车运行图与到发线运用进行协同编制优化;张英贵等将到发线运用抽象成排序问题,构建单站到发线运用第一类多目标窗时排序模型并采用多种分派规则求解;郑开娣等通过构建进路分配优化模型来优化企业枢纽车站到发线运用并采用遗传算法求解;郭彬等考虑列车作业与调车作业协同编制,采用()算法求解列车在站作业链优化模型。在实时调整层面,等考虑到发线故障因素,以最小化列车到站时刻偏移程度、最大化特定时间段维修工作量为优化目标,构建到发线运用调整混合整数规划模型并采用 求解;等以列车最大延误时间最小化为优化目标,构建替代图模型并
5、借助邻域搜索来缩短计算时间;等以最小化列车加权到发时刻偏离程度为优化目标,构建列车在站路径实时调整模型并设计分支定价算法求解;等引入冲突度概念,建立到发线运用调整模型,提出一种基于滚动时域的启发式求解算法;季学胜等设计基于优先级规则的启发式算法,求解整数规划模型以同步调整列车到发时刻与进路;彭其渊等运用分支定界算法求解列车晚点和到发线故障干扰下的单站到发线运用调整问题;徐培娟等基于替代图理论并采用两阶段算法求解多类干扰下的列车运行调整和列车径路优化问题。综上,国内外学者对到发线运用优化开展了大量基础研究,且多通过构建整数规划模型、采用商用求解器和设计启发式算法研究此类问题;列车在站技术作业过程
6、可视为工件在机器上的加工过程,可采用现代排序来求解到发线运用优化问题,但既有研究并未涉及线路级多站到发线运用层面;研究热点逐步由计划编制向实时调整、由局部优化向整体优化转移;基于整体视角,考虑高铁车站到发线运用实时调整技术作业过程排序特征,研究并提出高铁车站到发线运用实时调整优化方法。因此,采用现代排序理论,将线路级相邻若干高铁车站到发线运用实时调整抽象成具有混合流水作业性质的一类新型复合排序问题,兼顾列车到发时刻、车底周转计划、到发线和咽喉区进路占用等因素,构建高铁车站到发线运用实时调整第三类多目标复合排序模型,设计基于分派规则的复合排序算法和基于模拟退火()的实时调整优化算法,探讨分派规则
7、和算法的使用场景,高效合理制订到发线运用实时调整方案。问题描述高铁车站到发线运用技术作业主要包括列车接车作业、到发线占用、发车作业、始发(终到)列车的出(入)段作业、列车区间运行等环节,需占用车站到发线、咽喉区进路和区间等运输资源,到发线运用技术作业过程见图。将列车视为工件,到发线、咽喉区进路和区间视为加工机器,列车接车作业(出段)、到发线占用、发车作业(入段)、区间运行视为工序,则列车在单个车站的到发线运用技术作业过程可视为平行机作业(),相邻若干车站的到发线运用技术作业过程可视为混合流水作业()。图 到发线运用技术作业过程高铁车站到发线运用实时调整排序问题可以描述为:在已知工件初始延误(列
8、车初始晚点)、机器固定维护时段(到发线维修时间窗)的背景下,基于工件在车站的释放时间和工期(图定列车时刻表)、机器使用计划(到发线运用计划)、站场拓扑结构等要素,考虑工件图定及最小加工时间(咽喉区进路占用时间、图定及最小停站时间、图定及最小区间运行时间)、机器准备时间(同向接车、同向发车、不同时到发、不同时铁 道 学 报第 卷发到、到发线占用、咽喉区进路占用最小安全间隔时间)等约束,结合当前时间各工件(列车)和机器(到发线、咽喉区进路和区间)的实时工作状态,实时动态调整工件占用机器的方案,确保平行机加工和混合流水作业安全有序。在动态调整过程中,到发线、咽喉区进路和区间等资源不会随着列车加工作业
9、而产生消耗;需考虑到发线维修时间窗,通过列车一般只占用车站正线,车站正线一般也只能被通过列车占用;列车停站时间和区间运行时间均可控;始发(终到)列车在时间窗内出(入)段不产生损失,非始发(终到)列车在车站的提前或延误到(发)站均会产生一定的损失;区别于经典排序多追求最小化完工时间、工期延误时间、工件延误数量等优化目标,高铁车站到发线运用实时调整排序问题以图定列车时刻表和到发线运用计划为前提,应尽可能降低列车到发时刻和到发线运用方案的波动性,确保正常作业秩序和旅客服务质量。因此,高铁车站到发线运用实时调整具有可恢复资源排序、资源受限排序、可控排序、窗时排序、准时排序、多目标排序等现代排序特征,是
10、一类具有混合流水作业性质的新型复合排序问题,可从复合排序视角研究高铁车站到发线运用实时调整优化。模型构建为便于研究,不妨假设:列车出入段按行车作业办理;咽喉区进路采用一次性解锁方式;立折列车采用本线立折方式;不考虑不同咽喉区进路占用的时间差异。模型中的集合、参数及变量见表、表 和表。表 集合及说明集合说明列车集合,初始晚点列车集合,车站集合,为车站总数车站 的列车集合,车站 在当前时刻 之后接发的列车集合、车站 的始发、终到、通过、停站、立折列车集合,车站 的到发线集合,车站 的正线集合()车站 联锁表中的咽喉区接(发)车进路集合,(),()()()咽喉区进路()上的轨道电路区段集合车站 的站
11、台集合,列车 的重叠列车集合,包括列车 其中,模型的决策变量为、()、。列车在站到发时刻是高铁车站到发线运用实时调整的纽带,调整时应尽可能降低到发时刻变更对后续车站到发线运用的影响。考虑始发终到列车的出入段 表 参数及说明参数说明当前时刻列车 到达车站 的初始晚点时间、列车 在车站 的图定到站、发站时刻,到发线 的维修时间窗,为维修开始时刻,为维修结束时刻站台 的最大容许接车数、列车 在车站 的图定、最小停站时间,、,列车 在车站 和车站 的图定、最小区间运行时间、同向接车、同向发车、不同时到发、不同时发到、到发线占用、咽喉区进路占用最小安全间隔时间列车 的权重,列车为动车时取,为高铁时取 车
12、底周转计划列车 在车站 的有限度即可占用的到发线数量、咽喉区接、发车进路占用时间,始发列车 在车站 的出段时间窗,终到列车 在车站 的入段时间窗()到发线 和咽喉区进路()的映射关系,当咽喉区进路()连接到发线 时取,否则为 到发线 和站台 的映射关系,当到发线 对应停靠的站台为 时取,否则为 到发线 在维修时间窗内时取,否则为 列车 与列车 满足车底周转计划:时取,否则为()()咽 喉 区 进 路 间 的 敌 对 关 系,当()()时取,否则为、()、列车 既定占用到发线、咽喉区进路()、站台 时取,否则为 表 变量及说明变量说明、列车 在车站 的实际到站、发站时刻列车 在车站 的实际停站时
13、间,列车 在车站 和车站 的实际区间运行时间、列车 在车站 的实际到站、发站次序若始发列车 早于图定到站时间在车站 出段取,否则为 若终到列车 早于图定发站时间在车站 入段取,否则为 列车 与列车 在车站 的实际停站时间区间是否存在重叠,若,取,否则为、()、若列车 实际占用到发线、咽喉区进路()、站台取,否则为 时间窗,始发、终到、通过、停站、立折列车在 站加权到发时刻波动性、分别为()(,)(,)()()(,)(,)()()第 期张英贵等:高速铁路车站到发线运用实时调整复合排序模型与算法 ()()所有列车在所有车站的加权到发时刻波动性 为()()不同车站的到发线运用调整经由列车运行和到发时
14、刻产生相互影响,到发线的变更会导致咽喉区进路和站台的变更,调整时应尽量降低到发线占用的波动性。所有列车在所有车站的加权到发线运用波动性 为 ()考虑到、量纲不同,对、进行归一化处理,即()()()()式中:()、()分别为、最小(大)值;为一很小的正数,防止分母为。不妨设、分别表示在调整时调度员对列车到发时刻、到发线运用计划波动性的决策偏好,设 为总目标函数,采用第三类多目标排序将、转化为单目标 ()()()将列车图定时刻表(,)、列车权重、列车有限度、车底周转计划 、到发线维修时间窗,、机器准备时间(、)视为工件的加工特性,以列车加权到发时刻波动性最小和加权到发线运用计划波动性最小为优化目标
15、,考虑到发线、咽喉区进路占用的唯一性及最小安全间隔时间、同向接发车最小安全间隔时间、不同时到发和不同时发到最小安全间隔时间、车底周转计划、到发线故障等约束,利用现代排序理论,构建高铁车站到发线运用实时调整第三类多目标复合排序模型(采用国际使用的三元组 表示法),即(),()()()(),(),(),(),()(),()()()()()()()()()()()()()()()()(,)(,),()(,)(,)()()()(),()()(),()()()()()()()()()()()()()()()(),(),()()()(),(),(),(),(),()()()式 中:为 一 足 够 大 的
16、数;为 构 造 函 数,铁 道 学 报第 卷()。式()表示呈现混合流水作业()特征,包括 道工序,具有图定时刻表、列车权重、列车有限度等加工特性,以列车加权到发时刻和到发线运用方案波动性最小为优化目标的第三类多目标复合排序问题;式()表示初始晚点列车的实际到站时刻及图定到站时刻、初始到站晚点时间之间的关系;式()式()表示同向接车、同向发车、不同时到发、不同时发到时间间隔约束;式()、式()表示停站时间、区间运行时间约束;式()表示非终到列车不能提前发车;式()、式()表示固定当前时刻之前的列车到发时刻;式()、式()表示列车占用到发线和咽喉区接(发)车进路的唯一性约束;式()表示任一到发线
17、最多同时停靠 列列车;式()表示任一咽喉区接(发)车进路最多同时供 列列车占用;式()、式()表示到发线、咽喉区进路占用时间间隔约束;式()限制通过列车只能占用车站正线;式()表示车站立折列车需停靠同一到发线;式()表示列车不能占用故障到发线;式()表示固定当前时刻之前的列车的到发线运用方案;式()、式()表示到发线与咽喉区接(发)车进路及到发线与站台之间的映射关系约束;式()表示任意两列车不能同时占用咽喉区敌对进路;式()表示任一站台同时接车数不能超过其最大容许接车数;式()限制列车不能在区间越行;式()表示区间运行时间在车站间的传递;式()表示列车实际到、发站时刻决策变量的非负整数约束,式
18、()表示列车停靠不同车站特定到发线、咽喉区接发车进路、站台的 决策变量约束。算法设计车站到发线运用调整优化问题是一个 问题,由问题与算法的归约关系易知高铁车站到发线运用实时调整复合排序问题也是一个 问题,难以在短时间内找到最优方案,到发线运用实时调整的时效性要求极高,采用排序理论中的分派规则设计相应的启发式求解算法。具体如下:结合到发线运用技术作业过程及要求,采用不同分派规则确定列车排序指标,优先选择排序指标 值最大的列车分配惩罚费用最小的到发线,设计基于分派规则的到发线运用实时调整复合排序算法,确定规则解即实时调整满意方案;以规则解为初始解,设计基于 的到发线运用实时调整优化算法,寻求优化解
19、即实时调整优化方案。排序问题中常用的分派规则包括:最早工期优先加工;:先到先服务;:最短加权加工时间优先;:最小有限度优先;:最大工件权重优先;:明显滞后成本规则,综合考虑当前时间、加工时间、权重和工期;:考虑准备时间的明显滞后成本规则,在 基础上考虑机器准备时间;:考虑准备时间的批量明显滞后成本规则,在 基础上考虑工件实际释放时间;:含顺序决定准备时间与交付时间约束的明显滞后成本规则,考虑机器加工过程中工件的所有属性。采用、规则时,工件的排序指标值可能出现相等的情况,因此将 、规则与 或 规则组合使用。分派规则排序指标表达式见表。表 分派规则排序指标表达式分派规则排序指标 (,)(,)(,)
20、(,),(,)注:表示在第一个指标相同时比较第二个指标;为列车 在车站 占用到发线的准备时间,当列车为通过列车时为,否则为;、分别为剩余未排序列车在车站 的平均实际停站时间、平均准备时间。考虑问题自身特征,在 规则的基础上引入有限度、列车初始到站晚点时间要素,设计 规则,排序指标值 为第 期张英贵等:高速铁路车站到发线运用实时调整复合排序模型与算法 (,),(,)()、的排序指标表达式中,、为比例参数,通过调整比例参数取值可调整工期、加工时间、准备时间、实际释放时间等工件加工特性对排序指标的贡献度。、为剩余未排序列车在车站 的平均有限度、平均初始到站晚点时间。同时,为提升规则使用便利性,基于
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高速铁路 车站 到发线 运用 实时 调整 复合 排序 模型 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。