轮乘制下铁路客运专线乘务计划优化编制理论和方法

针对我国铁路现有乘务模式已难以适应客运专线运输特点，以及乘务员运用效益低下、计划编制手段落后的问题，拟围绕"轮乘制"下我国铁路乘务计划的优化编制理论和方法展开研究，解决轮乘制下的乘务计划优化编制问题（这是世界公认的NP难问题），特别是处理具有我国特色的乘务规则，包括人车捆绑、多班型、多乘务基地、换班时间窗等约束限制。主要内容包括两个方面：1）根据我国当前乘务模式和客运专线运输组织的特点，以及我国乘务员运用的特色约束，建立我国的乘务计划问题的科学定义，并建立列车乘务计划和机车乘务计划问题的统一模型；2）通过研究超启发式方法的融合，研制出能够支持轮乘制、解决我国的客运专线列车和机车乘务计划问题的优化方法。此项研究将为我国客运专线实施轮乘制提供理论和技术支持，有助于较大幅度提高乘务资源效益和管理水平，同时也可以应用于城际铁路、地铁等多种公共交通乘务计划问题，并丰富了运筹学应用研究理论。

针对我国铁路现有乘务模式已难以适应客运专线运输特点，以及乘务员运用效益低下、计划编制手段落后的问题，本项目围绕“轮乘制”下我国铁路乘务计划的优化编制理论和方法展开了研究，主要内容包括三个方面：（1）调研国内外乘务调度现状并定义科学问题；（2）建立能够适应轮乘制且更好反映现实约束的问题模型；（3）研究多种解决方法。该项目已经按计划完成，主要研究成果如下：.一、基于对实际问题的调研和分析，定义了更加通用的乘务调度科学问题. 对美国和加拿大的乘务调度问题进行了实际调研。包括访问麻省理工大学、乘务计划商业系统研发企业和公共交通运营企业，深入了解了其轮乘制下的乘务计划工作实践。. 对我国部分铁路客运专线，包括武广、京津、武汉至合肥等铁路段的高铁、动车或城铁的运营组织情况也进行了调研，分析了现有调度手段与方法，特别是归纳和总结出具有我国特色的轮乘制下的乘务调度规则，并且把西方较通用的乘务规则与我国特色的乘务规则融合起来，定义了更加通用的乘务调度问题。.二、建立了带有多种特色约束和复杂约束的乘务调度问题模型. 归纳和总结了轮乘制下我国铁路客运专线乘务调度问题的各种约束，建立了能够更准确反映现实问题的新模型，包括：1）带有中式用餐约束的乘务调度模型；2）具有多班型和多乘务基地的乘务调度模型；3）带有多种外加约束的乘务调度模型；4）带“时间窗”的乘务调度模型。.三、研制了多种求解方法.1.研究了多种潜在班次生成方法。不仅能够不需要进行问题简化，直接处理中式用餐约束、时间窗等问题，而且还能够借助这些约束的特性，在不损失最优解的前提下降低问题规模，进而提高调度算法的求解能力。.2.研究了多种求解乘务调度问题的智能计算方法。1）研制了一个新算法--分布估计算法（EDA）.其中，首先利用乘务调度问题特点，设计了一系列候选班次选择“规则”；然后，基于这些规则，定义了贝叶斯网络。该算法不同于传统的遗传算法，具有精确学习机制。2）研制了一个自适应演化计算的乘务调度方法（AECS）。其主要创新点在于：设计了一个新的染色体表示方法，调度过程中染色体长度可以自适应变化。实验证明该算法的求解质量和速度都显著优越。.3.研究了求解乘务调度问题的列生成技术。主要包括：利用乘务调度问题特点，加快列生成算法的收敛速度；研制了能够解决多种外加约束的列生成方法。