摘要
如何在考虑线路通过能力等复杂约束的基础上,快速编制高质量的车流径路方案,以期降低运输总成本,是铁路运输组织过程中面临的重要难题之一.针对铁路车流径路的树形径路特征,将相同到站的所有车流视为一个整体,同步考虑并提出入树的概念,进而将问题转化为求解每个终到站(树根节点)的入树方案;在此基础上,对经典的基于弧段的多商品流模型采用入树选择变量进行重构;针对重构模型的结构特点,提出两阶段求解方法,第1阶段采用列生成算法得到有潜力的入树方案池,第2阶段在方案池中对每个树根优选出符合条件的入树方案,进而得到每支车流的径路;最后,利用中国西南地区路网数据构造不同规模路网的算例,对算法性能进行验证.研究结果表明:本文方法能在较短时间内获得近似最优解,相较于CPLEX和模拟退化算法,列生成算法的求解效率更高、求解质量更佳;相较于弧段模型,入树模型具有更低的模型复杂度.
One significant challenge in railway transportation organization is how to quickly develop high-quality wagon flow routing schemes while considering complex constraints such as line capacity,with the aim of minimizing total transportation costs.Given the distinct tree structure of wagon flow routes,all the wagon flow towards the same destination station was considered as a whole,and the concept of in-tree was proposed.By doing so,the flow routing problem could be transformed into determining the in-tree scheme for each destination station(i.e.,root node).On this basis,the classic arc-based multi-commodity flow model was reformulated using the in-tree selection variables.Subsequently,a two-stage solution approach was proposed in consideration of the structure of the reformulated model.The first-stage model aimed to generate a pool of promising in-tree schemes by using the column generation algorithm.The second-stage model was intended to select the best in-tree scheme for each root and obtain the wagon flow routes.Finally,by using basic data from the railway network in Southwest China,test instances of varying network scales were constructed to evaluate the algorithm’s performance.The results demonstrate that the proposed method can obtain near-optimal solutions within a short computation time.Compared to CPLEX,the column generation algorithm achieves higher solution efficiency;compared to a simulated annealing algorithm,it delivers better solution quality.The in-tree model exhibits lower model complexity and higher computational efficiency than the traditional arc-based model.
作者
范丁元
彭其渊
赵军
王家喜
FAN Dingyuan;PENG Qiyuan;ZHAO Jun;WANG Jiaxi(School of Civil Engineering,Southwest Jiaotong University,Chengdu 610031,China;Planning and Research Institute,Planning and Standard Research Institute of the National Railway Administration,Beijing 100055,China;School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 610031,China;Zhejiang Lab,Hangzhou 311121,China)
出处
《西南交通大学学报》
2026年第2期478-487,498,共11页
Journal of Southwest Jiaotong University
基金
国家铁路集团有限公司科技研究开发计划(N2023X025)。
关键词
铁路车流
树形径路
整数规划模型
列生成算法
列车编组计划
wagon flow
tree-shaped path
integer programming model
column generation algorithm
train formation plan
