考慮要素協同的高鐵列車運行圖雙層優化模型

石敏涵，呂紅霞，2，3，倪少權，2，3，呂苗苗，2，3

（1.西南交通大學，交通運輸與物流學院，成都 611756；2.綜合交通大數據應用技術國家工程實驗室，成都 611756；3.綜合交通運輸智能化國家地方聯合工程實驗室，成都 611756）

0 引言

高速鐵路列車停站方案和列車運行圖的優劣決定了旅客出行的便捷程度，動車組接續方案的優劣決定了運輸成本。本文在考慮三者協同的條件下，研究列車運行圖的優化問題，旨在編制客運服務質量優、鐵路部門運輸組織成本低的綜合優化方案。

在當前運行圖優化研究中，越來越多的學者考慮了三者間的相互影響關系。有的學者[1-5]綜合優化列車運行圖與動車組接續方案，分析了兩者間的相互作用機理，建立協同優化模型來求解問題：周曉昭等[1]以突發情況下的晚點影響范圍最小為目標，針對具有大量始發終到作業車站所在調度區段的動車組接續特點，建立列車運行智能調整模型；王超等[2]以運用最少的動車組實現列車開行數量的最大化為目標，構建兩者的一體化優化模型；王聞蓉[3]把動車組運用問題類比為多車場多車輛路徑問題，在此基礎上建立了兩者的協同優化模型；張寧[4]在協同學基本原理的基礎上，提出了適應相、飽和相和緊張相三種情況下的協同編制方法，并采用分層協同優化思路進行優化；占曙光[5]在考慮干擾條件的情況下，建立考慮動車組周轉的列車運行調整模型，以保證在受干擾情況下快速有效地調整被干擾的列車。

部分研究[6-12]綜合優化列車運行圖與停站方案，其優化目標多為旅客服務質量和鐵路部門運輸效益最大化，但不同研究對于目標的處理各不相同：劉璐等[6]將與列車運行時分成正比的運營總費用最小化作為優化目標，將旅客需求滿足程度的考慮置于旅客需求約束中，以保證所有旅客能搭乘列車；Yang等[7]用列車在站停留時間最小化表示鐵路部門成本最小化這一目標，用列車實際發車時間與最佳發車時間的差值最小化代表旅客需求滿足程度最大化這一目標；Yue 等[8]提出鐵路部門收益可從側面反映旅客滿意程度，即鐵路部門收益越高，表示采用鐵路出行的乘客越多，將旅客服務質量和鐵路部門運輸效益均納入鐵路運輸收益最大化目標中；Dong 等[9]用旅客站內等待時間、列車停站造成的旅客延遲時間最小作為客運服務質量的最優化目標，用列車運行時間最小作為鐵路運輸部門成本的最優化目標。

但當前的研究仍存在一些可以改進的地方，在當前列車運行圖與停站方案綜合優化研究中，多采用列車運行時間最小、列車在站停留時間最小作為鐵路部門運輸成本最小化目標，僅用此類指標代表運輸成本具有較強的局限性。在實際運輸組織生產過程中，高速鐵路運輸組織成本與動車組運用息息相關，一列動車組的價格動輒上億，如何合理地運用動車組，最大限度地提高動車組利用效率、減少運用數量，是保證高速鐵路運輸成本最小化的關鍵，用列車運行時間表示鐵路部門運輸成本，得到的結果可參考性不強。因此，本文考慮停站方案、列車運行圖和動車組接續方案三者協同，以旅客服務質量最大化、鐵路部門運輸成本最小化為目標，建立雙層規劃模型[13-14]。為求解該問題，創新地設計了一種雙層嵌套啟發式算法，外層采用自適應大鄰域搜索算法（Adaptive Large Neighborhood Search Algorithm，ALNS），通過確定破壞和修復算子構建策略、算子自適應優化策略，獲得可行的停站方案和列車運行圖綜合優化結果；內層基于外層方案，采用模擬退火算法（Simulated Annealing Algorithm，SA）求解最優動車組接續方案，確定鐵路部門運輸成本相關指標。最后，通過算例分析，驗證模型及算法在實際應用中的可行性。

