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

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

(北京工業大學 城市建設學部,北京 100124)

0 引 言

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

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

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

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

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

1 問題描述

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

圖1為列車計劃運行圖,G1～G5為在車站1～4之間運行的列車。列車停站計劃是指在特定時間段內,明確列車在途經各個車站停留時間和順序的計劃。

圖1 列車計劃運行圖Fig. 1 Train schedule diagram

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

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

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

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

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

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

2 模型構建

筆者構建了票額分配和停站方案組合優化的模型,主要分為模型假設、目標函數和約束條件等3個部分。

2.1 模型假設和符號定義

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

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

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

假設3:列車在沿途各站均可停站。

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

表1 模型參數Table 1 Model parameter

表2 模型變量Table 2 Model variable

2.2 目標函數

筆者從鐵路公司收益和運營效率這兩方面設置目標函數。

2.2.1 鐵路運輸公司收益最大化

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

(1)

2.2.2 偏離計劃時刻表最小化

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

(2)

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

(3)

(4)

(5)

2.2.3 歸一化處理

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

(6)

若α越大,表明目標函數中鐵路公司的收益權重越大,列車的偏離時間權重越小。

2.3 約束條件

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

2.3.1 停站方案與票額分配相關約束

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

(7)

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

(8)

(9)

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

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

(10)

式(11)～式(12)為票額分配和停站方案一致性約束。表示當列車k沒在車站i?？繒r,分配到以車站i為起點(終點)的旅客數量為0,即當在車站i進行票額分配時,列車k必須在車站i?？?。

(11)

(12)

2.3.2 列車時刻表相關約束

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

(13)

(14)

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

(15)

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

(16)

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

?i∈S{Dk,Dk′}

(17)

?i∈S{Dk,Dk′}

(18)

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

(19)

(20)

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

(21)

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

(22)

(23)

3 算例分析

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

3.1 算例描述

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

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

圖5 列車計劃運行圖Fig. 5 Train schedule diagram

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

3.2 數據準備

3.2.1 票價表

文中假設全部為二等座,參考NJN到SHHQ各區段真實票價,各OD直達票價如表3。

3.2.2 OD需求表

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

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

3.2.3 其他數據

后續20輛列車各區間剩余容量總和與各個區段最小運行時間如表5。

表5 區間剩余容量總和與最小運行時間Table 5 Total remaining capacity of the interval and minimum operating time

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

表6 各站股道數量Table 6 Number of lanes at each station

3.3 算例設計

3.3.1 參數n取值分析

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

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

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

在實際中,調度人員可根據自己的偏好對n進行取值。筆者在優先考慮換乘旅客部分設置n=4來進行后續分析。

3.3.2 不優先考慮換乘旅客

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

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

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

算例中,當α從0.6增加到0.65時,鐵路公司的收益增量最大。圖9為α=0.65時,調整后的列車運行圖。

圖9 調整后的列車運行圖(α=0.65)Fig. 9 Train operation chart after adjustment (α=0.65)

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

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

3.3.3 優先考慮疏散換乘旅客

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

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

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

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

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

圖12 調整后的列車運行圖(α=0.35)Fig. 12 Train operation chart after adjustment (α=0.35)

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

4 結 論

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

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

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