改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化研究

韓天齊 宋波

摘 要：

公交是一種主要的城市公共交通工具，針對現(xiàn)有城市公交線網(wǎng)設(shè)計時普遍存在缺乏層次性規(guī)劃的問題，提出了改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方法。首先對當(dāng)前城市公交線網(wǎng)優(yōu)化的研究現(xiàn)狀進(jìn)行分析，然后設(shè)計相應(yīng)的城市公交線網(wǎng)優(yōu)化數(shù)學(xué)模型，采用改進(jìn)遺傳算法對城市公交線網(wǎng)優(yōu)化數(shù)學(xué)模型進(jìn)行求解，并通過引入動態(tài)懲罰系數(shù)確定適應(yīng)度，以調(diào)整收斂速度;通過自適應(yīng)機制確定交叉概率和變異概率，以調(diào)整搜索空間。最后采用具體算例對本文方法的性能進(jìn)行分析。結(jié)果表明，這個方法不僅可以找到更優(yōu)的城市公交線網(wǎng)優(yōu)化方案，而且求解的效率得到了明顯提升。

關(guān)鍵詞：

城市公交線網(wǎng); 層次性規(guī)劃; 遺傳算法; 收斂速度; 數(shù)學(xué)模型

中圖分類號： TP301

文獻(xiàn)標(biāo)志碼： A

Research on Bus Network Optimization Based on Improved Genetic Algorithm

HAN Tianqi， SONG Bo

（School of Cybersecurity， Chengdu University of Information Technology， Chengdu， Sichnan? 610225， China）

Abstract：

Bus is a major urban public transport. Aiming at the problem of lacking hierarchical planning in the design of urban public transport network， this paper proposes an improved genetic algorithm for the optimization of urban public transport network. Firstly， the current research situation of urban public transport network optimization is analyzed， the corresponding mathematical model of urban public transport network optimization is designed， and then an improved genetic algorithm is used to optimize the mathematical model of urban public transport network optimization. Finally， the performance of the proposed method is analyzed by a specific example. The results show that the proposed method can find a better urban public transport network optimization scheme， and efficiency of solution has been improved obviously.

Key words：

urban public transport network; hierarchical planning; genetic algorithm; convergence rate; mathematical model

0 引言

相對于其它交通工具，公交能耗小，乘坐方便，價格低廉，人們出行乘坐公交頻率高，許多城市提出了“公交優(yōu)先”的口號，以解決城市交通擁塞問題[1-2]。但是，在平常出行過程中，亦存在如換乘難、等車時間長等問題，對公交競爭力產(chǎn)生不利影響，而城市公交線網(wǎng)設(shè)計與優(yōu)化可以得到最優(yōu)的公交線路，解決乘客等車時間長等難問題，因此公交線網(wǎng)優(yōu)化研究成為城市公共交通管理領(lǐng)域中的一個重要研究方向[3]。

為了解決城市交通擁塞問題，世界各國都投入了大量的人力、財力進(jìn)行了深入的研究，其中如美國、英國等國外發(fā)達(dá)國家的研究時間比較早，研究技術(shù)比較成熟，提出了許多有效的公交線網(wǎng)優(yōu)化方法，而國內(nèi)的公交線網(wǎng)優(yōu)化研究起步相對比較晚，但是由于受到眾多學(xué)者的關(guān)注，發(fā)展速度相當(dāng)快，學(xué)者們提出了一些性能比較優(yōu)異的公交線網(wǎng)優(yōu)化方法[4]。公交線網(wǎng)優(yōu)化研究可以劃分兩個階段：第一個階段是手工階段，另一個階段是自動智能階段。手工階段主要為城市公共交通管理領(lǐng)域的專家根據(jù)相關(guān)數(shù)據(jù)、資料和自身的經(jīng)驗建立一些公交線路，該階段主要是由于公交線路少，路線比較簡單，但是該種方法得到最優(yōu)公交線路耗時比較長，需要大的人力，公交線網(wǎng)優(yōu)化不僅成本高，而且不靈活，難以保證得到最優(yōu)的公交線網(wǎng)，對于大規(guī)模的公交線網(wǎng)，其缺陷就更加明顯，無法滿足公交線網(wǎng)優(yōu)化的在線、實時性要求[5]。自動智能階段是信息技術(shù)、智能技術(shù)、遙感技術(shù)以及一些優(yōu)化理論融合的結(jié)果，它們首先對一個城市交通的公交線路進(jìn)行分析，設(shè)計公交線網(wǎng)優(yōu)化目標(biāo)，如：用戶費用和運營者費用最低，用戶出行時間最短等，根據(jù)優(yōu)化目標(biāo)建立公交線網(wǎng)優(yōu)化數(shù)學(xué)模型，然后采用動態(tài)規(guī)劃算法、非線性整數(shù)規(guī)劃算法、遺傳算法、蟻群算法等進(jìn)行求解，對最優(yōu)公交線路進(jìn)行搜索，得到了比較好的公交線網(wǎng)優(yōu)化方案[6-8]。然而在實際應(yīng)用中，這些算法存在一定的缺陷，如動態(tài)規(guī)劃算法、非線性整數(shù)規(guī)劃算法的公交線網(wǎng)優(yōu)化問題求解效率低，無法滿足現(xiàn)代大型城市交通管理的要求;遺傳算法的交叉概率、變異概率固定，易使種群多樣性變差，無法獲得全局最優(yōu)的公交線網(wǎng)優(yōu)化方案;蟻群算法的初始激素深度采用隨機方式確定，使得初始解比較差，從而影響最終的公交線網(wǎng)優(yōu)化結(jié)果[9]。