1 問題分析

1.1 列車運行圖相關方案分析

高速鐵路列車停站方案確定列車在各站是否停站；列車運行圖確定各列車經由各站的具體到達、出發時刻；動車組接續方案確定動車組運用數量和各動車組擔任的運輸任務車次，三者可統一表示在一個圖形示意結果中，如圖1所示。

圖1 列車運行圖綜合方案示意圖

在考慮三者的協同時，列車停站方案和列車運行圖可統一體現在列車運行線的布局上，動車組最優接續方案則在此基礎上進行分析。因此，本文以包括客流需求、線路概況、相關參數在內的基礎數據和初始方案為輸入，運用雙層規劃模型和算法求解問題，將列車停站方案、列車運行圖和動車組接續方案綜合優化結果作為結果輸出。本文研究的核心在于雙層規劃模型和雙層嵌套式算法，雙層規劃模型中，上層為各方案協同優化模型，對應求解算法為外層ALNS算法，下層是在上層運行線布局基礎上的最優動車組接續模型，對應求解算法為內層SA 算法，運用該算法得到當前運行線布局下的動車組最優接續方案和動車組運用指標，并將指標反饋至上層模型中，計算目標函數。

1.2 動車組最優接續問題分析

停站方案和列車運行圖方案綜合優化結果確定后，建立動車組接續網絡圖G=(N，A)，該網絡圖為有向網絡圖[15]，其中：N=L∪V，L表示運行圖中運行線集合，V表示線路上的動車所集合；A為網絡圖中的有向弧，表示動車組在各頂點間的可接續情況，主要包含動車組接續弧和動車組出入所弧，若兩對向列車在折返站的到發時間間隔滿足最小接續時間要求，則可構成一條由到達列車指向出發列車的有向接續弧，每條接續弧的費用表示兩列車間的接續時間。以圖1運行圖為例，構建動車組接續網絡如圖2所示，紅線為最優接續方案。

圖2 動車組接續網絡

動車組最優接續問題的本質，是在各動車組從動車所出發，擔任運輸任務后返回動車所，且每個運輸任務車次僅能被動車組擔任一次的前提下，確定最小的動車組運用數量和各動車組的運輸任務方案。該問題與圖論中的多人旅行商問題（Multiple Travelling Salesman Problem，MTSP）類似，因此本文將其轉化為帶有附加約束的MTSP問題進行建模和求解[16-17]。

MTSP 問題是指m個旅行商去n個城市推銷產品，規定都必須從同一個出發點出發并返回原出發點，且需要將所有的城市遍歷完畢，每個城市只能游歷一次，同時保證總的路線最短。基于各城市地理位置平面圖，可建立問題的基礎模型，與后文式（15）、式（17）～（19）建模思想一致。

1.3 問題的數學描述

為簡化問題，提高問題求解的可行性，本文作出以下假設：

假設1 列車運行圖中各運行線始發終到站均為區段兩端折返站。

假設2 區間兩端站附近各設置一個動車所，編制周期結束時，動車組可不返回始發動車所。

假設3 編制周期從每日7點開始，周期內最后一列上行、下行列車均采用站站停的停站方案。

問題相關變量及參數如下：

（1）集合

L表示列車集合，i，j∈L，|L|=NumL代表列車數量；LU、LD分別表示上、下行列車集合；Ilast=表示運行圖中最后一列上、下行列車集合；和分別表示列車i同方向前（左）、后（右）的第g列車。

S表示車站集合，m，n∈S，|S|=NumS代表車站數量；Sr1、Sr2分別表示區段兩端折返站和分別表示在列車i運行方向下，m站后方（已經過）和前方（未經過）的第g個車站；Oi和Di分別表示列車i的始發站和終到站；S{m～n}表示m至n的所有車站（包含m、n站）。

