面向車次取消的票額分配與停站方案組合優(yōu)化研究

孫立山,劉伊娜,許 琰,孔德文,邵 娟

(北京工業(yè)大學(xué) 城市建設(shè)學(xué)部,北京 100124)

0 引 言

高速鐵路(高鐵)給出行帶來了極大地方便,并在一定程度上刺激了沿線城市的經(jīng)濟(jì)發(fā)展。但高鐵的建設(shè)投資大、運(yùn)營維護(hù)成本高、回報(bào)周期長,鐵路公司面臨著嚴(yán)重的債務(wù)問題。當(dāng)列車受到嚴(yán)重干擾而被取消時(shí),大量的旅客將會在車站滯留;若不及時(shí)疏散滯留旅客,不僅會激化旅客的不滿情緒,還會造成客流流失,進(jìn)一步加重鐵路公司的經(jīng)濟(jì)損失。因此,當(dāng)在列車被取消情況下,如何有序、高效地疏散滯留旅客,對保證列車服務(wù)質(zhì)量、減少鐵路公司損失具有重要的現(xiàn)實(shí)意義。

票額分配是以客流需求為基礎(chǔ),在一定席位容量限制下設(shè)置各路徑票額數(shù)量的售票方法[1]。當(dāng)列車運(yùn)行發(fā)生突發(fā)情況時(shí),合理的票額分配在一定程度上能達(dá)到及時(shí)疏散滯留旅客、減少鐵路公司經(jīng)濟(jì)損失的目的。K．LITTLEWOOD[2]首次在航空領(lǐng)域利用收益管理理論對票額分配進(jìn)行分析,建立了考慮分級票價(jià)的票額分配模型;A．CIANCIMINO等[3]首次將收益管理理論引入到鐵路運(yùn)輸領(lǐng)域,建立了非嵌套式票額分配的確定性線性規(guī)劃模型。基于此,學(xué)者們利用該概念對列車票額分配展開了大量研究。在城市軌道領(lǐng)域,由于旅客出行無固定坐席,學(xué)界大多是針對票價(jià)定價(jià)展開研究[4-6];但我國高鐵采用的是固定坐席制且停站方案復(fù)雜,因此學(xué)者們在對高鐵進(jìn)行票額分配研究時(shí)的關(guān)注點(diǎn)也不盡相同。

作為票額分配的數(shù)據(jù)基礎(chǔ),客流需求對票額分配優(yōu)劣有至關(guān)重要的影響。R．GOPALAKRISHNAN等[7]基于長距離旅客的需求,構(gòu)建了票額分配的確定性線性規(guī)劃模型,并對印度鐵路票額分配方法進(jìn)行了研究;包云等[8]將客流需求的預(yù)測模型嵌入到隨機(jī)票額分配模型中,將得到的各OD確定性等客流作為輸入,構(gòu)建了以收益最大化為目標(biāo)的單列車票額分配模型;P．HETRAKUL等[9]從旅客行為出發(fā),在票額分配問題中引入乘客選擇行為和需求的函數(shù),提出了多項(xiàng)式對數(shù)模型和潛類模型形式的離散選擇方法;WANG Xinchang等[10]基于客流需求服從非齊次泊松分布的假設(shè),同步考慮旅客的選擇行為,構(gòu)建了單階段和多階段的票額分配模型,并將上述模型轉(zhuǎn)化為等價(jià)確定性模型;強(qiáng)麗霞等[11]基于客流分配技術(shù)的票額分配優(yōu)化基本原理,提出了客流分配流程,并進(jìn)行了票額分配優(yōu)化的研究;宋文波等[12]以收益最大化為目標(biāo),構(gòu)建了單一列車的不確定客流需求動(dòng)態(tài)定價(jià)與票額分配優(yōu)化模型。

作為票額分配的關(guān)鍵約束,停站方案往往嵌入到票額分配的協(xié)同優(yōu)化中。C．K．LEE等[13]將列車需求模型描述為具有廣義成本函數(shù)的路徑選擇問題,并構(gòu)建了上層考慮運(yùn)營成本,下層考慮乘客出行的雙層規(guī)劃模型;HAN Bing等[14]以旅客滿意度和平均入座率最大化為目標(biāo),搭建了高速鐵路停站方案與票額分配的通用建模框架;趙翔等[15]基于多列車、多停站場景,構(gòu)建了以收益最大化為目標(biāo)的非線性整數(shù)票額分配模型;V．CACCHIANI等[16]在需求不確定情況下,通過限制列車旅行時(shí)間和停靠站數(shù)量,提出了求解停站方案和列車時(shí)刻表的整數(shù)線性規(guī)劃模型。

