駱泳吉， 劉 軍， 賴晴鷹

（北京交通大學(xué) 軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100044）

收益管理起源于美國(guó)航空業(yè)，研究如何將易逝性產(chǎn)品在合適的時(shí)間以合適的價(jià)格銷售給合適的顧客以實(shí)現(xiàn)收益最大化的方法。近年來，有關(guān)收益管理的理論研究從單區(qū)段問題到多區(qū)段問題，從確定性需求到不確定需求，均得到顯著發(fā)展［1］；在現(xiàn)實(shí)中，航空企業(yè)也受益于收益管理的應(yīng)用，實(shí)現(xiàn)收益增長(zhǎng)［2］。

鐵路旅客運(yùn)輸同樣存在產(chǎn)品易逝性，固定成本高，可變成本低等特點(diǎn)。因此，鐵路客運(yùn)運(yùn)用收益管理同樣具有可行性。我國(guó)鐵路客運(yùn)一直使用的票額分配工作也屬于收益管理的研究范疇，并取得一定的成效［3－4］。針對(duì)單一票價(jià)下的席位分配問題，Ciancimino等研究在確定性需求下的DLP模型和隨機(jī)需求下的PNLP模型［5］；在文獻(xiàn)［5］的基礎(chǔ)上，You研究?jī)煞N票價(jià)等級(jí)下的鐵路席位分配問題，模型考慮超售情況下的沖撞成本，由線性規(guī)劃與粒子群算法相結(jié)合的優(yōu)化方法快速求解［6］；錢丙益等［7］對(duì)文獻(xiàn)［6］的模型進(jìn)行擴(kuò)展，考慮低價(jià)票售完后部分需求轉(zhuǎn)移至高價(jià)票的buyup行為；文獻(xiàn)［8］提出同一上車站的長(zhǎng)短途票額嵌套模型，利用蟻群算法進(jìn)行求解；文獻(xiàn)［9］研究隨機(jī)需求下的票額分配問題，通過計(jì)算客流量的期望值，將問題轉(zhuǎn)化為確定性票額分配模型進(jìn)行求解。

上述成果從不同角度研究鐵路席位控制問題，但均未考慮鐵路售票組織中常見的通售席位的設(shè)置方法。進(jìn)入預(yù)售期前，有限的席位能力不僅可被分配至不同OD，還可設(shè)置為通售席位，見圖1。與指定OD的票額不同，通售席位是一種共享資源，在預(yù)售期內(nèi)，當(dāng)某OD發(fā)生購(gòu)票預(yù)定請(qǐng)求時(shí)，優(yōu)先售出該OD的分配票額；若已分配票額售完，再使用可用的通售席位。通售席位能使票額分配方案更加靈活，在客流波動(dòng)較大或客流預(yù)測(cè)不準(zhǔn)的情況下，能起到減少客流損失的作用。

圖1 結(jié)合通售席位的票額分配示意圖

本文研究隨機(jī)需求下，考慮通售席位的鐵路旅客列車票額分配問題。首先，構(gòu)建引入通售席位的票額分配隨機(jī)非線性規(guī)劃模型。由于需求的隨機(jī)性，模型難以采用解析的方法求解。因此，主要采用抽樣隨機(jī)需求，模擬售票過程，進(jìn)而利用樣本梯度優(yōu)化決策變量的思想［10］對(duì)問題進(jìn)行求解。

1 考慮通售席位的票額分配模型

相比既有文獻(xiàn)，考慮通售席位的票額優(yōu)化模型引入新的決策變量，即各區(qū)間通售席位的數(shù)量。由于需求的隨機(jī)性和通售席位的“先到先得”特征，使優(yōu)化問題轉(zhuǎn)為隨機(jī)非線性規(guī)劃問題，從而進(jìn)一步增加模型的復(fù)雜度，模型構(gòu)造為

