靈活編組高鐵列車的售票時間窗優(yōu)化

閆振英，韓寶明，李曉娟，曹瑾鑫

(1.內(nèi)蒙古大學(xué) 交通學(xué)院，內(nèi)蒙古 呼和浩特 010020；2.北京交通大學(xué) 交通運輸學(xué)院，北京 100044；3.內(nèi)蒙古自治區(qū)科學(xué)技術(shù)研究院，內(nèi)蒙古 呼和浩特 010070)

2019年以來，我國鐵路部門積極探索構(gòu)建靈活的高鐵票價機制，研究并試點“一日一價”、“一車一價”等策略.高鐵收益管理理論研究早在高鐵定價權(quán)下放后便受到廣泛關(guān)注.在票額分配、動態(tài)定價及二者聯(lián)合優(yōu)化等方面取得了一系列研究成果，促進(jìn)高鐵運營管理效率的提升，助力高鐵運營市場化改革.隨著動車組技術(shù)的發(fā)展，我國研發(fā)出的新型CRH3X型動車組可實現(xiàn)2～16編靈活編組[1].靈活編組技術(shù)可用于調(diào)節(jié)供給容量，打破了傳統(tǒng)收益管理容量固定的限制，靈活編組下的高鐵收益管理理論和方法亟須探索和研究.

收益管理的研究始于美國航空領(lǐng)域，后廣泛應(yīng)用于各類易逝產(chǎn)品領(lǐng)域.相較于早期研究只考慮單一資源、假設(shè)產(chǎn)品需求獨立等特征，最新的收益管理研究更多集中在考慮旅客選擇行為的網(wǎng)絡(luò)收益管理上.Strauss等[2]總結(jié)了近十幾年基于選擇的收益管理理論和方法，基于顧客選擇的網(wǎng)絡(luò)收益管理問題可建立動態(tài)規(guī)劃模型精確描述，但是問題規(guī)模龐大無法精確求解，于是衍生出諸多獲取近似控制策略的研究.許多研究采用MNL(multiominal logit)模型刻畫旅客選擇行為，得到較為高效的近似控制策略.然而，收益管理中常出現(xiàn)產(chǎn)品不完全獨立的情形，MNL模型的IIA(independent of irrelevant alternatives)特性會帶來估計偏差[3].隨著偏好序模型研究的推進(jìn)[4]，這種無參數(shù)的選擇行為模型逐漸應(yīng)用于收益管理[5].Hosseinalifam等[5-6]提出了基于偏好序選擇模型的網(wǎng)絡(luò)存量控制和預(yù)訂限制控制策略，并設(shè)計了列生成求解算法.Paul等[7]利用樹結(jié)構(gòu)研究了基于偏好序的品類優(yōu)化和定價問題，提出了多項式時間算法.Barbier等[8]針對基于偏好序的網(wǎng)絡(luò)收益管理問題，從靜態(tài)近似的角度提出了產(chǎn)品停售控制策略.以上研究都在固定容量的前提下研究收益提升的方法.而Wang等[9]基于飛機機型調(diào)換思想為容量提供了部分柔性，研究發(fā)現(xiàn)機型調(diào)換與存量控制聯(lián)合優(yōu)化能夠提升收益.綜上，理論探索中尚缺乏有限柔性容量下考慮偏好序選擇行為的收益管理研究.

既有高鐵收益管理研究成果主要集中在票額分配[10-11]、動態(tài)定價[12]、動態(tài)定價與票額分配聯(lián)合優(yōu)化[13]等方面.票額分配一般預(yù)先確定客票價格，通過票額分配模型計算各列車的席位資源如何分配給不同OD(origin to destination)不同票價等級的客票，使得收益最大.動態(tài)定價則是通過為客票實時或分時段定價進(jìn)行預(yù)售控制.將實時或時段票價作為決策變量，通過建立票價與需求的彈性關(guān)系求解模型.動態(tài)定價與票額分配的聯(lián)合優(yōu)化則是將票額分配與票價同時作為變量進(jìn)行求解，得到各時段的最優(yōu)票價和票額分配方案.此外，Yan等[14]基于靈活編組研究了有限柔性容量下的高鐵票額分配問題.以上研究均考慮旅客選擇行為，但大多是基于MNL模型，較少采用偏好序模型.