目前關(guān)于票額分配的研究主要集中在列車運(yùn)行計(jì)劃制定階段,其成果無法應(yīng)用于列車取消等突發(fā)情況。當(dāng)部分車次取消情況時(shí),受后續(xù)列車停站方案限制,滯留旅客疏散需要增加停站,并同步調(diào)整后續(xù)列車的運(yùn)行圖;此外,滯留旅客中還存在著換乘其他線路的旅客,這就導(dǎo)致票額分配的情況更加復(fù)雜。因此,筆者基于列車容量限制的前提,分別考慮不優(yōu)先疏散換乘旅客(no priority transfer passenger, NPT)和優(yōu)先疏散換乘旅客(priority transfer passenger, PT)這兩種情況,以停站方案與票額為決策變量,將后續(xù)列車剩余載客能力與列車停站約束進(jìn)行關(guān)聯(lián),構(gòu)建了票額分配和停站方案組合的優(yōu)化模型,并通過算例驗(yàn)證了該模型的有效性。

1 問題描述

我國高速列車采用的是指定坐席制的票額分配方式。旅客在乘坐列車前,通常會提前購票并按照規(guī)定時(shí)間在規(guī)定座位就座。因此,當(dāng)某些車次被取消時(shí),對于被取消列車的旅客而言,只能選擇在出發(fā)站和目的站均有停站計(jì)劃且有剩余座位的后續(xù)列車。由于列車剩余容量有限,被取消列車的旅客可能無法全部成功改簽到最早的后續(xù)列車上,導(dǎo)致部分旅客在車站等待時(shí)間較長或改選其他交通方式,這就進(jìn)一步對鐵路公司收益和旅客滿意度造成損害。針對上述問題,筆者分別考慮NPT和PT兩種情況,采取靈活停站策略,對被取消列車的旅客重新進(jìn)行票額分配,以幫助旅客快速改簽到后續(xù)列車,完成出行計(jì)劃。

圖1為列車計(jì)劃運(yùn)行圖,G1～G5為在車站1～4之間運(yùn)行的列車。列車停站計(jì)劃是指在特定時(shí)間段內(nèi),明確列車在途經(jīng)各個(gè)車站停留時(shí)間和順序的計(jì)劃。

圖1 列車計(jì)劃運(yùn)行圖Fig. 1 Train schedule diagram

圖1中:所有列車在起始站和終點(diǎn)站必須停車,G1在中間車站2、3有停站計(jì)劃,G2在中間車站3有停站計(jì)劃,G3在中間車站2有停站計(jì)劃,G4在中間車站2、 3無停站計(jì)劃,G5在在中間車站2、 3有停站計(jì)劃。乘客只有在具有停站計(jì)劃的車站才能進(jìn)行乘降,其他車站無法組織旅客乘降。G2～G5是G1的后續(xù)列車且剩余載客能力均為1。白色和黑色旅客均準(zhǔn)備乘坐G1從車站2出發(fā),黑色旅客的目的地為車站3,白色旅客的目的地為車站4。

當(dāng)G1因突發(fā)情況被取消時(shí),為了到達(dá)目的地,滯留旅客會選擇改簽。對于黑色旅客而言,G5在車站2、 3有停站計(jì)劃和剩余容量,可以作為改簽的備選列車;對于白色旅客而言,G3、G5均在車站2、 4有停站計(jì)劃和剩余容量,可以作為改簽的備選列車。但由于后續(xù)列車容量和停站方案限制,滯留旅客可能改簽失敗,如圖2。

圖2 滯留旅客搭乘后續(xù)列車方案Fig. 2 The plan for stranded passengers to board subsequent trains

為滿足滯留旅客的出行需求,工作人員可在需求較大且后續(xù)列車有剩余容量的車站增加停站,如圖3。G2、 G4在車站2增加停站后,G2成為黑色旅客的備選列車,G4成為白色旅客的備選列車。在停站方案調(diào)整后,通過重新分配票額來疏散滯留旅客,使得旅客順利完成出行。