式中：m為旅客列車?？空緮?shù)量；i、j分別為上車站、下車站序號(hào)；Z為整數(shù)集合；l為區(qū)間序號(hào)；pij為OD對(duì)（i，j）的席別票價(jià)；Cl為區(qū)間l的可售席位數(shù)量；xij為OD對(duì)（i，j）的票額分配數(shù)量；yl為區(qū)間l的通售席位數(shù)量；x＝ x1，2，…，x1，m，…，xm－2，m，xm－1，m（）為OD分配票額數(shù)量的向量；y＝ y1，y2，…，ym－1（）為區(qū)間通售席位數(shù)量的向量；fij（xij，y）為 OD對(duì)（i，j）的售票量；E fij（xij，y）［］為fij（xij，y）的期望值。

式（2）表示列車各區(qū)間的席位數(shù)應(yīng)等于通過該區(qū)間的OD分配票額和該區(qū)間的通售席位數(shù)量的總和。式（3）、式（4）表示各OD分配票額及各區(qū)間通售席位數(shù)量均為不小于零的整數(shù)。

設(shè)OD對(duì)（i，j）的需求量為Dij，服從一定隨機(jī)分布（均值μij，標(biāo)準(zhǔn)差σij）。由于需求的隨機(jī)性，fij（xij，y）是關(guān)于xij和y的隨機(jī)函數(shù)。當(dāng)Dij≤xij時(shí)，該OD的票額xij可滿足其需求，則有fij（xij，y）＝Dij；當(dāng)Dij＞xij時(shí)，已分配票額不足以滿足其需求，需額外占用相應(yīng)區(qū)間的通售席位yl，l＝i～j－1。然而，通售席位屬于“共用”資源，可被其余OD需求以“先到先得”的方式售出。因此fij（xij，y）受xij、y 和其余OD需求量及購(gòu)票時(shí)間先后順序的綜合影響，使得E fij（xij，y）［］難以用解析式方法直接求解。本文擬通過對(duì)隨機(jī)需求進(jìn)行采樣，利用隨機(jī)樣本的梯度，迭代優(yōu)化決策變量x和y。

2 基于隨機(jī)梯度算法的求解步驟

首先，將原問題（P0）轉(zhuǎn)換為確定性需求下的資源分配問題，求初始可行解。在此基礎(chǔ)上，通過采樣隨機(jī)需求，生成樣本路徑，模擬計(jì)算樣本的一階差分，利用隨機(jī)梯度算法，迭代優(yōu)化決策變量，具體步驟為：

Step1 設(shè)置初始可行解x0（）和y0（）

將各OD隨機(jī)需求簡(jiǎn)化為確定性需求，即Dij＝E設(shè)定能力分配比例參數(shù)0＜θ＜1，將原問題簡(jiǎn)化為確定性線性規(guī)劃問題DLP（Deterministic Linear Programming），即

式中：μij為OD對(duì)（i，j）的平均需求量。式（6）表示OD分配票額不應(yīng)超過可分配的能力；式（7）表示各OD分配票額不應(yīng)大于μij。

設(shè)迭代次數(shù)k＝0，向下取整（P1）的最優(yōu)解，得到x的初始可行解為

已知x0（），y0（）由下式可得（i，j）的累計(jì)購(gòu)票數(shù)量。

需求序列ws的購(gòu)票過程描述為：當(dāng)購(gòu)票需求ws，t＝（i，j）到達(dá)時(shí)，若（i，j）的票額充足，即xij，t≥1，則令qij，t＋1＝qij，t＋1，xij，t＋1＝xij，t－1；若 （i，j）的分配票額不足，即xij，t＜0，但對(duì)應(yīng)區(qū)間有可用的通售席位，即l＝i，…，j－1，有yl，t≥1，則令qij，t＋1＝qij，t＋1，yl，t＋1＝y(tǒng)l，t－1（l＝i，…，j－1）；若 （i，j）的分配票額和相應(yīng)區(qū)間通售席位均不足，即xij，t＝0且-l＝i，…，j－1，有yl，t＜1，則該需求購(gòu)票失敗，各變量無變化。

模擬需求序列ws的售票過程，計(jì)算樣本收益針對(duì)xij的一階差分為

