代存杰，李引珍，展宗思，柴　獲

(1.蘭州交通大學(xué) 機(jī)電技術(shù)研究所，甘肅 蘭州　730070；2.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州　730070；3.西安市地下鐵道有限責(zé)任公司，陜西 西安　710016)

列車(chē)開(kāi)行方案是城市軌道交通運(yùn)營(yíng)組織的重要工作，列車(chē)發(fā)車(chē)時(shí)刻表是開(kāi)行方案設(shè)計(jì)的核心內(nèi)容，需要根據(jù)客流需求的分布特征科學(xué)制訂。由于列車(chē)運(yùn)行路線上存在區(qū)段客流不均衡、客流斷面突變現(xiàn)象，因此應(yīng)基于不同的列車(chē)交路模式，設(shè)計(jì)合理的列車(chē)發(fā)車(chē)時(shí)刻表，對(duì)列車(chē)開(kāi)行方案進(jìn)行優(yōu)化，以減少乘客等待時(shí)間、提高列車(chē)滿載率。

國(guó)內(nèi)外學(xué)者在列車(chē)發(fā)車(chē)時(shí)刻表優(yōu)化方面做了諸多研究，Serafini等[1]建立了時(shí)間約束下周期性事件調(diào)度模型，并應(yīng)用于列車(chē)發(fā)車(chē)時(shí)刻表的設(shè)計(jì)；Kwan等[2]考慮列車(chē)運(yùn)營(yíng)費(fèi)用和乘客滿意度，利用啟發(fā)式算法對(duì)列車(chē)發(fā)車(chē)時(shí)刻表進(jìn)行優(yōu)化；Liebchen[3]在既有圖解模型的基礎(chǔ)上對(duì)柏林地鐵系統(tǒng)的列車(chē)發(fā)車(chē)周期進(jìn)行了優(yōu)化；Kroon等[4]通過(guò)調(diào)整列車(chē)運(yùn)行的補(bǔ)償時(shí)間和相鄰列車(chē)之間的緩沖時(shí)間，提高列車(chē)發(fā)車(chē)時(shí)刻表在隨機(jī)擾動(dòng)下的魯棒性；廖勇[5]將客流到達(dá)車(chē)站的過(guò)程視為隨機(jī)過(guò)程，據(jù)此對(duì)城際列車(chē)發(fā)車(chē)間隔進(jìn)行優(yōu)化。

在城市軌道交通的實(shí)際運(yùn)營(yíng)過(guò)程中，不同時(shí)段內(nèi)不同車(chē)站的乘客到站數(shù)量存在差異，致使客流需求存在時(shí)間和空間上的不均衡性。若乘客到站數(shù)量服從均勻分布或泊松分布，則周期性的發(fā)車(chē)間隔時(shí)間可減少乘客等待時(shí)間[6]。在具有時(shí)變特征的客流需求下，固定發(fā)車(chē)間隔時(shí)間會(huì)導(dǎo)致部分乘客的等待時(shí)間過(guò)長(zhǎng)[7]。

根據(jù)客流需求在時(shí)間上分布不均衡的特征，Cury等[8]以乘客滿意度和列車(chē)運(yùn)營(yíng)成本為目標(biāo)建立模型，得到非固定的列車(chē)發(fā)車(chē)間隔時(shí)間；Albrecht[9]根據(jù)列車(chē)運(yùn)力確定最優(yōu)發(fā)車(chē)頻率后，設(shè)計(jì)了面向乘客需求的列車(chē)發(fā)車(chē)時(shí)刻表；Niu等[10]考慮擁擠情況下的客流時(shí)變特征，建立城市軌道交通列車(chē)發(fā)車(chē)時(shí)刻表的優(yōu)化模型；Barrena等[11]以乘客平均等待時(shí)間最小為目標(biāo)，對(duì)動(dòng)態(tài)客流需求下的列車(chē)發(fā)車(chē)時(shí)刻表優(yōu)化；Hassannayebi等[12]考慮客流需求和列車(chē)行程時(shí)間的不確定性，設(shè)計(jì)了兩階段模擬方法以生成魯棒的列車(chē)發(fā)車(chē)時(shí)刻表。