本文采用偏好序模型刻畫旅客選擇行為，旅客根據(jù)自己的偏好集合選擇購票，規(guī)避MNL模型的IIA問題.基于偏好序的無參數(shù)選擇行為，由大量歷史購買數(shù)據(jù)驅(qū)動，能夠更準(zhǔn)確表達(dá)旅客選擇行為，且不假定任何概率形式，具有更好的靈活性和動態(tài)性.利用靈活編組對供給容量進(jìn)行有限調(diào)節(jié)，各列車容量的增減在一定約束下進(jìn)行.在此基礎(chǔ)上，基于售票時間窗控制策略對高鐵收益管理展開研究.針對多列車、多停站的高鐵網(wǎng)絡(luò)，考慮每列車每個OD的相同類型座位提供不同票價的客票，建立非線性規(guī)劃模型同時優(yōu)化各類客票的售票時間窗和列車編組方案，從而實現(xiàn)更為精準(zhǔn)的供需匹配，提高高鐵線路總體獲利效果.考慮運營企業(yè)的售票要求可將客票進(jìn)行排序，據(jù)此可將模型轉(zhuǎn)化為線性規(guī)劃模型，并采用CPLEX快速求解.結(jié)果可為客票預(yù)售提供時間窗控制策略，還可從匹配需求和最大化獲利的角度為列車編組計劃提供編組規(guī)模依據(jù).

1 基于偏好序的靈活編組高鐵列車售票時間窗優(yōu)化模型

1.1 問題描述

一條高鐵線路上設(shè)有G個車站，開行B列列車服務(wù)于沿線的W個OD市場.根據(jù)收益管理原理，可以將相同列車、相同等級座位、服務(wù)于相同OD的客票設(shè)置不同的價格f.列車用b表示，OD用w表示，最終形成的客票可以用唯一標(biāo)識.依次將客票編號，用j表示，j∈J.不考慮超售和無座票，且假設(shè)所有客票停售后不再開啟銷售.將每列車在每個區(qū)段的席位資源定義為資源i∈I.那么客票與席位資源之間的占用關(guān)系可表示為矩陣A=[aij]i∈I,j∈J，當(dāng)產(chǎn)品j占用席位資源i時aij=1，否則aij=0.資源容量ci由列車編組方案zb和額定座位數(shù)c0決定.在此僅考慮同等級座位(如二等座)，增加其他等級的座位相當(dāng)于增加資源類型.將客票銷售期劃分為τ個時段，從t=0開始，到時段t=τ結(jié)束時售票結(jié)束.每個產(chǎn)品的售票時間窗由停售時間決定.由于旅客的購票選擇行為存在差異，將具有相似購票決策行為的旅客歸為一類，旅客類別l∈L.每個時段的旅客類別l的平均到達(dá)率為λl.鐵路運營企業(yè)需要決策每個產(chǎn)品j的停售時間和每列車的最佳編組方案使得整體獲利最大.

1.2 基于偏好序的選擇行為

(1)

否則Pl(j|S)=0.因此，將l類別旅客購買客票j的概率表示為Pl(j|{j}).

(2)

(3)

1.3 售票時間窗優(yōu)化模型

客票j的期望銷售量Q(DL)可表示為

(4)

(5)

s.t.公式(3)；

AQ(DL)≤c；

(6)

(7)

?g∈[1,G-1],?b∈[1,B]；

(8)

(9)

Tj∈[0,τ],?j∈J；

(10)

zb，m∈{0,1},?b∈[1,B],m∈M.

(11)

其中：約束條件(3)表示l類旅客可購買第k個客票的時段，即前k個客票的最晚停售時間超過前k-1個客票最晚停售時間的部分；約束條件(6)為容量約束，總售票數(shù)量不應(yīng)超過列車容量；約束條件(7)為前k個客票中的最晚停售時間的計算方式；約束條件(8)給出了資源容量與列車編組數(shù)量和額定席位數(shù)的關(guān)系，其中g(shù)表示區(qū)段；約束條件(9)保證每列車只有且只有一種編組方案.約束條件(10)和(11)給出了決策變量的取值范圍.根據(jù)模型非線性規(guī)劃的特征，引入客票排序?qū)⒓s束(7)線性化，從而將模型轉(zhuǎn)化為線性規(guī)劃模型進(jìn)行求解.

