白廣爭(zhēng)， 郭 進(jìn)，石紅國(guó)，楊 揚(yáng)，張?zhí)?/p>

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031；2.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；3.成都地鐵運(yùn)營(yíng)有限公司,四川 成都 610031)

隨著城市內(nèi)軌道交通線路的不斷增加，網(wǎng)絡(luò)化運(yùn)營(yíng)模式已經(jīng)成為一種趨勢(shì)，網(wǎng)絡(luò)中線路之間的相互影響也越來(lái)越顯著。為了減少乘客在換乘站的滯留時(shí)間，需要對(duì)各線路的行車(chē)組織進(jìn)行合理規(guī)劃，加強(qiáng)線路間列車(chē)運(yùn)行的銜接協(xié)調(diào)，進(jìn)而提高整個(gè)軌道交通網(wǎng)絡(luò)客流的暢通性。因此，優(yōu)化換乘站列車(chē)的銜接關(guān)系，對(duì)提高乘客換乘效率、降低乘客出行時(shí)間及提高乘客服務(wù)水平具有重要意義。

單個(gè)換乘站的協(xié)調(diào)是根據(jù)換乘站內(nèi)客流到達(dá)特征，對(duì)經(jīng)過(guò)該站的各方向列車(chē)的到發(fā)時(shí)刻進(jìn)行協(xié)調(diào)，使其形成良好的接續(xù)關(guān)系[1-7]，從而實(shí)現(xiàn)降低換乘站乘客候車(chē)時(shí)間的目的。而在網(wǎng)絡(luò)化的運(yùn)營(yíng)環(huán)境中，由于列車(chē)在線路上各站之間的運(yùn)行時(shí)間及各車(chē)站的停站時(shí)間具有相對(duì)確定性，雖可適當(dāng)調(diào)整，但調(diào)整幅度有限，因此，列車(chē)在不同換乘站的到發(fā)時(shí)刻之間存在一定的相互制約關(guān)系。針對(duì)單個(gè)換乘站的協(xié)調(diào)優(yōu)化結(jié)果放在網(wǎng)絡(luò)中會(huì)出現(xiàn)運(yùn)行時(shí)間沖突的問(wèn)題，要求換乘站之間的協(xié)調(diào)與換乘站內(nèi)各運(yùn)行方向上的銜接協(xié)調(diào)結(jié)合起來(lái)，才能制定出行之有效的優(yōu)化方案。

在網(wǎng)絡(luò)化的運(yùn)營(yíng)條件下，既要考慮單線路的行車(chē)條件要求，將協(xié)調(diào)對(duì)單線路的行車(chē)組織影響降至最低，又要實(shí)現(xiàn)全路網(wǎng)乘客換乘等待時(shí)間最少，因此，城市軌道交通時(shí)刻表?yè)Q乘協(xié)調(diào)工作是一個(gè)多目標(biāo)多約束問(wèn)題。本文分析單個(gè)換乘站中各方向運(yùn)行列車(chē)的接續(xù)問(wèn)題，得出換乘站客流的總換乘等待時(shí)間計(jì)算方法；考慮在網(wǎng)絡(luò)化運(yùn)行條件下?lián)Q乘站間列車(chē)運(yùn)行時(shí)間的調(diào)整問(wèn)題，以網(wǎng)絡(luò)中乘客總換乘等待時(shí)間最少及換乘站間列車(chē)運(yùn)行時(shí)間調(diào)整最小為目標(biāo)，建立多目標(biāo)優(yōu)化模型；設(shè)計(jì)非支配排序進(jìn)化算法(Non-dominated Sorting Genetic Algorithm Ⅱ，NSGA-Ⅱ) 求解問(wèn)題，并通過(guò)實(shí)例進(jìn)行驗(yàn)證。

1 條件假設(shè)與符號(hào)說(shuō)明

1.1 條件假設(shè)

設(shè)所協(xié)調(diào)時(shí)段為[ta，tb]，為了降低問(wèn)題復(fù)雜性，對(duì)運(yùn)行條件作如下假設(shè)：

