基于換乘導向的大型客運樞紐高鐵列車接續優化

喬俊 孟學雷 王東先 湯霖

摘 要：針對高速鐵路成網條件下的客運樞紐高鐵列車接續優化問題，分析了樞紐內的旅客換乘過程，提出了中長途客流的換乘滿意度概念;以平均換乘滿意度和樞紐車站列車到發均衡性為優化目標，以大站合理發車時間、合理終到時間、車站作業間隔時間、旅客換乘時間、車站到發線能力等為約束條件，建立了基于換乘協同的大型客運樞紐高速列車接續優化模型。設計了改進染色體編碼方式和選擇策略的遺傳算法對算例進行了求解。改進后的遺傳算法同基本遺傳算法、基本模擬退火算法相比，目標函數中所求的平均換乘滿意度分別增加了5.10%、2.93%，樞紐車站列車到發均衡性分別提高了0.27%、2.31%，算例結果驗證了改進遺傳算法的有效性和穩定性，表明所提方法可以有效地提高大型樞紐高鐵列車的接續質量。

關鍵詞：換乘滿意度;同站換乘;異站換乘;列車接續;改進遺傳算法

中圖分類號：TP301.6

文獻標志碼：A

High-speed train connection optimization for large passenger transport hub based on transfer orientation

QIAO Jun1， MENG Xuelei1*， WANG Dongxian1， TANG Lin2

1.School of Traffic and Transportation， Lanzhou Jiaotong University， Lanzhou Gansu 730070， China;

2.Lanzhou Railway Station， China Railway Lanzhou Bureau Group Company Limited， Lanzhou Gansu 730070， China

Abstract：

In view of the optimization of high-speed train connection in passenger transport hub under the condition of high-speed railway network， the concept of transfer satisfaction of medium and long distance passenger flow was proposed by analyzing the passenger transfer process in hub， and a high-speed train connection optimization model for large passenger transport hub based on transfer orientation was proposed with the average transfer satisfaction and the arrival and departure equilibrium of trains at hub stations as the optimization objective and with the constraint conditions of reasonable originating time of large stations， reasonable terminating time， station operation interval time， passenger transfer time and station arrival and departure line capacity. A genetic algorithm with improved chromosome coding mode and selection strategy was designed to solve the example. Compared with the basic genetic algorithm and the basic simulated annealing algorithm， the improved genetic algorithm increases the average transfer satisfaction in the objective function by 5.10% and 2.93% respectively， and raises the equilibrium of arrival and departure of trains at hub stations by 0.27% and 2.31% respectively. The results of the example verify the effectiveness and stability of the improved genetic algorithm， which indicates that the proposed method can effectively optimize the quality of the high-speed train connection in large passenger transport hub.

Key words：

transfer satisfaction; transfer inside one station; transfer between different stations; train connection; improved genetic algorithm

0 引言

我國高速鐵路的快速發展使得高鐵客流量和換乘客流量逐年攀升，客流種類和換乘方式也越來越多樣化。大型高速鐵路客運樞紐作為城市對內對外交通銜接的重要節點，樞紐內的換乘問題受到越來越多的重視。科學地分析樞紐的換乘條件，制定合理的換乘接續方案，優化樞紐內換乘接續列車到發時刻的銜接問題，對于保障客流高效地換乘具有重要意義。

近年來，大型鐵路客運樞紐的換乘協同問題受到了不少國內外學者的關注。國外學者多通過調整時刻表的方法研究列車接續優化問題，文獻[1]研究了鐵路與城市公交間的時刻協同問題，以換乘時間和公交運營成本最小為目標，建立了非線性模型并利用遺傳算法求解。文獻[2]構建了鐵路網絡時刻表，以換乘時間最小為目標建立了非線性時刻表優化模型，利用遺傳算法求解模型，但模型中沒有考慮車站到發線能力約束。文獻[3]提出通過調整鐵路非周期性時刻表減少乘客換乘時間，以列車運行時間、停站時間等為變量，乘客總的換乘等待時間最小為目標建立了混合整數規劃模型，利用改進的啟發式算法求解了模型，但只對同站換乘進行了研究。文獻[4]研究了城市軌道交通換乘可靠性，通過數學推導分析了發車間隔時間、運行時間對換乘等待時間的影響，但并未建立模型對發車間隔時間和運行時間進行優化。文獻[5]研究了鐵路周期性時刻表下的旅客換乘問題，以換乘旅客的時間損失最少為目標，建立了周期性時刻表優化模型，并通過啟發式算法求解了模型，但模型并未考慮不同方向列車之間的需求換乘客流量。文獻[6]研究了以換乘需求為導向的軌道交通換乘優化問題，以乘客換乘等待時間最小為目標，構建了線性和改進的非線性優化模型，并利用粒子群算法求解了改進的非線性模型。

