基于鲁棒优化的城市轨道交通乘务计划优化编制及其应急调整方法研究

The implementation of urban rail transit crew schedule is disrupted frequently by various abnormal interferences, which seriously affects the transportation safety. In order to improve the ability of coping with interferences for crew work organization, this paper will research the relevant methods form plan level and operation level, respectively. In plan level, we will study on crew scheduling model and algorithm based on robust optimization. In this part, by analyzing the common interferences and their characteristics for crew schedule, the sets of schedule buffer mechanism and adaptive adjustment mechanism will be designed, then a bi-objective model for minimizing the total crew duty cost and maximizing the number of buffer mechanism and adaptive adjustment mechanism in the schedule will be learned, after analyzing the mathematical characteristics of the model, an exact algorithm based on column generation approach will be studied. In operation level, the crew rescheduling method will be studied when the plan is disrupted and unusable. In this part, we firstly find out all of the affected duties and some unaffected duties, and take all of the duty segments contained by the duties to form a candidate crew segment set for rescheduling. Then a directed graph in duty segment interactive relations will be formulated, and numbers of replacing duties will be generated to form the candidate replacing duty set by using a depth-first route searching algorithm. Finally, a bi-objective model for minimizing the total crew duty costs and the number of adjusted duty segments will be learned, by analyzing the mathematical characteristics of the model, a heuristic algorithm based on Lagrangian relaxation approach will be studied.

城市轨道交通乘务计划实际执行经常遭受各种异常干扰，影响运输安全。本课题将分别从计划编制和实际执行两层面入手，研究提高乘务组织工作应对异常干扰能力的方法。在计划编制层面，研究乘务计划的鲁棒优化模型及算法，研究方法为：通过分析计划执行的常见干扰因素及其影响特性，设计乘务计划的缓冲机制和自适应调整机制集合；建立以乘务总值乘费用最小和计划具备的缓冲机制和自适应调整机制最多为双重目标的鲁棒优化模型；分析模型特性，设计结合列生成思想的精确求解算法。在实际执行层面，研究计划紊乱情况下的应急调整模型及算法，研究方法为：提取所有受影响和部分未受影响的乘务任务，以其包含的任务段组成参与调整的任务段集合；构建任务段衔接网络有向图，采用基于深度的路径搜索算法搜索一定数量的可行替换任务，形成候选任务集合；建立以调整费用最低和调整变更的任务段最少为双重目标的数学模型；分析模型特性，设计结合拉格朗日松弛的启发式算法。

城市轨道交通日常运营过程中时常出现列车延误、运营中断等列车运行紊乱情况，使得实际列车运行偏离计划，给行车组织、乘务组织工作带来了不确定性，并增加了运营风险。本课题研究基于鲁棒优化的城市轨道交通乘务计划优化编制及其应急调整方法，以期提高行车组织和乘务组织工作的抗干扰能力，保障城市轨道交通的运营安全。本课题在研究行车紊乱影响因素及其机制的基础上，分别研究了客流协同控制、运行图鲁棒优化等方法来提高列车运行的稳定性。同时，设计了考虑灵活班种的乘务计划编制方法、及运行紊乱情况下的应急调整方法，以提高乘务组织工作的稳定性和效率。项目始终按照计划开展工作，执行效果良好，研究过程中共发表SCI期刊论文6篇，EI论文1篇。研究成果研发了2套计算机辅助决策系统，成功应用南昌地铁3条线路和北京地铁机场线。具体地，首先研究了导致列车行车紊乱的主要因素及其影响机理，影响因素归纳为大客流、客流随机性、设备故障、乘务员突发状况等。其中大客流、客流随机性是导致日常行车延误的主要因素，容易进一步引发大面积的行车延误或者中断，需要重点防范。针对大客流因素，研究了面向过饱和地铁线路的客流协同控制方法，通过协同控制多个站点的进站客流量，缓解繁忙站点的客流拥堵，提高行车稳定性和安全性；针对客流随机特性，研究了列车运行图的鲁棒优化方法，通过设计多个客流随机场景，将列车运行图编制问题建立成随机优化模型，提高编制方案的鲁棒性。针对乘务计划鲁棒优化问题，设计了考虑灵活班种的乘务计划优化编制方法，通过考虑多个灵活班种（如尖峰班、替饭班等），提高乘务计划编制的灵活性，使其满足各种情形的列车运行图（如大小交路、高平峰差异等），以保证计划编制的适应性和稳定性。在乘务计划应急调整方面，构建了乘务计划的应急调整模型，以计划调整费用最小和调整量最小为双重目标，构建了相应的集覆盖模型，并设计了快速求解的启发式算法。