遺傳算法在城軌運行圖優化中的應用

李皓宇，陳榮武，林 藍

（西南交通大學 信息科學與技術學院， 成都 610031）

遺傳算法在城軌運行圖優化中的應用

李皓宇，陳榮武，林 藍

（西南交通大學 信息科學與技術學院， 成都 610031）

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

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

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

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

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

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

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

圖1 城市軌道交通運行圖

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

2 運行圖優化問題

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

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

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

本文中，運行圖優化問題歸結為一個最終目標：在適當的范圍內，最小化總旅行時間。由前文描述可知，運行圖有兩個主要的可優化參數：區間運行時分和車站停站時分。我們可以對這兩個目標進行適當優化，達到最小化總旅行時間的目的。

3 模型及算法

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

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

3.1 算法概述

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

圖2 遺傳算法流程圖

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

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

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

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

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

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

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

3.2 建模與仿真

3.2.1 模型的建立

（1）確定目標函數

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

因此對第i列車的優化目標函數F(i)為：

（2）確定約束條件

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

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

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

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

3.2.2 仿真

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

表1 車站數據

表2 站間距離及運行時分

表3 時刻表數據

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

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

表4 優化后的運行數據

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

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

4 結束語

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

圖3 運行圖顯示界面

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

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

[3]張文修,梁 怡. 遺傳算法的數學基礎[M]. 西安：西安交通大學出版社, 1999.

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

[5]陳國良.遺傳算法及其應用[M].北京：北京郵電出版社，1996.

責任編輯 王 浩

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

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