铁路客运网络列车开行方案优化模型的列生成算法

列车开行方案的设计是铁路旅客运输组织规划中的一个重要环节。本文首先给出了一个综合考虑铁路旅客运输的经济效益和公共服务性的优化模型,以铁路旅客运输的公共效益最大化为目标,对整个铁路客运网络上不同始发-终到和不同停站方式的列车开行方案进行优化。然后提出了一个求解此模型的启发式列生成算法,该算法与标准列生成算法相比,可以减少迭代次数并缩短收敛时间。最后给出一组利用随机生成的网络和需求进行求解的算例,验证本算法可以在较短时间内求解较大规模的铁路网络列车开行方案优化问题,并能有效缩小问题规模。

A Column-generation Approach to Line Planning in Rail Passenger Transport

The line planning problem is one of the fundamental elements in strategic planning of public rail transport.It consists in finding lines and corresponding frequencies in transport network such that a given demand can be satisfied.So far,most of the models in the literature aim to minimize the costs or to maximize the number of direct travelers.In this paper we present a new approach maximizing the operator ’s profit,while ensuring the nature of its public services.This new MIP(mixed integer programming)model takes into account of the operating cost,the number of direct travelers,and the total number of transported travelers.In addition,we introduce a heuristic column generation algorithm to solve the base model.Our column generation algorithm can effectively reduce the problem size.Numerical results of randomly generated data are presented.