喬俊 孟學(xué)雷 王東先 湯霖

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

關(guān)鍵詞：換乘滿意度;同站換乘;異站換乘;列車接續(xù);改進(jìn)遺傳算法

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：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 引言

我國(guó)高速鐵路的快速發(fā)展使得高鐵客流量和換乘客流量逐年攀升，客流種類和換乘方式也越來(lái)越多樣化。大型高速鐵路客運(yùn)樞紐作為城市對(duì)內(nèi)對(duì)外交通銜接的重要節(jié)點(diǎn)，樞紐內(nèi)的換乘問(wèn)題受到越來(lái)越多的重視。科學(xué)地分析樞紐的換乘條件，制定合理的換乘接續(xù)方案，優(yōu)化樞紐內(nèi)換乘接續(xù)列車到發(fā)時(shí)刻的銜接問(wèn)題，對(duì)于保障客流高效地?fù)Q乘具有重要意義。

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

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

針對(duì)這些問(wèn)題，對(duì)不同線路及方向的中長(zhǎng)途客流在樞紐內(nèi)的同站、異站換乘優(yōu)化問(wèn)題進(jìn)行研究，以樞紐內(nèi)需求換乘客流的平均換乘滿意度最大化和樞紐車站列車到發(fā)均衡性最大化為目標(biāo)，構(gòu)建了基于換乘導(dǎo)向的樞紐高鐵列車接續(xù)優(yōu)化模型，并設(shè)計(jì)改進(jìn)染色體編碼方式和選擇策略的遺傳算法進(jìn)行求解。

1 問(wèn)題描述

1.1 同站換乘過(guò)程

通常，大型客運(yùn)樞紐高鐵站均設(shè)有專門的中轉(zhuǎn)換乘通道，同站換乘旅客可以實(shí)現(xiàn)不出站換乘，整個(gè)換乘過(guò)程為旅客下車步行至接續(xù)列車?？空九_(tái)候車（或至專用候車室候車）然后檢票完成上車。

如圖1，定義從換出列車x到達(dá)車站h時(shí)刻ax起至接續(xù)列車x從同一車站h出發(fā)時(shí)刻dx止的時(shí)間為同站換乘時(shí)間，包括兩部分：一是旅客從換出列車下車步行至接續(xù)列車?？空九_(tái)（或至專用候車室）時(shí)止的必要走行時(shí)間tb;二是旅客從到達(dá)接續(xù)列車站臺(tái)或?qū)Ｓ煤蜍囀視r(shí)起至接續(xù)列車出發(fā)時(shí)止的等待時(shí)間tw。

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

1.2 異站換乘過(guò)程

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

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

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

2 樞紐內(nèi)換乘接續(xù)優(yōu)化模型的構(gòu)建

2.1 模型假設(shè)

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

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

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

2.4 約束條件

本文主要從高鐵站列車合理到發(fā)時(shí)間、換乘客流量、旅客換乘時(shí)間、車站間隔時(shí)間等方面對(duì)模型進(jìn)行約束：

1）高速列車合理到發(fā)時(shí)間約束。

amnixh-Tmnxh≥DmnE（5）

dmnjxh-Tmnxh≤AmnL（6）

T1≤amnixh≤T2（7）

T1≤dmnjxh≤T2（8）

式（5）表示到達(dá)樞紐車站的高速列車在其始發(fā)站的始發(fā)時(shí)刻不早于始發(fā)車站的最早發(fā)車時(shí)刻;式（6）表示離開(kāi)樞紐車站的高速列車到達(dá)其終點(diǎn)站的時(shí)刻不晚于終到車站的最晚終到時(shí)刻;式（7）、（8）表示樞紐車站的列車到發(fā)時(shí)刻應(yīng)在研究周期內(nèi)。

2）換乘客流量約束。

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

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

0，μ1<μ2（10）

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

3）換乘時(shí)間約束。

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*構(gòu)成接續(xù)關(guān)系，則兩列車在樞紐車站的出發(fā)和到達(dá)時(shí)刻差要滿足換乘時(shí)間約束。

4）通過(guò)列車停站時(shí)間約束。

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

5）車站間隔時(shí)間約束。

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

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

dmnjxh-amnixh≥Iad（16）

amnixh-dmnjxh≥Ida（17）

