基于遺傳算法的中小城市地鐵運(yùn)營(yíng)與建設(shè)的方案

吳家揚(yáng) 劉雯景

（廣東海洋大學(xué) 廣東省湛江市 524088）

1 引言

在經(jīng)濟(jì)高速發(fā)展的當(dāng)下，作為城市動(dòng)脈的地鐵，給人們帶來(lái)交通便利、快捷，一種千里江陵一日還的幸福生活。但中小城市地鐵建設(shè)成本昂貴、出行虧損、早晚高峰期交通擁堵，運(yùn)用合理科學(xué)的運(yùn)營(yíng)和優(yōu)化建設(shè)設(shè)計(jì)刻不容緩。根據(jù)相關(guān)報(bào)道顯示呼和浩特地鐵2019年年底開(kāi)始試運(yùn)營(yíng)，目前已有地鐵1 號(hào)線和2 號(hào)線兩條正在運(yùn)營(yíng)的線路。然而，因線路數(shù)量、人口基數(shù)相對(duì)較少和站點(diǎn)選址上的問(wèn)題地鐵運(yùn)營(yíng)收入依然較低，從而引進(jìn)科學(xué)的運(yùn)營(yíng)方案設(shè)計(jì)來(lái)有效降低運(yùn)營(yíng)成本提高運(yùn)行效率勢(shì)在必行。通過(guò)實(shí)例對(duì)基于遺傳算法與確定性模型的公交調(diào)度結(jié)果進(jìn)行比對(duì)，結(jié)果表明，基于遺傳算法獲得的地鐵調(diào)度模糊最優(yōu)解比確定性模型更為合理。[1]

2 問(wèn)題分析

2.1 基于遺傳算法模型分析

首先對(duì)原發(fā)車(chē)方案進(jìn)行評(píng)價(jià)，其次是求最優(yōu)發(fā)車(chē)的間隔時(shí)間和最優(yōu)的車(chē)廂數(shù)。車(chē)箱數(shù)默認(rèn)為6，把站點(diǎn)人數(shù)分成平峰期和高峰期，采用均值化進(jìn)行處理，再利用遺傳算法求發(fā)車(chē)最優(yōu)間隔時(shí)間。利用所求的最優(yōu)時(shí)間和成本函數(shù)，去比較車(chē)廂數(shù)不同時(shí)的利潤(rùn)值。當(dāng)利潤(rùn)值最大時(shí)，就為最優(yōu)的車(chē)廂數(shù)量。

3 模型的建立與求解

3.1 基于遺傳算法模型分析

3.1.1 數(shù)據(jù)的預(yù)處理

我們采用的數(shù)據(jù)是呼和浩特市2020年9月1日至2020年9月14日，2 條線路，45 個(gè)站點(diǎn)，間隔為15 分鐘的客流數(shù)據(jù)。將地鐵的運(yùn)營(yíng)時(shí)間分成高峰期和平峰期，早高峰為7:00-9:00，晚高峰為17:00-19:00，其余時(shí)間為平峰期。我們把早高峰期和晚高峰期的時(shí)間用S1去表示，平峰期的時(shí)間用S2去表示。我們用fijkq去表示第天，第j 號(hào)線，第k 個(gè)站點(diǎn)的人數(shù)，q 表示的是運(yùn)營(yíng)時(shí)間的分類(lèi)。其中(0

fijkq這個(gè)變量將被用于計(jì)算目標(biāo)函數(shù)的最優(yōu)值。為了優(yōu)化后面求最優(yōu)值的過(guò)程，首先對(duì)S1和S2兩個(gè)時(shí)期14 天的數(shù)據(jù)作均值化處理，用去表示每個(gè)站點(diǎn)14 天的平均值，q 的取值為0 和1，即

通過(guò)上面的統(tǒng)計(jì)我們可以得到S1和S2兩個(gè)時(shí)期每個(gè)站點(diǎn)的吞吐量信息，如圖1、圖2所示。

圖1：高峰期的客流情況

圖2：平峰期的客流情況

3.1.2 構(gòu)建遺傳算法模型

我們?cè)谇蠼獍l(fā)車(chē)的時(shí)間間隔t 用的是遺傳算法，該算法的實(shí)現(xiàn)如表1所示[2]。

表1：算法步驟

步驟1.確定優(yōu)化方程

