靈活編組高鐵列車的售票時間窗優化

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

(1.內蒙古大學 交通學院，內蒙古 呼和浩特 010020；2.北京交通大學 交通運輸學院，北京 100044；3.內蒙古自治區科學技術研究院，內蒙古 呼和浩特 010070)

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

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

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

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

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

1.1 問題描述

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

1.2 基于偏好序的選擇行為

(1)

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

(2)

(3)

1.3 售票時間窗優化模型

客票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)為容量約束，總售票數量不應超過列車容量；約束條件(7)為前k個客票中的最晚停售時間的計算方式；約束條件(8)給出了資源容量與列車編組數量和額定席位數的關系，其中g表示區段；約束條件(9)保證每列車只有且只有一種編組方案.約束條件(10)和(11)給出了決策變量的取值范圍.根據模型非線性規劃的特征，引入客票排序將約束(7)線性化，從而將模型轉化為線性規劃模型進行求解.

2 模型求解

2.1 客票排序

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

2.2 模型轉化

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

(12)

(13)

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

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

3 數值實驗

3.1 實驗數據

表1 客票與票價

圖1 列車服務網絡示意圖

表2 各OD旅客類別、平均到達率和偏好產品集合

3.2 實驗結果

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

表3 客票停售時間

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

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

3.3 討 論

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

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

圖2 不同到達率下的VOF變化規律

圖3 不同到達率下的編組方案

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

圖4 不同轉移購買概率下的VOF

圖5 不同轉移購買概率下的編組方案

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

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

4 結 論

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

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

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