目前國內對鐵路客運樞紐旅客換乘和列車接續優化問題的研究相對較少。文獻[7]研究了城市軌道交通的換乘，以各條線路首列車的發車時刻為變量，乘客總的換乘等待時間最小為目標，建立了城市軌道交通網列車時刻表優化模型，運用CPLEX工具進行了求解，但并未考慮需求換乘客流量約束以及發車間隔較大線路間的列車接續問題。文獻[8]研究了鐵路樞紐與城市公交間的接駁問題，以乘客總的換乘時間最小為目標，公交發車間隔、載客量等為約束建立了樞紐換乘時間調度模型。文獻[9]分析了鐵路樞紐內的同站和異站換乘過程，提出了換乘條件評價指標，但并未利用這些評價指標對樞紐列車接續優化進行深入研究。文獻[10]分析了歐洲鐵路旅客換乘組織和列車銜接方案，提出我國鐵路應當將列車銜接方案與開行方案、運行圖的編制過程結合起來，為優化樞紐列車接續問題提供了解決思路。文獻[11]以有效換乘客流量最大和換乘無效等待時間最短為目標建立了列車接續優化模型，但模型沒有考慮樞紐車站列車的到發均衡性和異站換乘?？偟膩碚f，上述文獻[1-3，6-8，11]研究目標多為換乘等待時間最小，約束條件[1-3，5，8，11]多為乘客必要換乘時間、列車停站時間、發車間隔時間等，且大多通過調整時刻表[1-3，5，7，11]優化了列車接續問題，這些研究成果為本文提供了重要參考，但研究問題多限于樞紐內單一客運站不同交通方式之間的換乘和軌道交通換乘，異站換乘的研究較少，且算法設計時大多未將車次與到發時刻相結合。鮮有文獻在已知開行方案的基礎上，通過優化與編排一定周期內換乘樞紐車站的所有列車到發順序和時間的方法來研究列車接續問題。

針對這些問題，對不同線路及方向的中長途客流在樞紐內的同站、異站換乘優化問題進行研究，以樞紐內需求換乘客流的平均換乘滿意度最大化和樞紐車站列車到發均衡性最大化為目標，構建了基于換乘導向的樞紐高鐵列車接續優化模型，并設計改進染色體編碼方式和選擇策略的遺傳算法進行求解。

1 問題描述

1.1 同站換乘過程

通常，大型客運樞紐高鐵站均設有專門的中轉換乘通道，同站換乘旅客可以實現不出站換乘，整個換乘過程為旅客下車步行至接續列車?？空九_候車（或至專用候車室候車）然后檢票完成上車。

如圖1，定義從換出列車x到達車站h時刻ax起至接續列車x從同一車站h出發時刻dx止的時間為同站換乘時間，包括兩部分：一是旅客從換出列車下車步行至接續列車?？空九_（或至專用候車室）時止的必要走行時間tb;二是旅客從到達接續列車站臺或專用候車室時起至接續列車出發時止的等待時間tw。

tb按照實際查定取值，等待時間tw受兩個因素影響，一是接續列車開行頻率和開行均衡性，二是換乘銜接方案。理論上來講，等待時間tw最小值為0，最大值為接續列車的開行間隔時間。

1.2 異站換乘過程

由于樞紐內不同高鐵站銜接的干線方向不同，部分起點和終點不在一個方向和線路的中長途旅客為了完成其旅行過程，通常需要在一個換乘樞紐內的不同車站間進行中轉，而從一個車站到另一車站，中間需要乘坐城市公共交通。