該問(wèn)題的關(guān)鍵是設(shè)置一個(gè)合理的間隔時(shí)間，從而找到盈利最優(yōu)的模式。可以把該問(wèn)題看成是如何求最小成本，也就是就能夠最大化盈利。查閱資料[3]，我們考慮如下公式，其中用α 表示列車(chē)運(yùn)營(yíng)成本權(quán)重系數(shù)，用β 表示乘客出行成本權(quán)重系數(shù)，C0表示軌道交通系統(tǒng)乘客出行成本，Cv為軌道交通系統(tǒng)列車(chē)運(yùn)營(yíng)成本。成本函數(shù)可表示為：

C=αC0+βCv

運(yùn)營(yíng)時(shí)間分成高峰期和平峰期，早高峰為7:00-9:00，晚高峰為17:00-19:00，其余時(shí)間為平峰期。依據(jù)這兩個(gè)時(shí)間段，采用熵權(quán)法去確立權(quán)值，高峰期用α1去表示，平峰期用α2去表示。最終，最優(yōu)的發(fā)車(chē)間隔通過(guò)t=α1×t1+α2×t2。

步驟2.生成初始解編碼

表4：早高峰期方案設(shè)計(jì)

表5：晚高峰期方案設(shè)計(jì)

選擇的編碼方式是二進(jìn)制編碼，將十進(jìn)制的數(shù)字轉(zhuǎn)換成二進(jìn)制。由于方程中xi的范圍處于[0,128]之間，因此統(tǒng)一轉(zhuǎn)換為7 位的二進(jìn)制數(shù)，例如當(dāng)xi=8 的時(shí)候需要轉(zhuǎn)換成xi=00000100。我們生成的初始解有4 個(gè)，分別是4,6,8,10，它們經(jīng)過(guò)編碼得到的結(jié)果，分別是：

x1=00000100

x2=00000110

x3=00001000

x4=00001100

步驟3.評(píng)估種群適應(yīng)度，淘汰最小解。

把上述生成的變量分別代入目標(biāo)函數(shù)中，通過(guò)Max(xi)去比較4 個(gè)解的概率，得到概率最小的解為xk，概率最小的解要被概率最高的解替換。即：

xk=Max(xi)

步驟4.交叉，變異。

是否進(jìn)行變異需要用過(guò)概率去決定。其中默認(rèn)變異率為Pm=0.001，變異概率P=Pm×m×q 可以通過(guò)求取。其中是編碼的位數(shù)用m 去表示，解的群體數(shù)用q 去表示。將求得的P 于1 進(jìn)行比較，當(dāng)P<1 不進(jìn)行變異，當(dāng)P>1 進(jìn)行變異。對(duì)初始解進(jìn)行交叉，交叉操作如圖3所示，即對(duì) 位二進(jìn)制數(shù)的后四位進(jìn)行交叉變換。

圖3：交叉變換的示意圖

步驟5.解碼得到最優(yōu)值。利用函數(shù)BinToDec()進(jìn)行解碼轉(zhuǎn)換

在前面求解的最優(yōu)發(fā)車(chē)間隔t 的時(shí)候，我們已經(jīng)建立了關(guān)于成本函數(shù)，當(dāng)成本函數(shù)值越小，地鐵公司的盈利越高。在求解最優(yōu)車(chē)廂數(shù)的時(shí)候，需要通過(guò)比較車(chē)廂數(shù)n 為3,4,5,6,7,8 時(shí)候的日成本量，當(dāng)日成本最小時(shí)，即為車(chē)廂數(shù)n 的最優(yōu)值。其中最優(yōu)發(fā)車(chē)間隔默認(rèn)為t=6，將上述所說(shuō)的n 與t 代入函數(shù)中計(jì)算比較，即可求得最優(yōu)發(fā)車(chē)間隔、最優(yōu)車(chē)廂數(shù)。

3.1.3 模型參數(shù)的設(shè)置

在求解的時(shí)候，我們?cè)谶z傳算法的參數(shù)設(shè)置[5]，如表2所示。

表2：參數(shù)設(shè)置

3.1.4 模型結(jié)果分析

通過(guò)圖4所示的流程，最終我們?cè)诘螖?shù)為75，求出了平峰期的最佳間隔時(shí)間為t1=8.3，高峰期發(fā)車(chē)間隔5.4。損失函數(shù)如圖5所示。