針對(duì)客流需求空間分布的不均衡性，常采用不同的列車(chē)開(kāi)行方案以適應(yīng)客流空間分布特征[13]；程婕等[14]以列車(chē)輸送能力與客流空間分布的最佳匹配為原則，建立了列車(chē)開(kāi)行方案優(yōu)化的多目標(biāo)0-1規(guī)劃模型；王媛媛等[15]以乘客出行成本及企業(yè)運(yùn)營(yíng)成本最小為目標(biāo)，構(gòu)建大小交路模式下列車(chē)開(kāi)行方案的優(yōu)化模型；凌俊等[16]根據(jù)城市軌道交通客流不均衡情況，對(duì)非高峰期列車(chē)開(kāi)行方案進(jìn)行研究。

但是，這些既有研究多從單一方面對(duì)城市軌道交通列車(chē)開(kāi)行方案進(jìn)行優(yōu)化，沒(méi)有同時(shí)考慮客流需求的時(shí)間和空間分布不均衡特征以及列車(chē)交路模式。為此，本文考慮客流需求的時(shí)間和空間分布特征，對(duì)大小交路模式下列車(chē)開(kāi)行方案優(yōu)化進(jìn)行研究。

1　問(wèn)題描述

1.1　動(dòng)態(tài)客流需求分析

動(dòng)態(tài)客流需求分析的核心工作是分析客流需求的時(shí)間和空間分布規(guī)律。影響客流在時(shí)間上變化的主要因素為乘客的出行行為，乘客的日常出行行為在1天內(nèi)是不同的，導(dǎo)致1天內(nèi)客流是動(dòng)態(tài)變化的，但在1天內(nèi)的出行行為又具有一定的規(guī)律性，所以，同一車(chē)站各時(shí)段內(nèi)的客流密度基本是確定的，不同車(chē)站的客流變化規(guī)律不同。

影響客流在空間上變化的主要因素是車(chē)站覆蓋的客流集散點(diǎn)的規(guī)模和數(shù)量不同，因而各車(chē)站的乘降人數(shù)不同，致使各斷面客流空間分布的不平衡；同時(shí)，新的居民住宅區(qū)入住和新的軌道交通線路投入運(yùn)營(yíng)，也會(huì)使車(chē)站乘降人數(shù)發(fā)生較大的變化。

為表達(dá)不同時(shí)段內(nèi)的動(dòng)態(tài)客流需求特征，定義如下參數(shù)：U={1,2,…,2N}為車(chē)站序號(hào)集合，其中1,2,…,N為上行方向車(chē)站編號(hào)，N+1,N+2,…,2N為下行方向車(chē)站編號(hào)，且車(chē)站1與2N；2與2N-1；…；N與N+1分別共用同一個(gè)站臺(tái)；T為城市軌道交通日運(yùn)營(yíng)時(shí)間長(zhǎng)度，δ為單位時(shí)間，列車(chē)發(fā)車(chē)時(shí)間點(diǎn)t∈T，且t=nδ，n為正整數(shù)；u∈U和v∈U為單個(gè)車(chē)站的編號(hào)，且v>u；ρu,v(t)為時(shí)間點(diǎn)t從u出發(fā)前往v的客流密度，當(dāng)u∈{1,2,…,N}且v∈{N+1,N+2,…,2N}時(shí)，ρu,v(t)=0；Πu,v(t)為列車(chē)開(kāi)始運(yùn)營(yíng)時(shí)間點(diǎn)0到時(shí)間點(diǎn)t之間從u出發(fā)前往v的累計(jì)客流需求。

Πu,v(t)與ρu,v(t)的關(guān)系表達(dá)式為

(1)

(2)

圖1　車(chē)站u的累計(jì)客流需求

(3)

(4)

(5)

對(duì)式(5)求和可得時(shí)段[t1,t2]內(nèi)從車(chē)站u出發(fā)的累計(jì)客流需求為

(6)

1.2　大小交路模式列車(chē)發(fā)車(chē)時(shí)間間隔分析