式（14）～（17）表示樞紐車站同方向兩列車到發(fā)的時(shí)間間隔應(yīng)滿足車站的列車到達(dá)、出發(fā)、到發(fā)、發(fā)到時(shí)間間隔約束。

6）樞紐車站到發(fā)線能力約束。

對(duì)于任意時(shí)刻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）中引入?yún)?shù)whxx表示列車x或x在樞紐內(nèi)h站的停站方式，whxx取-1表示始發(fā)列車，whxx取0表示通過(guò)列車，whxx取1表示終到列車。ψ1（dmnjxh，amnixh，whxx）表示列車開(kāi)始占用到發(fā)線的時(shí)間函數(shù)，ψ2（dmnjxh，amnixh，whxx）表示列車結(jié)束占用到發(fā)線的時(shí)間函數(shù)。

7）區(qū)間通過(guò)能力約束。

cra+crd≤CrT（22）

3 算法設(shè)計(jì)及算例分析

3.1 改進(jìn)遺傳算法設(shè)計(jì)

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

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

采用改進(jìn)染色體編碼和選擇策略的遺傳算法，設(shè)計(jì)的算法步驟如下：

1）構(gòu)造基因編碼和染色體。

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

2）初始種群的生成。

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

①在[T1，T2]內(nèi)生成一個(gè)隨機(jī)數(shù)t1，作為dmn1xh;

②在[t1，T2]內(nèi)生成一個(gè)隨機(jī)數(shù)t2，作為dmn2x′h;

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

同理可以生成染色體中任意兩個(gè)斷點(diǎn)之間的列車到達(dá)時(shí)刻升序排列片段，并將這些片段組成完整的染色體個(gè)體。

3）適應(yīng)度函數(shù)。

設(shè)K為種群規(guī)模，Zk是當(dāng)前種群中的第k個(gè)染色體的目標(biāo)函數(shù)值，Zmax和Zmin分別為當(dāng)前種群的最大、最小目標(biāo)函數(shù)值，gk為適應(yīng)度函數(shù)。

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

其中：γ是（0，1）內(nèi)的隨機(jī)數(shù)，引入γ使得當(dāng)染色體間的適應(yīng)值差距較大時(shí)，采用適應(yīng)值比例選擇，當(dāng)染色體間的適應(yīng)值差距較小時(shí)，則在相互競(jìng)爭(zhēng)的染色體中進(jìn)行純隨機(jī)的選擇。這樣使表現(xiàn)較優(yōu)的個(gè)體適應(yīng)度更大，進(jìn)入下一代的幾率也更大。

4）改進(jìn)選擇算子。

文中應(yīng)用如下混合改進(jìn)了的選擇方案，將選擇操作分為以下3個(gè)步驟：

①將計(jì)算得到的個(gè)體適應(yīng)度按照從大到小進(jìn)行排序，保留父代種群中的前1/4個(gè)體[16];

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

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

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為初始溫度。改進(jìn)的選擇算子借鑒了模擬退火算法中的拉伸方法，可以改善基本遺傳算法的早熟問(wèn)題，同時(shí)使得在遺傳算法后期過(guò)程中，當(dāng)個(gè)體染色體適應(yīng)度趨于一致時(shí)，改進(jìn)的算法具有更好的選擇效果，同時(shí)這一選擇算子不僅包含了父代種群中的最佳個(gè)體，保證了算法的收斂性，又保留了最優(yōu)個(gè)體以外的優(yōu)秀個(gè)體，增加了種群的多樣性，避免算法陷入局部最優(yōu)解。

5）交叉算子。

文中的染色體是由不同片段的車次實(shí)數(shù)編碼和列車有序到（發(fā)）時(shí)刻整數(shù)編碼元組構(gòu)成，采用傳統(tǒng)的交叉方法不能得到理想的結(jié)果，因此本文采用區(qū)域交叉，將交叉區(qū)域限定在兩個(gè)相鄰的斷點(diǎn)之間，并將交叉區(qū)域的到（發(fā)）時(shí)刻值與另一個(gè)群體基因位的時(shí)刻值進(jìn)行比較，交叉時(shí)車次不隨時(shí)刻交叉，具體操作步驟如下：

