考慮旅客多維出行需求的動態列車開行方案優化

孫國鋒，景 云,2，馬亞雯

(1.北京交通大學 交通運輸學院, 北京 100044; 2.北京交通大學 智慧高鐵系統前沿科學中心, 北京 100044;3.中國市政西北設計研究院有限公司，甘肅 蘭州 730030)

現階段高速鐵路(以下簡稱“高鐵”)旅客的出行需求呈現多維化，個性化的特點[1]。傳統列車開行方案在給定客流總量基礎上，決策列車起訖點，開行數量及停站方案等內容[2]，較少考慮對旅客出行時刻、旅行時間和票價等需求的響應。因此，有必要根據多維個性化客流需求，研究匹配旅客多維出行需求的動態列車開行方案優化問題。

列車開行方案的研究思路一般基于客流需求總量[3-5]和備選集思想[6-10]，編制滿足旅客空間位移需求的開行方案。文獻[3-5]均采用雙層規劃方法建立列車開行方案模型。為簡化列車開行方案優化問題規模，一些研究預先給定部分變量，在此基礎上優化其余變量，例如文獻[6]在給定列車停站方案的基礎上，優化列車運行路徑和客流徑路，文獻[7]預先給定了列車的起訖站等；還有一些研究采用壓縮變量可行域的方法簡化問題，如文獻[8]在生成備選開行列車集合基礎上研究列車開行方案問題。在求解策略方面，文獻[3-5]均設計了啟發式求解方法，而在運用備選集思想簡化問題后，也可以使用多項式算法求解列車開行方案問題，如列生成算法[6]、拉格朗日松弛算法[8]等。上述研究較少考慮旅客時間需求，導致列車開行方案難以滿足多維旅客出行需求。

近年來，也有學者在研究列車開行方案問題中考慮了客流時變需求[11-14]。文獻[11]考慮旅客出行時變需求，在列車開行方案中引入時間要素，得到了匹配時變需求的列車開行方案；文獻[12]在傳統列車開行方案中增加了列車始發時間的估計值，運用雙層規劃方法研究了面向服務水平的高鐵列車開行方案優化問題；文獻[13]在研究城際高鐵開行方案中引入了客流出行時間信息，基于時空網絡構建了開行方案優化模型，對客流時變特征明顯的城際鐵路列車開行方案進行了研究。雖然部分研究將旅客的時變需求引入列車開行方案問題中，但未考慮旅客出行需求與列車開行方案之間互相反饋的影響關系，未系統的考慮旅客多維度出行需求對列車開行方案問題的影響。

不同于傳統列車開行方案優化問題，本文考慮了出行時刻、旅行時間、票價等旅客需求，引入動態列車開行方案概念，在傳統開行方案決策變量基礎上，優化列車的始發時刻。

1 動態列車開行方案的內涵

1.1 動態列車開行方案定義

列車開行方案在較長的時間周期中(1年或2年)是靜態不變的，僅在新編列車運行圖之前進行微調。然而，隨著高鐵旅客出行需求的個性化發展，應當考慮旅客的出行選擇行為，動態優化列車開行方案。因此，動態列車開行方案是指，以滿足旅客出行需求為目標，確定起訖站、停站方案、開行數量等靜態指標及出發時刻、列車等級、票價等影響乘客出行選擇行為的動態指標。

傳統的列車開行方案問題一般是以OD客流量為驅動，決策開行方案靜態指標[15]，在客流分配過程中不考慮旅客出行選擇行為。動態列車開行方案在考慮旅客選擇行為的基礎上，動態分配客流，優化列車始發時刻等動態指標，與開行方案-運行圖協同優化問題的區別在于動態列車開行方案優化不考慮運行線沖突消解問題。

1.2 動態列車開行方案優化問題描述

沿高鐵列車運行方向，車站集合為U={1,2,3,…,m}，m為車站數，車站u∈U由列車始發終到候選車站和非始發終到候選車站兩類組成，見圖1。

圖1 高鐵線路示意

