駱泳吉， 劉 軍， 賴晴鷹

（北京交通大學 軌道交通控制與安全國家重點實驗室，北京 100044）

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

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

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

圖1 結合通售席位的票額分配示意圖

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

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

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

式中：m為旅客列車?？空緮?shù)量；i、j分別為上車站、下車站序號；Z為整數(shù)集合；l為區(qū)間序號；pij為OD對（i，j）的席別票價；Cl為區(qū)間l的可售席位數(shù)量；xij為OD對（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對（i，j）的售票量；E fij（xij，y）［］為fij（xij，y）的期望值。

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

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

2 基于隨機梯度算法的求解步驟

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

Step1 設置初始可行解x0（）和y0（）

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

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

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

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

需求序列ws的購票過程描述為：當購票需求ws，t＝（i，j）到達時，若（i，j）的票額充足，即xij，t≥1，則令qij，t＋1＝qij，t＋1，xij，t＋1＝xij，t－1；若 （i，j）的分配票額不足，即xij，t＜0，但對應區(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）的分配票額和相應區(qū)間通售席位均不足，即xij，t＝0且-l＝i，…，j－1，有yl，t＜1，則該需求購票失敗，各變量無變化。

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

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

Step2 近似計算隨機樣本梯度

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

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

計算所有樣本的一階差分的期望值，近似求得總收益關于xij的梯度

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

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

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

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

Step4 檢測迭代終止條件

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

3 實例

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

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

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

表1 價格、需求均值、標準差 （元，人，人）

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

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

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

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

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

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

4 結論

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

參考文獻：

［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］單杏花.鐵路客運收益管理模型及應用研究［D］.北京：中國鐵道科學研究院，2012：102－129.

［4］王洪業(yè)，呂曉艷，周亮瑾，等.基于客流預測的鐵路旅客列車票額智能分配方法［J］.中國鐵道科學，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行為的鐵路客運專線收益管理模型［J］.鐵道學報，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］.鐵道學報，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］.中國鐵道科學，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.