針對當(dāng)前公交線網(wǎng)優(yōu)化方法存在的計算時間復(fù)雜度高、優(yōu)化速度慢、求解精度差等難題，設(shè)計了一種改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方法，首先對基本遺傳算法的工作原理進(jìn)行分析，對其不足進(jìn)行相應(yīng)的改進(jìn)，然后將其引入到了公交線網(wǎng)優(yōu)化問題的求解中，最后進(jìn)行了仿真對比實驗，結(jié)果表明，本文方法加快了公交線網(wǎng)優(yōu)化問題求解的速度，提高了公交線網(wǎng)優(yōu)化問題求解精度，可以應(yīng)用于具體的城市交通管理中。

1 公交線網(wǎng)優(yōu)化的數(shù)學(xué)模型

1.1 相關(guān)概念

在一個城市交通系統(tǒng)中，公交線網(wǎng)是一種主要線路，通常對客流需求大的點進(jìn)行連接，其運行效率直接決定了整個城市交通運營的效率，是一個城市人口出行的動脈。公交線網(wǎng)的線種包括兩種類型，一種類型為骨架線路，其相當(dāng)于主動脈，另一種為城市公交接運線路，相當(dāng)于小動脈，對交通網(wǎng)絡(luò)起著補充作用，這樣一個公交線網(wǎng)可以劃分為2個層次：骨架線網(wǎng)和接運線網(wǎng)，它們具體如圖1所示。從圖1可知，當(dāng)兩個點之間的乘客量很大，那么就可以在它們之間建立骨架線路，如果兩個點之間的乘客量小，那么就沒必要布設(shè)骨架線路，建立接運線網(wǎng)，方便乘客的換乘，如圖1所示。

1.2 建立公交線網(wǎng)優(yōu)化的數(shù)學(xué)模型

根據(jù)相關(guān)研究，兩個節(jié)點i，j之間經(jīng)常包括許多個可行線路，它們組成一個集合rij，線路之間相互交織形成一個公交線網(wǎng)，公交線網(wǎng)優(yōu)化目標(biāo)為：直達(dá)客流量最大、線網(wǎng)可達(dá)性最大，具體如下[10]。

（1） 直達(dá)客流量為公交網(wǎng)各線路的直達(dá)客流量和，如式（1）所示。

式中，當(dāng)點i，j之間的第a條路徑屬于構(gòu)造網(wǎng)絡(luò)的線路時，xij=1否則，xij=0，ηaij表示i，j之間的第a條路徑的直達(dá)客流量密度具體如式（2）所示。

式中，daij和laij分別表示i，j間的第a條路徑的直達(dá)客流量和路徑長度。

（2） 線網(wǎng)可達(dá)性為不超過兩次換乘的客流量（R）和總客流量∑∑odij比值，計算式如式（3）所示。

式中，odij表示兩個節(jié)點i，j之間的所有客流量。

那么公交線網(wǎng)優(yōu)化的數(shù)學(xué)模型如式（4）所示。

2 改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方法

2.1 遺傳算法以及不足

遺傳算法是一種模擬自然界生物進(jìn)化過程的群智能優(yōu)化算法，將要解決問題的可行解與個體相對應(yīng)，所有個體組成一個種群，通過種群模擬自然界生物進(jìn)化過程，個體進(jìn)入下一代主要通過適應(yīng)度值的高低來決定，通過選擇概率選擇當(dāng)前種群中適應(yīng)度函數(shù)值最高的個體直接進(jìn)入到下一代種群，根據(jù)交叉概率和變異概率產(chǎn)生新的個體。常規(guī)遺傳算法的交叉概率、變異概率的值采用固定方式，到了進(jìn)化后，種群多樣性變差，搜索停滯不前，影響問題求解的速度和精度，為此本文對其進(jìn)行改進(jìn)。

