蒲 松， 吕红霞,2,3， 陈钉均,2,3， 倪少权,2,3

(1. 西南交通大学 交通运输与物流学院，四川 成都 610031；2. 西南交通大学 全国铁路列车运行图编制研发培训中心，四川 成都 610031；3. 综合交通运输智能化国家地方联合工程实验室，四川 成都 610031)

高速旅客列车开行方案编制计划(High Speed Railway Passenger Train Line Planning Problems,HSRPTLP)是旅客列车运行计划的核心环节，简称开行方案。开行方案在给定路网设施的条件下，根据起讫站间客流量确定列车的运行路径、开行对数、等级与停站方案等要素，并尽可能地降低运输企业的运营成本与旅客的出行成本。

影响HSRPTLP因素众多，优化内容包括多个方面，因而建模和求解均存在一定难度。既有研究几乎均对HSRPTLP进行简化，如Bussieck、 Claessens、杜欣等[1-4]在已知列车停站方案与客流分配的基础上，建立整数规划模型优化列车运行路径、开行对数; Borndorfer、付慧伶、佟璐等[5-7]预先给定停站方案，协同优化列车运行路径与客流径路;Chang、Park等[8-9]预先确定列车的起讫站，从运输企业与旅客两方面出发，建立多目标整数规划模型确定列车开行对数、运行路径、停站方案及客流分配，并分别用于研究台湾、韩国高速列车开行方案问题;史峰等[10-11]考虑运输企业与旅客之间不对等的博弈关系(Stackelber博弈)，建立双层规划模型，但因结构较复杂，很难得到全局最优解[12]。HSRPTLP属于NP-hard问题[1-3，5]，没有有效的多项式算法，传统的分支定界算法、拉格朗日松弛算法等很难在有效时间内获得最优解。蚁群算法、模拟退火算法、遗传算法等智能算法虽然能在有效时间内获得满意解，但很难保证解的质量。……