K表示動車組集合，k∈K，|K|=NumK代表動車組運用數量。

（2）參數

Psum表示一日內各OD 總客流量；表示列車i在m站停站時間的上、下限；tAD、tAS表示起車、停車附加時分表示列車i在m站與m站前方站間的區間運行時間；hmin表示最小追蹤間隔時間表示列車i停站次數的上、下限表示車站m上、下行列車停站次數的上、下限；表示在時段內，m站新增的從m至n的客流量；tcmin表示動車組最小折返時間標準；ku表示可用動車組數量；Qsum表示線路區段總運行里程；Ch、Ct表示動車組一級檢修距離、時間標準，分別取4 000 km、48 h。

（3）中間變量

2 考慮要素協同的運行圖雙層優化模型

鐵路列車運行圖協同優化問題可由一個雙層規劃描述，上層規劃為三方案協同優化模型，其優化目標由鐵路部門運輸組織成本最小化和客流需求滿足程度最大化構成，其中，成本最小化目標與下層規劃中的動車組運用情況相關。

2.1 運行圖優化上層模型

上層模型優化目標包括客流需求滿足程度最大化和鐵路企業運輸成本最小化。其中，前者主要通過減少乘客站內等待時間和乘客在列車上的延遲時間實現；鐵路企業運輸成本最小化目標可通過減少動車組運用數量和接續時間實現。

2.1.1 上層模型的數學表示

上層模型表示如下：

上層模型中，式（1）對于客流需求滿足程度的優化體現在旅客等待時間和列車上旅客的延遲時間最小，對鐵路部門運營成本的優化體現在動車組運用相關指標Numk、tc，這兩項指標滿足下層動車組最優接續模型，由于兩目標數量級不同，采用校正系數α進行修正；式（2）、（3）表示列車在各站的到、發時刻與列車停站判斷變量、停站時間和區間運行時間的關系，表示在各列車始發時刻、列車在站的停站相關變量確定的情況下，列車在各站的到、發時刻可通過推算得到；式（4）表示停站時間限制；式（5）表示兩列相鄰列車間的安全間隔約束；式（6）表示列車服務約束；式（7）、（8）表示車站上下行服務約束；式（9）為變量約束。

2.2.2 中間變量的計算

圖3 站內等待時間計算示意圖

2.2 動車組最優接續下層模型

上層優化目標中的動車組相關指標Numk、tc滿足下層規劃的動車組最優接續模型。下層模型優化的基礎是上層運行圖方案對應的動車組接續網絡，動車組運用的優化目標按重要度排序，依次為動車組運用數量最小化、動車組接續時間最小化。

將動車組最優接續問題轉化為有附加約束的MTSP問題進行處理，下層模型表示如下：

下層模型中，式（14）的β是一個校正項，為保證兩指標在同一數量級，需對動車組運用數量指標進行處理；式（15）為總接續時間計算方法；式（16）為動車組接續網絡可達路徑約束，其中M1是一個足夠大的懲罰項，表示若動車組接續網絡中由節點i至j不可達，則規定其弧段費用足夠大；式（17）、（18）為節點流量平衡約束，表示任一節點入度、出度均為1；式（19）表示每個節點運輸任務僅由一個動車組擔任；式（20）、式（21）表示動車組一級檢修的時間、距離約束；式（22）為變量約束。

3 算法構建

本文建立的列車運行圖優化模型是一個雙層非線性整數規劃模型，隨著問題規模的擴大，計算難度呈指數增長，是一個典型的NP-Hard 問題，直接求解該問題的復雜程度高。

為尋求可行較優解，本文將模型約束條件與算法規則結合，基于問題的雙層特性，設計了一種雙層嵌套啟發式算法。外層采用ALNS 算法確定可行的停站方案與列車運行圖綜合方案，根據算子的歷史表現動態調整算子被選擇概率，以便獲得更好的鄰域和解，在提高計算效率的同時，避免陷入局部最優解；內層采用SA 算法，基于外層給定的方案確定動車組最優接續方案，并將動車組最優接續方案的各項指標返回外層。由于該算法在搜索范圍與計算效率上表現良好，因此能夠在可接受時間范圍內得到可行較優解。

