高速列车周期性开行方案优化模型与交叉熵算法

中国高速铁路不同车站之间，旅客对乘车时间、频次、直达与中转等列车服务要求的异质特征明显. 如何在一个周期内(如1 h 或2 h)用有限的列车起讫点和停站方式组合，满足多样化客流需求是制定周期性列车开行方案所面临的问题. 建立整数规划模型，确定一个周期内大站停、隔站停多个层级列车的起讫点、停站、开行频率和编组，保证站间直达率，满足旅客异质需求. 模型从按特定规则生成的备选列车集合中优选列车，同时决策其开行频率，实现列车开行成本最低. 针对问题特点设计交叉熵算法，与CPLEX软件的实例求解结果和计算效率进行对比.结果表明，所提算法能有效求解大规模实际问题，列车开行方案服务指标较优.

Model and Cross Entropy Algorithm for Periodic Line Planning Problem of High-speed Trains

Passengers between different stations in China's high- speed railway have obviously heterogeneous demand for trip time, frequency, direct or transfer service. A periodic line plan is required to use limited combination of train OD and stopping patterns in a short period (e.g. 1 h or 2 h) to meet diverse passenger demand. In this paper, an integer programming model is established. The train OD, stops, frequencies and compositions in a period are determined for classified trains which either stop at major stations or skip-stop a subset of stations. A high non-transfer rate is ensured, and heterogeneous passenger demand is satisfied. The model selects trains from a set of candidate lines generated according to specific rules, decides their frequencies, and minimizes the operation cost. A cross entropy algorithm is designed, the instance solutions and computation efficiency are compared with those of CPLEX software. Results show that the proposed algorithm is effective when the problem size is large, and service indicators of line plans perform well.