2 模型求解

2.1 客票排序

高價產(chǎn)品和低價產(chǎn)品的嵌套控制是收益管理中非常有效的一種控制方式.例如在存量控制中允許高價產(chǎn)品占用分配給低價產(chǎn)品的資源，從而為高價產(chǎn)品保留更多的售出機會，提高總體收益.鐵路運輸領(lǐng)域常常存在保護(hù)長途客票的嵌套機制.在停售時間控制中，可以用客票停售時間排序來滿足嵌套銷售的需求.定義客票排序H={Hj}j∈J，如果Tu>Tv，那么Hu>Hv，且若Tu=Tv，則Hu=Hv.一般來說，可按照客票價格、價格除以資源數(shù)、單位里程價格等排序，也可以按照運營公司的特殊需要進(jìn)行排序.

2.2 模型轉(zhuǎn)化

當(dāng)給定排序H時，模型TC中的非線性約束條件(7)可以轉(zhuǎn)化為

(12)

(13)

s.t.式(3)，式(6)，式(8)～式(12).

轉(zhuǎn)化后的模型TCL為線性規(guī)劃模型，可選用CPLEX求解器快速求解.得到的模型最優(yōu)解T*和z*分別為各客票的停售時間和各列車的最佳編組.前者可直接植入售票系統(tǒng)作為售票控制策略使用，后者可為列車編組計劃提供參考依據(jù).該模型為靜態(tài)決策模型，可在售票開始前且編組方案可調(diào)整時優(yōu)化決策.也可在售票過程中且編組方案可調(diào)整時重新優(yōu)化以實現(xiàn)動態(tài)決策.

3 數(shù)值實驗

3.1 實驗數(shù)據(jù)

表1 客票與票價

圖1 列車服務(wù)網(wǎng)絡(luò)示意圖

表2 各OD旅客類別、平均到達(dá)率和偏好產(chǎn)品集合

3.2 實驗結(jié)果

按照上述參數(shù)設(shè)置，采用CPLEX在處理器為Intel(R)Core(TM)i5-6500 CPU 3.20 GHz，內(nèi)存4 GB的臺式電腦上進(jìn)行求解.所得最優(yōu)解為各類客票停售時間(如表3所示)和編組方案(如表4所示)，最優(yōu)目標(biāo)函數(shù)值(簡寫為VOF)為1 920 582元，求解時間為0.034 s.計算復(fù)雜性能夠滿足實際應(yīng)用的需要.

表3 客票停售時間

將8編固定編組(簡寫為G-8)和16編固定編組(簡寫為G-16)作為對比方案，本文提出的靈活編組方案用G-F代表，三種方案的對比情況如表4所示.可以看出，需求不足時方案G-F優(yōu)于兩個固定編組的對比方案.其他指標(biāo)保持不變時，到達(dá)率可以表征需求水平.到達(dá)率為0.2λl時，需求水平較低，靈活編組方案的優(yōu)越性體現(xiàn)在編組成本的節(jié)約上；當(dāng)?shù)竭_(dá)率增加到0.6λl時，與G-16相比優(yōu)勢在于節(jié)約成本，相比G-8的優(yōu)勢在于提高期望收益；當(dāng)?shù)竭_(dá)率增加到λl時，需求趨于飽和，此時各列車最佳的編組方案均為16編，G-F與G-16方案的收益性能一致.可見，靈活編組方案能夠根據(jù)需求調(diào)節(jié)編組方案，從而對高鐵運輸供給能力進(jìn)行調(diào)節(jié)，促進(jìn)供需匹配，獲得更好效益.

表4 不同需求強度下三種方案的對比

3.3 討 論

保持其他數(shù)據(jù)不變，改變到達(dá)率、轉(zhuǎn)移概率、編組成本等參數(shù)，研究靈活編組下的停售時間控制方案的收益性能變化規(guī)律，指導(dǎo)方案的實際應(yīng)用.到達(dá)率和轉(zhuǎn)移概率是描述市場需求規(guī)模和特征的重要參數(shù)，參數(shù)估計可參考文獻(xiàn)[4].