3.1 外層ALNS算法

外層ALNS 算法，通過對解進行破壞與修復，確定可行的停站方案與列車運行圖綜合方案，并根據解的質量，更新外層各破壞、修復算子的分數與權重，根據輪盤賭機制確定迭代過程中算子的被選擇概率[19]。

（1）解的重構

本文共設計兩對破壞-修復算子進行解的重構。列車的破壞-修復算子用于移除、插入列車，確定列車始發時刻決策變量；停站的破壞-修復算子用于刪除、增加列車停站，確定停站相關決策變量。解的重構流程如圖4 所示，每項操作設置3 個算子，根據動態調整的權重按照選擇概率進行選擇。其中，列車相關破壞-修復操作包括隨機或以發車間隔、客流需求為依據移除和增加列車，增加的列車均為站站停列車；停站相關破壞-修復算子包括隨機或以服務頻率、客流需求為依據刪除和增加停站。

圖4 解的重構流程

（2）算子動態調整

算子動態調整過程通過SA 方法控制，在相同溫度下的內層解生成、更新迭代結束后，根據該溫度下各算子的分數和使用次數，更新各算子的權重，該溫度下內層迭代全部結束后，進入下個溫度的迭代，此時，算子的分數全部重置為0。算子的動態調整通過以下兩式實現：

式中：ωo表示算子o的權重，初始情況下，各算子權重均為1；Ф表示與該算子功能相同的算子集合；η為反應系數，反映算子分數和選擇次數對權重變化的影響程度；no，l表示在某溫度下最后一段迭代l結束后，即將進入下一溫度迭代前算子o的被選擇次數；πo為算子在某溫度下的總得分，算子得分根據解的不同情況確定，若選用算子生成的解為最優解時，得分為σ1；若該解優于當前解時，得分為σ2；若生成解不是更優解，但為可接受解時，得分為σ3，σ1>σ2>σ3。

3.2 內層SA算法

內層SA 算法用于求解在外層停站方案和列車時刻表基礎上的動車組最優接續方案。

（1）解的表達形式

在動車組最優接續問題中，當列車數量為|L|、起始點為動車所、可用動車組數量為ku時，生成的解的形式為ku-1個0與|L|個車次號碼的隨機排列，按照此方法，圖3 中的動車組運用最優解可表示為：“2，3，8，0，4，5，10，9，0，1，6，7”。

（2）算法鄰域構造

本文中動車組最優接續問題的SA 算法鄰域構造方法包括交換法、移位法、倒置法，每次構造鄰域時，采用輪盤賭的方式以同樣的概率選擇方法。

3.3 算法流程

本文設計的雙層循環啟發式算法框架包含外層、內層兩個部分。

（1）外層算法

①外層算法參數初始化。設置初始溫度為T01、溫度下降比例為θ1、不同溫度下最大迭代次數為ITER_max，令初始迭代次數ITER=1。

②令初始方案為當前最優解，并計算其目標值。

③進行外層解的重構。根據算子選擇概率po，依次從列車刪除、增加和停站刪除、增加算子中各選擇一個算子，重構得到外層新解Rnew，即停站方案與列車運行圖綜合方案，轉（2）的①。

④計算Rnew的目標函數值，主要包括客流需求滿足程度指標和從（2）的⑦調用的對應動車組最優方案r和運用指標Z(r)。

⑤進行同一溫度下的最優解更新過程。

⑥算子權重動態調整、溫度及迭代次數更新。

⑦判斷是否達到外層算法終止條件。若否，轉至（1）的③；若是，輸出最優方案R及相應目標函數值Z(R)。

（2）內層算法

①根據（1）的③中輸入的方案，提取各列車在兩端折返站的始發、終到時刻，將其代入式（16）中，構造基于運行圖的接續時間矩陣，如圖5所示。