式中：Rsxk（），yk（）（）為ws在決策變量xk（）和yk（）下的列車總收益；xk（）＋為在xk（）基礎(chǔ)上單位增加OD （i，j）票額 （其余 OD 不變）后的新決策變量；yk（）－為在yk（）基礎(chǔ)上單位減少區(qū)間l＝i～j－1通售席位數(shù)量（其余區(qū)間不變）后的新決策變量；ΔijRsxk（），yk（）（）為決策變量變化前后的列車收益差。若xk（）＋、yk（）－不在可行域內(nèi)，則令ΔijRsxk（），yk（）（）＝0。

Step2 近似計(jì)算隨機(jī)樣本梯度

由于購(gòu)票過程具有隨機(jī)性，列車收益難以用解析方法表達(dá)。因此，參照文獻(xiàn)［10］對(duì)離散問題的梯度處理思想，用隨機(jī)樣本一階差分近似列車收益對(duì)于決策變量的梯度。

首先，設(shè)置隨機(jī)采樣數(shù)量n，根據(jù)OD需求的概率分布和實(shí)際購(gòu)票時(shí)間分布，隨機(jī)生成購(gòu)票需求序列ws，s＝1，2，…，n。設(shè)ws，t為ws中的第t個(gè)購(gòu)票需求的二元組，記錄該需求的上車站、下車站序號(hào)；xij，t、yl，t分別為第t個(gè)需求到達(dá)前 OD對(duì)（i，j）的票額和區(qū)間l的通售席位數(shù)量；qij，t為第t個(gè)需求到達(dá)前OD對(duì)

計(jì)算所有樣本的一階差分的期望值，近似求得總收益關(guān)于xij的梯度

式中：n為隨機(jī)采樣總數(shù)。

Step3 優(yōu)化OD分配票額xk（）和區(qū)間通售席位數(shù)量yk（）

設(shè)ρk（）為第k次迭代時(shí)的步長(zhǎng)，則為xij更新后的位置。由于＝不一定在可行域內(nèi)，首先計(jì)算在連續(xù)可行域內(nèi)的正交投影

取整x （k＋1）＝"x （k＋1）#，對(duì)y （k＋1）更新為

Step4 檢測(cè)迭代終止條件

若‖x （k＋1）－xk（）‖／‖xk（）‖＜ε或k＝kmax時(shí)，終止迭代，x（k＋1）、y（k＋1）為最終解；否則，令k＝k＋1，返回步驟2。

3 實(shí)例

以2013－08－01～2013－08－31上海虹橋開往北京南的G102次列車二等座為例，列車共有m＝8個(gè)停車站，見圖2。以周末（周五～周日）客流數(shù)據(jù)為基礎(chǔ)，統(tǒng)計(jì)OD均值和標(biāo)準(zhǔn)差。表1為OD的票價(jià)、需求均值、需求標(biāo)準(zhǔn)差的三元組。

圖2 G102次列車停車站示意圖

設(shè)列車定員為650人，OD分配票額初始分配比例θ＝0.8，迭代中的隨機(jī)采樣數(shù)量n＝20；與文獻(xiàn)［5－7］中鐵路需求量的隨機(jī)分布相同，假設(shè)OD需求總量服從正態(tài)分布，需求序列中不同OD的購(gòu)票順序根據(jù)歷史購(gòu)票時(shí)間分布生成；設(shè)迭代步長(zhǎng)隨迭代次數(shù)遞減，即ρ（k）＝0.2／，迭代終止系數(shù)ε＝0.01，最大迭代次數(shù)kmax＝500。采用Matlab編程實(shí)現(xiàn)，線性規(guī)劃問題（P1）和二次規(guī)劃問題（P2）可分別用優(yōu)化函數(shù)linprog、quadprog快速求解。

表1 價(jià)格、需求均值、標(biāo)準(zhǔn)差 （元，人，人）

