基于票額分配的高速鐵路動態定價分治優化方法

鄧連波，曾寧鑫，陳雨欣，肖龍文

基于票額分配的高速鐵路動態定價分治優化方法

鄧連波，曾寧鑫，陳雨欣，肖龍文

(中南大學 交通運輸工程學院，湖南 長沙 410075)

研究基于票額分配的高速鐵路多列車多OD的動態定價問題。以多列車的總收益最大為目標函數，建立多列車多OD的動態定價和票額分配聯合優化模型，并在約束條件中充分考慮實際運營的需要。設計了將模型分解為雙層規劃的分治優化方法，通過票額分配與動態票價的分治優化，有效降低該類大規模問題的求解難度，并提高了求解效率。最后用20列車350個乘車OD的大型算例對模型和方法進行驗證，為高速鐵路動態定價的實際應用提供支持與參考。

高速鐵路；動態定價；票額分配；多列車；分治優化

隨著中國高鐵網絡的迅速發展，中國已經從政策層面逐步放開了高鐵的自主定價權，并在部分線路上進行了嘗試。在政策實施的大背景下，借鑒其他行業應用收益管理的成功經驗，將收益管理理論與方法應用到我國高速鐵路票價制定體系中，對提升高速鐵路的運營效率和收益具有重要的現實意義。收益管理的主要內容包括需求預測、超售、座位分配和動態定價4個部分。對于鐵路行業而言，動態定價和座位分配是最適用的策略和手段。國內外學者對動態定價和座位分配問題大部分針對2個問題單獨研究。Weatherford[1]首先考慮了定價和座位分配聯合優化問題，研究對象是民航的單航班。此后FENG等[2?3]也研究了單航班的定價和座位分配聯合優化問題。Chew等[4]研究了單一產品動態定價和座位分配聯合優化的一般問題。而Kuyumcu等[5?9]研究了多航班的動態定價和座位分配聯合優化的問題。在鐵路研究領域，Ongprasert[10]研究了與民航競爭環境下日本城際高速鐵路的座位分配問題，提出了考慮乘客選擇和折扣票價的多列車多OD座位分配模型。Hetrakul等[11]利用數學規劃模型研究了城際鐵路多列車多OD的定價和座位分配問題。楊宇航等[12]基于旅客對票價變化的敏感程度研究了高速鐵路多列車差別定價策略。鄭金子[13]研究了多列車多階段的動態定價問題，在每一階段進行差異化定價，對整個模型采用近似動態規劃方法求解。宋文波等[14]研究了單列車多OD動態定價與票額分配綜合優化問題，運用穩健優化方法對模型進行求解。趙翔等[15]利用票價和票額綜合優化，研究了高速鐵路多列車差別定價方法。上述大部分文獻提出的方法仍然不具有普適性或只適用于小規模問題，并且在考慮座位分配時大都是從乘客的角度出發，基于乘客的效用或選擇來“被動”進行座位分配。本文在座位分配和動態定價時均以收益最大化為目標，建立多列車多乘車OD的動態定價和座位分配聯合優化模型，采用分治優化的方法來降低求解難度。

1 問題描述

1.1 基本假設

1) 假設只考慮單一線路一個方向的情況，多列車、多停站。在同一OD對起終點車站設置了停站的列車集可以互相視作可替代品，各趟列車具有不同起訖點和停站方案。

2) 假定各OD對之間的出行需求是相互獨立的。各個OD選擇某一列車的客流共同構成列車相鄰停站區間的斷面流，需要滿足列車能力約束。

3) 不同旅客愿意支付不同的價格購買相同的座位。每趟列車的定價、速度(旅行時間)和乘降時刻等會影響乘客出行行為。同時忽略因票價波動發生的退票情況。

4) 假定需求函數已知，不同OD的需求彈性在同一時間相同。將預售期劃分為若干售票時段，根據每個售票時段開始時各OD的剩余席位數，確定該時段計劃發售車票的票價和數量。

1.2 符號定義

采用廣義費用的指數函數來刻畫客流需求。給定O-D對(,)，具有相同O-D對(,)的全部高鐵旅客運輸產品的分時段彈性需求函數可以描述為以下形式

