改進遺傳算法的公交線網優化研究

韓天齊 宋波

摘 要：

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

關鍵詞：

城市公交線網; 層次性規劃; 遺傳算法; 收斂速度; 數學模型

中圖分類號： TP301

文獻標志碼： 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 引言

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

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

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

1 公交線網優化的數學模型

1.1 相關概念

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

1.2 建立公交線網優化的數學模型

根據相關研究，兩個節點i，j之間經常包括許多個可行線路，它們組成一個集合rij，線路之間相互交織形成一個公交線網，公交線網優化目標為：直達客流量最大、線網可達性最大，具體如下[10]。

（1） 直達客流量為公交網各線路的直達客流量和，如式（1）所示。

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

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

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

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

那么公交線網優化的數學模型如式（4）所示。

2 改進遺傳算法的公交線網優化方法

2.1 遺傳算法以及不足

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

2.2 遺傳算法不足的改進

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

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

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

3.3 改進遺傳算法的公交線網優化方法

3.3.1 改進遺傳算法的公交線網優化方法設計

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

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

（3） 建立適應度函數，因為適應度函數決定著種群的進化方向，結合公交線網優化問題的特點，引入動態懲罰系數構建適應度函數，具體如式（7）所示。

式中，ω表示動態懲罰系數。

（4） 選擇策略的確定，當前遺傳算法有兩種選擇策略：輪盤賭策略和錦標賽策略，相對于輪盤賭策略，錦標賽策略的穩定性更好，因此本文采用錦標賽策略選擇部分優秀個體直接進入下一代種群。

（5） 交叉和變異操作的確定，根據公交線網優化問題的特點，本文采用單點交叉概率和隨機變異方式。

3.3.2 改進遺傳算法的公交線網優化步驟

Step1：設計城市公交網絡的層次性規劃圖像，并建立公交線網優化問題的數學模型。

Step2：建立公交線網優化方案的可行解集合，初始化種群。

Step3：初始化種群中個體采用十進制方式進行編碼，每一個個體代表一種公交線網優化方案。

Step4：采用適應度函數值對每一種公交線網優化方案進行評價，并對它們進行排序。

Step5：根據錦標賽策略選擇部分適應度函數值較高的個體進入下一代種群。

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

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

Step8：判斷是否達到終止條件，若達到就輸出最優個體，不然跳轉到Step4繼續執行。

Step9：對最優個體進行解碼，得到最優的公交線網優化方案。

3 公交線網優化方法的算例分析

采用Vc++6.0語言編程公交線網優化問題求解的改進遺傳算法程序，仿真測試環境為：Intel 酷睿i3 8100 CPU，金士頓DDR3 1600 8G RAM， Windows 10操作系統為，選擇常規遺傳算法進行對比測試。改進遺傳算法的相關參數如表1所示。

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

統計改進遺傳算法和常規遺傳算法的公交線網優化方案對該城市道路覆蓋率和公交乘客不需換乘百分比如表2所示。從表2可以發現，改進遺傳算法的公交線網優化方案道路覆蓋率達到90%以上，遠遠高于常規遺傳算法的公交線網優化方案道路覆蓋率，同時公交乘客不需換乘百分比也明顯高于常規遺傳算法的公交線網優化方案，結果表明，改進遺傳算法獲得更加理想的公交線網優化方案。

4 總結

本文提出了改進遺傳算法的公交線網優化方法，以最大化網絡直達客流量和網絡可達性為優化目標建立公交線網優化數學模型，引入改進遺傳算法對公交線網優化數學模型進行求解，并通過了仿真實驗驗證了改進遺傳算法的公交線網優化方法的有效性和優越性。

參考文獻

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

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

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

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

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

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

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

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

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

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

（收稿日期： 2019.02.13）