如圖2，定義從換出列車x到達車站h時刻ax起至接續列車x從另一車站h出發時刻dx止的時間為異站換乘時間，包括5個部分：一是旅客從換出列車下車步行至公共交通站臺的必要走行時間tb′;二是旅客從到達公共交通站臺到等待公共交通上車的公共交通候車時間tw′;三是旅客乘坐城市公共交通從h車站到另一接續車站h的公共交通旅行時間時間t公;四是旅客從另一公共交通站臺步行至接續車站檢票至候車室的必要走行時間tb″;五是旅客從接續車站候車室時起至完成上車，接續列車出發時止的等待時間tw。

其中tb′、tw′、t公按照不同城市公共交通的異站換乘客流分擔率、發車間隔、旅行速度等結合實際查定取值，參考文獻[12-15]可知，當樞紐采用以軌道交通為主的集疏運模式時，軌道交通、公交、出租車和社會車輛的換乘客流分擔率一般分別為60%、30%、10%;tb″的取值要考慮旅客進站排隊檢票和安檢過程;tw取值原則與同站換乘一致。

2 樞紐內換乘接續優化模型的構建

2.1 模型假設

本文的研究基于以下假設：1）已知研究周期內樞紐各個高鐵站的高速列車開行方案，且不存在不停車通過樞紐的高速列車;2）已知研究周期內樞紐不同高速列車之間的需求換乘乘客流量預測值;3）不考慮高速列車運行晚點情況;4）同一線路同一方向、同一線路相反方向間不存在高速列車接續;5）研究周期內的換乘客流在整個旅行過程中只進行一次換乘，且在所研究的樞紐內完成換乘;6）本文只考慮同方向列車的換乘接續情況。

14Jmn（dmnj+2x″h-dmnjxh-2Emndh）2]（4）

其中：x，x′，x″∈Xmnah;x，x′，x″∈Xmndh;Emnah=（T2-T1）/Iahmn，Emnah表示樞紐h站連接的m線路n方向上的列車平均到達間隔時間;Emndh=（T2-T1）/Idhmn，Emndh表示樞紐h站連接的m線路n方向上的列車平均出發間隔時間。

2.4 約束條件

本文主要從高鐵站列車合理到發時間、換乘客流量、旅客換乘時間、車站間隔時間等方面對模型進行約束：

1）高速列車合理到發時間約束。

amnixh-Tmnxh≥DmnE（5）

dmnjxh-Tmnxh≤AmnL（6）

T1≤amnixh≤T2（7）

T1≤dmnjxh≤T2（8）

式（5）表示到達樞紐車站的高速列車在其始發站的始發時刻不早于始發車站的最早發車時刻;式（6）表示離開樞紐車站的高速列車到達其終點站的時刻不晚于終到車站的最晚終到時刻;式（7）、（8）表示樞紐車站的列車到發時刻應在研究周期內。

2）換乘客流量約束。

pqxjmnxi≥f（Qpqx*jmnxi，Q）; x≠x*且m≠p（9）

f（μ1， μ2）=1， μ1≥μ2

0，μ1<μ2（10）

表示m線路n方向上第i列到達樞紐且車次為x的列車與p線路q方向上第j列離開樞紐且車次為x*的列車之間的接續關系由兩列車之間的換乘客流量決定。

3）換乘時間約束。

Tsmin≤pqx*jmnxi（dpqjx*h-amnixh）≤Tsmax;m≠p，x≠x*（11）

Tdmin≤pqx*jmnxi（dpqjx*h-amnixh*）≤Tdmax;

h≠h*， m≠p， x≠x*（12）

式（11）、（12）表示若列車x與x*構成接續關系，則兩列車在樞紐車站的出發和到達時刻差要滿足換乘時間約束。

4）通過列車停站時間約束。

thmin≤dpqjxh-amnixh≤thmax; m=p時，q≠n（13）

5）車站間隔時間約束。

amni+1x′h-amnixh≥Iaa（14）

dmnj+1x′*h-dmnjxh≥Idd（15）

dmnjxh-amnixh≥Iad（16）

amnixh-dmnjxh≥Ida（17）

式（14）～（17）表示樞紐車站同方向兩列車到發的時間間隔應滿足車站的列車到達、出發、到發、發到時間間隔約束。

6）樞紐車站到發線能力約束。

對于任意時刻t，有如下約束：