圖3 增加停站后,滯留旅客搭乘后續(xù)列車Fig. 3 After adding stops, stranded passengers can board subsequent trains

此外,當(dāng)滯留人數(shù)中存在少量有換乘其他線路需求的旅客(簡稱:換乘旅客)時(shí),可將取消列車中所有旅客視為直達(dá)旅客進(jìn)行疏散;當(dāng)滯留人數(shù)中存在大量換乘旅客時(shí),可優(yōu)先考慮疏散換乘旅客,以免錯(cuò)過其他線路的接續(xù)列車,造成更大程度的延誤。

2 模型構(gòu)建

筆者構(gòu)建了票額分配和停站方案組合優(yōu)化的模型,主要分為模型假設(shè)、目標(biāo)函數(shù)和約束條件等3個(gè)部分。

2.1 模型假設(shè)和符號定義

高鐵的上下行方向列車分別占用不同的正線和到發(fā)線,相互獨(dú)立不干擾,因此筆者針對雙線鐵路的單一方向票額分配和停站方案組合優(yōu)化進(jìn)行分析。為研究方便,筆者做如下假設(shè):

假設(shè)1:滯留旅客不改變其需求,目的地為原計(jì)劃車站;

假設(shè)2:滯留旅客僅在同一線路的單方向上進(jìn)行改簽,不考慮跨線改簽;

假設(shè)3:列車在沿途各站均可停站。

模型所用符號及定義如表1、表2。

表1 模型參數(shù)Table 1 Model parameter

表2 模型變量Table 2 Model variable

2.2 目標(biāo)函數(shù)

筆者從鐵路公司收益和運(yùn)營效率這兩方面設(shè)置目標(biāo)函數(shù)。

2.2.1 鐵路運(yùn)輸公司收益最大化

鐵路公司的收益與疏散旅客數(shù)量呈正相關(guān)。以鐵路公司收益最大化為目標(biāo),在盡可能運(yùn)送更多旅客的同時(shí)優(yōu)先疏散遠(yuǎn)距離出行旅客。其目標(biāo)函數(shù)Z1如式(1)。

(1)

2.2.2 偏離計(jì)劃時(shí)刻表最小化

采用靈活停站策略會對原有的列車運(yùn)行圖帶來影響。列車運(yùn)行圖調(diào)整過程中,為保證列車上原有旅客的出行計(jì)劃,調(diào)整后的運(yùn)行圖應(yīng)盡量減少與原有運(yùn)行圖的時(shí)間偏差,該目標(biāo)函數(shù)Z2可通過式(2)來實(shí)現(xiàn)。

(2)

為將式(2)線性化,引入中間決策變量aki和dki。由于列車調(diào)整后實(shí)際離開的時(shí)間不能早于計(jì)劃時(shí)間,故需要對列車實(shí)際到達(dá)時(shí)間與計(jì)劃到達(dá)時(shí)間的差值進(jìn)行線性化處理,如式(3)～式(5)。

(3)

(4)

(5)

2.2.3 歸一化處理

為消除不同數(shù)據(jù)之間的量綱影響,需要將數(shù)據(jù)轉(zhuǎn)換成無量綱的純數(shù)值。筆者所考慮的兩個(gè)目標(biāo)函數(shù)單位分別為金額和時(shí)間,這兩個(gè)函數(shù)值相差較大,若直接進(jìn)行分析,會突出金額在分析中的作用;故需將目標(biāo)函數(shù)進(jìn)行歸一化處理,使得各數(shù)據(jù)處于同一數(shù)量級后再進(jìn)行分析。

(6)

若α越大,表明目標(biāo)函數(shù)中鐵路公司的收益權(quán)重越大,列車的偏離時(shí)間權(quán)重越小。

2.3 約束條件

為安全快速的疏散滯留旅客并保證所得解的可行性,筆者構(gòu)建了列車停站方案、票額分配、列車時(shí)刻表等約束集。

2.3.1 停站方案與票額分配相關(guān)約束

式(7)為原有的停站約束。表示保留列車k原有的停站方案,保證對原有旅客的客運(yùn)服務(wù)。

