城市轨道交通列车运行图优化模型与算法研究

摘要

列车运行图是列车运行时刻表的图解，也是城市轨道交通运输组织工作的基础。随着我国城市轨道交通规模不断扩大，城市居民出行需求持续增加，列车运行图的编制和调整已成为一项大规模的组合优化问题。然而，由于城市轨道交通系统内客流变化幅度较大，列车之间相互影响频繁，列车运行图优化作为一个复杂问题，仍然是轨道交通行业专家学者的工作难点。为进一步深入研究该问题，本文提出了一类基于离散时间的网络图，对系统中元素进行离散化处理，并根据图中点和边的定义与性质构建优化模型，设计相应的求解算法。本文的研究内容涵盖了列车运行图在编制阶段的综合优化与列车流模拟、在调整阶段的延误源分析搜索与有效调整等优化问题。具体地，本文主要工作及创新点如下。
　　1.改进了Caprara等人(2002)提出的离散时空图，并根据时变的客流需求与乘客上下车速率分析列车停站过程。基于离散时空图构建了优化模型，优化目标包括乘客时间成本、列车能耗成本，以及与车队规模有关的车辆成本，并考虑了发车频率对这些目标的影响。在优化算法中，整合了分支定界、发车频率确定、滚动优化等算法。其中，滚动优化算法考虑了优化函数的特征，并反映了客流需求、列车旅行时间等因素对发车间隔的影响。算例结果指出，本文提出的模型能准确描述高峰客流对列车停站时间的影响，提出的算法能很好地适应客流变化，且相比传统遗传算法、模式搜索和增广拉格朗日乘子等经典算法能节约超过95％的计算时间。在满足客流需求且能耗成本与车辆成本接近的前提下，本文编制的非周期性运行图比经典算法最多能节约9.09％的乘客等待时间，比当前多数运营企业采用的周期性运行图最多能节省27.37％的乘客等待时间。
　　2.根据列车运行动力学方程，提出了以离散时间为横坐标、以列车工况为纵坐标的描述速度时分曲线与能耗关系的离散时间-工况图。基于该网络图分析了列车运行过程，建立了模拟模型，并设计了考虑节能控制与线路约束的列车流模拟算法。算例结果表明，本文提出的模拟算法能生成适应不同线路条件的列车运行结果。在无约束条件下，本文模拟结果比经典方法最好结果节约了3％左右的能耗;当添加不同的线路约束后，本文结果比经典方法最好结果节约了超过10％的能耗，并且在安全性、乘客舒适度、可操作性等方面更具优势。另外，本文模拟结果可用来测试运行图的鲁棒性，并为运行图的进一步改进提供支持。
　　3.基于离散时间下的列车运行数据，提出了以离散时间为横轴、以列车编号为纵轴的列车状态图，图中的点表示列车运行过程中的关键要素，边表示要素之间的耦合关系。对应轨道网络和城市轨道交通线路两种场景，根据点和边的不同定义构建了两类优化模型;根据点和边的性质设计了回溯搜索系统性延误源的关键路径算法，并基于关键路径结果分析延误传播机理。算例研究指出，本文提出的关键路径算法能准确找到延误源，且关键路径元素包含受延误源影响的时刻、列车编号及区间车站编号等延误信息，能为延误传播分析及运行图调整提供支持。另外，通过消除搜索到的延误源，系统节省了超过20％的能耗和超过10％的列车旅行时间。
　　4.基于列车状态图，建立了列车运行图调整模型，并设计了两阶段优化算法。在第一阶段，进一步改进了关键路径算法，基于列车流模拟结果对延误实现并行搜索，并用不同的关键路径串联起对应不同延误源的延误信息。在第二阶段，设计了整合信息搜索的混合遗传算法，以关键路径结果为输入，并根据模拟结果设定基因值下界，不仅缩小了优化范围，还加快了收敛速度。算例研究表明，本文提出的优化算法能兼顾宏观优化目标和微观控制策略，对延误情境下的列车运行图进行快速有效的调整。与调整前相比，本文的调整结果最多节省了超过15％的延误成本和能耗成本;与传统遗传算法相比，本文的算法节省了超过75％的计算时间，且优化率最多能提升10％。另外，本文的算法能提供更符合运营企业实际需求（运行图调整幅度更小）的调整方案。

目录

声明

致谢

摘要

1绪论

1．1研究背景及意义

1．2国内外研究现状

1．2．1列车运行图编制问题

1．2．2列车运行图调整问题

1．3列车运行图优化模型与算法面临的问题

1．3．1面临的问题

1．3．2本文的解决思路

1．4本文主要内容与组织结构

2列车运行图优化基础模型与算法

2．1列车运行图优化模型

2．1．1基于离散时空图的0-1整数规划模型

2．1．2滚动时域模型

2．2列车运行图优化算法

2．2．1模式搜索算法与增广拉格朗日乘子算法

2．2．2遗传算法

2．2．3分支定界法

2．2．4关键路径算法

2．3本章小结

3考虑时变客流与车辆成本的运行图编制模型与算法

3．1问题背景

3．1．1研究动机

3．1．2符号与假设

3．1．3城市轨道交通列车运行图编制问题描述

3．2模型构建

3．2．1停站过程分析建模

3．2．2目标函数及约束条件

3．2．3整体优化模型

3．2．4基于离散时空图的优化模型

3．3优化算法

3．3．1问题分解

3．3．2子问题OST的求解算法

3．3．3子问题OH的求解算法

3．4算例研究

3．4．1小规模算例

3．4．2基于北京地铁4号线的算例

3．4．3灵敏度分析

3．5本章小结

4考虑节能控制与线路约束的列车流模拟模型与算法

4．1问题背景

4．1．1研究动机

4．1．2速度时分曲线的几种形式

4．2列车运行过程分析及建模

4．2．1符号和假设

4．2．2列车运行过程的动力学分析

4．2．3列车流模拟模型

4．3列车流模拟算法

4．3．1设计思路

4．3．2 "理想速度时分曲线"的生成

4．3．3工况选择策略

4．3．4列车状态更新

4．3．5总体框架

4．4算例研究

4．4．1单一区间下的算例研究

4．4．2北京地铁亦庄线实例研究

4．5本章小结

5轨道系统延误源搜索及延误传播分析模型与算法

5．1问题背景

5．1．1研究动机

5．1．2不同场景下延误源的产生及传播

5．2模型构建

5．2．1符号及假设

5．2．2约束条件

5．2．3基于轨道网络(场景1)的优化模型

5．2．4基于城市轨道交通线路(场景2)的优化模型

5．3关键路径算法

5．3．1基于轨道网络(场景1)的关键路径算法

5．3．2基于城市轨道交通线路(场景2)的关键路径算法

5．4算例研究

5．4．1基于轨道网络的算例研究

5．4．2基于城市轨道交通线路的算例研究

5．5本章小结

6基于列车流模拟与延误传播分析的运行图调整模型与算法

6．1问题背景

6．1．1研究动机

6．1．2城市轨道交通列车运行图调整问题描述

6．2模型构建

6．2．1符号及假设

6．2．2优化模型

6．3优化算法

6．3．1改进的延误源搜索关键路径算法

6．3．2混合遗传算法

6．4算例研究

6．4．1延误源搜索关键路径算法结果分析

6．4．2混合遗传算法结果分析

6．4．3灵敏度分析

6．5本章小结

7结论与展望

7．1结论

7．2未来研究展望

参考文献

附录

作者简历及攻读博士学位期间取得的研究成果

学位论文数据集