(1)線路上、下行列車(chē)獨(dú)立運(yùn)行，各自到達(dá)與離開(kāi)換乘站的時(shí)刻相互沒(méi)有制約關(guān)系。

(2)乘客均能乘上所遇到的第一趟換乘列車(chē)，不會(huì)因?yàn)閾頂D而錯(cuò)過(guò)，即運(yùn)能是充足的。

(3)協(xié)調(diào)時(shí)段內(nèi)，各線路列車(chē)采取均衡行車(chē)方式。

(4)同一線路的上、下行之間不產(chǎn)生換乘關(guān)系。

(5)列車(chē)的區(qū)間運(yùn)行時(shí)間與車(chē)站停站時(shí)間可做適當(dāng)調(diào)整。

1.2 符號(hào)說(shuō)明

為了方便問(wèn)題描述，對(duì)網(wǎng)絡(luò)中某一個(gè)確定換乘站的運(yùn)行參數(shù)作如下符號(hào)說(shuō)明。

Rij：線路i的j方向，j=1，2。其中j=1表示上行；j=2表示下行；i=1，2，…，n。其中n為經(jīng)過(guò)該換乘站的線路數(shù)。

nijs：[ta，tb]內(nèi)，Rij方向上共開(kāi)行的列車(chē)對(duì)數(shù)。

Aij：[ta，tb]內(nèi)Rij上各列車(chē)到達(dá)該換乘站的時(shí)刻集合。

Dij：[ta，tb]內(nèi)Rij上各列車(chē)在該換乘站的停站時(shí)間集合。

Lij：[ta，tb]內(nèi)Rij上各列車(chē)駛離該換乘站的時(shí)刻集合。

hij：[ta，tb]內(nèi)Rij上各列車(chē)的行車(chē)間隔。

M：[ta，tb]內(nèi)該換乘站所有接續(xù)關(guān)系的集合。即：M={Rij→Rpq︱i≠p；i，p∈{1，2，…，n}；j，q∈{1，2}}。

對(duì)于網(wǎng)絡(luò)化環(huán)境中，運(yùn)行參數(shù)做如下設(shè)定：

U：網(wǎng)絡(luò)中換乘站集合，存在Um、Un∈U。

S：網(wǎng)絡(luò)中換乘站總個(gè)數(shù)。

2 單個(gè)換乘站乘客換乘等待時(shí)間計(jì)算

列車(chē)在線路上采取等間隔方式運(yùn)行，則會(huì)在換乘站內(nèi)形成穩(wěn)定的“銜接周期”[1]，即當(dāng)相交的兩條線路上列車(chē)行車(chē)間隔分別為h1和h2時(shí)，則這兩條線路在換乘站內(nèi)以lcm(h1，h2)為周期形成銜接關(guān)系。文獻(xiàn)[1]分析了“銜接周期”內(nèi)乘客換乘總候車(chē)時(shí)間的計(jì)算方法，并以該值最小為優(yōu)化目標(biāo)。但是，在實(shí)際運(yùn)營(yíng)過(guò)程中，每趟列車(chē)帶來(lái)的換乘客流量各不相同，乘客在每個(gè)“銜接周期”內(nèi)的到站量分布并不一定相同，因此，在一個(gè)“銜接周期”內(nèi)乘客換乘總候車(chē)時(shí)間最少并不能代表在其他“銜接周期”內(nèi)的換乘乘客總等待時(shí)間也最少。因此，本文計(jì)算協(xié)調(diào)時(shí)段換乘站內(nèi)所有換乘乘客的總候車(chē)時(shí)間，并做為網(wǎng)絡(luò)化運(yùn)營(yíng)協(xié)調(diào)的基礎(chǔ)。

為了計(jì)算單個(gè)換乘站內(nèi)乘客的總換乘候車(chē)時(shí)間，首先應(yīng)確定與換乘站相關(guān)的列車(chē)運(yùn)行基本參數(shù)，包括到發(fā)時(shí)刻的表示及各參數(shù)受到的約束；然后計(jì)算一個(gè)換乘接續(xù)方向上所有乘客的換乘等待時(shí)間；最后，對(duì)各接續(xù)方向乘客換乘候車(chē)時(shí)間求和，即可得出換乘站中所有換乘乘客的候車(chē)時(shí)間表達(dá)式。

