李皓宇，陳榮武，林 藍(lán)

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 成都 610031）

遺傳算法在城軌運(yùn)行圖優(yōu)化中的應(yīng)用

李皓宇，陳榮武，林 藍(lán)

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 成都 610031）

隨著城市軌道交通的迅猛發(fā)展，如何在現(xiàn)有基礎(chǔ)設(shè)施的情況下最大限度地提高運(yùn)輸效率、提升運(yùn)輸能力是城市軌道交通運(yùn)營(yíng)中一個(gè)迫切需要解決的問(wèn)題。本文旨在通過(guò)建立運(yùn)行圖優(yōu)化模型，利用遺傳算法對(duì)其進(jìn)行優(yōu)化的方式來(lái)優(yōu)化運(yùn)行圖運(yùn)營(yíng)組織過(guò)程，從而達(dá)到提高運(yùn)輸效率、提升運(yùn)輸能力的目的。

城市軌道交通；運(yùn)行圖；遺傳算法

我國(guó)城市軌道交通在近幾年內(nèi)飛速發(fā)展，一線城市如北京、上海等，已形成較為完善的城市軌道交通運(yùn)輸網(wǎng)，涵蓋城市范圍廣，成都、武漢、重慶等城市已建成地鐵線路或正在規(guī)劃建設(shè)中。如何提高城市軌道交通運(yùn)輸效率成為城軌運(yùn)營(yíng)組織中一個(gè)有待解決的關(guān)鍵課題。

列車運(yùn)行圖是城市軌道交通運(yùn)輸組織的重要組成部分，城市軌道交通運(yùn)行圖算法優(yōu)化研究與實(shí)現(xiàn)更是提高運(yùn)行圖質(zhì)量的基礎(chǔ)。因此，研究一個(gè)高效、準(zhǔn)確的運(yùn)行圖優(yōu)化算法對(duì)于城市軌道交通運(yùn)輸系統(tǒng)顯得尤為重要。本文采用遺傳算法，對(duì)城市軌道交通運(yùn)行圖進(jìn)行建模，確立優(yōu)化目標(biāo)，對(duì)運(yùn)行圖中各項(xiàng)時(shí)間數(shù)據(jù)進(jìn)行優(yōu)化，從而達(dá)到提高城軌運(yùn)輸能力、運(yùn)輸效率的目的。

1 城市軌道交通運(yùn)行圖概述

列車運(yùn)行圖作為鐵路列車運(yùn)營(yíng)的關(guān)鍵技術(shù)文件，規(guī)定了列車在鐵路區(qū)間的運(yùn)行時(shí)分，列車在各個(gè)車站的到發(fā)時(shí)刻以及在車站的停站時(shí)間等，是鐵路組織列車運(yùn)行的基礎(chǔ)。城市軌道交通運(yùn)行圖通常以橫坐標(biāo)表示時(shí)間，縱坐標(biāo)表示距離的方式來(lái)顯示。

根據(jù)不同使用需求，列車運(yùn)行圖按時(shí)間劃分有3種：二分格形式、十分格形式和小時(shí)格形式。由于城市軌道交通時(shí)隔短、距離短等因素，實(shí)際應(yīng)用中常使用二分格運(yùn)行圖。二分格運(yùn)行圖如圖1所示，它的橫軸是以間隔2 min的細(xì)豎線加以劃分，10 min線和小時(shí)線均用較粗的豎線表示[1]。

圖1 城市軌道交通運(yùn)行圖

在城市軌道交通中，列車運(yùn)行圖由一些必要的基本要素組成，包括：列車在相鄰兩車站之間的運(yùn)行時(shí)分；列車在每個(gè)車站的停站時(shí)間（由列車在每個(gè)車站的到發(fā)時(shí)刻確定）；追蹤列車間隔時(shí)間等。對(duì)列車運(yùn)行圖進(jìn)行優(yōu)化的過(guò)程，也就是對(duì)這些要素進(jìn)行優(yōu)化的具體過(guò)程。

