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

doi:10.16381/j.cnki.issn1003-207x.2016.06.019

摘要/Abstract

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

关键词: 优化模型, 收益管理, 客运专线, 列生成算法

Abstract: 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.

Key words: optimization model, revenue management, passenger railway, column generation algorithm

中图分类号:

蓝伯雄, 王童姝. 大规模客运专线网络运营优化模型与求解算法[J]. 中国管理科学, 2016, 24(6): 159-170.

LAN Bo-xiong, WANG Tong-shu. Optimization Model and Algorithms for Large-scale Rail Passenger Transport Network Operation[J]. Chinese Journal of Management Science, 2016, 24(6): 159-170.

参考文献

[1] Ben-Khedher N, Kintanar J, Queille C, et al. Schedule optimization at SNCF:From conception to day of departure[J]. Interfaces, 1998, 28(1):6-23.

[2] Goossens J W, Van Hoesel S, Kroon L. A branch-and-cut approach for solving railway line-planning problems[J]. Transportation Science, 2004, 38(3):379-393.

[3] Goossens J W H M. Models and algorithms for railway line planning problems[D]. Massitricht, Netherlands:Maastricht University, 2004.

[4] Schöbel A. Line planning in public transportation:Models and methods[J]. OR Spectrum, 2012,34(3):491-510.

[5] Claessens M T, van Dijk N M, Zwaneveld P J. Cost optimal allocation of rail passenger lines[J]. European Journal of Operational Research, 1998, 110(3):474-489.

[6] Bussieck M R. Optimal lines in public rail transport[D]. Germany:Technische University, Braunschweig, 1998.

[7] Goossens J W H M. Models and algorithms for railway line planning problems[D]. Massitricht, Netherlands:Maastricht University, 2004.

[8] Goossens J W, van Hoesel S, Kroon L. On solving multi-type railway line planning problems[J]. European Journal of Operational Research, 2006, 168(2):403-424.

[9] Dienst H. Linienplanung in spurgeführten Personenverkehr mitHilfe eines heuristischenVerfahrens[D].Technische Universität Braunschweig (in German),1978.

[10] Bussieck M R, Kreuzer P, Zimmermann U T. Optimal lines for railway systems[J]. European Journal of Operational Research, 1997, 96(1):54-63.

[11] Schöbel A, Scholl S. Planung von Linien mit minimalen Umsteigevorgängen[C]//Proceedings of the GOR-work shop on "Optimierung im öffentlichen Nahverkehr, 2003:69-89.

[12] Schöbel A, Scholl S. Line planning with minimal traveling time[C]//Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS105). Palma de Mallorca, Spain, October 7, 2005.

[13] Scholl S. Customer-oriented line planning[D]. Kaiserslauternn, Germany. Technische Universität Kaiserslautern, 2006.

[14] Nachtigall K, Jerosch K. Simultaneous network line planning and traffic assignment[C]//Proceeding of 8th workshop on Algorithm Appriaches for Transportation Modelling, Optimization, and Systems (ATMOS'08), Karlsruhe, Germany, September 18, 2008.

[15] Dorhout P. Building rail revenue management on an airline foundation-Choosing wisely from a mixed bag[J]. Journal of Revenue & Pricing Management, 2014, 13(3):261-264.

[16] Ciancimino A, Inzerillo G, Lucidi S. A mathematical programming approach for the solution of railway yield management problem[J]. Transportation Science, 1999, 33(2):168-181.

[17] Kraft E R, Srikar B N, Phillips, R L. Revenue management in railroad applications[J]. Transportation Quarterly, 2000, 54(1):157-176.

[18] Hood I S A. Merlin:Model to evaluate revenue and loadings for intercity[M]//Ingold A, Yeoman I, McMahon-Beatrie U. Yield management:Strategies for the service industries, Thomson Learning, 2000:98-110.

[19] Bharill R, Rangaraj N. Revenue management in railway operations:A study of the Rajdhani Express, Indian Railways[J]. Transportation Research Part A:Policy and Practice, 2008, 42(9):1195-1207.

[20] You Pengsheng. An efficient computational approach for railway booking problems[J]. European Journal of Operational Research, 2008, 185(2):811-824.

[21] Hetrakul P, Cirillo C. A latent class choice based model system for railway optimal pricing and seat allocation[J]. Transportation Research Part E:Logistics and Transportation Review, 2014, 61(61):68-83.

[22] Kroon L, Maróti G, Nielsen L. Rescheduling of railway rolling stock with dynamic passenger flows[J]. Transportation Science, 2014, 49(2):165-184.

[23] Armstrong A, Meissner J. Railway revenue management:Overview and models[R]. Lancaster University Management School, Working Paper, 2010.

[24] Zhang Xiaoqiang, Li Jingfan, Zhuang Qianqiu. An overview of railway revenue management in China[C]//Proceedings of 2014 International Conference of Logistics Engineering and Management (ICLEM), Shanghai, Octobeer 9-11, 2014.

[26] 蓝伯雄,张力.高速铁路客运专线的收益管理模型[J].中国管理科学,2009,17(4):53-59.

[27] 蓝伯雄,吴李知.高速铁路客运网络列车开行方案优化模型[J].中国管理科学,2010,18(6):51-58.

[28] 蓝伯雄,吴李知.铁路客运网络列车开行方案优化模型的列生成算法[J].运筹与管理,2012,21(1):1-10