(7)

式(8)～式(9)為旅客需求約束。表示分配到列車k上OD對為(i,j)的票額數(shù)量不大于總需求。

(8)

(9)

式(10)為剩余容量約束。表示保證分配到每一列車上的旅客數(shù)量不能超過該列車的剩余容量。

?k∈K,?i∈S{Dk}

(10)

式(11)～式(12)為票額分配和停站方案一致性約束。表示當(dāng)列車k沒在車站i停靠時(shí),分配到以車站i為起點(diǎn)(終點(diǎn))的旅客數(shù)量為0,即當(dāng)在車站i進(jìn)行票額分配時(shí),列車k必須在車站i停靠。

(11)

(12)

2.3.2 列車時(shí)刻表相關(guān)約束

式(13)～式(14)為到發(fā)時(shí)間約束。若因增加停站而需要對列車運(yùn)行圖進(jìn)行調(diào)整,則調(diào)整后的列車在各個(gè)車站實(shí)際發(fā)車時(shí)間不能早于計(jì)劃發(fā)車時(shí)間;同時(shí)考慮到列車上有換乘旅客,因此到達(dá)晚點(diǎn)時(shí)間不能超過換乘旅客的可接受范圍。

(13)

(14)

式(15)為區(qū)間運(yùn)行時(shí)間約束。表示列車區(qū)間運(yùn)行時(shí)分不小于最小運(yùn)行時(shí)分。

(15)

式(16)為最小停站時(shí)間約束。表示列車若在某一車站停車時(shí),則停站時(shí)間不能小于完成必要技術(shù)操作所需要的最小時(shí)間;若列車在某一車站不停車,則停站時(shí)間為0。

(16)

式(17)～式(20)為列車安全間隔約束。表示為確保相鄰兩列車到達(dá)和離開同一車站時(shí)的必要安全間隔,保證列車安全運(yùn)行。假定列車的站間旅行時(shí)間只與列車速度和車站之間的距離有關(guān),且不允許列車在車站區(qū)間內(nèi)進(jìn)行越行。故相鄰兩列車離開車站i的順序即為其在下一車站i+1的到達(dá)順序。

?i∈S{Dk,Dk′}

(17)

?i∈S{Dk,Dk′}

(18)

k,k′∈K,?i∈S{Dk,Dk′}

(19)

(20)

式(21)～式(23)為車站容量約束。由于列車到達(dá)或通過車站時(shí)必須占用車站線路且同一線路在同一時(shí)間只能被一列列車占用,而每個(gè)車站線路數(shù)量有限,因此需要設(shè)置列車容量約束,以保證列車經(jīng)過該車站時(shí)至少有一條空閑線路供其使用。

(21)

?k≠k′,k,k′∈K,?i∈S{Ok,Ok′,Dk,Dk′}

(22)

(23)

3 算例分析

為驗(yàn)證文中模型的有效性,筆者以京滬線為背景進(jìn)行算例分析。通過添加中間變量構(gòu)建不等式組,將列車偏離計(jì)劃時(shí)刻表最小化的非線性方程進(jìn)行了線性化處理,優(yōu)化模型均為線性方程。使用CPU為Intel(R) Core(TM) i7-7700HQ CPU@2.80 GHz,內(nèi)存為16 GB的服務(wù)器,在Python3.7中調(diào)用GUROBI9.5.1商業(yè)求解器對模型進(jìn)行求解。

3.1 算例描述

筆者以京滬高鐵為背景,以南京南站到上海虹橋站下行區(qū)段為算例進(jìn)行模型驗(yàn)證。圖4為車站名稱,右側(cè)放大圖中括號內(nèi)的字母為車站代號;圖5為NJN至SHHQ下行區(qū)段上的列車計(jì)劃運(yùn)行圖。G0～G20代表各列車編號。

圖4 京滬高鐵車站示意Fig. 4 The Beijing-Shanghai high-speed railway

圖5 列車計(jì)劃運(yùn)行圖Fig. 5 Train schedule diagram