G（ψv，t）=1， ψv≤t

0，ψv>t; v∈{1，2}（18）

ψ1（dmnjx*h，amnixh，whxx*）=

whxx*（dmnjx*h-Tb），? whxx*=-1

whxx*+1（amnixh-Tap），whxx*=0

whxx*（amnixh-Tap）， whxx*=1（19）

ψ2（dmnjxh，amnixh，whxx）=

whxx（dmnjxh-Tde），? whxx=-1

whxx+1（dmnjxh-Tde），whxx=0

whxx（amnixh-Ta），whxx=1（20）

∑2m=1∑2n=1∑Jmnj=1∑Imni=1[G（ψ1，t）-G（ψ2，t）]≤dfh（21）

式（19）、（20）中引入參數whxx表示列車x或x在樞紐內h站的停站方式，whxx取-1表示始發列車，whxx取0表示通過列車，whxx取1表示終到列車。ψ1（dmnjxh，amnixh，whxx）表示列車開始占用到發線的時間函數，ψ2（dmnjxh，amnixh，whxx）表示列車結束占用到發線的時間函數。

7）區間通過能力約束。

cra+crd≤CrT（22）

3 算法設計及算例分析

3.1 改進遺傳算法設計

遺傳算法在求解一些復雜的非線性問題時能發揮其全局搜索優勢，且在鐵路運輸組織優化方面取得了廣泛應用。由于模型為多目標非線性整數規劃模型，為了便于求解，得到研究周期內的樞紐車站所有列車到發時刻，因而將多目標轉換成單目標模型求解。由于兩個目標函數的量綱和量級不同，首先應統一量綱和量級，使得目標函數規范化，轉換后的目標函數如式（23），式中Z2，min、Z2，max表示到發均衡性最小值和最大值，λ為加權系數。

min Z=λ（-Z1）+（1-λ）Z2-Z2，minZ2，max-Z2，min（23）

采用改進染色體編碼和選擇策略的遺傳算法，設計的算法步驟如下：

1）構造基因編碼和染色體。

本文關于換乘樞紐車站列車到發時間編排問題的研究對象包括車次、線路、方向、到達（出發）車站、到達（出發）順序和時間。編碼時將車次和車次對應的到達（出發）時刻構成一個元組，作為本文遺傳算法的基因，并采用兩段式染色體編碼方式，以換乘樞紐內存在兩個高鐵站，樞紐連接兩條線路，且兩車站之間存在聯絡線為例，構造如圖3所示的染色體編碼結構：第一部分表示樞紐內兩個車站的各個線路各個方向的列車依次到達（出發）時刻編排，依次為h站1線路1方向到達、h站1線路1方向出發、h站1線路2方向到達（出發）、h站2線路1方向到達（出發）、h站2線路2方向到達（出發）以及h站各個線路和方向的列車到發時間編排;第二部分表示不同車站不同線路和方向的列車依次到達和出發時刻之間的斷點位置。

2）初始種群的生成。

由于研究周期[T1，T2]內每個個體染色體基因中的實數編碼、整數編碼分別表示到達（離開）樞紐車站的列車車次和對應列車在樞紐車站的到達（出發）時刻，首先隨機生成一個樞紐車站所有線路和方向不重復的到達（出發）車次序列，其次生成該車次序列對應的列車到達（出發）時刻，由于列車到達（出發）時刻是按照時間序排列的，因此每個個體的染色體基因段中的列車到達（出發）時刻應該是Xmnah（Xmndh）這些車次的到達（出發）時刻的升序排列。因此可以按照以下方法得到兩個斷點之間列車出發時刻升序排列的染色體片段：

①在[T1，T2]內生成一個隨機數t1，作為dmn1xh;

②在[t1，T2]內生成一個隨機數t2，作為dmn2x′h;

③依此類推，在[tj-1，T2]內隨機生成tj作為h站發往m線路n方向第j列車的出發時刻。

同理可以生成染色體中任意兩個斷點之間的列車到達時刻升序排列片段，并將這些片段組成完整的染色體個體。

3）適應度函數。

設K為種群規模，Zk是當前種群中的第k個染色體的目標函數值，Zmax和Zmin分別為當前種群的最大、最小目標函數值，gk為適應度函數。