2.1 換乘站列車(chē)到發(fā)時(shí)刻分析

nij=0，1，2，…，nijs-1

( 1 )

式( 1 )中，nij滿足

( 2 )

( 3 )

根據(jù)Rij上列車(chē)的離站時(shí)刻集合Lij和列車(chē)停站時(shí)間集合Dij，可以確定列車(chē)的到站時(shí)刻集合Aij為

( 4 )

2.2 線路間換乘接續(xù)關(guān)系分析

( 5 )

相鄰兩趟列車(chē)離站時(shí)刻滿足

( 6 )

( 7 )

( 8 )

2.3 換乘站內(nèi)乘客總候車(chē)時(shí)間計(jì)算

以上求得一個(gè)換乘接續(xù)方向上所有換乘乘客的候車(chē)時(shí)間。而在換乘站中通常會(huì)存在多個(gè)換乘接續(xù)方向，因此，對(duì)各接續(xù)方向乘客候車(chē)時(shí)間求和可得站內(nèi)乘客換乘總候車(chē)時(shí)間為

( 9 )

3 網(wǎng)絡(luò)化運(yùn)營(yíng)條件下列車(chē)運(yùn)行協(xié)調(diào)優(yōu)化

網(wǎng)絡(luò)化運(yùn)營(yíng)條件下，換乘站的協(xié)調(diào)比單個(gè)換乘站的協(xié)調(diào)優(yōu)化問(wèn)題增加了換乘站之間列車(chē)運(yùn)行時(shí)間及停站時(shí)間的影響，根據(jù)第2節(jié)研究所得出的單個(gè)換乘站列車(chē)離站時(shí)刻協(xié)調(diào)結(jié)果，放在網(wǎng)絡(luò)中往往會(huì)造成換乘站之間運(yùn)行時(shí)間的沖突，列車(chē)在線路上運(yùn)行，無(wú)法同時(shí)滿足多個(gè)換乘站各自計(jì)算的離站時(shí)刻要求。為了協(xié)調(diào)換乘站之間的離站時(shí)刻，需要對(duì)線路上車(chē)站間的運(yùn)行時(shí)間及各站停站時(shí)間做一定調(diào)整。由于平峰時(shí)段網(wǎng)絡(luò)中各線路行車(chē)間隔基本較大，因此適當(dāng)調(diào)整列車(chē)站間運(yùn)行時(shí)間和停站時(shí)間的方案是可行的。調(diào)整的依據(jù)是相鄰換乘站Um、Un之間的運(yùn)行時(shí)間TUm→Un和TUn→Um，使其滿足

(10)

或者

(11)

圖1 換乘站位置關(guān)系

TUm→Un由Um→Un的車(chē)站停車(chē)時(shí)間和區(qū)間運(yùn)行時(shí)間組成，即

(12)

TUn→Um同理可得

(13)

(14)

(15)

為了避免調(diào)整對(duì)原有運(yùn)行時(shí)間的影響過(guò)大，要求列車(chē)運(yùn)行參數(shù)調(diào)整的幅度越小越好。

根據(jù)以上分析可以得出，網(wǎng)絡(luò)條件下運(yùn)行協(xié)調(diào)的第一目標(biāo)是使得整個(gè)網(wǎng)絡(luò)中在協(xié)調(diào)時(shí)段內(nèi)乘客總換乘等待時(shí)間最小，如式(16)所示，即

Obj 1:

(16)

協(xié)調(diào)的第二目標(biāo)是換乘站站間運(yùn)行時(shí)間及停站時(shí)間調(diào)整最少，以調(diào)整后與調(diào)整前的運(yùn)行時(shí)間方差來(lái)表示，則運(yùn)行調(diào)整應(yīng)滿足

Obj 2:

(17)