本文提出考慮旅客多維出行需求的動態列車開行方案優化，主要研究思路為：首先，基于高鐵線路的最小列車追蹤時間值，生成研究時段內可行開行列車備選集合。然后，以備選開行列車集合為輸入，基于時空網絡構建動態列車開行方案優化問題模型；模型的輸入為路網信息、備選列車信息、旅客需求信息；目標函數為系統效用最大化；決策變量為列車選擇開行弧段變量和客流分配變量；模型輸出為列車開行和客流分配方案，其中列車開行方案包括開行列車對數、每列車的發車時刻、列車停站。最后，設計基于模擬退火算法框架的求解算法，并以實際案例驗證模型和算法的有效性。

在建立模型時，重點圍繞旅客需求與動態開行方案之間的關系進行優化，因此需要對高鐵運輸服務過程中的影響因素進行假設：

(1)列車的所有席位為二等座。

(2)所有列車均采用固定編組的方式，并且列車的定員一致。

(3)計算列車在區間運行時間時，只考慮區間純運行時分，不考慮起停車附加時分[16]。

(4)在優化動態列車開行方案中，假設各車站候車能力和到發線能力充足。

1.3 符號說明

動態列車開行方案優化模型的相關集合、索引、參數和變量見表1。

表1 集合、索引、參數和變量

2 旅客多維出行需求及時空網絡

2.1 多維旅客出行需求分析

影響旅客出行選擇行為的主要因素包括旅行時間、期望出發時刻和票價等。基于旅客出行選擇的3個需求屬性，在效用函數中考慮3個影響因素，分別是旅行時間Tn,i，旅客期望出行時間偏差πn,i和票價Fn,i。則旅客群體n選擇列車i的效用函數μn,i為

μn,i=α1Tn,i+α2πn,i+Fn,i

(1)

(2)

MNL模型通常會高估或錯誤分配重新選擇概率，而廣義吸引模型(Generalized Attraction Model，GAM)可以有效解決該問題[17]，準確描述旅客對列車的選擇行為。

在GAM中，wn,i為列車i∈I對旅客群體n的影子吸引力，則旅客群體n選擇任列車i∈I′的概率pn,i為

(3)

(4)

根據式(4)可更準確描述高鐵旅客的決策過程。

2.2 時空網絡構建

利用時空網絡描述動態列車開行方案優化問題，時空網絡有向圖為G=(H，A)。(u,s)∈H表示時間坐標為s、空間坐標為u的節點，弧(u,v,s,t)∈A表示在s時刻從節點u出發至t時刻到達節點v的路徑。

時空網絡構建過程見圖2，包含2類弧段，分別為運行弧和停站弧。其中運行弧是連接相鄰兩車站頂點之間的弧段；停站弧是連接同一車站節點不同時刻之間的弧段。列車對時空網絡弧段占用形成了完整的列車時空路徑，可描述列車在各站的到發時刻及停站方案。

圖2 時空網絡示意

3 模型建立

3.1 目標函數

綜合考慮企業運營收益和旅客出行需求，以系統的整體效用最大為目標，從最大化高鐵運輸收益、最小化旅客總旅行時間損失和期望出發時間偏差等3方面來構造目標函數。目標函數為

(ω1Fn,i-ω2α1Tn,i-ω3α2πn,i)

(5)

(6)

(7)

3.2 約束條件

(1)列車流平衡約束

(8)

(2)列車始發終到車站約束

列車必須從始發、終到候選集合中選擇始發車站和終到車站

(9)

(3)客流分配約束

對同一時段內相同起訖點的客流進行合并，形成旅客群體。每個旅客群體最多只能選擇一列高鐵列車出行。

(10)

(11)

(4)客流平衡約束

任意旅客群體只能在一個時空節點上車或者下車，則客流平衡約束為

?(u,s)∈V

(12)

(13)

(14)

(15)

(5)列車能力約束

列車所分配的旅客數量不得超過列車的額定載客能力，即

(16)

(6)開行列車數量約束[13]