在大小交路模式下確定列車(chē)開(kāi)行方案時(shí)，為避免列車(chē)在線路中的行車(chē)沖突，通常取固定發(fā)車(chē)間隔時(shí)間，不同交路列車(chē)的開(kāi)行數(shù)量為嚴(yán)格的倍數(shù)關(guān)系，但這種固定發(fā)車(chē)間隔時(shí)間會(huì)導(dǎo)致客流需求低峰期時(shí)的運(yùn)力浪費(fèi)或客流需求高峰期時(shí)的運(yùn)力不足[18]。在列車(chē)運(yùn)行控制技術(shù)可行的前提下，大小交路列車(chē)的開(kāi)行只要滿足最大、最小追蹤間隔約束，可根據(jù)客流需求特征動(dòng)態(tài)設(shè)定非固定的發(fā)車(chē)間隔時(shí)間[20]，使列車(chē)交路方案確定的輸送能力與客流需求空間特征達(dá)到最佳匹配。

2　多目標(biāo)優(yōu)化模型

2.1　假設(shè)條件

根據(jù)城市軌道交通實(shí)際運(yùn)營(yíng)情況首先作如下假設(shè)：①各站乘客服從“先到先服務(wù)”的原則；② 乘客不選擇列車(chē)交路類型，即可能登乘時(shí)則登乘；③列車(chē)在各站停靠時(shí)間和站間行駛時(shí)間是確定的；④不存在列車(chē)越行和會(huì)讓的情況。

2.2　參數(shù)定義

2.3　模型建立

根據(jù)假設(shè)條件和相關(guān)參數(shù)定義，計(jì)算模型的相關(guān)參數(shù)，具體如下。

(7)

列車(chē)j從車(chē)站u的出發(fā)時(shí)間為

(8)

(9)

當(dāng)車(chē)站u無(wú)滯站乘客存在時(shí)，可成功登乘列車(chē)j的乘客數(shù)量γj,u為

(10)

(11)

(12)

γj,u=A-(Cj-u-1-Oj,u)

(13)

此時(shí)，部分乘客需要等待列車(chē)j+1，則Bj,u為

Bj,u=Wj,u-γj,u

(14)

(15)

當(dāng)列車(chē)為小交路運(yùn)行時(shí)，列車(chē)需要在車(chē)站u′清客，則該部分乘客在車(chē)站u′的等待時(shí)間為

(16)

(17)

在整個(gè)日運(yùn)營(yíng)時(shí)間長(zhǎng)度T內(nèi)，根據(jù)式(6)可得車(chē)站u的累計(jì)客流需求為

(18)

由此可計(jì)算所有乘客的平均等待時(shí)間?，即

(19)

(20)

(21)

考慮客流需求的動(dòng)態(tài)特征和大小交路模式特點(diǎn)，以減少乘客平均等待時(shí)間、提高列車(chē)平均滿載率、減少列車(chē)總走行公里數(shù)為優(yōu)化目標(biāo)，建立城市軌道交通列車(chē)開(kāi)行方案的多目標(biāo)混合整數(shù)非線性優(yōu)化模型為

(22)

s.t.

(23)

(24)

(25)

(26)

(27)

約束條件中：式(23)和式(24)分別為最小和最大發(fā)車(chē)間隔時(shí)間分別滿足最小和最大追蹤列車(chē)間隔時(shí)間約束；式(25)為車(chē)輛運(yùn)力供需比約束，即開(kāi)行列車(chē)的輸送能力不小于客流需求量；式(26)和式(27)分別為列車(chē)j與相鄰列車(chē)j-1和j+1在車(chē)站u′的追蹤列車(chē)間隔時(shí)間不小于最小追蹤列車(chē)間隔時(shí)間Imin，以保證小交路運(yùn)行的列車(chē)j在折返站u′折返后的運(yùn)行安全。

3　求解算法設(shè)計(jì)

