基于遺傳算法的智能公交調(diào)度系統(tǒng)的研究

李清逸 李文娟 謝 鵬 劉向東 閆利霞

（蘇州城市學(xué)院，江蘇 蘇州 215000）

隨著我國(guó)國(guó)力的不斷增強(qiáng)，國(guó)民經(jīng)濟(jì)飛速發(fā)展，城市化建設(shè)也得到不斷推進(jìn)，城市人口逐漸上升，公共交通和私家車成為城市居民的出行主要工具，私家車數(shù)量的增加造成了較為嚴(yán)重的空氣污染和交通擁堵，不斷增長(zhǎng)的城市人口為公共交通帶來(lái)了巨大壓力。科學(xué)規(guī)劃交通，合理調(diào)度資源，建設(shè)現(xiàn)代化的城市智能交通調(diào)度系統(tǒng)迫在眉睫。

智能公交調(diào)度系統(tǒng)在實(shí)際公共交通中的應(yīng)用增多，許多學(xué)者針對(duì)出現(xiàn)的問(wèn)題和不足采用不同的算法進(jìn)行研究和改善。其中遺傳算法、啟發(fā)式算法、BP神經(jīng)網(wǎng)絡(luò)和其他智能優(yōu)化算法對(duì)智能公交的調(diào)度優(yōu)化方面有較大幫助。與其他優(yōu)化算法相比，遺傳算法的搜索從群體出發(fā)，在解決多輛公交調(diào)度的優(yōu)化問(wèn)題方面有較大優(yōu)勢(shì)。

1 智能公交調(diào)度系統(tǒng)現(xiàn)狀

2021年智能公交領(lǐng)域進(jìn)入發(fā)展冷卻期，全國(guó)城市公交客流量大幅下降，但智能公交調(diào)度仍是城市公交發(fā)展的主要方向。隨著智能公交調(diào)度系統(tǒng)的不斷發(fā)展，一線城市與非一線城市的差距逐漸擴(kuò)大。一線城市的發(fā)展趨于飽和，非一線城市的智能化基礎(chǔ)設(shè)施完善程度有待提高、信息化基礎(chǔ)較為薄弱、城市信息化設(shè)備老舊等因素為智能公交調(diào)度系統(tǒng)的發(fā)展帶來(lái)巨大挑戰(zhàn)。

在政策支持、技術(shù)進(jìn)步、城市化進(jìn)程和機(jī)動(dòng)車保有量持續(xù)攀升等多重因素推動(dòng)下，我國(guó)智能交通行業(yè)規(guī)模將穩(wěn)步上升。綜合政策規(guī)劃和交通運(yùn)輸行業(yè)細(xì)分市場(chǎng)的發(fā)展?fàn)顩r，預(yù)計(jì)到2026年我國(guó)智能交通行業(yè)市場(chǎng)規(guī)模將突破4 000億元，年均復(fù)合增長(zhǎng)率在16%左右，智能公交系統(tǒng)的整體發(fā)展趨勢(shì)穩(wěn)步上升。2021～2026年中國(guó)智能交通行業(yè)市場(chǎng)規(guī)模預(yù)測(cè)如圖1所示。

圖1 2021～2026年中國(guó)智能交通行業(yè)市場(chǎng)規(guī)模預(yù)測(cè)

2 公交調(diào)度模型

公交調(diào)度指根據(jù)線路實(shí)時(shí)客流量情況，確定線路中各時(shí)間段發(fā)車次數(shù)及發(fā)車間隔，制成發(fā)車時(shí)間表，借此指揮城市公交的運(yùn)營(yíng)。

2.1 公交調(diào)度

公交調(diào)度分為動(dòng)態(tài)調(diào)度和靜態(tài)調(diào)度。動(dòng)態(tài)調(diào)度指調(diào)度員在公交發(fā)車后，根據(jù)道路交通情況、車輛運(yùn)行情況以及突發(fā)事件等其他實(shí)時(shí)信息，對(duì)公交的行車間隔等運(yùn)營(yíng)信息進(jìn)行調(diào)整，保證公交車運(yùn)行通暢，維持正常設(shè)定的服務(wù)水平。在動(dòng)態(tài)調(diào)度中遺傳算法應(yīng)用較多，遺傳算法能夠較好地解決陷入局部最優(yōu)解的問(wèn)題。靜態(tài)調(diào)度主要是確定線路上的車輛配比和發(fā)車計(jì)劃，在滿足客流需求的條件下，使城市公交的運(yùn)營(yíng)變得科學(xué)高效。靜態(tài)調(diào)度是公交調(diào)度的基礎(chǔ)，文章主要從靜態(tài)調(diào)度入手，研究基于遺傳算法的公交調(diào)度系統(tǒng)。