gk=Zmax-Zk+γZmax-Zmin+γ; k∈{1，2，…，K}（24）

其中：γ是（0，1）內的隨機數，引入γ使得當染色體間的適應值差距較大時，采用適應值比例選擇，當染色體間的適應值差距較小時，則在相互競爭的染色體中進行純隨機的選擇。這樣使表現較優的個體適應度更大，進入下一代的幾率也更大。

4）改進選擇算子。

文中應用如下混合改進了的選擇方案，將選擇操作分為以下3個步驟：

①將計算得到的個體適應度按照從大到小進行排序，保留父代種群中的前1/4個體[16];

②隨機在父代種群中選取1/2K個個體，K為種群規模（排除①中選中的個體）按照下文的5）交叉算子和6）變異算子生成新子代[16];

③將①中選擇出的個體與②中生成的新子代進行模擬退火選擇，其次將模擬退火選擇之后得到的個體與原父代種群合并組成臨時種群，設臨時種群規模為K′，臨時種群中每個個體為k′，則保證了隨著算法迭代次數的下降，改進算法的臨時種群規模K′始終大于種群規模K。依據改進方法，借鑒模擬退火算法，將各個染色體的適應度函數值進行拉伸[17]，運用式（25）計算臨時種群中每個個體k′被選擇的概率，從臨時種群中選出K個個體組成新的一代進行下一輪遺傳算法操作：

P（k′）=eg（k′）/Tv′/∑K′k′=0eg（k′）/Tv′; k′∈{1，2，…，K′}（25）

Tv′=1ln（v′/T0+1）（26）

其中：Tv′為漸趨于0的退火溫度（v′=1，2，…），T0為初始溫度。改進的選擇算子借鑒了模擬退火算法中的拉伸方法，可以改善基本遺傳算法的早熟問題，同時使得在遺傳算法后期過程中，當個體染色體適應度趨于一致時，改進的算法具有更好的選擇效果，同時這一選擇算子不僅包含了父代種群中的最佳個體，保證了算法的收斂性，又保留了最優個體以外的優秀個體，增加了種群的多樣性，避免算法陷入局部最優解。

5）交叉算子。

文中的染色體是由不同片段的車次實數編碼和列車有序到（發）時刻整數編碼元組構成，采用傳統的交叉方法不能得到理想的結果，因此本文采用區域交叉，將交叉區域限定在兩個相鄰的斷點之間，并將交叉區域的到（發）時刻值與另一個群體基因位的時刻值進行比較，交叉時車次不隨時刻交叉，具體操作步驟如下：

①在父代種群中，隨機選擇兩個個體作為父代1和父代2，并隨機選取兩個相鄰斷點之間的兩個交叉點，規定父代1和父代2的兩個相鄰斷點的選擇相同。將這兩個交叉點之間的所有時刻基因值作為交叉對象進行交叉操作。

②將父代2交叉區域內的時刻基因值分別與父代1中所有的時刻基因值之差的絕對值進行比較。若差值為0，則父代1中的基因值不變;若差值不為0，則將交叉區域內的時刻基因值與父代1中絕對值最小的基因位上的時刻值進行替換，若存在兩個基因時刻值的絕對值相等，則將父代1中對應的時刻基因值較大的時刻值替換，從而得到交叉后的子代1，同理可以得到交叉后的子代2。例如某兩個相鄰斷點之間的交叉操作如圖4和圖5。

6）變異算子。

在染色體個體變異之前，為了避免算法陷入局部最優，同時得到研究周期內樞紐車站最優的列車到發順序，應隨機生成K個不同的樞紐車站所有線路方向不重復的到發車次序列替換上述交叉后的子代染色體基因中的車次序列。

采用均勻變異，將每條染色體上的一個或多個基因點設置為變異點，以一定的變異概率Pm確定一個隨機數，并確定變異點的取值范圍，以變異后的值取代變異點先前的取值，變異時基因元組中的車次不變。例如，隨機選中的一個個體k，個體k中的amnixh為變異點，amnixh的取值范圍為[amnixh-σ，amnixh+σ]。變異點的新基因值為：

a′mnixh=amnixh-σ+β[（amnixh+σ）-（amnixh-σ）]（27）

其中β∈（0，1），是一個隨機數。