所以，服務于O-D對(,)所有列車的每個旅客平均費用

2 模型構建

以所有列車所有乘車OD各個售票時段的總售票收益最大化為優化目標，目標函數為

約束條件包含了列車能力約束，非負約束和各類票價約束。

1) 每一趟列車各區間的能力約束。

2) 售票數量非負約束。

3) 售票數量不大于需求量。

4) 票價上下界約束：任何時段、任何列車、任何點對的票價均滿足上下限的約束。

5) 同一列車長程票價不低于短程票價。

6) 同一列車、同一點對的票價隨著發車時間的接近而單調增加(或者不下降)。

上述模型可以等價轉換成一個雙層規劃模型，其中上層主規劃模型是多列車多乘車OD的票額分配模型，下層子規劃模型是單列車單乘車OD的動態定價模型，將多列車的動態價格策略問題分解為多列車的票額分配計劃和各列車各乘車OD的動態定價策略2部分。

2.1 上層主規劃模型：票額分配模型(M1)

以所有列車所有乘車OD各個售票時段的總售票收益最大化為優化目標，目標函數為：

約束條件僅包含預售期內各列車的能力約束。

2.2 下層子規劃模型：單列車單乘車OD的動態定價模型(M2)

以單列車單乘車OD各個售票時段的總售票收益最大化為優化目標，目標函數為：

將式(15)變換可得

約束條件包含乘車OD的票額約束、售票數量非負約束和各類票價約束。

該乘車OD的票額約束為

其他約束條件與式(7)，(9)，(10)和(11)一致。

3 模型求解

再結合式(1)，可得

將式(21)代入式(20)，可得：

約束條件包含能力約束和售票數量非負約束。能力約束與式(13)一致，非負約束如下：

5) 返回2)。

該方法通過模型分解有效降低了求解難度。模型中，M1’求解宏觀票額分配這一靜態問題，約束條件是線性的，是高維二次規劃問題，M2求解票額分配下單列車單乘車OD的動態票價，是維數較低的非線性規劃問題，同時可以在前次求解方案的鄰域內迭代，提高了求解效率。

圖1 模型求解流程圖

4 算例分析

選取2014年7月1日武漢站到深圳北站這一段線路下行方向的20趟列車作為優化對象。20趟列車包含了該段線路上各種起訖點，具體如表1 所示。

表1 算例列車組成表

圖2 總收益收斂圖

圖3 總客座公里收斂圖

表2 G6215次列車的優化前后結果對比

為了更直觀地呈現優化后的結果，選取從廣州南到深圳北的G6215次列車，以表格的形式對優化前后的結果進行對比。從表2可以看出，優化后各OD各階段的票價均滿足模型中各項約束條件，是可行的。同時典型列車的在收益和客座公里在8次以后也都趨于收斂。

5 結論

1) 構建以多列車總收益最大化為目標函數的數學規劃模型，并從實際運營的角度考慮，將列車能力限制、票價的各種約束納入了約束條件，使模型更貼近現實需求。

2) 在求解時針對問題規模較大的情況，提出分治策略的求解方法，通過將模型分解為雙層規劃模型的等價變換，利用票額分配與動態票價的分治求解，有效降低了求解難度，并有效利用解的鄰域進行搜索，提高了求解效率。

3) 以實際運營情況作為基礎數據進行了20列車總計350個乘車OD的大規模算例分析。優化后收益增長了2.19%，且快速收斂，得到了各方面均符合預期的結果，驗證了模型的正確性和求解方法的有效性。

[1] Weatherford L. Using prices more realistically as decision variables in perishable-asset revenue management problems[J]. Journal of Combinatorial Optimization, 1997, 1(3): 277?304.

[2] FENG Y, XIAO B. Integration of pricing and capacity allocation for perishable products[J]. European Journal of Operational Research, 2006, 168(1): 17?34.

[3] Cizaire C. Optimization models for joint airline pricing and seat inventory control: Multiple products, multiple periods[D]. America: Massachusetts Institute of Technology, 2011.

[4] Chew E P, Lee C, Liu R J. Joint inventory allocation and pricing decisions for perishable products[J]. International Journal of Production Economics, 2009, 120: 139?150.

