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

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

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

0 引 言

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

票額分配是以客流需求為基礎(chǔ),在一定席位容量限制下設(shè)置各路徑票額數(shù)量的售票方法[1]。當(dāng)列車運(yùn)行發(fā)生突發(fā)情況時,合理的票額分配在一定程度上能達(dá)到及時疏散滯留旅客、減少鐵路公司經(jīng)濟(jì)損失的目的。K．LITTLEWOOD[2]首次在航空領(lǐng)域利用收益管理理論對票額分配進(jìn)行分析,建立了考慮分級票價的票額分配模型;A．CIANCIMINO等[3]首次將收益管理理論引入到鐵路運(yùn)輸領(lǐng)域,建立了非嵌套式票額分配的確定性線性規(guī)劃模型?；诖?學(xué)者們利用該概念對列車票額分配展開了大量研究。在城市軌道領(lǐng)域,由于旅客出行無固定坐席,學(xué)界大多是針對票價定價展開研究[4-6];但我國高鐵采用的是固定坐席制且停站方案復(fù)雜,因此學(xué)者們在對高鐵進(jìn)行票額分配研究時的關(guā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ù),提出了多項式對數(shù)模型和潛類模型形式的離散選擇方法;WANG Xinchang等[10]基于客流需求服從非齊次泊松分布的假設(shè),同步考慮旅客的選擇行為,構(gòu)建了單階段和多階段的票額分配模型,并將上述模型轉(zhuǎn)化為等價確定性模型;強(qiáng)麗霞等[11]基于客流分配技術(shù)的票額分配優(yōu)化基本原理,提出了客流分配流程,并進(jìn)行了票額分配優(yōu)化的研究;宋文波等[12]以收益最大化為目標(biāo),構(gòu)建了單一列車的不確定客流需求動態(tài)定價與票額分配優(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ù)線性規(guī)劃模型。

目前關(guān)于票額分配的研究主要集中在列車運(yùn)行計劃制定階段,其成果無法應(yīng)用于列車取消等突發(fā)情況。當(dāng)部分車次取消情況時,受后續(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)化模型,并通過算例驗證了該模型的有效性。

1 問題描述

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

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

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

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

當(dāng)G1因突發(fā)情況被取消時,為了到達(dá)目的地,滯留旅客會選擇改簽。對于黑色旅客而言,G5在車站2、 3有停站計劃和剩余容量,可以作為改簽的備選列車;對于白色旅客而言,G3、G5均在車站2、 4有停站計劃和剩余容量,可以作為改簽的備選列車。但由于后續(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ù)中存在少量有換乘其他線路需求的旅客(簡稱:換乘旅客)時,可將取消列車中所有旅客視為直達(dá)旅客進(jìn)行疏散;當(dāng)滯留人數(shù)中存在大量換乘旅客時,可優(yōu)先考慮疏散換乘旅客,以免錯過其他線路的接續(xù)列車,造成更大程度的延誤。

2 模型構(gòu)建

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

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

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

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

假設(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)送更多旅客的同時優(yōu)先疏散遠(yuǎn)距離出行旅客。其目標(biāo)函數(shù)Z1如式(1)。

(1)

2.2.2 偏離計劃時刻表最小化

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

(2)

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

(3)

(4)

(5)

2.2.3 歸一化處理

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

(6)

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

2.3 約束條件

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

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?？繒r,分配到以車站i為起點(終點)的旅客數(shù)量為0,即當(dāng)在車站i進(jìn)行票額分配時,列車k必須在車站i?？?。

(11)

(12)

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

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

(13)

(14)

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

(15)

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

(16)

式(17)～式(20)為列車安全間隔約束。表示為確保相鄰兩列車到達(dá)和離開同一車站時的必要安全間隔,保證列車安全運(yùn)行。假定列車的站間旅行時間只與列車速度和車站之間的距離有關(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è)置列車容量約束,以保證列車經(jīng)過該車站時至少有一條空閑線路供其使用。

(21)

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

(22)

(23)

3 算例分析

為驗證文中模型的有效性,筆者以京滬線為背景進(jìn)行算例分析。通過添加中間變量構(gòu)建不等式組,將列車偏離計劃時刻表最小化的非線性方程進(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)行模型驗證。圖4為車站名稱,右側(cè)放大圖中括號內(nèi)的字母為車站代號;圖5為NJN至SHHQ下行區(qū)段上的列車計劃運(yùn)行圖。G0～G20代表各列車編號。

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

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

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

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

3.2.1 票價表

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

3.2.2 OD需求表

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

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

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

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

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

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

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

3.3 算例設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖12為α=0.35時,調(diào)整后列車運(yùn)行圖。圖12中:G18、G20在昆山南站增加停站,后續(xù)列車偏離時刻表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é)合實際情況選用。若滯留旅客較多,則可通過增大α獲得一個疏散滯留旅客較多的解;若滯留旅客較少,則列車準(zhǔn)時性更加關(guān)鍵,應(yīng)選擇使列車總體偏離時間較小的解。

4 結(jié) 論

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

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

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