2 運(yùn)行圖優(yōu)化問(wèn)題

如前文所述，列車運(yùn)行圖主要影響因素有兩點(diǎn)：列車在站間的運(yùn)行時(shí)分以及列車在車站的停站時(shí)間。那么對(duì)運(yùn)行圖的優(yōu)化問(wèn)題就可以簡(jiǎn)化為對(duì)這兩項(xiàng)參數(shù)的優(yōu)化問(wèn)題了，同時(shí)還需要考慮系統(tǒng)列車追蹤間隔時(shí)間的限制條件[2]。

列車區(qū)間運(yùn)行時(shí)分取決于兩站間的線路距離和列車運(yùn)行速度。當(dāng)列車在區(qū)間以最大的允許速度移動(dòng)時(shí)，列車在站間運(yùn)行時(shí)分最小。然而列車運(yùn)營(yíng)要考慮效率和節(jié)能要求，并且要給乘客營(yíng)造一個(gè)舒服的乘車環(huán)境，就需要限制列車站間運(yùn)行的最大時(shí)間，在這個(gè)最大和最小運(yùn)行時(shí)分之間，就是我們能對(duì)列車的運(yùn)行時(shí)分進(jìn)行變動(dòng)的范圍。

列車最小停站時(shí)分是通過(guò)列車到站后，司機(jī)開(kāi)關(guān)門(mén)的操作時(shí)間及乘客上下車時(shí)間兩方面來(lái)決定的。車站不一樣，客流多少也不一樣，所以停站最小時(shí)間值也會(huì)由于在不同車站而略有不同。同樣，列車在站內(nèi)的停車時(shí)間不能無(wú)限地拉長(zhǎng)（考慮到行車追蹤間隔等因素），所以停站時(shí)分最大值也必須規(guī)定好。

本文中，運(yùn)行圖優(yōu)化問(wèn)題歸結(jié)為一個(gè)最終目標(biāo)：在適當(dāng)?shù)姆秶鷥?nèi)，最小化總旅行時(shí)間。由前文描述可知，運(yùn)行圖有兩個(gè)主要的可優(yōu)化參數(shù)：區(qū)間運(yùn)行時(shí)分和車站停站時(shí)分。我們可以對(duì)這兩個(gè)目標(biāo)進(jìn)行適當(dāng)優(yōu)化，達(dá)到最小化總旅行時(shí)間的目的。

3 模型及算法

在建立列車運(yùn)行優(yōu)化模型的過(guò)程中，主要分為兩個(gè)步驟：

（1）確定優(yōu)化目標(biāo)；（2）根據(jù)運(yùn)行圖的各種約束條件，利用遺傳算法對(duì)優(yōu)化目標(biāo)進(jìn)行優(yōu)化。

3.1 算法概述

本文采用遺傳算法對(duì)優(yōu)化模型進(jìn)行仿真驗(yàn)證，遺傳算法的靈感來(lái)源于人類自然進(jìn)化的過(guò)程。人的進(jìn)化過(guò)程通過(guò)染色體的選擇、交叉以及變異過(guò)程實(shí)現(xiàn)，染色體的選擇、變異和重組過(guò)程都是無(wú)記憶的。將這些概念用數(shù)學(xué)方法進(jìn)行表述就形成了遺傳算法的基本機(jī)理[3]。其基本原理如圖2所示。

圖2 遺傳算法流程圖

（1）編碼：把待解決問(wèn)題的數(shù)據(jù)信息用遺傳算法的方式表示出來(lái)，它是運(yùn)用遺傳算法求解問(wèn)題的第1步。

（2）選擇：在群體中選擇適應(yīng)度高的個(gè)體產(chǎn)生新的個(gè)體的過(guò)程。遺傳算法采用選擇算子來(lái)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰的操作，選擇適應(yīng)度高的個(gè)體產(chǎn)生新個(gè)體直到求得最優(yōu)解。

