考慮通售席位的旅客列車票額優(yōu)化方法

駱泳吉， 劉 軍， 賴晴鷹

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

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

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

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

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

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

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

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

式中：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ù)應(yīng)等于通過該區(qū)間的OD分配票額和該區(qū)間的通售席位數(shù)量的總和。式（3）、式（4）表示各OD分配票額及各區(qū)間通售席位數(shù)量均為不小于零的整數(shù)。

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

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

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

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

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

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

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

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

需求序列ws的購票過程描述為：當(dāng)購票需求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，但對應(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，則該需求購票失敗，各變量無變化。

模擬需求序列ws的售票過程，計算樣本收益針對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 近似計算隨機樣本梯度

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

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

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

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

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

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

取整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ù)為基礎(chǔ)，統(tǒng)計OD均值和標(biāo)準(zhǔn)差。表1為OD的票價、需求均值、需求標(biāo)準(zhǔn)差的三元組。

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

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

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

首先，采用確定性線性規(guī)劃模型（DLP）求解無通售席位的票額分配方案，即令θ＝1，求解式（5）～式（7），分配結(jié)果見表2。設(shè)隨機測試樣本數(shù)量N＝50，針對隨機需求序列ws，模擬在該票額分配方案下的售票過程，計算仿真總收益r （ws），統(tǒng)計平均仿真總收益／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)需求具有較強的隨機性時，引入通售席位的票額分配方法使分配方案更加靈活，相比經(jīng)典的DLP模型，收益有一定程度的提高。但是，數(shù)據(jù)成本方面，本文算法需要統(tǒng)計旅客歷史購票時間的分布，作為樣本采樣的基礎(chǔ)，數(shù)據(jù)成本更高；計算成本方面，隨著隨機采樣數(shù)量增多，雖然能使梯度的估計值越準(zhǔn)確，但計算效率更低，相比無須隨機采樣的DLP模型更為耗時。通過不同需求數(shù)據(jù)下的反復(fù)試驗，可以發(fā)現(xiàn)模型的優(yōu)化結(jié)果依賴于初始分配比例參數(shù)θ，即算法不保證能夠收斂于全局最優(yōu)解。盡管如此，優(yōu)化算法能使票額分配方案總體上向列車收益上升方向更新，在實際應(yīng)用中具有一定的價值。

參考文獻：

［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īng)用研究［D］.北京：中國鐵道科學(xué)研究院，2012：102－129.

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

［8］包云，劉軍，馬敏書，等.高速鐵路嵌套式票額分配方法研究［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.

［9］包云，劉軍，劉江川，等.基于隨機需求的單列車票額分配方法［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.

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