在對(duì)模型求解時(shí)，需要根據(jù)客流特征動(dòng)態(tài)安排列車(chē)的交路模式和發(fā)車(chē)時(shí)間，此問(wèn)題屬于組合優(yōu)化問(wèn)題，可用遺傳算法有效地求解[10]。由于各求解目標(biāo)并不統(tǒng)一，只能根據(jù)各目標(biāo)的優(yōu)化準(zhǔn)則得到非支配解。因此，本文將快速非支配遺傳算法NSGA-Ⅱ與自適應(yīng)鄰域搜索方法相結(jié)合對(duì)模型求解，并對(duì)遺傳操作中的交叉和變異算子進(jìn)行改進(jìn)。

NSGA-Ⅱ?yàn)槎嗄繕?biāo)進(jìn)化算法，降低了非支配排序遺傳算法的復(fù)雜性，具有運(yùn)行速度快、收斂性好的優(yōu)點(diǎn)，成為其他多目標(biāo)優(yōu)化算法的基準(zhǔn)[21]。本文在標(biāo)準(zhǔn)NSGA-Ⅱ的基礎(chǔ)上，設(shè)計(jì)多點(diǎn)動(dòng)態(tài)交叉操作，并結(jié)合啟發(fā)式鄰域搜索機(jī)制，對(duì)染色體的變異操作進(jìn)行改進(jìn)，以產(chǎn)生性能更優(yōu)的新染色體，加快算法的求解速度。

3.1　編碼設(shè)計(jì)

考慮列車(chē)發(fā)車(chē)時(shí)間的離散性，對(duì)染色體采用0-1編碼方式。染色體中的每個(gè)基因表示時(shí)段T內(nèi)的單位時(shí)間點(diǎn)，對(duì)應(yīng)編碼0或1。基因值為1表示該時(shí)間點(diǎn)有列車(chē)出發(fā)，基因值為0表示在對(duì)應(yīng)時(shí)間點(diǎn)無(wú)列車(chē)出發(fā)。設(shè)間隔時(shí)間基準(zhǔn)δ=1(min)，Imin=3δ，Imax=10δ，染色體結(jié)構(gòu)如圖2所示。

二進(jìn)制編碼可表示單一交路模式的列車(chē)離散發(fā)車(chē)間隔時(shí)間，為適應(yīng)大小交路模式，在設(shè)計(jì)染色體編碼時(shí)需要考慮交路類型。在染色體的基因信息中加入開(kāi)行列車(chē)的交路模式，0表示該時(shí)刻沒(méi)有列車(chē)發(fā)出，1表示該時(shí)刻有交路類型1的列車(chē)發(fā)出，2表示該時(shí)刻有交路類型2的列車(chē)發(fā)出。大小交路模式的染色體結(jié)構(gòu)在圖2的基礎(chǔ)上變?yōu)槿鐖D3所示。

圖2　染色體結(jié)構(gòu)

圖3　大小交路模式的染色體結(jié)構(gòu)

3.2　選擇操作

針對(duì)染色體種群，利用快速非支配排序策略計(jì)算每條染色體的層級(jí)序號(hào)r(·)和擁擠距離d(·)。 根據(jù)r(·)和d(·)可以比較2條染色體的優(yōu)劣。將染色體x1和染色體x2進(jìn)行比較，如果x1優(yōu)于x2，則x1至少滿足下面2種條件之一：①r(x1)>r(x2)； ②r(x1)=r(x2),d(x1)>d(x2)。

3.3　交叉算子設(shè)計(jì)

在傳統(tǒng)單點(diǎn)交叉的基礎(chǔ)上，設(shè)計(jì)動(dòng)態(tài)多點(diǎn)交叉操作。雖然這種交叉方式可能會(huì)破壞優(yōu)秀染色體的結(jié)構(gòu)，但會(huì)提高算法對(duì)整個(gè)解空間的搜索能力，比單點(diǎn)交叉表現(xiàn)出更好的收斂性能[22]。

圖4　動(dòng)態(tài)多點(diǎn)交叉操作

在交叉操作后，只保留滿足約束條件的子代染色體。將可行子代染色體放入新的種群，用來(lái)與父代染色體所在種群進(jìn)行非支配比較，達(dá)到精英保留和種群優(yōu)化的目的。

3.4　變異算子設(shè)計(jì)