首先，采用確定性線性規(guī)劃模型（DLP）求解無通售席位的票額分配方案，即令θ＝1，求解式（5）～式（7），分配結(jié)果見表2。設(shè)隨機(jī)測(cè)試樣本數(shù)量N＝50，針對(duì)隨機(jī)需求序列ws，模擬在該票額分配方案下的售票過程，計(jì)算仿真總收益r （ws），統(tǒng)計(jì)平均仿真總收益／N＝33.25萬元 。

使用本文提出的優(yōu)化方法求解考慮通售席位的票額分配方案，迭代過程見圖3，分配結(jié)果見表3、表4，平均仿真總收益為34.29萬元，相比無通售席位的DLP模型提高3.14%。

圖3 迭代優(yōu)化過程

表2 無通售席位的DLP求解方案 張

表3 考慮通售席位的OD分配票額數(shù)量 張

表4 區(qū)間通售席位數(shù)量 張

4 結(jié)論

當(dāng)需求具有較強(qiáng)的隨機(jī)性時(shí)，引入通售席位的票額分配方法使分配方案更加靈活，相比經(jīng)典的DLP模型，收益有一定程度的提高。但是，數(shù)據(jù)成本方面，本文算法需要統(tǒng)計(jì)旅客歷史購(gòu)票時(shí)間的分布，作為樣本采樣的基礎(chǔ)，數(shù)據(jù)成本更高；計(jì)算成本方面，隨著隨機(jī)采樣數(shù)量增多，雖然能使梯度的估計(jì)值越準(zhǔn)確，但計(jì)算效率更低，相比無須隨機(jī)采樣的DLP模型更為耗時(shí)。通過不同需求數(shù)據(jù)下的反復(fù)試驗(yàn)，可以發(fā)現(xiàn)模型的優(yōu)化結(jié)果依賴于初始分配比例參數(shù)θ，即算法不保證能夠收斂于全局最優(yōu)解。盡管如此，優(yōu)化算法能使票額分配方案總體上向列車收益上升方向更新，在實(shí)際應(yīng)用中具有一定的價(jià)值。

參考文獻(xiàn)：

［1］TALLURI K T，VAN RYZIN G J.The Theory and Prac－tice of Revenue Management［M］.USA：Kluwer Academic Publishers，2004：27－127.

［2］SMITH B C，LEIMKUHLER J F，DARROW R M.Yield Management at American Airlines［J］.Interfaces，1992，22（1）：8－31.

［3］單杏花.鐵路客運(yùn)收益管理模型及應(yīng)用研究［D］.北京：中國(guó)鐵道科學(xué)研究院，2012：102－129.

［4］王洪業(yè)，呂曉艷，周亮瑾，等.基于客流預(yù)測(cè)的鐵路旅客列車票額智能分配方法［J］.中國(guó)鐵道科學(xué)，2013，34（3）：128－132.WANG Hongye，LV Xiaoyan，ZHOU Liangjin，et al.Intelligent Seat Allotment Method for Railway Passenger Train Based on Passenger Flow Forecast［J］.China Railway Science，2013，34（3）：128－132.

［5］CIANCIMINO A，INZERILLO G，LUCIDI S，et al.A Mathematical Programming Approach for the Solution of the Railway Yield Management Problem［J］.Transportation Science，1999，33（2）：168－181.

［6］YOU P.An Efficient Computational Approach for Railway Booking Problems［J］.European Journal of Operational Research，2008，185（2）：811－824.

［7］錢丙益，帥斌，陳崇雙，等.基于旅客buy－up行為的鐵路客運(yùn)專線收益管理模型［J］.鐵道學(xué)報(bào)，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.

［8］包云，劉軍，馬敏書，等.高速鐵路嵌套式票額分配方法研究［J］.鐵道學(xué)報(bào)，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.

［9］包云，劉軍，劉江川，等.基于隨機(jī)需求的單列車票額分配方法［J］.中國(guó)鐵道科學(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.

［10］BERTSIMAS D，DE BOER S.Simulation－based Booking Limits for Airline Revenue Management［J］.Operations Research，2005，53（1）：90－106.