①在父代種群中，隨機(jī)選擇兩個(gè)個(gè)體作為父代1和父代2，并隨機(jī)選取兩個(gè)相鄰斷點(diǎn)之間的兩個(gè)交叉點(diǎn)，規(guī)定父代1和父代2的兩個(gè)相鄰斷點(diǎn)的選擇相同。將這兩個(gè)交叉點(diǎn)之間的所有時(shí)刻基因值作為交叉對(duì)象進(jìn)行交叉操作。

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

6）變異算子。

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

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

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

其中β∈（0，1），是一個(gè)隨機(jī)數(shù)。

7）終止條件。

設(shè)定改進(jìn)的遺傳算法最大進(jìn)化代數(shù)，當(dāng)遺傳算法運(yùn)行到最大進(jìn)化代數(shù)之后，停止運(yùn)行，輸出結(jié)果;否則轉(zhuǎn)步驟3）。

3.2 算例分析

選擇高速鐵路網(wǎng)中某一大型樞紐，樞紐銜接兩條高速鐵路線路，存在兩個(gè)高鐵站且兩車站之間存在聯(lián)絡(luò)線，該樞紐采用以軌道交通為主的客流集疏運(yùn)模式，圖6是研究客運(yùn)樞紐的換乘接續(xù)示意圖。

該樞紐詳細(xì)概況如下：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。選

取該樞紐的中長(zhǎng)途旅客換乘時(shí)段13：00—14：00作為研究周期，樞紐內(nèi)兩個(gè)高鐵站的列車開(kāi)行方案如表1所示。由于文獻(xiàn)[11-12，18]研究樞紐與文中所研究樞紐概況、換乘客流量相當(dāng)，因而推算得出研究周期內(nèi)不同列車間的換乘客流量預(yù)測(cè)值，如表2所示。

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

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

鑒于本文設(shè)計(jì)改進(jìn)的遺傳算法結(jié)合了模擬退火算法的思想，因此，本文又以基本模擬退火算法作為對(duì)比算法，在同一臺(tái)計(jì)算機(jī)上利用Matlab編程實(shí)現(xiàn)基本模擬退火算法求解模型，通過(guò)進(jìn)行多次實(shí)驗(yàn)，得到基本模擬退火算法計(jì)算的結(jié)果為：算法迭代了696次之后，目標(biāo)函數(shù)值趨于穩(wěn)定且到達(dá)最小，此時(shí)求得的目標(biāo)函數(shù)值為-0.1088，其中目標(biāo)值Z1滿意度為0.6186，目標(biāo)值Z2列車到發(fā)均衡性值為655.7341，進(jìn)一步將基本模擬退火算法、基本遺傳算法以及本文改進(jìn)的遺傳算法進(jìn)行比較，如表5所示。

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

在樞紐列車到發(fā)均衡性方面，h2站連接的2線路2方向列車到達(dá)和2線路1方向列車出發(fā)、h1站連接的1線路2方向列車出發(fā)和2線路1方向列車到達(dá)，這幾個(gè)方向的列車到發(fā)均

衡性較優(yōu)，而h1站連接的1線路列車到發(fā)均衡性較差。總的來(lái)說(shuō)，h2站的列車到發(fā)均衡性較h1站更優(yōu)。

為了進(jìn)一步驗(yàn)證改進(jìn)后遺傳算法的穩(wěn)定性，分別運(yùn)用基本遺傳算法和改進(jìn)遺傳算法對(duì)算例求解，圖7是隨機(jī)抽取的50次實(shí)驗(yàn)結(jié)果的收斂代數(shù)情況?？梢钥闯?，在種群規(guī)模和迭代次數(shù)相同的情況下，改進(jìn)后的遺傳算法穩(wěn)定性更好。

利用本文模型和改進(jìn)的遺傳算法對(duì)高速鐵路網(wǎng)中某一大型客運(yùn)樞紐高速列車接續(xù)問(wèn)題進(jìn)行優(yōu)化，得到目標(biāo)函數(shù)值隨迭代次數(shù)變化情況，如圖8所示。

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

由以上分析結(jié)果可知，本文設(shè)計(jì)改進(jìn)的遺傳算法更加適合所研究問(wèn)題的模型特征，具有更快的收斂速度和更優(yōu)的求解性能，因此，文中基于換乘的高速鐵路樞紐列車接續(xù)優(yōu)化模型和改進(jìn)的遺傳算法能夠?qū)Q乘樞紐的列車接續(xù)優(yōu)化問(wèn)題進(jìn)行有效求解。