在設(shè)計(jì)染色體變異算子時(shí)，結(jié)合自適應(yīng)鄰域搜索機(jī)制對(duì)染色體進(jìn)行啟發(fā)式變異，分為染色體破壞操作和染色體修復(fù)操作。

1)染色體破壞操作

破壞操作是用來(lái)減少開(kāi)行的列車(chē)數(shù)量或?qū)⒘熊?chē)由大交路運(yùn)行模式變?yōu)樾〗宦愤\(yùn)行模式，以提高列車(chē)的滿載率，避免運(yùn)力過(guò)剩，同時(shí)減少列車(chē)走行公里數(shù)。操作步驟如下。

2)染色體修復(fù)操作

修復(fù)操作是用于增加開(kāi)行列車(chē)數(shù)量，或根據(jù)折返站前后連續(xù)客流斷面的平均值，進(jìn)行列車(chē)大小交路調(diào)整，以減少乘客的等待時(shí)間。操作步驟如下。

4　算例及結(jié)果分析

以西安地鐵2號(hào)線為研究對(duì)象，此線路共設(shè)有21座車(chē)站，北客站至韋曲南站為方向上行。列車(chē)在各區(qū)間的運(yùn)行時(shí)間、在各站的?？繒r(shí)間見(jiàn)表1。

韋曲南站的停留時(shí)間為大交路列車(chē)在該站進(jìn)行折返作業(yè)時(shí)間，會(huì)展中心站的停留時(shí)間分別為小交路列車(chē)的折返作業(yè)時(shí)間和大交路列車(chē)的?？繒r(shí)間。大交路列車(chē)的走行公里數(shù)為L(zhǎng)2=53.0 km，小交路列車(chē)的走行公里數(shù)為L(zhǎng)1=39.8 km，日運(yùn)營(yíng)時(shí)間為06:10至23:15，即T=1 025 min。

地鐵2號(hào)線的運(yùn)營(yíng)車(chē)輛采用B型車(chē)、3動(dòng)3拖6輛編組方式，列車(chē)定員為1 468人，終點(diǎn)站均采用站后折返；北客站最小全折返時(shí)間為5.7 min，韋曲南站最小全折返時(shí)間為4.3 min。最小追蹤列車(chē)間隔時(shí)間Imin=3 min，最大追蹤列車(chē)間隔時(shí)間為Imax=10 min，大交路的運(yùn)營(yíng)周期時(shí)間為104.0 min，小交路的運(yùn)營(yíng)周期時(shí)間為82.6 min。

根據(jù)地鐵自動(dòng)售檢票系統(tǒng)，可得到某日運(yùn)營(yíng)時(shí)間內(nèi)地鐵2號(hào)線各站累計(jì)到達(dá)客流需求變化曲線(以30 min為時(shí)間粒度提取)，如圖5所示。

表1　列車(chē)站間運(yùn)行時(shí)間和各站?？繒r(shí)間

*為小交路折返站

圖5　累計(jì)到達(dá)客流需求變化曲線

設(shè)置染色體的種群規(guī)模為200，最大迭代次數(shù)為300，交叉概率為0.8，動(dòng)態(tài)交叉點(diǎn)個(gè)數(shù)為5，變異概率為0.15。取ε=0.2；當(dāng)s>ε時(shí)，d=rand(30,50)，m=rand(20,30)； 當(dāng)s≤ε時(shí)，m=rand(30,50)，d=rand(20,30)。經(jīng)過(guò)計(jì)算，可得到大小交路模式下列車(chē)發(fā)車(chē)時(shí)間優(yōu)化結(jié)果。在生成的非支配解集中，解的空間分布如圖6所示。

在非支配解集中，取各個(gè)目標(biāo)函數(shù)的最優(yōu)值時(shí)，對(duì)應(yīng)的列車(chē)開(kāi)行方案見(jiàn)表2。

解析非支配解集中的任一非支配解，都可得到列車(chē)在始發(fā)站出發(fā)時(shí)刻及對(duì)應(yīng)的列車(chē)運(yùn)行圖。以解集中的非極值解(3.26,85.53%,8.63)為例，對(duì)應(yīng)的開(kāi)行列車(chē)總數(shù)為170列，其中大交路開(kāi)行列車(chē)總數(shù)為142列，小交開(kāi)行路列總數(shù)為28列，在u=1的列車(chē)發(fā)車(chē)時(shí)刻及運(yùn)行情況如圖7所示。