式中：TUm→Un(0)表示調(diào)整前相鄰換乘站之間列車(chē)的運(yùn)行時(shí)間；TUm→Un表示調(diào)整后相鄰換乘站之間列車(chē)的運(yùn)行時(shí)間；lx表示共需要調(diào)整的換乘站間運(yùn)行時(shí)間的數(shù)量。

根據(jù)以上分析，得出網(wǎng)絡(luò)條件下線路間銜接性協(xié)調(diào)優(yōu)化模型。其中式(16)、式(17)為模型目標(biāo)，式( 1 )～式(15)為模型約束條件及參數(shù)間關(guān)系描述。在求解目標(biāo)(16)的過(guò)程中參考第2節(jié)單個(gè)換乘站乘客等待時(shí)間的求解過(guò)程。

4 算法設(shè)計(jì)

網(wǎng)絡(luò)化換乘站協(xié)調(diào)優(yōu)化模型包含兩個(gè)目標(biāo)，屬于多目標(biāo)優(yōu)化問(wèn)題(MOP)。在求解MOP時(shí)，通常采用兩類(lèi)方法：其一為首先按照某種策略確定多種目標(biāo)之間的權(quán)重，然后將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題的傳統(tǒng)求解方法，如加權(quán)求和法、理想點(diǎn)法等，最終求解單目標(biāo)的優(yōu)化解；其二為采用一些近代智能搜索算法，如NSGA、NSGA-Ⅱ、PAES、PESA、SPEA等，通過(guò)搜索多個(gè)目標(biāo)的非劣(又稱Pareto)解，找出可接受的“不壞”解[8]供決策者參考，實(shí)現(xiàn)多目標(biāo)優(yōu)化。多目標(biāo)優(yōu)化問(wèn)題一般不存在單個(gè)最優(yōu)解，而是一個(gè)Pareto解集。在眾多的多目標(biāo)進(jìn)化算法中，NSGA-Ⅱ算法是目前處理2～3個(gè)優(yōu)化目標(biāo)中最優(yōu)秀的算法之一，本文設(shè)計(jì)NSGA-Ⅱ算法求解。

采用實(shí)數(shù)編碼方式，編碼對(duì)象為各個(gè)換乘站內(nèi)的各方向上列車(chē)在協(xié)調(diào)時(shí)段內(nèi)的初始離站時(shí)刻，進(jìn)化過(guò)程中的選擇操作設(shè)置為二元錦標(biāo)賽模式，賽制規(guī)模取2。為了簡(jiǎn)化設(shè)計(jì)，本文采取算術(shù)交叉策略，設(shè)計(jì)交叉策略為[9]

(18)

分別采取均勻變異策略和非均勻變異策略為[10]

(19)

(20)

Δ(g，y)=y×γ×(1-g/G)b

式中：b為形參，其值可取2～5，本算法中取2；γ為[0，1]的隨機(jī)數(shù)，在計(jì)算過(guò)程中隨機(jī)產(chǎn)生；G為終止代數(shù)，在本文算例中取200。

5 案例分析

5.1 初始數(shù)據(jù)設(shè)置

某城市軌道交通網(wǎng)絡(luò)如圖2所示，由3條線路構(gòu)成，即R1，R2，R3。3條線路存在5個(gè)換乘車(chē)站a，b，c，d，e，其中R1與R2相交于換乘車(chē)站c，R1與R3相交于換乘車(chē)站b，d，R2與R3相交于換乘車(chē)站a，e。規(guī)定各線路運(yùn)行時(shí)間如網(wǎng)絡(luò)圖中所示，例如線路R1中，由換乘站b出發(fā)到離開(kāi)換乘站c的運(yùn)行時(shí)間tbc=9.5 min，由換乘站c出發(fā)到離開(kāi)換乘站d的運(yùn)行時(shí)間tcd=7.3 min。為了計(jì)算方便，設(shè)定調(diào)整前相同兩換乘站之間列車(chē)上行運(yùn)行時(shí)間與下行運(yùn)行時(shí)間相同。

圖2 城市軌道交通網(wǎng)絡(luò)