利用本文的模型和改進(jìn)遺傳算法對(duì)算例中的大型客運(yùn)樞紐高鐵列車接續(xù)進(jìn)行優(yōu)化，算法迭代了623次之后，目標(biāo)函數(shù)值趨于穩(wěn)定且達(dá)到最小，得到目標(biāo)函數(shù)值隨迭代次數(shù)變化情況如圖8所示。

4 結(jié)語(yǔ)

1） 通過(guò)優(yōu)化與編排周期內(nèi)換乘樞紐車站的所有列車到發(fā)順序的方法來(lái)研究換乘樞紐列車接續(xù)問(wèn)題。建立基于換乘導(dǎo)向的大型高速鐵路樞紐列車接續(xù)優(yōu)化模型，以換乘客流的平均換乘滿意度和樞紐車站列車到發(fā)均衡性為目標(biāo)，考慮大站合理發(fā)車時(shí)間、換乘時(shí)間、車站間隔時(shí)間等約束，為解決換乘樞紐列車接續(xù)問(wèn)題提供了理論基礎(chǔ)和方法借鑒。

2） 定義了換乘滿意度函數(shù)，在求解模型時(shí)將多目標(biāo)問(wèn)題轉(zhuǎn)化成單目標(biāo)問(wèn)題，借助于改進(jìn)染色體編碼方式和選擇策略的遺傳算法，有效地求解了模型。研究結(jié)果優(yōu)化了換乘樞紐車站的列車接續(xù)問(wèn)題，驗(yàn)證了模型和算法的有效性。

3） 通過(guò)對(duì)改進(jìn)的遺傳算法與基本遺傳算法、基本模擬退火算法進(jìn)行比較，可以看出本文設(shè)計(jì)的改進(jìn)遺傳算法不僅穩(wěn)定性和求解效率更高，且求得的解的質(zhì)量更優(yōu)，對(duì)文中問(wèn)題求解具有較好的適應(yīng)性。

4） 模型未考慮換出列車或接續(xù)列車發(fā)生晚點(diǎn)時(shí)的列車接續(xù)問(wèn)題，對(duì)于這一問(wèn)題的研究將是后續(xù)工作的重點(diǎn)。

參考文獻(xiàn)

[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]禹丹丹，韓寶明，董寶田，等.基于換乘協(xié)同的軌道交通網(wǎng)列車時(shí)刻表優(yōu)化模型[J]. 中國(guó)鐵道科學(xué)，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]姚鳳金，楊浩.旅客樞紐換乘時(shí)間調(diào)度研究[J].交通運(yùn)輸系統(tǒng)工程與信息，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]郭瑾.高速鐵路綜合樞紐換乘條件評(píng)價(jià)及應(yīng)用研究[D].北京：北京交通大學(xué)，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]郭根材，聶磊，賀振歡，等.基于歐洲列車時(shí)刻表的高速列車銜接方案探討[J]. 北京交通大學(xué)學(xué)報(bào)，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]黃曲.大型換乘站旅客列車接續(xù)方案優(yōu)化研究[D].成都：西南交通大學(xué)，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]王建聰.城市客運(yùn)樞紐換乘組織關(guān)鍵問(wèn)題研究[D].北京：北京交通大學(xué)，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]謝仲磊.高鐵樞紐與城市路網(wǎng)的銜接分析[J]. 交通與運(yùn)輸，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]張發(fā)才.鐵路客運(yùn)與城市交通運(yùn)營(yíng)組織銜接研究[D].南京：東南大學(xué)，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]周軍.高鐵客運(yùn)樞紐與城市交通銜接方式優(yōu)化研究[D].武漢：武漢理工大學(xué)，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]李政偉，譚國(guó)俊.改進(jìn)的退火遺傳優(yōu)化策略應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，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網(wǎng)絡(luò)優(yōu)化的并行模擬退火遺傳算法[J].計(jì)算機(jī)應(yīng)用，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]王瑩.面向超長(zhǎng)距離客流的高速鐵路網(wǎng)絡(luò)化列車開(kāi)行方案研究[D].北京：北京交通大學(xué)，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.