圖6　非支配解的空間分布圖

優(yōu)化目標(biāo)?/min λ/%l/103km開(kāi)行列車(chē)總數(shù)/列其中大交路開(kāi)行列車(chē)總數(shù)/列其中小交路開(kāi)行列車(chē)總數(shù)/列?2 9577 819 4318914544 λ7 1599 917 461411392l6 5699 877 451421366

圖7　列車(chē)發(fā)車(chē)時(shí)刻及運(yùn)行圖

分析圖5和圖7可知：列車(chē)開(kāi)行方案中發(fā)車(chē)間隔時(shí)間的大小與客流需求的變化是吻合的，如早高峰和晚高峰時(shí)段，客流量較大，則列車(chē)發(fā)車(chē)間隔時(shí)間較小，并且同時(shí)開(kāi)行大、小交路列車(chē)；在平峰或低峰時(shí)段，客流量較小，則列車(chē)發(fā)車(chē)間隔時(shí)間較大，且僅開(kāi)行大交路列車(chē)。

將大小交路模式下的列車(chē)開(kāi)行方案設(shè)置為固定追蹤列車(chē)間隔時(shí)間，并設(shè)最小追蹤列車(chē)間隔時(shí)間Imin=5 min，最大追蹤列車(chē)間隔時(shí)間為Imax=10 min。對(duì)模型求解后生成非支配解集，當(dāng)各目標(biāo)函數(shù)分別取最優(yōu)值時(shí)，得到固定追蹤列車(chē)間隔時(shí)間條件下的開(kāi)行方案見(jiàn)表3。

表3　固定追蹤列車(chē)間隔時(shí)間的列車(chē)開(kāi)行方案參數(shù)

對(duì)比表2和表3可知：固定追蹤列車(chē)間隔時(shí)間與非固定追蹤列車(chē)間隔時(shí)間條件下對(duì)各優(yōu)化目標(biāo)取極值時(shí)，乘客平均等待時(shí)間增加34.24%，列車(chē)平均滿載率降低0.04%，列車(chē)總走行公里數(shù)提高0.13%。因此，根據(jù)客流的動(dòng)態(tài)需求采用非固定列車(chē)追蹤間隔時(shí)間，可以降低乘客的平均等待時(shí)間，減小列車(chē)開(kāi)行總數(shù)，從而更好地滿足乘客和運(yùn)營(yíng)企業(yè)雙方的利益。

為了分析列車(chē)在大小交路模式與單一大交路模式下的運(yùn)行方案差異，使用相同的客流數(shù)據(jù)和遺傳操作參數(shù)，得到單一大交路模式下列車(chē)運(yùn)行數(shù)據(jù)的非支配解。為使數(shù)據(jù)具有可比性，分別在生成的非支配解集中取近似相同的列車(chē)平均滿載率，計(jì)算不同模式下乘客平均等待時(shí)間、列車(chē)總走行公里數(shù)和開(kāi)行列車(chē)總數(shù)。并將其與大小交路模式下的結(jié)果進(jìn)行對(duì)比，見(jiàn)表4和表5。

表4　單一大交路模式下不同時(shí)的列車(chē)開(kāi)行方案參數(shù)

表5　大小交路模式下不同時(shí)的列車(chē)開(kāi)行方案參數(shù)

注：()內(nèi)為大交路開(kāi)行列車(chē)總數(shù)