（3）交叉：又稱重組，它模仿了染色體基因互換的過(guò)程。按一定的概率從個(gè)體中選擇兩個(gè)個(gè)體，對(duì)這兩個(gè)個(gè)體的編碼染色體交叉位置進(jìn)行確定，確定交叉位置后進(jìn)行交叉。交叉在遺傳算法過(guò)程中起關(guān)鍵作用，在編碼設(shè)計(jì)時(shí)要一起考慮。

（4）變異：就是以較小的概率對(duì)個(gè)體染色體編碼上的某些位置進(jìn)行突變操作，如二進(jìn)制編碼中“0”變成“1”和“1”變成“0”，進(jìn)而產(chǎn)生新個(gè)體編碼，它能夠避免由于選擇和交叉運(yùn)算而造成的某些信息丟失，保證遺傳算法的有效性。

（5）適應(yīng)度函數(shù)：適應(yīng)度函數(shù)的設(shè)計(jì)種類可以有很多，一般需要滿足單值、連續(xù)、非負(fù)、一致性好并且計(jì)算量小等要求。

（6）約束條件處理：對(duì)約束條件進(jìn)行處理是遺傳算法中必須進(jìn)行的，需要具體問(wèn)題具體分析。針對(duì)具體問(wèn)題選擇合適的約束條件處理方法，是求解問(wèn)題的重要一步。

（7）控制參數(shù)選擇：遺傳算法中控制參數(shù)選擇至關(guān)重要，這些控制參數(shù)包含群體規(guī)模N，編碼長(zhǎng)度L，交叉概率，變異概率等。一般建議取值范圍是0.2～0.99，的取值范圍是0.001～0.1。

3.2 建模與仿真

3.2.1 模型的建立

（1）確定目標(biāo)函數(shù)

目標(biāo)函數(shù)是列車運(yùn)行圖優(yōu)化模型建立的第一步，它和城市列車運(yùn)行圖優(yōu)化的目標(biāo)直接相關(guān)，為了確定模型的目標(biāo)函數(shù)，可以通過(guò)分析待優(yōu)化目標(biāo)的方式來(lái)進(jìn)行。通常，在城市軌道交通運(yùn)行圖優(yōu)化問(wèn)題中，我們可以簡(jiǎn)化地以最小化全旅行時(shí)間作為優(yōu)化目標(biāo)，計(jì)劃的總旅行時(shí)間由第i列車在每一站的停站時(shí)間和兩兩站間的運(yùn)行時(shí)分之和組成[4]。

因此對(duì)第i列車的優(yōu)化目標(biāo)函數(shù)F(i)為：

（2）確定約束條件

一般來(lái)說(shuō)，在城市軌道交通的運(yùn)行圖優(yōu)化問(wèn)題中，約束條件有以下幾種：用戶約束、運(yùn)營(yíng)約束、鐵路基礎(chǔ)設(shè)備約束等。本文里，只考慮用戶約束、運(yùn)營(yíng)約束和列車追蹤間隔時(shí)間約束。

a.用戶約束：列車在起點(diǎn)站的發(fā)車時(shí)間約束和在終點(diǎn)站的到達(dá)時(shí)間約束。

b.運(yùn)營(yíng)約束：列車區(qū)間的運(yùn)行時(shí)分約束和列車在車站的停站時(shí)間約束。

c.列車追蹤間隔時(shí)間的約束：為保證兩列車間的安全運(yùn)行，其追蹤間隔時(shí)間要在安全運(yùn)行允許的范圍內(nèi)變化[5]。

3.2.2 仿真

本文選取北京1號(hào)線八通段進(jìn)行仿真驗(yàn)證。根據(jù)北京地鐵官方網(wǎng)站2014年所公布的信息，車站數(shù)據(jù)與列車站間運(yùn)行時(shí)間數(shù)據(jù)如表1、表2和表3所示。

表1 車站數(shù)據(jù)

表2 站間距離及運(yùn)行時(shí)分

