白宏圖，劉華

(西安鐵路職業(yè)技術(shù)學(xué)院，陜西 西安 710014)

一種基于遺傳算法的軌道交通乘車路徑求解方法

白宏圖，劉華

(西安鐵路職業(yè)技術(shù)學(xué)院，陜西 西安 710014)

針對城市軌道交通最佳乘車路徑問題，改進了一種城市軌道交通網(wǎng)絡(luò)建模方法，提出了一種基于遺傳算法的乘車路徑求解方法，方法還可實現(xiàn)對多條乘車路徑的優(yōu)化排序。實例計算表明方法簡單實用，合理可行。

城市軌道交通；遺傳算法；路徑優(yōu)化；乘車；交通網(wǎng)絡(luò)；模型

0 引 言

隨著我國經(jīng)濟和城市建設(shè)的迅速發(fā)展，越來越多的城市開始興建大量的軌道交通，人們已逐步適應(yīng)這種快速便捷的出行方式。由于城市結(jié)構(gòu)的復(fù)雜性和人們出行的隨機性，從出發(fā)地到目的地可能會有多種選擇路徑，也經(jīng)常會面臨不同線路之間的換乘，如何快速尋找一條快捷便利的乘車路徑，不僅是每個乘客關(guān)心的問題，也是不同運營商在車資分配中以及軌道交通的設(shè)計時都會面對的問題[1]。

對于城市軌道交通最佳乘車路徑問題，由于站點線路的離散特征，一般很難寫出問題的解析表達，故傳統(tǒng)的優(yōu)化計算方法很難得以應(yīng)用，而作為現(xiàn)在優(yōu)化算法之一的遺傳算法對各種復(fù)雜系統(tǒng)具有優(yōu)良的自適應(yīng)和優(yōu)化能力，可將其應(yīng)用與城市軌道交通最佳乘車路徑的優(yōu)化問題,本文在該領(lǐng)域運用了遺傳算法，獲得了良好的應(yīng)用效果[2]。

1 問題描述

城市軌道交通最佳乘車路經(jīng)可描述為：已知乘客的“起始站點”和“目標(biāo)站點”，求解從“起始站點”到“目標(biāo)站點”的最佳路徑，本文進一步假設(shè)最佳路徑即為通過的站點最少的路徑，忽略不同站點間行車時間的差異和站點換乘所耗費的時間。

必須明確的是，起始站點和目標(biāo)站點之間是可到達的，實際中城市軌道交通網(wǎng)內(nèi)一般不會存在一條和其他軌道均不相連通的軌道，若存在，該軌道可另行單獨處理，因此，實際要面對的是若干相交的軌道構(gòu)成的復(fù)雜軌道網(wǎng)絡(luò)。

實際的城市軌道交通網(wǎng)絡(luò)較為復(fù)雜，研究是需要簡化處理，城市軌道交通站點可分為兩類：(1)各條軌道相交的“換乘站點”；(2)不是“換乘站點”的“其他站點”。實際乘車過程中，只有遇到“換乘站點”，才會遇到選擇路徑的問題；若乘客位于“其他站點”，一般只會沿著來路繼續(xù)前進，沿原路返回顯然是不符合邏輯嘗試的，也是任何優(yōu)化過程肯定會淘汰的選擇，因此對于“其他站點”不存在路徑選擇的問題。若起始站點和目標(biāo)站點不是“換乘站點”，則可轉(zhuǎn)化為線路上下游“換乘站點”來處理。本文的處理方法和文獻[3]有所差異，更加簡化。

圖1 上海市軌道交通 網(wǎng)絡(luò)簡化模型

本文同樣以文獻[3]提供的上海市軌道交通線路為案例對象進行分析，根據(jù)本文上述簡化，上海市軌道交通線路可簡化為圖1所示模型。按照本文上述假設(shè)，文獻[3]中處理站點1到站點6的問題，在本文中即被轉(zhuǎn)化為求解站點2到站點7的問題，兩者是完全等效的，但本文的計算量會明顯降低。

針對本文問題，建立結(jié)構(gòu)體數(shù)組A[M],其中M為總“換乘站點”數(shù)，A[i]為第i個“換乘站點”對應(yīng)的結(jié)構(gòu)體。結(jié)構(gòu)體定義為{int K;int I[K];int J[K]}，其中K為與每個“換乘站點”直接相鄰的“換乘站點”的數(shù)目，int I[K]依次標(biāo)記了每個相鄰“換乘站點”的編號，而int J[K]則依次表示兩個相鄰“換乘站點”之間所經(jīng)過的路段數(shù)，即所謂的權(quán)值，而非文獻[3]中的站點數(shù)，這樣更能反映路徑的距離遠近，所以圖1和文獻[3]中站點間的數(shù)字有所差異[3]。

