韓天齊 宋波

摘 要：

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

關(guān)鍵詞：

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

中圖分類(lèi)號(hào)： 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 引言

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

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

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

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

1.1 相關(guān)概念

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

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

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

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

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

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

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

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

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

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

2.1 遺傳算法以及不足

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

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

改進(jìn)遺傳算法的基本思想為：如果個(gè)體適應(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)遺傳算法的公交線(xiàn)網(wǎng)優(yōu)化方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

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

[5] 王健，曹陽(yáng)，王運(yùn)豪. 考慮出行時(shí)間窗的定制公交線(xiàn)路車(chē)輛調(diào)度方法[J].中國(guó)公路學(xué)報(bào)， 2018， 31（5）： 143-150.

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

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

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

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

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

（收稿日期： 2019.02.13）