以10:00～12:00為例，設(shè)置換乘客流量見(jiàn)表1，單元格中的數(shù)據(jù)表示相交于對(duì)應(yīng)換乘站的兩線路所在行方向的一列車(chē)所帶來(lái)的要換乘到所在列方向的客流量。

各線路上列車(chē)采取均衡行車(chē)方式， 且同一線路的上、下行行車(chē)間隔相同，R1、R2、R3行車(chē)間隔分別設(shè)置為h1=360 s，h2=330 s，h3=300 s。各車(chē)站各方向乘客換乘走行時(shí)間均設(shè)置為100 s。各換乘站對(duì)應(yīng)線路上列車(chē)的停車(chē)時(shí)間設(shè)置見(jiàn)表2。

表1 每列車(chē)運(yùn)送的換乘客流量數(shù)據(jù) 人

表2 各換乘站停站時(shí)間 s

根據(jù)圖2線路網(wǎng)絡(luò)所示，各線路上、下行方向在換乘站的離站時(shí)刻共有20個(gè)，因此，決策變量個(gè)數(shù)為20，采用實(shí)數(shù)編碼方式的染色體設(shè)置見(jiàn)表3。

表3 實(shí)數(shù)編碼染色體設(shè)置

每一代的種群規(guī)模設(shè)置為200，交叉概率取0.9，變異概率取0.1[11]。分別采取均勻變異策略和非均勻變異策略以驗(yàn)證計(jì)算結(jié)果。

5.2 計(jì)算結(jié)果及分析

通過(guò)均勻變異和非均勻變異兩種方法計(jì)算，求得Pareto解集近似相同，圖3顯示了非均勻變異的計(jì)算結(jié)果。

圖3 非均勻變異運(yùn)算結(jié)果

圖3顯示的計(jì)算結(jié)果均為優(yōu)化解，根據(jù)圖3所示， 模型的兩個(gè)目標(biāo)存在“此消彼長(zhǎng)”的博弈。若增大站間

運(yùn)行時(shí)間的調(diào)整幅度，即目標(biāo)f2增大，則乘客的換乘等待時(shí)間f1減??；相反，若目標(biāo)f2減小，則目標(biāo)f1增大。表4列出了兩組調(diào)整方案，分別對(duì)應(yīng)以上兩種情況。

具體選擇哪一組結(jié)果做調(diào)整方案，則由決策者根據(jù)以下情況判斷：若期望調(diào)整對(duì)單線路的原有時(shí)刻表影響較小，即換乘站間列車(chē)運(yùn)行時(shí)間調(diào)整幅度較小，則選擇圖3中偏右下方的優(yōu)化解，例如表4中第1組優(yōu)化解；而若更看重網(wǎng)絡(luò)乘客的整體換乘時(shí)間優(yōu)化，則選擇圖3中偏左上方的優(yōu)化解，例如表4中第2組優(yōu)化解。

為了檢驗(yàn)優(yōu)化效果，將模型的目標(biāo)1網(wǎng)絡(luò)乘客換乘總等待時(shí)間修改為取倒數(shù)后再求最小值，目標(biāo)2不變，仍采用本文算法求解，對(duì)計(jì)算結(jié)果的目標(biāo)1再取倒數(shù)變換后，由此得出一些站間運(yùn)行時(shí)間調(diào)整幅度近似情況下的較劣運(yùn)行時(shí)刻協(xié)調(diào)結(jié)果。表5列出了其中的一組較劣解，該組解與表4中的第1組解對(duì)比，全網(wǎng)換乘等待時(shí)間延長(zhǎng)了約6.4%，與表4中的第2組解對(duì)比，換乘時(shí)間延長(zhǎng)了約11.3%。

表4 兩組優(yōu)化解

表5 一組較劣解

6 結(jié)束語(yǔ)