由表4和表5可知：當(dāng)開(kāi)行列車(chē)的平均滿載率近似相等時(shí)，大小交路模式列車(chē)開(kāi)行方案要明顯優(yōu)于單一大交路模式的列車(chē)開(kāi)行方案；在開(kāi)行列車(chē)總數(shù)相差無(wú)幾的情況下，單一大交路模式下的乘客平均等待時(shí)間遠(yuǎn)高于大小交路模式下乘客平均等待時(shí)間。從計(jì)算過(guò)程的中間數(shù)據(jù)可知，在客流高峰時(shí)段，由于區(qū)段客流斷面的分布不均，單一大交路模式下共線路段的滯站乘客數(shù)量較大，致使乘客等待時(shí)間的增加。因此，考慮乘客出行需求的時(shí)間依賴特征，以及客流斷面分布不均的空間特征，開(kāi)行大小交路模式列車(chē)，能夠同時(shí)減少乘客等待時(shí)間和列車(chē)總走行公里數(shù)。

5　結(jié)　論

(1)通過(guò)分析乘客出行需求的時(shí)間、空間分布特征，采用4參數(shù)Logistic函數(shù)對(duì)累計(jì)客流曲線分段擬合，推導(dǎo)出各車(chē)站在任意時(shí)間段內(nèi)客流需求量的計(jì)算公式。

(2)考慮運(yùn)營(yíng)企業(yè)和乘客雙方的不同需求，以最大、最小追蹤列車(chē)間隔時(shí)間和運(yùn)力供需比為約束條件，以所有乘客平均等待時(shí)間最小、列車(chē)平均載客率最高、列車(chē)總走行公里最少為目標(biāo)函數(shù)，建立城市軌道交通列車(chē)開(kāi)行方案的多目標(biāo)混合整數(shù)非線性優(yōu)化模型；結(jié)合自適應(yīng)鄰域搜索策略，設(shè)計(jì)改進(jìn)的NSGA-Ⅱ算法對(duì)模型求解，并根據(jù)大小交路模式的列車(chē)發(fā)車(chē)特點(diǎn)，設(shè)計(jì)特殊結(jié)構(gòu)的編碼方式。

(3)以西安地鐵2號(hào)線某工作日的客流數(shù)據(jù)為例，對(duì)列車(chē)開(kāi)行方案進(jìn)行了優(yōu)化。結(jié)果表明，根據(jù)動(dòng)態(tài)客流需求對(duì)大小路模式下的列車(chē)開(kāi)行方案優(yōu)化，可有效減少乘客的平均等待時(shí)間，提高列車(chē)平均滿載率并減少列車(chē)總走行公里數(shù)，從而更好地滿足乘客和運(yùn)營(yíng)企業(yè)雙方利益訴求。

[1]SERAFINI P, UKOVICH W. A Mathematical Model for Periodic Scheduling Problems [J]. Siam Journal on Discrete Mathematics, 1989, 2(4):550-581.

[2]KWAN C M, CHANG C S. Application of Evolutionary Algorithm on a Transportation Scheduling Problem: the Mass Rapid Transit[C]//The 2005 IEEE Congress on Evolutionary Computation. Edinburgh: IEEE, 2005:987-994.

[3]LIEBCHEN C. The First Optimized Railway Timetable in Practice [J]. Transportation Science, 2008, 42(4): 420-435.

[4]KROON L, MAROTI G, HELMRICH M R, et al. Stochastic Improvement of Cyclic Railway Timetables [J]. Transportation Research Part B Methodological, 2008, 42(6):553-570.

[5]廖勇.公交化城際列車(chē)開(kāi)行間隔優(yōu)化[J].鐵道學(xué)報(bào),2010,32(1):8-12.

(LIAO Yong. The Headway Optimization of Intercity Trains of Mass Transit Type [J]. Journal of the China Railway Society, 2010, 32(1):8-12. in Chinese)

[6]KROON L, HUISMAN D, ABBINK E, et al. The New Dutch Timetable: the OR Revolution [J]. Interfaces, 2009, 39(1):6-17.

[7]CANCA D, ZARZO A, ALGABA E, et al. Confrontation of Different Objectives in the Determination of Train Scheduling [J]. Procedia-Social and Behavioral Sciences, 2011, 20(6):302-312.

[8]CURY J, GOMIDE F, MENDES M. A Methodology for Generation of Optimal Schedules for an Underground Railway System [J]. IEEE Transactions on Automatic Control, 1979, 25(2):217-222.

[9]ALBRECHT T. Automated Timetable Design for Demand-Oriented Service on Suburban Railways [J]. Public Transport, 2009, 1(1):5-20.