模型的目標函數主要考慮旅客多維出行需求，可能會造成開行列車數量越多，目標函數越好的情況。因此，在保證旅客服務質量的同時，為了減少高速鐵路企業的運營成本，應對列車開行數量進行約束

Num(Ω)≤Nummax

(17)

(7)安全間隔約束

列車在始發站的出發時刻必須滿足安全出發間隔。約束為

(18)

(8)變量約束為

(19)

(20)

(21)

(22)

4 算法設計

本文構建的非線性整數規劃模型為NP-hard問題，很難在多項式時間內求解，元啟發式算法對求解該類問題具有很好的效果，作為元啟發式算法之一的模擬退火算法被多次運用求解列車開行方案問題[11,13-14,18]。因此，本文結合問題特點，基于模擬退火算法框架設計求解算法。

運用模擬退火算法求解動態列車開行方案問題的思路如下：生成由停站方案、列車在始發站發車時刻、客流分配三部分組成的初始解；通過設計刪除列車、拆分列車、超出上座率客流調整、未分配客流重新分配等方法生成鄰域解；在內層循環中，分別設計隨機交換停站信息和合并開行列車策略，若產生新解優于當前解，則用新解替換當前解，否則，按給定的概率隨機替換當前解；在算法外層，保存算法歷史最優解；當滿足算法終止條件時算法結束，得到動態開行方案最優解。

4.1 初始解的生成

(1)解的表達形式

動態列車開行方案初始解的構成包括列車開行解和客流分配解兩部分，即問題的解Ω為

(23)

(24)

式中：Ti為列車i的開行解，由停站方案和列車發車時刻組成；Pi為分配給列車i的客流。STi為列車i的停站，表示列車在沿途各車站的停站弧占用情況，取值為0或1；DTi為列車i的發車時刻，表示列車i在始發站占用列車運行弧的情況。由于列車在各區間的運行時分和停站時長已知，可通過式(24)確定列車在各站的到發時刻。

(2)基于貪心算法的初始解生成方法

在生成初始解的過程中，客流分配解采用貪心算法生成，在客流分配解的基礎上，根據分配客流的始發終到車站需求，生成列車開行解。客流分配解生成的方法如下。

遍歷長度為m的旅客群體列表，每次選擇一個未分配的旅客群體進行分配，遍歷旅客群體的期望出發時間序列，將該旅客群體分配給期望出發時間偏差最小的列車，執行m次迭代后將返回的結果作為客流分配的初始結果。具體流程如下：

Step1初始化。初始化客流分配列表，生成n行m列取值為0的二維初始客流分配列表。

Step2基于貪心算法生成客流分配列表。

生活中，我們可以有意制造這樣的機會。比如：當孩子請你幫他做一件事時，你可以告訴他：“媽媽還有事，五分鐘后能幫你，你可以等一會嗎？”當孩子問你問題時，你不妨說：“這個問題很有意思，讓媽媽想一下，你也再思考下，五分鐘后我們來交換答案好嗎？”當孩子渴望立即得到回應，興奮地要跟你講一件事時，如果你正在忙，大可不必停下手中事轉向他，而是可以讓他稍作等待。

for 每個旅客群體n∈N

初始化旅客群體n的期望出發時間偏差列表。

for 每列車i∈I

計算期望出發時間偏差πn,i，將旅客群體n對每列車的期望出發時間偏差添加到期望出發時間偏差列表中。

Step3計算旅客群體n的期望出發時間偏差列表中的最小值。

Step4將最小值對應索引處的客流分配結果由0改為1。

Step5通過貪心算法可生成期望出發時間偏差值相對較好的客流分配初始解，合并列車開行初始解和客流分配初始解便可生成動態列車開行方案問題的初始解。

4.2 鄰域解的生成

動態列車開行方案生成鄰域解，需要同時考慮列車開行解和客流分配解，生成策略主要包括：停開列車、拆分列車、超出上座率閾值的客流分配調整、未分配客流重新分配。