圖4：遺傳算法流程

圖5：損失函數(shù)圖像

利用熵權(quán)法我們可以求得的權(quán)重平峰期α1為0.3，高峰期α2為0.7。得到結(jié)果如表3所示。當(dāng)車(chē)廂數(shù)為4 時(shí)，求得的成本節(jié)約18%。

表3：計(jì)算結(jié)果

3.2 以2c站點(diǎn)為例提出錯(cuò)峰出行建議

3.2.1 錯(cuò)峰出行目標(biāo)函數(shù)的建立

以最大客流量站點(diǎn)為2c 為研究對(duì)象，比較不同的錯(cuò)峰出行方式會(huì)對(duì)該站點(diǎn)的客流量造成影響。

了解到該地區(qū)的學(xué)生群體的上學(xué)時(shí)間7:45-8:00 之間，放學(xué)時(shí)間17:00-18:00。上班群體的時(shí)間為7:30-8:10 之間，下班時(shí)間為17:30-18:15。可以看見(jiàn)現(xiàn)在的上學(xué)時(shí)間和上班群體的時(shí)間存在較大的交叉性。

因此我們根據(jù)實(shí)際情況，對(duì)早高峰期和晚高峰期分別設(shè)置了3種不同的方案[6]，在不影響上班群體和學(xué)生群體的出行情況下，盡可能的減少出行時(shí)間的交叉，如表格4、5所示。

考慮到學(xué)生群體有到校時(shí)間的準(zhǔn)則，上班群體也有到崗時(shí)間的準(zhǔn)則，因此它們?cè)诓煌瑫r(shí)間段將會(huì)有不同的權(quán)重。用αi1去表示用第i 個(gè)方案上學(xué)時(shí)間的權(quán)重，用αi2去表示用第i 個(gè)方案上班時(shí)間的權(quán)重。

3.2.2 錯(cuò)峰出行目標(biāo)函數(shù)的求解

舒適度的結(jié)果如表6、表7所示。從表中可以看見(jiàn)，早高峰期與晚高峰期都是方案三的擁擠度最低，因此上學(xué)時(shí)間設(shè)置為7:20-7:30，上班時(shí)間為8:35-8:55，放學(xué)時(shí)間為16:50-17:20，下班時(shí)間為17：40-18:15，能夠有效減少2c 站點(diǎn)所出現(xiàn)的擁擠情況。

表6：早高峰期舒適度

表7：晚高峰期舒適度

綜上早晚高峰期的優(yōu)化計(jì)算，可實(shí)現(xiàn)最終平峰目標(biāo)的方案設(shè)置，如表8所示。

表8：平峰目標(biāo)方案

4 模型的評(píng)價(jià)及優(yōu)化

4.1 誤差分析

在地鐵1 號(hào)線，2 號(hào)線各站點(diǎn)人流量均互不影響的前提下，會(huì)忽略實(shí)際生活中出現(xiàn)的換乘等情況，且統(tǒng)計(jì)樣本有重復(fù)性。地鐵運(yùn)營(yíng)成本統(tǒng)計(jì)忽略實(shí)際能耗成本，維護(hù)成本等方面，與實(shí)際會(huì)有較大出入。

4.2 模型的優(yōu)點(diǎn)

模型邏輯清晰，可操作性強(qiáng)，可移植性強(qiáng)。模型基于數(shù)學(xué)推導(dǎo)，分析嚴(yán)謹(jǐn)，穩(wěn)定性高，結(jié)論具有普遍意義。結(jié)合實(shí)際城市地形分析，結(jié)論嚴(yán)謹(jǐn)，有一定程度上的實(shí)用價(jià)值。

4.3 模型的缺點(diǎn)

在選址問(wèn)題上只選取了一天的站點(diǎn)吞吐量分析，而具體人流量會(huì)受交通管制，天氣，節(jié)假日等因素影響。模型忽略了具體城市的原有交通布局方案，實(shí)際合理性上會(huì)有一定程度欠妥。

4.4 模型的推廣

本文使用的模型移植性高，如遺傳算法可用在各類(lèi)優(yōu)化問(wèn)題上求解，基于遺傳算法改進(jìn)的站點(diǎn)優(yōu)化模型可應(yīng)用在公共基礎(chǔ)設(shè)施選址等具有實(shí)際效益的問(wèn)題上。[7]