2.2 遺傳算法不足的改進(jìn)

改進(jìn)遺傳算法的基本思想為：如果個體適應(yīng)度小于種群適應(yīng)度均值，那么表示其性能比較差，一旦它被選中，那么就要采用較大的交叉概率和變異概率，不然就采用較小的交叉概率和變異概率，交叉概率和變異概率的自適應(yīng)變化形式如式（5）、式（6）所示。

式中，fmax為群體中最大適應(yīng)值，favg是群體的平均適應(yīng)值;f′和f分別為交叉和變異后的最大適應(yīng)度值，ki（

i=1，2，3，4）為0～1中的常數(shù)。

3.3 改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方法

3.3.1 改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方法設(shè)計

（1） 個體編碼，編碼是遺傳算法解決公交線網(wǎng)優(yōu)化問題，首先需要根據(jù)公交線網(wǎng)優(yōu)化問題的特征點設(shè)計，本文采用十進(jìn)制編碼方式，個體長度為n，個體編碼表示公交網(wǎng)中的線路數(shù)量，個體代表一種公交線網(wǎng)優(yōu)化方案。

（2） 初始種群生成，常規(guī)遺傳算法采用隨機方式產(chǎn)生初始種群，即公交線網(wǎng)優(yōu)化方案的可行解集合，這樣種群個體單一性比較嚴(yán)重，影響公交線網(wǎng)優(yōu)化問題的求解，為此本文采用均勻方式產(chǎn)生初始種群，使得個體在公交線網(wǎng)優(yōu)化方案的可行解空間均勻分布，有利于獲得更優(yōu)的公交線網(wǎng)優(yōu)化方案。

（3） 建立適應(yīng)度函數(shù)，因為適應(yīng)度函數(shù)決定著種群的進(jìn)化方向，結(jié)合公交線網(wǎng)優(yōu)化問題的特點，引入動態(tài)懲罰系數(shù)構(gòu)建適應(yīng)度函數(shù)，具體如式（7）所示。

式中，ω表示動態(tài)懲罰系數(shù)。

（4） 選擇策略的確定，當(dāng)前遺傳算法有兩種選擇策略：輪盤賭策略和錦標(biāo)賽策略，相對于輪盤賭策略，錦標(biāo)賽策略的穩(wěn)定性更好，因此本文采用錦標(biāo)賽策略選擇部分優(yōu)秀個體直接進(jìn)入下一代種群。

（5） 交叉和變異操作的確定，根據(jù)公交線網(wǎng)優(yōu)化問題的特點，本文采用單點交叉概率和隨機變異方式。

3.3.2 改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化步驟

Step1：設(shè)計城市公交網(wǎng)絡(luò)的層次性規(guī)劃圖像，并建立公交線網(wǎng)優(yōu)化問題的數(shù)學(xué)模型。

Step2：建立公交線網(wǎng)優(yōu)化方案的可行解集合，初始化種群。

Step3：初始化種群中個體采用十進(jìn)制方式進(jìn)行編碼，每一個個體代表一種公交線網(wǎng)優(yōu)化方案。

Step4：采用適應(yīng)度函數(shù)值對每一種公交線網(wǎng)優(yōu)化方案進(jìn)行評價，并對它們進(jìn)行排序。

Step5：根據(jù)錦標(biāo)賽策略選擇部分適應(yīng)度函數(shù)值較高的個體進(jìn)入下一代種群。

Step6：根據(jù)式（5）計算交叉概率，并隨機選擇兩個個體進(jìn)行單點交叉操作，選擇較優(yōu)的個體進(jìn)入下一代種群。

Step7：根據(jù)式（6）計算變異概率，并隨機選擇一個個體進(jìn)行變異操作，與父代個體進(jìn)行比較，選擇較優(yōu)的個體進(jìn)入下一代種群，進(jìn)化迭代次數(shù)增加。

Step8：判斷是否達(dá)到終止條件，若達(dá)到就輸出最優(yōu)個體，不然跳轉(zhuǎn)到Step4繼續(xù)執(zhí)行。

Step9：對最優(yōu)個體進(jìn)行解碼，得到最優(yōu)的公交線網(wǎng)優(yōu)化方案。

3 公交線網(wǎng)優(yōu)化方法的算例分析