2 方法描述

2.1 遺傳算法介紹

遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的高度并行、隨機、自適應(yīng)搜索算法，它主要用在處理最優(yōu)化問題和機器學(xué)習(xí)。隱含并行性和對全局信息的有效利用能力是遺傳算法的兩個顯著特點，使遺傳算法只需檢測少量的結(jié)構(gòu)就能反映搜索空間的大量區(qū)域，并具有魯棒性。與傳統(tǒng)的優(yōu)化算法相比，遺傳算法主要有以下幾個不同之處：(1)遺傳算法不是直接作用在參變量集上，而是利用參變量集的某種編碼；(2)遺傳算法不是從單個點，而是從一個點的群體開始搜索；(3)遺傳算法利用適應(yīng)值信息，無須導(dǎo)數(shù)或其他輔助信息；(4)遺傳算法利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。因此遺傳算法對于非解析離散問題具有較好的實用性[4]。

2.2 遺傳算法的優(yōu)化設(shè)計流程

圖2所示為標(biāo)準(zhǔn)遺傳算法程序框圖，本文遺傳算法就是基于此流程開展設(shè)計[5-6]。

圖2 標(biāo)準(zhǔn)遺傳算法框圖

(1)染色體編碼

染色體為規(guī)模等于總“換乘站點”數(shù)目M的一維整數(shù)數(shù)組，數(shù)組的第一個數(shù)值為“起點站點”編號，后續(xù)數(shù)值對應(yīng)不同的“換乘站點”編號。前后兩個數(shù)值編號代表的“換乘站點”必須連接，這條約束可結(jié)合對結(jié)構(gòu)體數(shù)組A[M]中相應(yīng)結(jié)構(gòu)體內(nèi)容int I[K]的隨機選取來實現(xiàn)。

一條染色體中不能同時出現(xiàn)兩個相同的“換乘站點”，這條約束可通過將簡單的循環(huán)判斷算法加在上一條約束上實現(xiàn)，即通過判斷將結(jié)構(gòu)體內(nèi)容int I[K]中已經(jīng)在前面出現(xiàn)過的站點排除在隨機選取對象之外，這樣會出現(xiàn)符合條件的“換乘站點”不存在的情況，此時將下一級“換乘站點”設(shè)為“目標(biāo)站點”，并將這兩個站點之間的權(quán)值取為軌道交通網(wǎng)絡(luò)總路段數(shù)，后續(xù)站點均設(shè)為“目標(biāo)站點”，“目標(biāo)站點”之間的權(quán)值為0。

通過從前到后一級級連續(xù)“換乘站點”的生成，直到出現(xiàn)“目標(biāo)站點”，后續(xù)站點均設(shè)為“目標(biāo)站點”，“目標(biāo)站點”之間的權(quán)值為0。

(2)初始種群生成

利用上述染色體編碼原理，生成初始種群。由于染色體編碼約束較多，生成質(zhì)量高，多樣性好，所以初始種群規(guī)模不需要太大，30～50已經(jīng)足夠。

(3)種群個體適應(yīng)度函數(shù)評估

個體適應(yīng)度函數(shù)是反應(yīng)個體優(yōu)劣的指標(biāo)，合理的適應(yīng)度函數(shù)可大大加快最優(yōu)解的收斂速度，本文個體適應(yīng)度函數(shù)如下：

F(x)=1-f(x)/Gmax

(1)

f(x)為每一條路徑上所經(jīng)過的路段數(shù)的總和，即權(quán)值的總和，Gmax為軌道交通網(wǎng)絡(luò)的總路段數(shù)，即總權(quán)值。本文個體適應(yīng)度函數(shù)值越大，路徑經(jīng)歷的總路段數(shù)越小，表明個體越優(yōu)秀。

(4)選擇操作

選擇操作是依據(jù)個體適應(yīng)度函數(shù)，基于優(yōu)勝劣汰的原則從種群中挑選比較優(yōu)異的個體遺傳至下一代種群中。個體適應(yīng)函數(shù)值越大，個體越優(yōu)秀，被選中的概率越大。本文實用了最優(yōu)保全策略，即將最優(yōu)個體不加改變的直接遺傳給下一代，而將權(quán)值大于軌道交通網(wǎng)絡(luò)總權(quán)值的個體(即F(x)<0)全部淘汰掉，在下一代中按照染色體編碼發(fā)生重新生成新的個體。