2.2 公交調(diào)度優(yōu)化問(wèn)題分析

調(diào)度的目的是合理規(guī)劃資源分配，制定科學(xué)高效的行車計(jì)劃，在運(yùn)能供應(yīng)充足和滿足客流需求的條件下，提高行車速度和公里數(shù)，節(jié)約公司成本，公交調(diào)度的核心問(wèn)題是保證乘客和公交公司的利益最大化。乘客利益方面，候車時(shí)間長(zhǎng)短是乘客滿意度的重要因素，如果要縮短乘客候車時(shí)長(zhǎng)，需要增加運(yùn)營(yíng)的公交車數(shù)量，提高公交車到站頻率。對(duì)公交公司而言，增加公交車運(yùn)行數(shù)量，不符合經(jīng)濟(jì)利益，也為城市道路容量帶來(lái)壓力。公交公司利益方面，公交公司的收入要承擔(dān)公交車的日常維護(hù)、折損、燃油和人員工資等問(wèn)題。乘客利益與公交公司利益成對(duì)立狀態(tài)，找出調(diào)度優(yōu)化的平衡點(diǎn)是問(wèn)題的關(guān)鍵。

2.3 模型建立

建立的目標(biāo)函數(shù)包括乘客利益最大化，即乘客的平均等車時(shí)間最短；公交公司利益最大化，公司的發(fā)車次數(shù)最少。

目標(biāo)函數(shù)如下：

式中：C1——乘客候車成本；σ1——乘客單位時(shí)間內(nèi)的候車成本（元/min）；a——站點(diǎn)；b——車輛數(shù)；C2——公司運(yùn)營(yíng)成本；σ2——一輛公交單位時(shí)間內(nèi)的運(yùn)營(yíng)成本（元/min）；ρ——a站的到站率；Tb，a——第b輛車到達(dá)a站的時(shí)間；tb，a——第b輛車離開(kāi)a站的時(shí)間。

為了使目標(biāo)函數(shù)滿足乘客利益和公司利益的平衡，達(dá)到雙目標(biāo)優(yōu)化的效果，需要分別對(duì)乘客候車成本和公交公司運(yùn)營(yíng)成本進(jìn)行加權(quán)整合，加權(quán)系數(shù)分別為α、β，約束條件為最大發(fā)車間隔時(shí)間，文章選取為10 min，最小發(fā)車間隔時(shí)間為1 min，則目標(biāo)函數(shù)為（其中min為函數(shù)的最小值，即目標(biāo)函數(shù)C的結(jié)果為最小成本）：

3 基于遺傳算法的智能公交調(diào)度

靜態(tài)公交車調(diào)度是多目標(biāo)優(yōu)化問(wèn)題，遺傳算法的搜索從群體出發(fā)，經(jīng)過(guò)編碼，選擇，交叉，變異四個(gè)過(guò)程，能夠快速找出問(wèn)題的最佳解決方案。

3.1 基于遺傳算法的公交調(diào)度模型求解

（1）編碼。由于遺傳算法不能直接處理問(wèn)題空間的參數(shù)，必須通過(guò)編碼將需要求解的問(wèn)題表示成遺傳空間的染色體或者個(gè)體[1]。系統(tǒng)采用浮點(diǎn)數(shù)編碼中的實(shí)數(shù)編碼較為簡(jiǎn)便，以公交的發(fā)車時(shí)間為變量，客流量峰值控制發(fā)車間隔。根據(jù)發(fā)車時(shí)段劃分生成發(fā)車間隔，結(jié)合種群大小和一段時(shí)間內(nèi)首末班車的發(fā)車時(shí)間和截止時(shí)間，完成初始種群選取。實(shí)數(shù)算法的優(yōu)勢(shì)在于種群的個(gè)體就是問(wèn)題的解，不需要使用函數(shù)進(jìn)行轉(zhuǎn)換，且個(gè)體的優(yōu)良基因段將會(huì)繼續(xù)遺傳到下一代，使得每一代都有進(jìn)化。

（2）選擇操作。選擇操作是為了在群體中開(kāi)展優(yōu)勝劣汰。采用選擇操作中的輪盤賭選擇法和最佳個(gè)體保存法，使適應(yīng)度值越好的個(gè)體被選擇的概率越大。在遺傳中每一代先保留一個(gè)最佳個(gè)體，且個(gè)體中不含重復(fù)的基因片段，按照選擇概率劃分區(qū)域?qū)€(gè)體放入輪盤，然后對(duì)隨機(jī)算子選中的個(gè)體進(jìn)行配對(duì)。