[5] Kuyumcu A, Garcia D A. A polyhedral graph theory approach to revenue management in the airline industry[J]. Computers and Industrial Engineering, 2000, 38(3): 375?395.

[6] Bertsimas D, de Boer S. Joint network pricing and resource allocation[EB/OL].2002.

[7] Cote J, Marcotte P, Savard G. A bilevel modeling approach to pricing and fare optimization in the airline industry[J]. Journal of Revenue and Pricing Management, 2003, 2(1): 23.

[8] Walczak D, Brumelle S. Semi-Markov information model for revenue management and dynamic pricing[J]. OR Spectrum, 2007, 29(1): 61?83.

[9] 曹海娜. 基于MNL模型的平行航班艙位控制與動態定價研究[D]. 北京: 北京理工大學, 2015. CAO Haina. Research on seat allocation and dynamic pricing for parallel flights with multinomial logit model[D]. Beijing: Beijing Institute of Technology, 2015.

[10] Ongprasert S. Passenger behavior on revenue management systems of inter-city transportation[D]. Japan: Kochi University of Technology, 2006.

[11] Hetrakul, Pratt, Cinzia Cirillo. A latent class choice based model system for railway optimal pricing and seat allocation[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 61: 68?83.

[12] 楊宇航, 張琦. 京滬高速鐵路票價調整與優化策略研究[J]. 鐵道科學與工程學報, 2017, 14(10): 2043?2049. YANG Yuhang, ZHANG Qi. Research on ticket price adjustment and optimization strategy of Beijing-Shanghai high speed railway[J]. Journal of Railway Science and Engineering, 2017, 14(10): 2043?2049.

[13] 鄭金子. 高速鐵路票價動態優化方法的研究[D]. 北京: 北京交通大學, 2017. ZHENG Jinzi. Research on ticket fare dynamic optimization for high-speed train[D]. Beijing: Beijing Jiaotong University, 2017.

[14] 宋文波, 趙鵬, 李博. 高速鐵路單列車動態定價與票額分配綜合優化研究[J]. 鐵道學報, 2018, 40(7): 10?16. SONG Wenbo, ZHAO Peng, LI Bo. Research on comprehensive optimization of dynamic pricing and seat allocation for high-speed single trains[J]. Journal of the China Railway Society, 2018, 40(7): 10?16.

[15] 趙翔, 趙鵬, 姚向明, 等. 高速列車折扣票價與票額分配組合優化模型[J]. 東南大學學報(自然科學版), 2018, 48(4): 759?765. ZHAO Xiang, ZHAO Peng, YAO Xiangming, et al. An integrated optimization model of discount fare and ticket allocation for high-speed train[J]. Journal of Southeast University (Natural Science Edition), 2018, 48(4): 759? 765.

A divide-and-conquer optimization method for dynamic pricing of high-speed railway based on seat allocation

DENG Lianbo, ZENG Ningxin, CHEN Yuxin, XIAO Longwen

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

This paper studies the dynamic pricing problem based on seat allocation of multiple trains and multiple O-D itineraries on high speed railway. Take the maximum total revenue of multiple trains as the objective function. A joint optimization model of dynamic pricing and seat allocation for multiple trains and multiple O-D itineraries was established. The actual operation requirements were fully considered in the constraint conditions. The model was decomposed into a bilevel programming to solve the problem. Dynamic price and seat allocation were optimized by divide-and-conquer method. The difficulty of solving this kind of large-scale problem was reduced effectively. And improve the solving efficiency. Finally, the model and method were verified with a large scale of example with 20 trains and 350 O-D itineraries. It provided support and reference for the practical application of dynamic pricing.

high speed railway; dynamic pricing; seat allocation; multiple trains; divide-and-conquer optimization

U293

A

1672 ? 7029(2019)10? 2407 ? 07

10.19713/j.cnki.43?1423/u.2019.10.004

2019?01?15

國家自然科學基金資助項目(71471179)；中國鐵路總公司重點課題(N2018X009)

鄧連波(1977?)，男，遼寧昌圖人，教授，從事交通運輸規劃與管理研究；E?mail：lbdeng@csu.edu.cn

(編輯 陽麗霞)