假設(shè)G0(虛線)受到嚴(yán)重?cái)_動(dòng)而被取消發(fā)車,后續(xù)列車均可正點(diǎn)發(fā)車。考慮到從NJN到SHHQ的乘客還可選擇其他交通替代方式,例如客車大概需要4 h,故滯留旅客若等待后續(xù)列車時(shí)間過長,則會退票并選擇其他交通方式出行,這對鐵路運(yùn)營收益造成較大損失。故筆者只選取運(yùn)行時(shí)間在4 h之內(nèi)的后續(xù)20列列車(實(shí)線,車次從左到右為G1～G20)。

3.2 數(shù)據(jù)準(zhǔn)備

3.2.1 票價(jià)表

文中假設(shè)全部為二等座,參考NJN到SHHQ各區(qū)段真實(shí)票價(jià),各OD直達(dá)票價(jià)如表3。

3.2.2 OD需求表

設(shè)置各列車每個(gè)區(qū)間最大載客量為810人,G0停站方案為NJN—ZJN—CZB—KSN—SHHQ,共服務(wù)10個(gè)OD區(qū)間,G0各OD區(qū)間的需求如表4。其中滯留旅客人數(shù)為各個(gè)OD對人數(shù)之和,共計(jì)1 060人。

表4 列車G0的OD區(qū)間需求Table 4 OD interval demand for train G0

3.2.3 其他數(shù)據(jù)

后續(xù)20輛列車各區(qū)間剩余容量總和與各個(gè)區(qū)段最小運(yùn)行時(shí)間如表5。

表5 區(qū)間剩余容量總和與最小運(yùn)行時(shí)間Table 5 Total remaining capacity of the interval and minimum operating time

假設(shè)始發(fā)站與終點(diǎn)站有足夠多的股道數(shù)量,參考“京滬高速鐵路動(dòng)車組停車站到發(fā)線安排”,算例中各站股道數(shù)量設(shè)置如表6。此外相鄰兩列車到達(dá)和發(fā)車時(shí)間隔最小停站時(shí)間均為2 min,旅客可接受的到達(dá)晚點(diǎn)時(shí)間為5 min。

表6 各站股道數(shù)量Table 6 Number of lanes at each station

3.3 算例設(shè)計(jì)

3.3.1 參數(shù)n取值分析

為深入了解參數(shù)n對旅客疏散效果的影響,設(shè)定不同的α,并分析n取值從1～10對具有換乘需求滯留旅客疏散數(shù)量的影響,如圖6。

圖6 不同α和n時(shí),疏散換乘旅客數(shù)量Fig. 6 The number of evacuated passengers with transfer requirement for differen α and n

由圖6可知:當(dāng)α固定,隨著n的增加,疏散具有換乘需求的旅客數(shù)量也顯著增加。特別是當(dāng)n取較大值時(shí),即便α為一個(gè)相對較小的數(shù),但仍可疏散較多具有換乘需求的旅客。具體而言,α=0.2時(shí),當(dāng)n從1增加至10,疏散具有換乘需求旅客數(shù)量增加了86.67%。

在實(shí)際中,調(diào)度人員可根據(jù)自己的偏好對n進(jìn)行取值。筆者在優(yōu)先考慮換乘旅客部分設(shè)置n=4來進(jìn)行后續(xù)分析。

3.3.2 不優(yōu)先考慮換乘旅客

在NPT情況下,可通過靈活停站策略對滯留旅客進(jìn)行疏散。圖7表示不同α下的疏散旅客數(shù)量與實(shí)際收益關(guān)系;圖8表示不同α下的列車偏離時(shí)間與增加停站數(shù)量關(guān)系。由圖7、圖8可知:隨著α增大,疏散的滯留旅客數(shù)量增多,鐵路公司收益增加,列車增加停站數(shù)量增多,列車偏離時(shí)刻表時(shí)間也隨之增長。這說明為疏散滯留旅客而增加停站,對列車偏離原時(shí)刻表時(shí)間有一定影響。除此之外,在一定范圍內(nèi)改變目標(biāo)函數(shù)權(quán)重系數(shù)并不會改變最優(yōu)解,且隨著滯留旅客數(shù)量減少,α增大對鐵路公司收益的影響程度也隨之減少。

圖7 NPT時(shí),不同α的疏散旅客數(shù)量與實(shí)際收益Fig. 7 Number of evacuated passengers and the actual revenue for different α in the NPT case