采用Vc++6.0語言編程公交線網(wǎng)優(yōu)化問題求解的改進(jìn)遺傳算法程序，仿真測試環(huán)境為：Intel 酷睿i3 8100 CPU，金士頓DDR3 1600 8G RAM， Windows 10操作系統(tǒng)為，選擇常規(guī)遺傳算法進(jìn)行對比測試。改進(jìn)遺傳算法的相關(guān)參數(shù)如表1所示。

對于一個具體公交線網(wǎng)優(yōu)化問題，采用改進(jìn)遺傳算法和常規(guī)遺傳算法對最優(yōu)公交線網(wǎng)優(yōu)化方案進(jìn)行求解，兩種算法均進(jìn)行5次實驗，它們找到最優(yōu)解的迭代次數(shù)分別如圖2所示。從圖2可以清楚的看出，改進(jìn)遺傳算法找到最優(yōu)公交線網(wǎng)優(yōu)化方案的迭代次數(shù)明顯減少，加快了公交線網(wǎng)優(yōu)化問題求解的速度，可以更好滿足大中城市交通管理要求。

統(tǒng)計改進(jìn)遺傳算法和常規(guī)遺傳算法的公交線網(wǎng)優(yōu)化方案對該城市道路覆蓋率和公交乘客不需換乘百分比如表2所示。從表2可以發(fā)現(xiàn)，改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方案道路覆蓋率達(dá)到90%以上，遠(yuǎn)遠(yuǎn)高于常規(guī)遺傳算法的公交線網(wǎng)優(yōu)化方案道路覆蓋率，同時公交乘客不需換乘百分比也明顯高于常規(guī)遺傳算法的公交線網(wǎng)優(yōu)化方案，結(jié)果表明，改進(jìn)遺傳算法獲得更加理想的公交線網(wǎng)優(yōu)化方案。

4 總結(jié)

本文提出了改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方法，以最大化網(wǎng)絡(luò)直達(dá)客流量和網(wǎng)絡(luò)可達(dá)性為優(yōu)化目標(biāo)建立公交線網(wǎng)優(yōu)化數(shù)學(xué)模型，引入改進(jìn)遺傳算法對公交線網(wǎng)優(yōu)化數(shù)學(xué)模型進(jìn)行求解，并通過了仿真實驗驗證了改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化方法的有效性和優(yōu)越性。

參考文獻(xiàn)

[1] 李貞鎬，金德鵬. 基于移動大數(shù)據(jù)的城市深夜公交線路改進(jìn)方案[J].計算機工程， 2018， 44（4）： 23-27.

[2] 袁長偉，吳群琪，袁華智，等. 考慮軌道交通作用效應(yīng)的城市公交線網(wǎng)優(yōu)化方法[J]. 公路交通科技，2014，31（8）：119-125.

[3] 齊振濤，李文勇，余子威，等. 基于直達(dá)客流量的公交路徑優(yōu)化模型及求解算法[J].桂林電子科技大學(xué)學(xué)報，2016，36（5）：412-415.

[4] 錢萌，彭張節(jié)，程樹林，等. 基于綜合評價指數(shù)的城市公交線路選擇優(yōu)化模型[J]. 吉林大學(xué)學(xué)報（信息科學(xué)版），2008，7（2）：180-185.

[5] 王健，曹陽，王運豪. 考慮出行時間窗的定制公交線路車輛調(diào)度方法[J].中國公路學(xué)報， 2018， 31（5）： 143-150.

[6] 陳丹，徐文遠(yuǎn). 基于遺傳算法的軌道交通與常規(guī)公交線路優(yōu)化方案[J]. 西北大學(xué)學(xué)報（自然科學(xué)版）， 2016，46（3）：364-370.

[7] 潘若愚，褚偉，楊善林. 基于Dijkstra-PD-ACO算法的大城市公交線路優(yōu)化與評價方法研究[J].中國管理科學(xué)， 2015， 23（9）：106-115.

[8] 于曉冬，孫宇. 混合策略遺傳算法的公交線路優(yōu)化模型研究[J]. 計算機與數(shù)字工程， 2012， 40（1）： 14-15.

[9] 王寧，曹為政，儲曉雷. 采用元胞遺傳算法的軌道交通接運公交線路優(yōu)化[J]. 交通科技與經(jīng)濟， 2018，20（4）：13-18.

[10] 王佳，符卓，杜靖毅. 基于遺傳算法的城市公交骨架線網(wǎng)優(yōu)化設(shè)計[J].計算機應(yīng)用研究， 2012， 29（12）： 4518-4521，4533.

（收稿日期： 2019.02.13）