7）終止條件。

設定改進的遺傳算法最大進化代數，當遺傳算法運行到最大進化代數之后，停止運行，輸出結果;否則轉步驟3）。

3.2 算例分析

選擇高速鐵路網中某一大型樞紐，樞紐銜接兩條高速鐵路線路，存在兩個高鐵站且兩車站之間存在聯絡線，該樞紐采用以軌道交通為主的客流集疏運模式，圖6是研究客運樞紐的換乘接續示意圖。

該樞紐詳細概況如下：dfh1、dfh2為14條、13條;thmin、thmax分別為3min、20min;Iaa、Idd、Ida、Iad分別為2min、2min、3min、3min;tap、tde、tb、ta分別為5min、2min、23min、20min;D11E、D12E、D21E、D22E分別為360、390、330、420;A11L、A12L、A21L、A22L分別為1380、1380、1440、1380;C1T、C2T、C3T、C4T分別為16、7、12、10。選

取該樞紐的中長途旅客換乘時段13：00—14：00作為研究周期，樞紐內兩個高鐵站的列車開行方案如表1所示。由于文獻[11-12，18]研究樞紐與文中所研究樞紐概況、換乘客流量相當，因而推算得出研究周期內不同列車間的換乘客流量預測值，如表2所示。

根據文獻[11，18]，結合所研究樞紐的概況、換乘客流量、鐵路部門的成本和收益等因素綜合確定換乘接續列車判定接續旅客人數Q為50人。同時為了保證旅客能夠在一定時間內順利完成換乘，Tsmin、Tsmax按照樞紐內客流高峰時段的乘客必要走行時間、檢票時間以及接續列車開行間隔時間來取值，分別取15min、45min;Tdmin、Tdmax結合樞紐內客流高峰時段的乘客必要走行時間、檢票時間、接續列車開行間隔時間、城市公共交通的運行時間和換乘客流的分擔率取值，分別取40min、70min。

遺傳算法的參數設置為：種群規模K取300，交叉概率pc取0.75，變異概率pm取0.06，最大迭代次數1000，T0初始溫度取為100，λ取0.6。依據上述模型和算法，利用Matlab R2014a軟件工具編程求解算例，分別運用基本遺傳算法和改進的遺傳算法對算例求解，得到改進后遺傳算法的優化結果如表3和表4，目標函數為-0.1257，其中目標值Z1滿意度為0.6367，目標值Z2列車到發均衡性值為640.5826，以及目標函數隨迭代次數變化示意圖8。

鑒于本文設計改進的遺傳算法結合了模擬退火算法的思想，因此，本文又以基本模擬退火算法作為對比算法，在同一臺計算機上利用Matlab編程實現基本模擬退火算法求解模型，通過進行多次實驗，得到基本模擬退火算法計算的結果為：算法迭代了696次之后，目標函數值趨于穩定且到達最小，此時求得的目標函數值為-0.1088，其中目標值Z1滿意度為0.6186，目標值Z2列車到發均衡性值為655.7341，進一步將基本模擬退火算法、基本遺傳算法以及本文改進的遺傳算法進行比較，如表5所示。

在樞紐客流換乘滿意度方面，分析表3和表4可以看出，12對列車實現了有效接續，其中7對列車的接續時間使得換乘客流滿意度達到60%以上，1對列車的接續時間使得換乘客流滿意度最低。同時由表4求得該樞紐換乘客流的平均同站換乘時間為27min，平均異站換乘時間為49.83min。

在樞紐列車到發均衡性方面，h2站連接的2線路2方向列車到達和2線路1方向列車出發、h1站連接的1線路2方向列車出發和2線路1方向列車到達，這幾個方向的列車到發均

衡性較優，而h1站連接的1線路列車到發均衡性較差?？偟膩碚f，h2站的列車到發均衡性較h1站更優。

為了進一步驗證改進后遺傳算法的穩定性，分別運用基本遺傳算法和改進遺傳算法對算例求解，圖7是隨機抽取的50次實驗結果的收斂代數情況?？梢钥闯?，在種群規模和迭代次數相同的情況下，改進后的遺傳算法穩定性更好。

利用本文模型和改進的遺傳算法對高速鐵路網中某一大型客運樞紐高速列車接續問題進行優化，得到目標函數值隨迭代次數變化情況，如圖8所示。