1)不同到達(dá)率的情況.保持其他數(shù)據(jù)不變，通過乘以一定倍數(shù)改變各類旅客的到達(dá)率，得到不同到達(dá)率下的VOF和編組方案變化情況如圖2、圖3所示.隨著旅客到達(dá)率的提高，需求規(guī)模增加，靈活編組方案中的編組單元總數(shù)相應(yīng)增加，直到所有列車都達(dá)到最大編組單元數(shù).但是列車G5的編組單元數(shù)并不是呈現(xiàn)單調(diào)增加的態(tài)勢，這也反映出編組方案是4列列車綜合考慮的優(yōu)化結(jié)果.從VOF來看，G-F方案較固定編組方案的收益性能更好，尤其是在需求不飽和的狀態(tài)下.當(dāng)需求達(dá)到飽和時，各列車最佳列車編組方案都達(dá)到最大編組單元數(shù)，G-F方案與G-16方案的收益性能相同.

圖2 不同到達(dá)率下的VOF變化規(guī)律

圖3 不同到達(dá)率下的編組方案

2)不同轉(zhuǎn)移購買概率的情況.保持其他數(shù)據(jù)不變，改變轉(zhuǎn)移購買概率，得到VOF和編組方案變化情況如圖4、圖5所示.當(dāng)各類別旅客的到達(dá)率保持不變時，轉(zhuǎn)移購買概率變化直接影響著需求規(guī)模.轉(zhuǎn)移購買概率越高，需求規(guī)模越大，總編組單元數(shù)越大，目標(biāo)函數(shù)值也越大.可見旅客的轉(zhuǎn)移購買行為對收益產(chǎn)生顯著影響，實際運營中應(yīng)重視旅客購買行為的研究.

圖4 不同轉(zhuǎn)移購買概率下的VOF

圖5 不同轉(zhuǎn)移購買概率下的編組方案

3)編組成本的影響.高鐵列車的運營成本核算十分復(fù)雜.收益管理中通常不考慮運營成本，是因為固定運營成本遠(yuǎn)遠(yuǎn)大于單位旅客的邊際運輸成本.本文研究靈活編組下的收益管理方案，不能簡單忽略增減列車編組時所產(chǎn)生的成本變化.本文提出的模型只需要核算出不同編組方案下運營成本的區(qū)別.用單位編組成本乘以不同系數(shù)，研究成本核算誤差對最佳編組方案的影響.如表5所示，單位編組成本在3 680～6 900元這個區(qū)間內(nèi)最佳編組方案保持不變.可見編組方案成本核算存在一定誤差對最佳編組方案的影響并不顯著.

表5 編組成本對最佳編組方案的影響

4 結(jié) 論

1)本文采用偏好序選擇模型刻畫旅客購票選擇行為，克服了MNL模型的IIA特性，提出了靈活編組下售票時間窗控制策略.綜合考慮高鐵線路上開行的多列車，通過尋求供給和需求的最佳匹配，實現(xiàn)運營企業(yè)獲利最大化，得到各客票的停售時間策略和各列車的最佳編組方案.通過引入客票銷售排序，將非線性規(guī)劃模型轉(zhuǎn)化為線性規(guī)劃模型，利用CPLEX快速求解.實驗結(jié)果表明，該模型能夠得到獲利最大化的客票銷售時間窗控制策略和最佳編組方案，且求解速度能夠滿足應(yīng)用需求.

2)與固定編組方案相比，靈活編組方案下的售票時間窗控制策略能夠更好地權(quán)衡成本與收益，方案整體獲利效果更好.當(dāng)需求達(dá)到飽和狀態(tài)后，各列車最佳編組方案均達(dá)到最大編組單元數(shù)，靈活編組下的售票時間窗控制策略與16編固定編組具有相同獲利效果.

3)轉(zhuǎn)移概率對需求規(guī)模和需求特征具有顯著影響.數(shù)值實驗表明：轉(zhuǎn)移概率越大，需求規(guī)模越大，使得編組方案越趨向大編組，目標(biāo)函數(shù)值也越大.可見旅客的轉(zhuǎn)移購買行為對收益產(chǎn)生顯著影響，實際運營中應(yīng)重視旅客購買行為的研究.編組方案成本核算對最佳編組方案產(chǎn)生一定影響，但是影響并不靈敏.實際運用中，可以允許一定的核算誤差.