趙 翔, 趙 鵬, 李 博
(北京交通大學(xué) 交通運(yùn)輸學(xué)院, 北京 100044)
票額分配是在一定席位能力條件下以客流需求為基礎(chǔ),合理設(shè)置各路徑(OD)票額數(shù)量以提高客座率和客票收益的售票方法。高速鐵路若采用先到先得的售票原則會引起因短途旅客購票而長途旅客無法購買到所需車票,造成部分區(qū)段客票緊張和部分區(qū)段席位虛糜并存的現(xiàn)象,不利于高速鐵路客座能力的利用和客票收益的提高,票額分配是避免上述問題的有效手段。精準(zhǔn)的客流預(yù)測是票額分配的前提,但客流需求具有隨機(jī)性和時變性,預(yù)測結(jié)果的精度難以保證,同時高速鐵路旅客運(yùn)輸是多區(qū)段、多OD需求、多列車、多停站方案的復(fù)雜問題,如何在非確定性需求情況下合理分配票額是提高運(yùn)輸收益的主要難題之一。
航空領(lǐng)域最早開始利用收益管理概念研究席位利用問題,也取得一系列研究成果。高速鐵路旅客列車票額分配問題可以借鑒航空運(yùn)輸?shù)南豢刂颇P?,但是高速鐵路旅客列車票額分配所涉及OD更多,各客流區(qū)段之間關(guān)聯(lián)性更強(qiáng),停站方案更復(fù)雜,因此難以照搬航空領(lǐng)域的研究成果。由于各國鐵路運(yùn)營方式不同,對席位控制問題的關(guān)注點(diǎn)也不盡相同。文獻(xiàn)[1]用確定的線性模型和概率非線性模型研究了意大利鐵路席位控制問題,提出鐵路席位控制問題是一個多區(qū)段、單一票價的收益管理問題,文中假設(shè)需求是連續(xù)獨(dú)立的隨機(jī)變量,采用非嵌套席位控制方法。文獻(xiàn)[2]研究了兩等級票價、多區(qū)段、單列旅客列車的席位控制問題。文獻(xiàn)[3]建立了考慮上座率、收益和旅客公平的鐵路收益管理模型,并通過日本鐵路的實(shí)例對該模型進(jìn)行驗(yàn)證。文獻(xiàn)[4]對印度鐵路旅客列車的超售問題進(jìn)行研究。國內(nèi)專家學(xué)者對適用于我國國情的票額分配方法進(jìn)行了探究。文獻(xiàn)[5]以直接人公里數(shù)最大為目標(biāo),在確定性需求條件下研究多列站站停旅客列車的票額分配方法。文獻(xiàn)[6]建立了列車席位控制和發(fā)車間隔同時優(yōu)化的數(shù)學(xué)模型,研究多區(qū)段、多車次、站站停旅客列車的票額分配方法。文獻(xiàn)[7]以單列旅客列車的預(yù)測客流為基礎(chǔ),以旅客列車全程的客座率、收入以及整體效益最大為目標(biāo),提出先長途后短途、先有座后無座等旅客列車票額分配的主要原則,并給出票額分配的具體算法。文獻(xiàn)[8]以已知的獨(dú)立正態(tài)分布需求為基礎(chǔ),研究兩級票價、嵌套式、多區(qū)段、單列車的票額分配方法,以及旅客buy-up行為對票額分配的影響。文獻(xiàn)[9]通過對需求情景進(jìn)行模擬,研究了嵌套式、多區(qū)段、單列車的票額分配方法。文獻(xiàn)[10]對比了非嵌套式票額控制、嵌套式票額控制、投標(biāo)價格控制三種票額分配方法,對適合我國國情的多區(qū)段單列旅客列車票額分配方法進(jìn)行了探究。文獻(xiàn)[11]通過差分自回歸移動平均模型得到確定性需求的表達(dá)式和隨機(jī)性需求的分布函數(shù),對單列車隨機(jī)票額分配問題進(jìn)行了研究??土黝A(yù)測具有不確定性,在隨機(jī)需求下研究旅客列車的票額分配方法更符合實(shí)際情況。但隨機(jī)需求條件下票額分配的模型和求解更加復(fù)雜,所以單列車的客流預(yù)測和票額分配方法是國內(nèi)外學(xué)者的主要研究對象,對多列車票額分配方法的研究較少,特別是不同列車多種停站方案對票額分配的影響考慮不足。我國高速鐵路路網(wǎng)規(guī)模龐大,運(yùn)輸需求更加復(fù)雜,為了滿足不同OD客流需求,在編制開行方案階段就設(shè)計(jì)了不同列車的多種停站方案。提供相同OD客運(yùn)服務(wù)的旅客列車之間具有可替代性,現(xiàn)有的先客流分配再票額分配的方法缺乏對收益提高的整體考慮,不利于從全部旅客列車角度提高運(yùn)輸收益。
針對以上不足,本文重點(diǎn)考慮了不同列車多種停站方案對票額分配的影響,在各OD隨機(jī)需求下直接以所有旅客列車收益最大為目標(biāo)構(gòu)建多列車多停站方案的票額分配模型,針對模型離散非線性特點(diǎn)設(shè)計(jì)粒子群算法進(jìn)行求解。同時對比先客流分配再以單列車收益最大為目標(biāo)的票額分配方法。
停站方案是在列車運(yùn)行路徑、類別、開行對數(shù)確定后,根據(jù)客流需求及列車協(xié)調(diào)配合情況確定各列車的停站序列。列車停站方案主要有三種基本模式:大站停列車、交錯停列車、站站停列車。大站停列車是指選擇沿途全部或部分客流量較大或有特殊需求的車站??康牧熊?;交錯停列車除在沿線大站停靠外,同時也選擇部分小站???,是大站停和站站停模式的有機(jī)結(jié)合,是高速鐵路旅客列車停站方案的主要模式;站站停列車在運(yùn)行區(qū)段中的各個車站均???,對未滿足客流需求和服務(wù)頻率要求的車站提供服務(wù),并實(shí)現(xiàn)所有站間客流的可達(dá)性。
如圖1所示,一條高速鐵路上共有A、B、C、D 4個??空?,兩列旅客列車,其中列車1在A、B、D??浚熊?在A、B、C、D???。假設(shè)各列車定員為560人,客流需求:(A,D)840人,(A,B)280人,(C,D)280人。方案1不考慮列車停站方案的差異,將客流需求平均分配,將有(C,D)140人的客流需求因無可利用席位而不能被滿足;方案2根據(jù)列車停站方案的不同對票額進(jìn)行了調(diào)整,各OD客流需求均得到了滿足。
從上述票額分配方案的例子不難看出,列車停站方案影響票額分配方案,實(shí)際路網(wǎng)中的停站方案復(fù)雜多樣,只有在整體對不同列車的多種停站方案進(jìn)行考慮,才能制定更合理的票額分配方案,提高席位利用率和運(yùn)輸收益。
(1) 問題描述
相鄰?fù)?空?能夠辦理旅客乘降作業(yè))之間的路段稱為區(qū)段;一個或多個連續(xù)區(qū)段構(gòu)成的旅行線路稱為路徑(OD),其基本特征為途徑區(qū)段、線路長度、客流需求、車票價格等。
假設(shè)一條由L+1個??空竞蚅個區(qū)段組成的高速鐵路上開行了n列旅客列車并有多種停站方案。不同旅客列車同一OD上具有相同的單一票價,各OD上的客流需求由已知的正態(tài)分布函數(shù)進(jìn)行描述。只提供有座車票且不允許超售,以整條高速鐵路客票收益最大為目標(biāo),以各列車各區(qū)段的席位能力為約束,優(yōu)化所有旅客列車的票額分配方案。
(2) 符號定義
m表示運(yùn)行區(qū)段,m=1,2,…,L,整條高速鐵路包括L個運(yùn)行區(qū)段,L+1個??空?;G表示旅客列車集合,g∈G,g=1,2,…,n;(i,j)表示一個或多個連續(xù)區(qū)段構(gòu)成的OD,其中i為OD的起點(diǎn)車站,j為OD的終點(diǎn)車站;Cgm表示列車g在運(yùn)行區(qū)段m上提供的最大席位能力;fij(x)表示(i,j)上的客流需求概率密度函數(shù);μij表示(i,j)上客流需求的平均值;σij表示(i,j)上客流需求的標(biāo)準(zhǔn)方差;pij表示(i,j)上的車票價格;ugij為列車g能否在(i,j)提供服務(wù)的0-1判斷變量,若列車g在i車站和j車站均有???,則ugij=1,否則ugij=0;bgij表示列車g為(i,j)提供服務(wù)的票額限制決策變量,當(dāng)ugij=1時,bgij≥0,當(dāng)ugij=0時,bgij=0。
(3) 模型建立前提和相關(guān)參數(shù)計(jì)算公式
借鑒文獻(xiàn)[1]描述客流需求的方法,各OD客流需求服從獨(dú)立正態(tài)分布,則(i,j)客流需求的概率密度函數(shù)為
1≤i ( 1 ) 每列旅客列車共有L(L+1)/2個票額限制決策變量,當(dāng)有n列旅客列車時,共有n×L×(L+1)/2個票額限制決策變量,這里設(shè)置一個N=n×L×(L+1)/2的搜索空間,對應(yīng)向量B=(b111,b112,…,bgij,…),其中元素bgij在B中的位置為 0.5(n-1)L(L+1)+ ( 2 ) 若列車g在(i,j)的客流需求概率密度函數(shù)fgij(x)可求,借鑒文獻(xiàn)[2]的單列車客票期望銷售量計(jì)算方法,列車g在(i,j)的客票期望銷售量為 ( 3 ) ( 4 ) 式中:Rgij表示列車g在(i,j)的客票期望收益。 n列旅客列車在(i,j)的客票期望收益為 ( 5 ) n列旅客列車的客票期望收益為 ( 6 ) 現(xiàn)有的鐵路12306購票系統(tǒng)是將客票和席位對應(yīng)出售,即列車g在(i,j)的某一席位對應(yīng)的客票一旦售出,則在(i,j)途徑的區(qū)段上該席位不能被再次利用,本文只考慮有座車票且不考慮超售,所以bgij滿足 ?g,m ( 7 ) (4) 多列車多停站方案票額分配模型 基于預(yù)測的各OD客流需求,以高速鐵路客票收益最大為目標(biāo),以各列車各區(qū)段的最大席位能力為約束,建立高速鐵路多列車多停站方案票額分配模型為 ( 8 ) s.t. ?g,mbgij為整數(shù) ?g,i,j ( 9 ) (ugij-1)bgij=0ugij=0,1 bgij≥0 ?g,i,j (10) 本文提出的多列車多停站方案票額分配模型為非線性整數(shù)規(guī)劃,對于這類問題,粒子群算法易于提高初始解、所需設(shè)置參數(shù)少、占用內(nèi)存空間小、大規(guī)模問題的求解性能優(yōu)異。粒子群算法是由Kennedy和Eberhart[12]在1995年源于鳥類捕食行為的研究提出的。使用粒子群算法需要解決初始解的生成、粒子適用值的計(jì)算方法、粒子位置的更新規(guī)則等問題,根據(jù)前述票額分配模型,求解算法如下。 (1) 初始解的生成 在非確定性客流需求條件下,本文提出的模型為非線性整數(shù)規(guī)劃,難以實(shí)現(xiàn)精確求解,若將客流需求變?yōu)榇_定值,則該問題將轉(zhuǎn)化為線性規(guī)劃。因此在初始解生成階段,將非確定性客流需求的平均值作為確定性客流需求取值,松弛整數(shù)約束,建立線性規(guī)劃模型進(jìn)行求解,并將求得最優(yōu)解作為粒子群算法初始解的生成向量。確定性客流需求下的線性規(guī)劃模型為 (11) s.t. ?g,m (12) (13) (ugij-1)bgij=0ugij=0,1bgij≥0 ?g,i,m (14) (15) 式中:rh的各分量服從(-r,r)上的均勻分布,r為整數(shù),其大小可根據(jù)實(shí)際情況而定。 (2) 粒子適用值計(jì)算 (16) (3) 粒子位置更新 (17) (18) (19) (20) 算法流程見圖2,具體步驟為 Step2設(shè)置種群規(guī)模Psize和ω,γ1,γ2等相關(guān)參數(shù)。 Step3計(jì)算所有粒子的適用值并記錄。 Step4設(shè)置輸入?yún)?shù)l=0,h=1,Kmax=500。 Step10若h Step11如果l Step12輸出所有粒子的最佳位置對應(yīng)的向量B和其適用值T。 考慮一個由7個區(qū)段、8個??空窘M成的高速鐵路,列車按8節(jié)編組,每列旅客列車在每個區(qū)段的最大席位能力均為560個席位。該高速鐵路服務(wù)28個OD,需求均值和標(biāo)準(zhǔn)差均為常數(shù)。某一時段內(nèi)共有4列旅客列車,其中大站停列車1列,交錯停列車2列,站站停列車1列。具體停站方案及站間距離,見圖3,參數(shù)pij、μij、σij取值見表1。 設(shè)定粒子群規(guī)模Psize=25,最大迭代次數(shù)500次,收斂控制因子ω=0.5,γ1=0.5,γ2=0.5,借助于Matlab工具進(jìn)行模型求解。表2為確定性客流需求下線性規(guī)劃模型的計(jì)算結(jié)果,即初始解生成向量,給出了每列旅客列車各OD票額限制。表3給出了粒子群算法求解的最終票額分配方案,圖4為求解過程,算法在迭代到150步時達(dá)到收斂。 表1 參數(shù)取值(pij,μij,σij) 以相同的客流需求為基礎(chǔ),盡量滿足長途客流需求并以人公里數(shù)最大為目標(biāo)進(jìn)行客流分配,再以單列旅客列車客票收益最大為目標(biāo)進(jìn)行票額分配,可以求得票額分配方案。表4為求得的方案,稱為對比方案。 在相同的客流需求下,對比方案的客票期望收益為76.368萬元,本文方案的客票期望收益為78.211萬元,期望收益提高約2.41%。因此本文方案不但簡化客流分配過程實(shí)現(xiàn)多列車1次性優(yōu)化,同時說明站在收益角度從整體優(yōu)化不同停站方案旅客列車間的相互協(xié)調(diào)對收益提高有著明顯影響。 在客流需求方差不變的情況下,客流需求較大時,本文方案期望收益提高較大;客流需求較小時,因席位能力充足,大部分客流需求在兩種方案下都能得到較好滿足,期望收益差別較小。如圖5(a)所示,當(dāng)客流需求減小為0.5μij時,兩種方案的期望收益已無明顯差別。 對比方案第一階段整體優(yōu)化時未考慮客流波動的影響,在第二階段單列車票額分配再考慮客流波動,因協(xié)調(diào)空間變小,客流波動影響較大;本文方案從整體考慮客流波動情況,能夠更好地避免客流波動造成的影響。如圖5(b)所示,在客流需求均值不變的情況下,客流波動越大,相比之下本文方案越優(yōu)。 表2 初始解生成向量(列車1,列車2,列車3,列車4) 表3 多列車多停站方案票額分配結(jié)果(列車1,列車2,列車3,列車4) 表4 對比方案票額分配結(jié)果(列車1,列車2,列車3,列車4) 本文研究了多列車多停站方案的票額分配方法,根據(jù)建立的模型特點(diǎn)設(shè)計(jì)粒子群算法進(jìn)行求解,并將本文提出方法和先客流分配再票額分配的方法進(jìn)行了對比。結(jié)果表明,多列車多停站方案的票額分配方法能夠更好地對不同停站方案的旅客列車進(jìn)行協(xié)調(diào),站在整個線路所有旅客列車的角度提高客運(yùn)收益。本文所得的控制方法仍是靜態(tài)的,但在預(yù)訂過程中不斷更新客流需求和席位能力也能達(dá)到動態(tài)的效果。同時本文僅考慮了單一票價形式,多等級票價及其嵌套方式等收益管理問題是進(jìn)一步研究的方向。 參考文獻(xiàn): [1] CIANCIMINO A, INZERILLO G, LUCIDIS, et al. A Mathematical Programming Approach for the Solution of the Railway Yield Management Problem[J]. Transportation Science, 1999, 33(2): 168-181. [2] YOU P S. An Efficient Computational Approach for Railway Booking Problems[J]. European Journal of Operational Research, 2008, 185(2): 811-824. [3] ONGPRASERT S. Passenger Behavior on Revenue Management Systems of Inter-city Transportation[D]. Japan: Kochi University of Technology, 2006. [4] BHARILL R, RANGARAJ N. Revenue Management in Railway Operations: A Study of the Rajdhani Express, Indian Railways[J]. Transportation Research Part A, 2008, 42(9): 1 195-1 207. [5] 史峰,陳彥,周文梁,等. 基于用戶平衡分析的鐵路旅客列車票額分配計(jì)劃制定及評價方法[J]. 中國鐵道科學(xué),2008,29(6):98-103. SHI Feng, CHEN Yan, ZHOU Wenliang, et al. Railway Passenger Train Seats Allotment Plan Establishment and Evaluation Method Based on User Equilibrium Analysis[J]. China Railway Science, 2008,29(6):98-103. [6] 藍(lán)伯雄,張力. 高速鐵路客運(yùn)專線的收益管理模型[J]. 中國管理科學(xué),2009,17(4):53-59. LAN Boxiong, ZHANG Li. Revenue Management Model for High-speed Passenger Railway[J]. Chinese Journal of Management Science,2009,17(4):53-59. [7] 單杏花,周亮瑾,呂曉艷,等. 鐵路旅客列車票額智能預(yù)分研究[J]. 中國鐵道科學(xué),2011,32(6):125-128. SHAN Xinghua, ZHOU Liangjin, Lü Xiaoyan, et al. Research on Intelligent Pre-assignment of Ticket Allotment for Railway Passenger Train[J]. China Railway Science, 2011,32(6):125-128. [8] 錢丙益,帥斌,陳崇雙,等. 基于旅客buy-up行為的鐵路客運(yùn)專線收益管理模型[J]. 鐵道學(xué)報,2013,35(8):10-15. QIAN Bingyi, SHUAI Bin, CHEN Chongshuang, et al. Revenue Management Model for Dedicated Passenger Line Based on Passengers’ Buy-up Behavior[J]. Journal of the China Railway Society, 2013,35(8):10-15. [9] 包云,劉軍,馬敏書,等. 高速鐵路嵌套式票額分配方法研究[J]. 鐵道學(xué)報,2014,36(8):1-6. BAO Yun, LIU Jun, MA Minshu, et al. Nested Seat Inventory Control Approach for High-speed Trains[J]. Journal of the China Railway Society, 2014,36(8):1-6. [10] BAO Yun, LIU Jun, MA Minshu, et al. Seat Inventory Control Methods for Chinese Passenger Railways[J]. Journal of Central South University, 2014(4):1 672-1 682. [11] 包云,劉軍,劉江川,等. 基于隨機(jī)需求的單列車票額分配方法[J]. 中國鐵道科學(xué),2015,36(2):96-102. BAO Yun, LIU Jun, LIU Jiangchuan, et al. Seat Allotment Method for Single Train Based on Stochastic Demand[J]. China Railway Science, 2015,36(2):96-102. [12] KENNEDY J, EBERHART R. Particle Swarm Optimization[C]//Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia: IEE,1995:1 942-1 948. [13] PARK C, SEO J. Seat Inventory Control for Sequential Multiple Flights with Customer Choice Behavior[J]. Computers and Industrial Engineering, 2011(11):1 189-1 199. [14] LAN Y, BALL M O, KARAESMEN I Z, et al. Analysis of Seat Allocation and Overbooking Decisions with Hybrid Information[J]. European Journal of Operational Research, 2015(1):493-504.2 求解算法
3 算例
4 結(jié)論