由于本文設計的遺傳算法結合所研究問題設計了兩段式染色體編碼方式，將車次和車次對應的到達（出發）時刻構成一個元組即設計的算法基因，并在選擇算子中融入了模擬退火算法的拉伸方法和退火選擇，將遺傳算法全局尋優能力強的特點和模擬退火算法局部尋優能力強的特點相結合，使得改進的遺傳算法具有更好的選擇效果，有效地提高了本文設計算法的解的質量。由表5可知，對比基本模擬退火算法，本文改進的遺傳算法，目標函數值更優，其中旅客平均換乘滿意度增加約2.93%，到發均衡性增加約2.31%，旅客無效等待時間更少，h1站和h2站兩個車站的列車到發均衡性指標值的差異更小;對比基本遺傳算法，本文改進的遺傳算法使得旅客平均換乘滿意度增加約5.10%，到發均衡性增加約0.27%，且求得的目標函數值、平均無效等待時間、h1站和h2站兩個車站的列車到發均衡性指標差異均比基本遺傳算法求得的解更優。

由以上分析結果可知，本文設計改進的遺傳算法更加適合所研究問題的模型特征，具有更快的收斂速度和更優的求解性能，因此，文中基于換乘的高速鐵路樞紐列車接續優化模型和改進的遺傳算法能夠對換乘樞紐的列車接續優化問題進行有效求解。

利用本文的模型和改進遺傳算法對算例中的大型客運樞紐高鐵列車接續進行優化，算法迭代了623次之后，目標函數值趨于穩定且達到最小，得到目標函數值隨迭代次數變化情況如圖8所示。

4 結語

1） 通過優化與編排周期內換乘樞紐車站的所有列車到發順序的方法來研究換乘樞紐列車接續問題。建立基于換乘導向的大型高速鐵路樞紐列車接續優化模型，以換乘客流的平均換乘滿意度和樞紐車站列車到發均衡性為目標，考慮大站合理發車時間、換乘時間、車站間隔時間等約束，為解決換乘樞紐列車接續問題提供了理論基礎和方法借鑒。

2） 定義了換乘滿意度函數，在求解模型時將多目標問題轉化成單目標問題，借助于改進染色體編碼方式和選擇策略的遺傳算法，有效地求解了模型。研究結果優化了換乘樞紐車站的列車接續問題，驗證了模型和算法的有效性。

3） 通過對改進的遺傳算法與基本遺傳算法、基本模擬退火算法進行比較，可以看出本文設計的改進遺傳算法不僅穩定性和求解效率更高，且求得的解的質量更優，對文中問題求解具有較好的適應性。

4） 模型未考慮換出列車或接續列車發生晚點時的列車接續問題，對于這一問題的研究將是后續工作的重點。

參考文獻

[1]SHRIVASTAVA P， DHINGRA S L. Development of coordinated schedules using genetic algorithms [J]. Journal of Transportation Engineering， 2002， 128（1）： 89-96.

[2]YANG Z， KOSEKI T， SONE S. Railway network timetabling for reducing transfer time using genetic algorithm [J]. IEEJ Transactions on Sensors and Micromachines， 2008， 120（6）： 802-809.

[3]WONG R C W， YUEN T W Y， FUNG K W， et al. Optimizing timetable synchronization for rail mass transit [J]. Transportation Science， 2008， 42（1）： 57-69.

[4]MULLER T H J， FURTH P G. Transfer scheduling and control to reduce passenger waiting time [J]. Transportation Research Record： Journal of the Transportation Research Board， 2009， 3（2112）： 111-118.

[5]MESA J A， ORTEGA F A， POZO M A， et al. Rescheduling railway timetables in presence of passenger transfers between lines within a transportation network [M]// de SOUSA J F， ROSSI R. Computer-based Modelling and Optimization in Transportation， AISC 262. Berlin： Springer， 2014： 347-360.

[6]HASSANNAYEBI E， ZEGORDI S H， YAGHINI M， et al. Timetable optimization models and methods for minimizing passenger waiting time at public transit terminals [J]. Transportation Planning and Technology， 2017， 40（3）： 278-304.