(1)停開列車和拆分列車[13]

檢查每列車在各區間的上座率，若某列車在各區間的上座率均小于規定停開列車閾值，則停開該列車。若某列車在某區間的上座率小于規定拆分列車閾值，對列車進行拆分，停開低于閾值區間的列車，更新拆分列車后新列車在始發站的發車時刻。

(2)調整超出上座率閾值的客流分配

檢查每列車在各弧段的上座率，如果列車在某弧段的上座率大于上座率閾值，首先計算超出上座率閾值的客流數量；然后隨機搜索上座率小于上座率閾值的列車，按照期望出發時間偏差由大到小將超出客流在客流分配列表中的值由1改為0，直至所有弧段上座率滿足列車能力約束。

(3)未分配客流重新分配

當停開列車、拆分列車及調整超出上座率閾值的客流分配后，可能存在未分配的客流，重新分配該部分客流，直至所有客流均被分配。

首先遍歷未分配旅客n∈N，判斷旅客群體n的出行需求弧段；然后遍歷列車開行列表，如果列車i的開行弧段滿足旅客群體n的出行需求弧段，并且該弧段上座率小于上座率規定閾值，則將旅客群體n分配至列車i；最后檢查所有旅客是否全部分配，如果還有旅客未被分配，則采用貪心算法，增開列車，直至所有未被分配旅客均分配完畢。

4.3 適應度函數及內層合并列車操作

(1)適應度函數

解Ω的適應度函數為

fitness(Ω)=Z(Ω)-Λ·Num(Ω)

(25)

式中：fitness(Ω)為當前解Ω對應的適應度函數；Z(Ω)為當前解Ω的目標函數值；Λ為開行列車懲罰系數；Num(Ω)為當前解Ω的開行列車數量。

(2)合并列車操作

首先在列車開行解中隨機生成需要合并的列車i_num_col，然后在i_num_col±10范圍內隨機生成需要合并的另一列車，判斷生成的兩列車是否均開行。如果不是，重新執行該步驟，直至生成均開行列車的兩行解；如果是，則對生成的兩行解進行合并，將原本分配給兩列車的客流重新分配給合并后的列車。計算合并后新解在各區間的客座率，對超出客座率的客流重新分配，分配過程為：計算每列車在各區間的平均客座率，如果當前平均客座率大于0且小于閾值L，則將當前客流分配給該列車，遍歷所有列車后，若還存在未分配客流，增開列車，直至所有客流全部被分配。

4.4 基于模擬退火的算法步驟

模擬退火算法，需要設置初始溫度、溫度下降規則、同溫度下迭代次數、終止規則等參數。溫度下降規則選擇給定降溫系數下降方式；同一溫度下的迭代次數使用最大迭代次數進行控制；算法終止規則使用當前溫度低于給定的終止溫度。算法步驟如下：

Step1初始化。初始化初始溫度為Γ0，終止溫度為Γe，退火步長，允許接受概率為初始化初始解為Ω0。

Step3當前溫度Γ>Γe，執行內層算法：

Step5溫度下降，Γ=Γ×，返回Step3。

5 案例分析

5.1 基礎數據

北京北—呼和浩特東高鐵，運營里程為459 km，沿線共設車站16個。根據線路結構特點及現有列車開行模式，由于沙河站和旗下營南站客流極少，故暫不考慮這兩個車站。考慮到北京北和清河站的動車段配屬在清河，兩個車站的旅客出行需求相似，可將北京北站和清河站合并為清河站，客流需求數據也相應合并處理。共13個車站，車站編號依次為1～13，線路和車站信息見圖3，區間運行時分信息通過列車運行圖獲得。

圖3 清河(北京北)—呼和浩特東間區間和車站信息

按照2021年某日客流優化動態列車開行方案，總客流為23 790人，由于篇幅有限，未詳細列舉各OD的客流信息。依據現行開行方案隨機生成某時間段旅客出發時刻需求。為了減少問題計算規模，對同一時段內相同起訖點的客流進行合并，形成旅客群體共計793組。