圖5 內層算法接續時間矩陣構造

②參數初始化。設置初始溫度值為T02、溫度下降比例為θ2、最大迭代次數為iter_max、令內層初始迭代數iter=1。

③隨機生成初始解r0，即生成一個ku-1 個0 與|L|個運輸任務節點編號的隨機序列。令其為當前最優解并計算其目標函數值Z(r0)。

④根據鄰域構造規則生成新解rnew，并計算相應目標值Z(rnew)。

⑤進行同一溫度下的最優解更新過程。

⑥溫度、迭代次數更新。

⑦判斷是否達到內層算法終止標準。若否，轉（2）的④；若是，將最優動車組接續方案r和運用指標Z(r)輸出至（1）的④。

算法步驟的整體流程圖如圖6所示。

圖6 雙層算法流程圖

4 算例分析

某高速鐵路線路上共有8 個車站，站5 為必須停車的大型站，兩端折返站附近各設有一個動車所，示意見圖7。已知線路區間各站間日均客流需求如表1所示，假設各站間客流在時段內的到達服從泊松隨機過程，各參數按照表2取值。

圖7 線路車站分布情況示意圖

表1 各站間日均客流需求 單位：人

表2 相關參數取值

將客流OD 數據及相關處理結果作為模型的上層輸入，根據泊松分布模擬的各站間客流OD 的到達曲線，得到各站間，隨后根據式（10）～（13）計算和得到客流需求相關目標值。

例如，初始方案中站1 至站4 的客流到達服從參數λ的泊松分布，其中：λ=OD 客流量/時段長度=110/725=0.151 7。據此，得出乘客累積到達曲線如圖8所示，篩選在站1和站4均停靠的下行列車，并根據其發車時刻將時段劃分得到站1 至站4 間的值，按照i從1至4依次為9、33、61、7。按此方法，可得到各站間的

圖8 乘客在站累積到達曲線

圖9 雙層算法收斂曲線

運用MATLAB R2018a 實現模型與算法的編程求解，設外層、內層算法最大迭代次數分別為100、200次，雙層算法大約平均經過50次左右可收斂至最優解，能在可接受時間范圍內取得較優結果，算法收斂曲線如圖9所示。優化結果集中體現在運行圖上，初始方案如圖10、表3所示，優化方案如表4、圖11所示。

圖10 初始方案

圖11 優化方案

表4 優化方案數據

表3 初始方案數據

對比優化方案與初始方案的各項指標，結果如表5所示。

表5 指標對比

根據上表可以看出，優化方案的各項評價指標均比當前的原始方案更優。對于乘客而言，列車整體停站次數雖然減小，但旅客服務相關指標都取得更優值，人均等待和延遲時間減小；對于鐵路運輸部門而言，動車組運用數量由11組減少為7組，接續時間由1 420 min 減少為1 194 min，鐵路運輸部門成本顯著減小。

由此可以看出，本文構建的雙層模型和算法具備可行性，得到的結果較優。

5 結束語

本文提出高速鐵路列車停站方案、列車運行圖和動車組接續方案的協同優化方法，相較于傳統的分步編制方法，綜合考慮了三者之間的相互影響，盡可能保證旅客滿意程度最大化和鐵路部門運輸成本最小化。構建雙層規劃模型和設計雙層啟發式算法，分別對該問題進行數學描述和算法求解。最后通過實例分析，驗證該方法能夠有效地減少乘客等待時間和鐵路部門動車組運用數量和接續時間，具備可行性。

本文對于列車運行圖協同優化的分析具有一定的局限性，當前設計的模型和算法更加適用于沿線車站數量不超過10 個、列車開行對數不超過28 對的算例規模，當算例規模過大時，可能存在由于復雜程度高、計算時間長而無法求解的問題。在本文研究的基礎上，如何提高模型和算法對于大規模問題的適應性，是后續研究的另一重要方向。