(5)交叉操作

選擇兩個未經(jīng)淘汰的個體，尋找是否存在除“初始站點”和“目標(biāo)站點”外編號相同的站點，若存在，則從該“換乘站點”開始將后續(xù)站點進行交換，若不存在，重新尋找兩個個體進行交叉操作。

(6)變異操作

根據(jù)一定的變異概率來改變產(chǎn)生新的個體，可以避免遺傳算法計算陷入局部最優(yōu)。本文針對被選中個體進行變異操作時，選中除“初始站點”和“目標(biāo)站點”外的任一“換乘站點”，從該站點開始，利用染色體編碼方式，重新生成后續(xù)“換乘站點”。

(7)優(yōu)化路徑求解

按照圖2流程，不斷循環(huán)執(zhí)行上述操作，經(jīng)過一定的進化代數(shù)，即可獲得最優(yōu)路徑。若執(zhí)行過程中發(fā)現(xiàn)最優(yōu)路徑總權(quán)值不變而路徑不斷變化，說明存在多條總權(quán)值相同的最優(yōu)路徑，則在下一次執(zhí)行程序時，將某條最優(yōu)路徑的總權(quán)值設(shè)置為軌道交通網(wǎng)絡(luò)的總權(quán)值，即將這條路徑淘汰掉。通過這樣的操作，通過一次次執(zhí)行程序，不僅可以找到多條最優(yōu)路徑，而且可以對所有可到達的路徑進行排序，逐漸找到次優(yōu)路徑，次次優(yōu)路徑。

3 實例計算

初始種群大小取為50，交叉概率取0.5，變異概率取0.1，進化代數(shù)取100，站點4到站點10的前4條最優(yōu)路徑如表1所示。

表1 站點4到站點10的前4條最優(yōu)路徑

從表1可以看出，本文所采用的方法和文獻[3]獲得的路徑完全相同，由于采用了路段數(shù)而非站點數(shù)描述路徑長度，所以各條路徑的總權(quán)值f(x)存在差異，但這并不影響問題的最終求解。

4 結(jié)束語

本文改進了一種城市軌道交通網(wǎng)絡(luò)的簡化模型，并提出了一種基于遺傳算法的軌道交通乘車最優(yōu)路徑求解方法，實例計算表明該方法不僅可以求解最優(yōu)乘車路徑，還可以對乘車路徑進行優(yōu)化排序，簡單實用，合理可行。

[1] 代才. 基于分解的多目標(biāo)進化算法研究[D]. 西安:西安電子科技大學(xué), 2014.

[2] 譚艷艷. 幾種改進的分解類多目標(biāo)進化算法及其應(yīng)用[D]. 西安:西安電子科技大學(xué), 2013.

[3] 葉晉,史有群,樣學(xué)斌,等. 遺傳算法在軌道交通換乘路徑求解問題上的應(yīng)用[J]. 電腦與信息技術(shù), 2009,17(4)：24-27.

[4] 董妍汝. 基于選擇算子的遺傳算法改進[J]. 辦公自動化(學(xué)術(shù)版), 2015,21(16):59-61.

[5] 吳亮紅.多目標(biāo)動態(tài)差分進化算法及其應(yīng)用研究[D]. 湖南大學(xué), 2011.

[6] FAN HY, LU JWZ, XU ZB. An empirical comparison of three novel genetic algorithms [J]. Engineering Computations, 2000,17(8):981-1001.

A Solution for Rail Transit Riding Path Based on the Genetic Algorithm

Bai Hongtu, Liu Hua

(Xi’an Institute of Railway Technology, Xi’an Shaanxi 710014, China)

With regards to optimization of riding path for urban rail transit, this paper presents an improved modeling method for urban rail transit networks, and proposes a rail transit path solution based on the genetic algorithm, which can realize optimal sequencing of multiple riding paths. Practical calculation shows that this method is simple, practical, reasonable and feasible.

urban rail transit; genetic algorithm; path optimization;riding;traffic network;model

10.3969/j.issn.1000-3886.2017.02.012

U212

A

1000-3886(2017)02-0039-02

白宏圖(1981-)女，陜西咸陽人，碩士，大學(xué)講師，研究方向：計算機技術(shù)、計算機網(wǎng)絡(luò)。

定稿日期: 2016-08-07