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

李皓宇，陳榮武，林 藍

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

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

李皓宇，陳榮武，林 藍

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

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

城市軌道交通；運行圖；遺傳算法

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

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

1 城市軌道交通運行圖概述

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

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

圖1 城市軌道交通運行圖

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

2 運行圖優(yōu)化問題

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

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

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

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

3 模型及算法

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

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

3.1 算法概述

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

圖2 遺傳算法流程圖

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

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

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

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

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

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

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

3.2 建模與仿真

3.2.1 模型的建立

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

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

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

（2）確定約束條件

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

a.用戶約束：列車在起點站的發(fā)車時間約束和在終點站的到達時間約束。

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

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

3.2.2 仿真

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

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

表2 站間距離及運行時分

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

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

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

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

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

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

4 結(jié)束語

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

圖3 運行圖顯示界面

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

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

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

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

[5]陳國良.遺傳算法及其應(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

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