表3 時(shí)刻表數(shù)據(jù)

其中，表2中的運(yùn)行時(shí)分由運(yùn)行等級(jí)確定，運(yùn)行等級(jí)分為1、2、3、4級(jí)，分別表示最高時(shí)速（80 km/h）的100%、90%、75%和50%。

利用遺傳算法對(duì)以上基礎(chǔ)數(shù)據(jù)進(jìn)行二進(jìn)制編碼，計(jì)算目標(biāo)函數(shù)、適應(yīng)度函數(shù)，通過(guò)選擇交叉變異對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，輸出優(yōu)化后的時(shí)間數(shù)據(jù)。并通過(guò)運(yùn)行圖軟件界面顯示出優(yōu)化后的線路數(shù)據(jù)，結(jié)果如表4所示。

表4 優(yōu)化后的運(yùn)行數(shù)據(jù)

對(duì)比表3和表4的數(shù)據(jù)，總旅行時(shí)間從30 min減小到29 min，達(dá)到了對(duì)總旅行時(shí)間的優(yōu)化目的。具體看來(lái)，路線中列車在四惠東、高碑店、雙橋等站的到站時(shí)間發(fā)生了改變，在高碑店、通州北苑等站的停站時(shí)間發(fā)生了改變。利用運(yùn)行圖顯示界面對(duì)優(yōu)化后的數(shù)據(jù)進(jìn)行顯示，如圖3所示。

綜上，優(yōu)化前后列車的總旅行時(shí)間減少了1 min，達(dá)到了優(yōu)化總旅行時(shí)間的目的，驗(yàn)證了算法的有效性。

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

城軌運(yùn)行圖優(yōu)化問(wèn)題是一個(gè)多約束多目標(biāo)的優(yōu)化問(wèn)題。本文中，為了簡(jiǎn)化優(yōu)化模型，將目標(biāo)設(shè)為最小化全旅行時(shí)間，以到發(fā)時(shí)間為變量，采用遺傳算法對(duì)問(wèn)題進(jìn)行求解。在實(shí)驗(yàn)室平臺(tái)下，通過(guò)運(yùn)行圖顯示界面對(duì)優(yōu)化結(jié)果進(jìn)行了驗(yàn)證，結(jié)果表明，該算法有效，能夠達(dá)到優(yōu)化運(yùn)行圖的目的。

圖3 運(yùn)行圖顯示界面

[1]胡思繼. 鐵路行車組織[M]. 北京：中國(guó)鐵道出版社, 2009：174-178.

[2]陳榮武, 諸昌鈐, 劉 莉. CBTC 系統(tǒng)列車追蹤間隔計(jì)算及優(yōu)化[J]. 西南交通大學(xué)學(xué)報(bào), 2011, 46（4）：579-582.

[3]張文修,梁 怡. 遺傳算法的數(shù)學(xué)基礎(chǔ)[M]. 西安：西安交通大學(xué)出版社, 1999.

[4]章優(yōu)仕, 金煒東. 基于遺傳算法的單線列車運(yùn)行調(diào)整體系[J].西南交通大學(xué)學(xué)報(bào), 2005， 40（2）：147-152.

[5]陳國(guó)良.遺傳算法及其應(yīng)用[M].北京：北京郵電出版社，1996.

責(zé)任編輯 王 浩

Optimization of Urban Transit diagram based on Genetic Algorithm

LI Haoyu, CHEN Rongwu, LIN Lan
( School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China )

With the rapid development of Urban Transit, how to improve the transportation eff i ciency and capacity with existing infrastructures has become a urgent problem to be solved. We established a running optimization model by using Genetic Algorithm in order to improve the transportation eff i ciency and capacity of Urban Transit.

Urban Transit; diagram; Genetic Algorithm

U231.92∶TP39

A

1005-8451（2015）12-0059-04

2015-03-11

李皓宇，在讀碩士研究生； 陳榮武，高級(jí)工程師。