廖正文, 苗建瑞, 孟令云, 李海鹰, 赵 岚
(1. 北京交通大学 轨道交通控制与安全国家重点实验室,北京 100044;2. 北京交通大学 交通运输学院,北京 100044; 3. 西安铁路职业技术学院,陕西 西安 710014)
列车运行图是铁路行车组织的基础,编制和优化运行图是铁路运输组织领域的经典问题。对此,各国专家学者建立目标和约束条件各异的优化模型,并根据模型特点,设计不同的求解算法。但利用数学规划方法对列车运行图进行优化,精确的算法只能求解小规模算例,对于大规模问题必须采取不同的策略将原
问题分解或简化,以求降低问题的规模,如国外CAREY[1]、CAREY and LOCKWOOD[2]、CASTILLO[3],国内周磊山[4]、彭其渊[5]、史峰[6]等均根据问题的不同特点设计基于问题分解的启发式求解算法。
列车运行图优化,无论是既有线上以旅客列车总旅行时间最短、货物列车开行数量最多,还是客运专线上以列车服务频次高、旅行时间短等为目标,本质均是有限时空资源分配的组合优化问题,尽管当前计算机运算速度和储存空间有较大发展,但是列车运行图的组合规模决定人们依然难以使用传统的方法直接求解大规模问题。因此,目前解决这类问题的思路主要分为两大类:一类为采用模拟人工编图的启发式算法或遗传算法、模拟退火算法等智能优化算法;另一类为将复杂的原问题分解为相对容易求解的子问题,进而获得原问题的较优解。国外有研究采用拉格朗日松弛算法求解列车运行图问题[7-12],该研究表明拉格朗日松弛算法对于求解列车运行图问题具有一定的适用性,并且能够通过分析优化间隔评价求解结果的质量,是解决列车运行图优化问题的高效方法。……