[10]NIU H, ZHOU X. Optimizing Urban Rail Timetable under Time-Dependent Demand and Oversaturated Conditions [J]. Transportation Research Part C Emerging Technologies, 2013, 36(11):212-230.

[11]BARRENA E, CANCA D, COELHO L C, et al. Exact Formulations and Algorithm for the Train Timetabling Problem with Dynamic Demand[J]. Computers & Operations Research, 2014, 44(3):66-74.

[12]HASSANNAYEBI E, SAJEDINEJAD A, MARDANI S. Urban Rail Transit Planning Using a Two-Stage Simulation-Based Optimization Approach [J]. Simulation Modeling Practice & Theory, 2014, 49:151-166.

[13]TIAN Q, ZHANG J, WANG H. Equilibrium Properties of the Morning Peak-Period Commuting in a Many-to-One Mass Transit System [J].Transportation Research Part B, 2007,41(6):616-631.

[14]程婕,彭其淵,趙軍. 城市軌道交通列車(chē)交路優(yōu)化模型[J]. 西南交通大學(xué)學(xué)報(bào), 2013, 48(6):1116-1121.

(CHENG Jie，PENG Qiyuan，ZHAO Jun. Train Routing Optimization Model for Urban Rail Transit [J]. Journal of Southwest Jiaotong University, 2013, 48(6):1116-1121. in Chinese)

[15]王媛媛,倪少權(quán).城市軌道交通大小交路模式列車(chē)開(kāi)行方案的優(yōu)化[J].鐵道學(xué)報(bào),2013, 35(7):1-8.

(WANG Yuanyuan, NI Shaoquan. Optimization of Train Schedules of Full-Length Short-Turn Operation Modes in Urban Rail Transit[J]. Journal of the China Railway Society, 2013, 35(7):1-8. in Chinese)

[16]凌俊,胡雄,何紅弟,等.城市軌道交通非高峰期列車(chē)交路方案優(yōu)化[J].鐵道科學(xué)與工程學(xué)報(bào), 2015(1):190-195.

(LING Jun, HU Xiong, HE Hongdi, et al. Optimization of the Train Routing Scheme during the Off-Peak Period in Urban Rail Transit[J]. Journal of Railway Science and Engineering, 2015(1):190-195. in Chinese)

[17]CANCA D, BARRENA E, ALGABA E, et al. Design and Analysis of Demand-Adapted Railway Timetables [J]. Journal of Advanced Transportation, 2014, 48(2):119-137.

[18]江志彬,徐瑞華,吳強(qiáng),等. 計(jì)算機(jī)編制城市軌道交通共線交路列車(chē)運(yùn)行圖[J].同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版, 2010, 38(5):692-696.

(JIANG Zhibin, XU Ruihua, WU Qiang, et al. Shared-Path Routing Timetable Computer Designing in Rail Transit System[J]. Journal of Tongji University: Natural Science, 2010, 38(5): 692-696. in Chinese)

[19]王彥棟. 大小交路套跑條件下網(wǎng)絡(luò)化城市軌道交通行車(chē)優(yōu)化模型研究[J].物流技術(shù),2011, 30(21):71-74.

(WANG Yandong. Study on Optimization Model of Urban Transit Network Organization and Coordination with Long and Short Routing [J]. Logistics Technology, 2011, 30(21):71-74. in Chinese)

[20]FU L, DESSOUKY M. Models and Algorithms for Dynamic Headway Control [J]. Computers & Industrial Engineering, 2017, 103:271-281.

[21]LIN C H, LIN P L. Improving the Non-Dominated Sorting Genetic Algorithm Using a Gene-Therapy Method for Multi-Objective Optimization [J]. Journal of Computational Science, 2014, 5(2):170-183.

[22]席裕庚,柴天佑,揮為民.遺傳算法綜述[J].控制理論與應(yīng)用,1996, 13(6):697-708.

(Xl Yugeng, CHAI Tianyou, YUN Weimin. Survey on Genetic Algorithm [J]. Control Theory and Applications, 1996, 13(6):697-708. in Chinese)