[7]禹丹丹，韓寶明，董寶田，等.基于換乘協同的軌道交通網列車時刻表優化模型[J]. 中國鐵道科學，2015，36（4）：129-135.（YU D D， HAN B M， DONG B T， et al. Optimization model of train timetable for rail transit network based on transfer synchronization [J]. China Railway Science， 2015， 36（4）： 129-135.）

[8]姚鳳金，楊浩.旅客樞紐換乘時間調度研究[J].交通運輸系統工程與信息，2008，8（1）：133-137.（YAO F J， YANG H. On transferring time scheduling of passenger hubs [J]. Journal of Transportation Systems Engineering and Information Technology， 2008， 8（1）： 133-137.）

[9]郭瑾.高速鐵路綜合樞紐換乘條件評價及應用研究[D].北京：北京交通大學，2011：33-59.（GUO J. Research on evaluation and application of transfer condition for integrated hub of high-speed railway [D]. Beijing： Beijing Jiaotong University， 2011： 33-59.）

[10]郭根材，聶磊，賀振歡，等.基于歐洲列車時刻表的高速列車銜接方案探討[J]. 北京交通大學學報，2012，36（6）： 21-26. （GUO G C， NIE L， HE Z H， et al. Train connection plan for high-speed railway based on European rail timetable [J]. Journal of Beijing Jiaotong University， 2012， 36（6）： 21-26.）

[11]黃曲.大型換乘站旅客列車接續方案優化研究[D].成都：西南交通大學，2018：38-39.（HUANG Q. Research on optimization of passenger train connection scheme in large transfer station [D]. Chengdu： Southwest Jiaotong University， 2018： 38-39.）

[12]王建聰.城市客運樞紐換乘組織關鍵問題研究[D].北京：北京交通大學，2006： 30-31.（WANG J C. Key issues on transfer organization of city passenger traffic hubs [D]. Beijing： Beijing Jiaotong University， 2006： 30-31.）

[13]謝仲磊.高鐵樞紐與城市路網的銜接分析[J]. 交通與運輸，2018，34（4）：12-14.（XIE Z L. Analysis of connection between high-speed railway hub and urban road network [J]. Traffic and Transportation， 2018， 34（4）： 12-14.）

[14]張發才.鐵路客運與城市交通運營組織銜接研究[D].南京：東南大學，2006：24-28. （ZHANG F C. Study on passenger transfer of operation between railway station and urban traffic [D]. Nanjing： Southeast University， 2006： 24-28.）

[15]周軍.高鐵客運樞紐與城市交通銜接方式優化研究[D].武漢：武漢理工大學，2013： 44-46.（ZHOU J. Study on the optimization of high-speed passenger transport hubs urban transportation mode [D]. Wuhan： Wuhan University of Technology， 2013： 44-46.）

[16]李政偉，譚國俊.改進的退火遺傳優化策略應用研究[J].計算機工程與應用，2010，46（4）：245-248. （LI Z W， TAN G J. Research and application of improved simulated annealing genetic strategy [J]. Computer Engineering and Applications， 2010， 46（4）： 245-248.）

[17]劉月娥，何東健，李崢嶸.一種用于BP網絡優化的并行模擬退火遺傳算法[J].計算機應用，2006，26（1）：204-206.（LIU Y E， HE D J， LI Z R. Parallel simulated anneling genetic algorithm for optimizing BP neural network [J]. Journal of Computer Applications， 2006， 26（1）： 204-206.）

[18]王瑩.面向超長距離客流的高速鐵路網絡化列車開行方案研究[D].北京：北京交通大學，2018：138-140.（WANG Y. Study on high-speed railway network line planning for extra-long distance passenger flow [D]. Beijing： Beijing Jiaotong University， 2018： 138-140.）

This work is partially supported by the National Natural Science Foundation of China （71861022， 61563028）.

QIAO Jun， born in 1993， M. S. candidate. Her research interests include operation management and decision optimization of rail transit.

MENG Xuelei， born in 1979， Ph. D.， professor. His research interests include operation management and decision optimization of rail transit.

WANG Dongxian， born in 1992， M. S. candidate. His research interests include operation management and decision optimization of rail transit.

TANG Lin， born in 1989， M. S. His research interests include operation management and decision optimization of rail transit.