本文分析了網(wǎng)絡(luò)化運(yùn)營(yíng)條件下，線路間列車(chē)運(yùn)行協(xié)調(diào)優(yōu)化問(wèn)題。針對(duì)平峰時(shí)段，以網(wǎng)絡(luò)中乘客總換乘候車(chē)時(shí)間最少及路網(wǎng)列車(chē)運(yùn)行參數(shù)調(diào)整幅度最小為目標(biāo)建立多目標(biāo)優(yōu)化模型。設(shè)計(jì)了NSGA-Ⅱ算法，并對(duì)案例求解，結(jié)果驗(yàn)證了本模型能夠有效減少乘客的換乘等待時(shí)間。研究過(guò)程及結(jié)論可為網(wǎng)絡(luò)化的運(yùn)行協(xié)調(diào)工作提供參考。

參考文獻(xiàn)：

[1]張銘,杜世敏.基于遞階偏好的軌道交通網(wǎng)絡(luò)化運(yùn)營(yíng)換乘協(xié)調(diào)優(yōu)化[J].鐵道學(xué)報(bào),2009,31(6):9-14.

ZHANG Ming,DU Shimin.Transfer Coordination Optimization for Network Operation of Urban Rail Transit Based on Hierarchical Preference[J].Journal of the China Railway Society,2009,31(6):9-14.

[2]周艷芳,周磊山,樂(lè)逸祥.城市軌道網(wǎng)絡(luò)換乘站列車(chē)銜接同步協(xié)調(diào)優(yōu)化研究[J].鐵道學(xué)報(bào),2011,33(3):9-16.

ZHOU Yanfang,ZHOU Leishan,YUE Yixiang.Synchronized and Coordinated Train Connection Optimization for Transfer Stations of Urban Rail Networks[J].Journal of the China Railway Society,2011,33(3):9-16.

[3]徐瑞華,張銘,江志彬.基于線網(wǎng)運(yùn)營(yíng)協(xié)調(diào)的城市軌道交通首末班列車(chē)發(fā)車(chē)時(shí)間域研究[J].鐵道學(xué)報(bào),2008,30(2):7-11.

XU Ruihua,ZHANG Ming,JIANG Zhibin.Study on Departure Time Domain of the First and Last Trains of Urban Mass Transit Network Based on Operation Coordination[J].Journal of the China Railway Society,2008,30(2):7-11.

[4] RACHEL C W.Optimizing Timetable Synchronization for Rail Mass Transit[J].Transportation Science,2008,42(1):57-69.

[5] CUUNG M K,CHANG C S.Timetable Synchronization of Mass Rapid Transit System Using Multiobjective Evolutionary Approach[J].IEEE Transactions on Systems,Man,and Cybernetics,2008,38(5):636-648.

[6]孫鵬,趙佳虹,丁宏飛.基于換乘協(xié)調(diào)的城市軌道交通列車(chē)開(kāi)行方案優(yōu)化[J].鐵道運(yùn)輸與經(jīng)濟(jì),2011,33(12):67-70.

SUN Peng,ZHAO Jiahong,DING Hongfei.The Optimization of Urban Rail Transit Operation Scheme based on Coordinated Transfer[J].Railway Transport and Economy,2011,33(12):67-70.

[7]白廣爭(zhēng),郭進(jìn),石紅國(guó),等.基于離站時(shí)刻協(xié)調(diào)的地鐵換乘站列車(chē)銜接優(yōu)化研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2013,13(5):134-139,201.

BAI Guangzheng,GUO Jin,SHI Hongguo,et al.Optimization of Convergence Based on the Coordination of Train Departure Time in Transfer Station[J].Journal of Transportation Systems Engineering and Information Technology,2013,13(5):134-139,201.

[8]雷德明,嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2009.

[9]陳小平,于盛林.實(shí)數(shù)遺傳算法的交叉策略的改進(jìn)[J].電子學(xué)報(bào),2003(1):71-74.

CHEN Xiaoping,YU Shenglin.Improvement on Crossover Strategy of Real-valued Genetic Algorithm[J].Acta Electronica Sinica,2003(1):71-74.

[10]朱燦.實(shí)數(shù)編碼遺傳算法機(jī)理分析及算法改進(jìn)研究[D].長(zhǎng)沙：中南大學(xué),2009.

[11]徐宗本.計(jì)算智能(第一冊(cè))——模擬進(jìn)化算法[M].北京:高等教育出版社,2005.