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

基于票額分配的高速鐵路動態(tài)定價(jià)分治優(yōu)化方法

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

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075)

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

高速鐵路；動態(tài)定價(jià)；票額分配；多列車；分治優(yōu)化

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

1 問題描述

1.1 基本假設(shè)

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

2) 假定各OD對之間的出行需求是相互獨(dú)立的。各個(gè)OD選擇某一列車的客流共同構(gòu)成列車相鄰?fù)Ｕ緟^(qū)間的斷面流，需要滿足列車能力約束。

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

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

1.2 符號定義

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

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

2 模型構(gòu)建

以所有列車所有乘車OD各個(gè)售票時(shí)段的總售票收益最大化為優(yōu)化目標(biāo)，目標(biāo)函數(shù)為

約束條件包含了列車能力約束，非負(fù)約束和各類票價(jià)約束。

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

2) 售票數(shù)量非負(fù)約束。

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

4) 票價(jià)上下界約束：任何時(shí)段、任何列車、任何點(diǎn)對的票價(jià)均滿足上下限的約束。

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

6) 同一列車、同一點(diǎn)對的票價(jià)隨著發(fā)車時(shí)間的接近而單調(diào)增加(或者不下降)。

上述模型可以等價(jià)轉(zhuǎn)換成一個(gè)雙層規(guī)劃模型，其中上層主規(guī)劃模型是多列車多乘車OD的票額分配模型，下層子規(guī)劃模型是單列車單乘車OD的動態(tài)定價(jià)模型，將多列車的動態(tài)價(jià)格策略問題分解為多列車的票額分配計(jì)劃和各列車各乘車OD的動態(tài)定價(jià)策略2部分。

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

以所有列車所有乘車OD各個(gè)售票時(shí)段的總售票收益最大化為優(yōu)化目標(biāo)，目標(biāo)函數(shù)為：

約束條件僅包含預(yù)售期內(nèi)各列車的能力約束。

2.2 下層子規(guī)劃模型：單列車單乘車OD的動態(tài)定價(jià)模型(M2)

以單列車單乘車OD各個(gè)售票時(shí)段的總售票收益最大化為優(yōu)化目標(biāo)，目標(biāo)函數(shù)為：

將式(15)變換可得

約束條件包含乘車OD的票額約束、售票數(shù)量非負(fù)約束和各類票價(jià)約束。

該乘車OD的票額約束為

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

3 模型求解

再結(jié)合式(1)，可得

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

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

5) 返回2)。

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

圖1 模型求解流程圖

4 算例分析

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

表1 算例列車組成表

圖2 總收益收斂圖

圖3 總客座公里收斂圖

表2 G6215次列車的優(yōu)化前后結(jié)果對比

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

5 結(jié)論

1) 構(gòu)建以多列車總收益最大化為目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃模型，并從實(shí)際運(yùn)營的角度考慮，將列車能力限制、票價(jià)的各種約束納入了約束條件，使模型更貼近現(xiàn)實(shí)需求。

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

3) 以實(shí)際運(yùn)營情況作為基礎(chǔ)數(shù)據(jù)進(jìn)行了20列車總計(jì)350個(gè)乘車OD的大規(guī)模算例分析。優(yōu)化后收益增長了2.19%，且快速收斂，得到了各方面均符合預(yù)期的結(jié)果，驗(yàn)證了模型的正確性和求解方法的有效性。

[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模型的平行航班艙位控制與動態(tài)定價(jià)研究[D]. 北京: 北京理工大學(xué), 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] 楊宇航, 張琦. 京滬高速鐵路票價(jià)調(diào)整與優(yōu)化策略研究[J]. 鐵道科學(xué)與工程學(xué)報(bào), 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] 鄭金子. 高速鐵路票價(jià)動態(tài)優(yōu)化方法的研究[D]. 北京: 北京交通大學(xué), 2017. ZHENG Jinzi. Research on ticket fare dynamic optimization for high-speed train[D]. Beijing: Beijing Jiaotong University, 2017.

[14] 宋文波, 趙鵬, 李博. 高速鐵路單列車動態(tài)定價(jià)與票額分配綜合優(yōu)化研究[J]. 鐵道學(xué)報(bào), 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] 趙翔, 趙鵬, 姚向明, 等. 高速列車折扣票價(jià)與票額分配組合優(yōu)化模型[J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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

國家自然科學(xué)基金資助項(xiàng)目(71471179)；中國鐵路總公司重點(diǎn)課題(N2018X009)

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

(編輯 陽麗霞)