第1章绪论
本章分析了轨道列车时刻表问题的现实及科学意义，介绍了列车运行图、时空网络、客流需求等基础概念.讨论了列车时刻表研究领域国际学术界重要的研究问题、建模方法和求解算法，*后给出了全书的内容结构.
1.1基础概念
轨道交通是指运营车辆需要在特定轨道上行驶的公共交通模式.在我国，轨道交通包括高速铁路(时速不低于250千米)、快速铁路(时速介于160千米至250千米之间)、普速铁路(时速低于160千米)以及城市轨道交通(含地铁、轻轨、有轨电车)等4种类型.轨道交通是节能环保的绿色交通方式，在综合交通系统中具有明显的竞争优势.一般而言，在重要城市节点间的旅客运输中，高速、快速铁路优势明显;在中长距离大宗货物运输中，快速、普速铁路以运量大、成本低而著称;城市轨道交通，则具有运量大、频率高、准时、节能环保的优势，是缓解城市交通拥挤*有效的手段.大力发展轨道交通，已成为世界各国的共识与潮流.
列车时刻表由轨道运营企业编制，它详细规定了列车占用区间的次序以及在每一个车站的到达、出发和通过时刻，其时空图示形式又称为列车运行图，是轨道企业*重要的技术文件以及协调轨道交通不同部门、工种、环节进行运输生产活动的基础(杨浩，2017;毛保华，2017;胡思继，2013).列车时刻表是连接轨道交通服务供给和需求的桥梁，它向社会全面展示了轨道企业提供的服务产品，用户可以根据各自的需求有偿使用这些列车服务.从轨道列车的服务对象来看，可分为旅客运输需求和货物运输需求两类.根据问题的重要性、应用的广度和研究的热度，本书重点关注旅客列车时刻表优化问题.
列车时刻表设计，*大的困难是如何处理不同列车占用轨道资源引发的时空冲突，这种时空冲突与列车运行追踪、越行、交汇耦合在一起，构成了复杂的约束条件.这类问题的决策优化，是在特定的时空网络中，为每个列车确定一条合理的移动路径，使基于乘客的度量指标(如旅行时间)或企业的度量指标(如运营成本)等达到*优(彭其渊等，1995;倪少权等，2003;牛惠民，2021).轨道列车时刻表优化问题，数学上是典型的大规模、多目标、强耦合的整数或0-1规划模型，其中加入需求因素并嵌入旅客行为，将使问题变得异常复杂.根据不同的运营环境和约束要求，构建列车时刻表问题合理的数学模型、设计有效的求解算法，是非常具有挑战性的科学难题.
现实的轨道列车时刻表，主要是基于某些简化条件和已知参数而设计的，如基于时段均衡或给定停站方案的列车时刻表，设计中没有或较少考虑客流需求的时变特征，又称为基于供给的列车时刻表(Supply-Based Train Timetable).这种类型的列车时刻表，往往会造成客流需求高峰时段旅客不能乘上期望的列车，而在非高峰时段列车能力虚糜的现象，难以实现列车运行线和客流需求时空分布的合理匹配.轨道运营部门已经意识到了该问题的弊端并着手进行修正，如我国铁路个别线路或区段试行的“一日一图”做法，就是试图在不同的客流需求条件下使用差异化的列车运行图.
在列车时刻表阶段直接使用客流需求，会明显增加问题的难度.首先，客流需求具有连续、时变的属性，而列车运行线则有离散、稳定的特点，利用解析方法将两者耦合为一个整体，将极大增加数学建模的难度;其次，建模中使用时变的客流需求会导致出现非线性表达式，必然会使模型的求解变得更加困难，特别是对于繁忙的高速铁路走廊或城市地铁线路，问题的复杂性会极度增加甚至无法克服.
因此，迫切需要系统化、科学化的理论和方法，从根本上解决复杂环境条件下列车时刻表的优化问题.本书主要内容，就是研究如何设计真正意义上面向需求的轨道列车时刻表，以匹配时变异质的客流需求，向社会提供高质量的旅客列车服务产品.
1.1.1列车运行图
实际上，列车时刻表给出了每个列车从始发至终到的整个过程中，在空间和时间维度上的演变细节，包括列车沿途经过的车站以及到达、出发和通过车站的准确时刻.从狭义角度讲，列车时刻表详细指定了列车时空移动的轨迹坐标.如表1.1所示，是一个典型的高铁列车时刻表.利用这样的列车时刻表，铁路运营部门可以实时组织列车途经区间和车站的技术作业，旅客可以提前安排自己的出行活动.
当乘客利用轨道交通出行时，通常需要考虑途经出发站与目的站之间线路上的多个列车，以选择*适合自己的服务产品.对于铁路运营管理部门，则更关心运行在该线路上彼此关联的全部列车(或列车流)，以有序合理地安排沿线车务、机务、工务、电务和车辆部门的工作.列车时刻表的优化，应该考虑当前线路上所有列车的移动计划.具体地，为该线路上每个列车确定一条合理的时空路径，消除不同列车之间占用时空资源的冲突，*大限度地实现供给和需求双方利益的*大.
根据这样的考量和认识，学术上所指的列车时刻表基本上都是基于线路的广义列车时刻表(Single-Line Train Timetable)，即线路上所有列车的时空移动计划.
在计划编制阶段，不失一般性，通常假定任意列车在每个区间的运行速度恒定.在直角坐标平面内，以时间为横轴、空间为纵轴(欧洲国家多用时间为纵轴、空间为横轴)，可以组成二维时空平面.在二维时空平面中，按照一定的比例关系，将列车运行轨迹用若干条线段连接出来，就可得到相应的列车运行线.类似地，对于所考虑的轨道线路，全体列车运行线的总体，称为该线路的列车运行图，图1.1显示了京沪高铁简化后的列车运行图.列车运行图的基础概念，在许多教科书中都有详细的介绍，本书在此不再赘述.
图1.1含G107的列车运行图(2018年3月)(见文后彩图)显然，列车运行图就是列车时刻表的时空图示，两者之间本质上没有差异.利用列车运行图，可以清楚地获悉每个列车的移动细节及不同列车间的逻辑关系.
在轨道交通内部，列车运行图则更为现场工作人员习惯和熟知，是轨道行业*重要的技术文件.实践中，轨道运营部门会定期编制列车运行图，随着客流需求大小和时空分布变化的加剧，频繁编制或修改列车运行图已成为常态.对应地，在研究列车时刻表问题的文献中，为了便于比较和分析计算结果，总是将列车运行图作为*后的输出呈现出来.需要说明的是，在理论研究层面，列车时刻表(Train Timetable)的称谓更被国际学术界所认可，而在有些场合，列车调度问题(Train Scheduling Problem)也等同于列车时刻表问题.
在研究轨道列车时刻表及相关问题时，为了直观地展示研究内容，特别是列车与列车之间、列车与车站之间、列车与乘客之间的复杂关系，通常会画出列车运行图的简化形式，其中仍然以时间和空间为维度，但不必硬性规定横轴与纵轴的具体含义;*为重要的是，不深究各类对象的准确坐标，而重点关注它们之间的时空逻辑关系，如两个节点之间相对的左右、上下位置，这样得到的图形表示形式，称为列车运行时空网络(Space-Time Network).以下介绍本书经常提到的两类特殊列车运行图，了解和熟悉它们，有助于设计更加普遍和复杂的列车时刻表.
1.平行运行图
如果同方向的列车在同一区间的运行速度相同，称为平行运行图.平行运行图结构简单，所有列车运行线相互平行，可以*大化地使用线路通过能力，对应于只有单一速度等级列车的情况.实践中，有纯平行运行图和广义平行运行图两种类型.纯平行运行图除了具有相同的区间运行速度，还有相同的列车停站模式和停站时间，这类运行图不考虑列车之间的越行，通常在城市轨道交通或短距离城际铁路中选用.广义平行运行图更加灵活多样，它除了区间运行速度相同，列车在一个车站是否停站、停站多长时间，都可以根据需要自由选择，不同列车之间还可以选择是否进行越行，这样的列车运行图为旅客出行提供了多样化的服务选择，有利于轨道运营企业降低成本和节约能耗.通常情况下，远距离高铁线路多使用广义平行运行图.近年来，个别城市轨道交通也尝试使用这种运营模式.
2.均衡运行图
在列车运行图中，如果所有列车的时间间隔或车头距(Headway)始终相同，则称为均衡(或等间隔)列车运行图.完全均衡的运行图很少直接在实践中使用，但可以由此生成其他更为复杂的列车运行图.例如，以均衡运行图为基础，修改部分列车的停站模式和停站时间得到的运行图.特别地，为了满足客流需求分布的时间不均衡性，可进一步生成基于阶段均衡的列车运行图.具体地，将运营日划分为若干个时段，如高峰和非高峰时段，或者1小时为1个时段，在每个时段采用均衡列车运行图.阶段均衡的列车运行图按阶段设置各自不同的发车间隔，能够较好地匹配时变的客流需求(Niu and Zhang，2012)，因而在实践中较多选用.
1.1.2运营环境
在列车时刻表问题中，不同的运营环境将导致不同的研究假设、建模框架、求解算法和计算复杂性，本章主要分析以下两种运营环境.
1.网络结构
单条线路(或走廊)的情形，是列车时刻表问题*主要的研究对象.在这样的运营环境中，只需关心该线路上列车移动和乘客上下车情况，不必考虑不同线路上列车之间的到发接续或者客流中转换乘问题，这类情形是目前学术界主要的研究对象.在单线路的运营环境中，根据所有列车的始发站和终到站是否相同，可以分为列车运行区段相同和运行区段不同的时刻表问题.大部分的城市轨道交通和短距离城际铁路，多采取列车始发和终到站相同的运行模式;长距离的高速铁路走廊，如我国的京沪高铁，则选择始发和终到站不同的运行模式，此时每个列车都有各自的始发站和终到站.值得注意的是，对于当前线路上开行的跨线列车，只要视列车上线接轨站为始发站、下线接轨站为终到站，则这类列车可认为是运行在当前线路上相应区段的本线列车.由于要考虑客流在接轨站的中转换乘，含有跨线列车的时刻表问题会复杂许多.
由多条线路组成的轨道交通网络，是更一般的列车运营环境.研究这类时刻表问题的直观方法，是先设计单条线路的列车时刻表，然后根据一定的优化目标，将多个单线路列车时刻表合并成网络列车时刻表(Network-Wide Train Timetable).
需要指出的是，目前无论是理论研究还是实践应用，均没有非常理想的方法处理网络时刻表优化问题.这类问题*合理的优化目标，是考虑不同线路列车在枢纽站的有效接续，但这很难照顾到全部列车和全部枢纽车站，因为部分列车在部分车站的良好接续，就有可能牺牲其他列车在其他车站的衔接效果(Tianand Niu，2019).
同时，列车接续和乘客换乘应该同步考虑，而问题中一旦出现客流需求，模型的复杂性将急剧增大，从而影响*后的优化质量.基于这样的考虑，有些文献转而研究网络环境下部分特殊列车(如早班或晚班列车)时刻表的优化问题(Kangetal.，2016;Kangand Meng，2017).
2.速度等级
在研究列车时刻表问题时，速度等级是另一类重要的考虑因素，不同的速度等级将导致不同的构模假设.对于大多数城市轨道交通或短距离城际铁路，单一速度等级是*常见的运输组织模式，在这样的运营环境中，所有列车具有相同的运行速度，可以实现*大的线路通过能力.
多种速度等级是更一般的列车运行组织模式，对于中长距离的铁路走廊，通常会采用这种方式，它可以满足多样化、异质化的客流需求以及部分跨线列车的运行需要.例如，在我国的京沪高铁走廊上，长期开行高速列车和动车组列车两种速度等级的列车;兰渝线开行时速160千米和120千米的旅客列车以及80千米的货物列车.实际上，在单一速度等级的列车运行环境中，选择多样的列车停站模式，会导致实际的列车旅行速度不同.对于多等级速度的运营环境，必然会发生不同列车之间的越行问题，相应的列车时刻表问题会变得异常复杂.本书第5、6章，将对越行环境下多等级列车时刻表优化问题进行详细讨论.
1.1.3客流需求
1.不直接使用客流需求
从本质上讲，尽可能实现客流需求与列车运
展开