算法中相關參數取值分別為：Γ0=100；Γe=0.1；=0.9；鄰域解生成過程中，允許刪除列車閾值為0.10；允許拆分列車閾值為0.18；適應度函數中，Λ=1 000；合并列車操作中，L=0.75。

5.2 優化結果分析

(1)動態開行方案結果分析

動態列車開行方案見圖4，圖中圓圈表示列車在該站停車，列車開行數量共計28列，列車起訖點和開行數量見表2。

圖4 清河(北京北)—呼和浩特東動態列車開行方案

表2 優化前后列車起訖點和開行數量對比 列

優化后開行列車總對數共計減少2列。優化前全部開行清河(北京北)—呼和浩特東的長程列車，優化后除開行長程列車外，還增開清河(北京北)—張家口/烏蘭察布的短程列車，滿足旅客出行需求。

優化前后各個車站經過的列車數、停站列車數對比情況如圖5所示。圖中橫坐標為各車站序號，左側縱坐標為停站列車數，右側縱坐標為經停比。優化前后開行列車及停站方案綜合對比情況見表3。

圖5 各車站列車停站情況

表3 優化前后列車開行及停站對比

表3中的停站總數包含列車在始發終到站的停站次數。優化后開行列車數量減少了6.67%，列車停站總數減少了14.94%；優化后得到的動態列車開行方案在滿足旅客多維需求的同時，減少了列車開行對數和停站次數，有效降低高速鐵路運營成本。

優化后開行方案在各區間的客座率見圖6。所有列車的平均客座率為51.14%；列車在各區間的客座率比較均衡，客流分配結果滿足列車能力約束。

圖6 各區間列車客座率

(2)優化目標結果分析

目標函數及各部分的數值隨迭代次數的變化規律，如圖7所示。隨著迭代次數的增加，目標函數整體呈現增長趨勢，旅客群體總旅行時間損失和期望出發時間偏差呈現遞減趨勢。

圖7 目標函數及各部分的數值隨迭代次數的變化規律

為了進一步驗證模型的正確性和適用性，對可變參數ω1、ω2和ω3取不同值的計算結果進行分析，得到動態列車開行方案統計指標見表4。表中客票收益、總旅行時間損失、期望出發時間偏差均為基于旅客群體選擇概率的計算結果。當ω1的取值增加時，考慮旅客群體選擇概率的系統客票收益呈遞增趨勢，ω2和ω3取不同值的計算結果也具有相似的特征。符合動態列車開行方案的優化目標。

表4 不同參數取值下動態列車開行方案統計指標

(3)計算效率分析

算法在PyCharm 2021平臺使用Python語言實現，運行環境為1臺CPU Intel i7-5500U，4 GB內存的計算機，當ω1、ω2和ω3取不同參數值時，算法平均計算時間約為3.6 h。ω1=0.3,ω2=0.4,ω3=0.3時算法收斂迭代過程如圖8所示，算法迭代至35代時收斂。本文設計的求解算法整體收斂性良好，能有效求解動態列車開行方案優化問題。

圖8 算法收斂迭代圖

6 結論

本文引入廣義吸引力模型描述旅客出行選擇行為，構建開行方案時空網絡，將旅客對列車的選擇概率嵌入目標函數，建立基于旅客多維出行需求的動態列車開行方案優化模型，以鐵路運營企業和旅客系統最優為目標，考慮列車流平衡約束、始發終到站約束、客流分配約束、客流平衡約束、列車能力約束、列車開行數量約束、發車安全間隔約束，設計模擬退火算法進行求解。實例計算結果表明，本文所構建的列車開行方案模型與算法能設計考慮旅客出行選擇行為的開行方案，優化列車出發時刻等動態指標，響應旅客多維出行需求，為面向市場導向的高鐵開行方案制定提供決策支撐。

在未來的研究中，將進一步考慮路網條件下動態列車開行方案優化問題，設計更加高效的算法求解動態開行方案優化問題。