圖8 NPT時(shí),不同α的列車偏離時(shí)間與增加停站數(shù)量Fig. 8 Train deviation time and the number of adding stops for different α in the NPT case

算例中,當(dāng)α從0.6增加到0.65時(shí),鐵路公司的收益增量最大。圖9為α=0.65時(shí),調(diào)整后的列車運(yùn)行圖。

圖9 調(diào)整后的列車運(yùn)行圖(α=0.65)Fig. 9 Train operation chart after adjustment (α=0.65)

圖9中:G13、G15在昆山南站增加停站,后續(xù)列車偏離時(shí)刻表4 min,疏散人數(shù)增加26.8%,鐵路公司收益增加27.0%,相應(yīng)的票額分配方案如表7。

表7 票額分配結(jié)果(α=0.65)Table 7 Ticket allocation results (α=0.65)

3.3.3 優(yōu)先考慮疏散換乘旅客

當(dāng)取消列車中換乘旅客的數(shù)量較多時(shí),可優(yōu)先考慮疏散換乘旅客。圖10為不同α下的疏散旅客數(shù)量與實(shí)際收益(PT情況下);圖11為不同α下的列車偏離時(shí)間與增加停站數(shù)量(PT情況下)。由圖10、圖11可知:在PT情況下,隨著α增大,疏散滯留旅客數(shù)量與列車偏離時(shí)刻表時(shí)間的變化趨勢與NPT基本相同。算例中,當(dāng)α從0.3增加到0.35時(shí),鐵路公司的收益增量最大。

圖10 PT時(shí),不同α的疏散旅客數(shù)量與實(shí)際收益Fig. 10 Number of evacuated passengers and the actual revenue for different α in the PT case

圖11 PT時(shí),不同α的列車偏離時(shí)間與增加停站數(shù)量Fig. 11 Train deviation time and the number of adding stops for different α in the PT case

圖12為α=0.35時(shí),調(diào)整后列車運(yùn)行圖。圖12中:G18、G20在昆山南站增加停站,后續(xù)列車偏離時(shí)刻表4 min,疏散人數(shù)增加19.7%,鐵路公司收益增加21.8%,相應(yīng)的票額分配方案如表8。

表8 票額分配結(jié)果(α=0.35)Table 8 Ticket allocation results (α=0.35)

圖12 調(diào)整后的列車運(yùn)行圖(α=0.35)Fig. 12 Train operation chart after adjustment (α=0.35)

綜上可知:在不優(yōu)先疏散換乘旅客和優(yōu)先疏散換乘旅客這兩種情況下,采用靈活停站策略可有效地疏散滯留旅客。此外,α取值應(yīng)結(jié)合實(shí)際情況選用。若滯留旅客較多,則可通過增大α獲得一個(gè)疏散滯留旅客較多的解;若滯留旅客較少,則列車準(zhǔn)時(shí)性更加關(guān)鍵,應(yīng)選擇使列車總體偏離時(shí)間較小的解。

4 結(jié) 論

1)筆者針對當(dāng)列車取消時(shí),利用票額分配來疏散滯留旅客的問題進(jìn)行了研究。研究表明:針對不優(yōu)先疏散換乘旅客和優(yōu)先疏散換乘旅客這兩種情況,采用靈活的停站策略可有效疏散滯留旅客。

2)采用靈活停站策略時(shí),應(yīng)根據(jù)滯留旅客數(shù)量靈活選用α值。若滯留旅客較多,則應(yīng)通過增大α獲得一個(gè)疏散滯留旅客較多的解;若滯留旅客較少,則列車準(zhǔn)時(shí)性更加關(guān)鍵,應(yīng)選擇使列車總體偏離時(shí)間較小的解。α從0.6增加到0.65時(shí)(PT情況下),鐵路公司收益增量最大,疏散人數(shù)增加26.8%,收益增加27.0%;當(dāng)α從0.3增加到0.35時(shí)(NPT情況下),鐵路公司收益增量最大,疏散人數(shù)增加19.7%,收益增加21.8%。

4)隨著問題規(guī)模的擴(kuò)大,如何根據(jù)問題特點(diǎn)設(shè)計(jì)更加高效的算法(比如滾動(dòng)時(shí)域算法)是筆者下一步研究的重點(diǎn)。