随着我国高速铁路的快速发展,人们对高速铁路的服务要求越来越高,高速铁路列车运行图作为高速铁路运输组织的基础,是高速铁路运输组织的核心技术文件,它的编制质量会直接影响到铁路运输各环节的工作效率,从而对高速铁路的服务质量和运输企业经济效益产生影响。高速铁路与普速铁路相比具有速度快,容量大,发车密度大,发车间隔时间小的特点,这就对列车运行图的编制提出了新的要求。列车运行图的编制问题属于超大规模的多目标优化问题,有求解难度较大的特点,通过对高速铁路列车运行图的编制优化进行研究,有利于提高列车运行图的质量,增加高速铁路列车运营的经济效益和社会效益。本文在总结高速铁路列车运行图编制优化理论和研究应用的基础上,首先对高速铁路的图形表示方法和高速铁路列车运行图的编制要素进行了介绍,并就高速列车运行图与普速旅客列车运行图的不同特点进行了对比分析,为后文高速铁路列车运行图编制优化的研究奠定了理论基础。其次,针对高速铁路列车运行图编制问题的性质展开研究,介绍了列车运行图编制问题的NP属性,并最后为列车运行图中的列车运行线构建了时空网络,将列车运行图问题中复杂的列车组合优化问题转换为不同列车运行线的最短路径问题。本文在高速铁路列车运行图编制优化理论的基础上,结合以往优化模型,在考虑车站能力限制的情况下,建立时空网络构建整数规划模型对高速铁路列车运行图编制问题进行求解,并对该模型的各类约束进行了特征分析,确定了列车运行图编制问题中的难约束。针对约束条件中的难约束的存在会大大增加求解难度的特点,首先对约束条件中的难约束进行了松弛处理,然后通过拉格朗日松弛算法对原问题进行迭代更新,求解得到问题的较优可行解。最后本文以武广高速铁路下行方向的列车运行线为案例,在确定了各列车运行线停站方案和高速铁路沿线各车站股道数的基础上,对跨线列车运行线做固定处理,利用建立的整数规划模型与拉格朗日松弛算法对案例进行求解得到结果并进行了比较分析,然后根据求解出的结果铺画列车运行图,并对模型中的参数值进行灵敏度检验和分析。