大规模客运专线网络运营优化模型与求解算法

本文在分析铁路运营优化模型的研究进展的基础上,提出了一个适合大规模客运专线网络运营的优化模型,并提出了求解此模型的列生成算法和启发式快速算法。目的是将客运专线网路的开行方案优化与动态收益优化问题结合起来,解决更大、更复杂的客运网络运营优化问题。模型以列车运营总收益最大化为目标。用随机生成数据进行的模型试验表明,模型及算法可以在较短的时间内求解较大规模的收益管理优化问题。

Optimization Model and Algorithms for Large-scale Rail Passenger Transport Network Operation

China has operated the largest high-speed railway network in the world. However, the existing methods of operation management are not adjusted to fit the technology advantage and the new operation environment, leading to the restriction of the service improvement. The application of optimization technology and revenue management method to the rail passenger operation practice is necessary for improving the operation and service efficiency. A optimization model for large-scale rail passenger transportation operation is proposed in this paper, which combines line planning model and revenue management model. The new model can solve more complicated operation problem of the railway network with multi-lines, multi-trains, multi-discount levels and dynamic demand. It optimizes seat allocation among trains and finds the optimal train departure schedule to maximize the total operational revenue. The passengers' purchase behaviors is also considered in the model with estimated transfer probabilities between different ticket discount level. A column generation algorithm and two fast heuristic algorithms are introduced in this paper, which solve the large-scale mixed integer program model more efficiently. Using randomly generated data, a group of test models with two by two line network structure are solved by XPRESS software. Numerical results shows that the column generation algorithm and fast heuristic algorithms can reduce the model scales and computational complexity. The heuristic algorithms may increase the solving efficiency more than ten to hundred times with tiny sacrifice of solution accuracy. It's concluded that the new model and algorithm is suitable to solve large scale railway network optimization model which is close to real application.