（3）交叉操作。采用單點(diǎn)交叉可以得到更多合理的發(fā)車時(shí)間表。通過(guò)隨機(jī)算子決定是否進(jìn)行交叉操作，進(jìn)行交叉的頻率受設(shè)置的交叉率影響，個(gè)體在隨機(jī)選擇的位置點(diǎn)上進(jìn)行交叉，得到兩個(gè)新的個(gè)體，如果新個(gè)體中含重復(fù)片段，則重新選擇交叉位點(diǎn)，直至新個(gè)體中不含重復(fù)的基因片段。

（4）變異操作。采用實(shí)數(shù)編碼限制了變異基因的變異范圍，不允許新個(gè)體中含有重復(fù)的基因片段。由隨機(jī)算子決定是否進(jìn)行變異操作，若進(jìn)行編譯操作，隨機(jī)選擇變異染色體的某個(gè)基因，將其轉(zhuǎn)化為二進(jìn)制編碼后隨機(jī)選擇一位二進(jìn)制位點(diǎn)進(jìn)行變。如果變異后所選基因的值為0、1或者不在可變異區(qū)間內(nèi)則重新進(jìn)行變異。

3.2 算法的應(yīng)用

（1）初始化變量。運(yùn)算參數(shù)設(shè)定包括乘客的候車成本為1 元/min；公司運(yùn)營(yíng)成本為2 元/min，線路的站點(diǎn)總數(shù)為25個(gè)，線路的車輛總數(shù)為10輛，首班車時(shí)間為6:00，末班車的時(shí)間為21:00，發(fā)車次數(shù)為50次，平均運(yùn)行時(shí)間為20 km/h。公交的到站率由每個(gè)站點(diǎn)的購(gòu)票人數(shù)和發(fā)車間隔求出，將公交的發(fā)車時(shí)間到截止時(shí)間劃分為幾個(gè)時(shí)段區(qū)間，發(fā)車次數(shù)由預(yù)設(shè)定給出，具結(jié)合實(shí)際公交客流量數(shù)據(jù)樣例。

（2）不同權(quán)重下最小成本的計(jì)算結(jié)果。模型中的權(quán)重取值代表利益中乘客利益和公交公司利益的占比大小，目標(biāo)函數(shù)中權(quán)重的不同取值代表不同的最小成本，按照參數(shù)和蘇州公交公司某條線路單日客流量數(shù)據(jù)進(jìn)行計(jì)算得到不同權(quán)重下的計(jì)算結(jié)果，在α=0.5，β=0.5時(shí)（α+β=1）最小成本明顯低于其他測(cè)試值。最小成本隨α占比變化如圖2所示。

圖2 最小成本隨α占比變化

（3）不同交叉率、變異率、迭代次數(shù)下平均成本的計(jì)算結(jié)果。交叉率會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生不同程度的影響，當(dāng)交叉概率P1=0.7時(shí)，種群的平均成本較小，優(yōu)于其他交叉概率下的測(cè)試值。

不同變異率對(duì)平均成本的影響較大，當(dāng)變異概率P2=0.000 5時(shí)的平均成本優(yōu)于其他測(cè)試值。

平均成本隨迭代次數(shù)的增加而減小，當(dāng)?shù)螖?shù)n=400時(shí)的平均成本趨于穩(wěn)定狀態(tài)。

平均成本隨交叉概率變化如圖3所示。

圖3 平均成本隨交叉概率變化

平均成本隨變異概率變化如圖4所示。

圖4 平均成本隨變異概率變化

平均成本隨迭代次數(shù)變化如圖5所示。

圖5 平均成本隨迭代次數(shù)變化

4 結(jié)語(yǔ)

隨著時(shí)代的快速發(fā)展，解決城市交通擁堵的問(wèn)題迫在眉睫，大力發(fā)展城市公交，優(yōu)化城市公交調(diào)度系統(tǒng)能夠有效解決交通擁堵問(wèn)題，結(jié)合遺傳算法、科學(xué)規(guī)劃交通以及合理調(diào)度資源為城市公交的發(fā)展帶來(lái)更多可能。在未來(lái)的實(shí)踐中，應(yīng)結(jié)合動(dòng)態(tài)調(diào)度分析在各類異常情況下的調(diào)度決策問(wèn)題，聯(lián)合實(shí)際城市公交現(xiàn)狀找到問(wèn)題的更優(yōu)解，形成更加成熟的現(xiàn)代化城市公交調(diào)度系統(tǒng)。