武可心

（西安交通工程學院交通運輸學院，陜西西安 710300）

公交網(wǎng)絡(luò)是城市公共交通系統(tǒng)的重要組成部分之一，是緩解城市交通壓力和提高交通資源利用率的重要手段?，F(xiàn)有的公交網(wǎng)絡(luò)研究成果[1-4]存在算法過于復(fù)雜、運行效率低等問題，導(dǎo)致公交網(wǎng)絡(luò)的運行資源得不到充分利用。為滿足乘客對公交運行網(wǎng)絡(luò)的需求，基于需求響應(yīng)（Demand Responsive Transit，DRT）的公交網(wǎng)絡(luò)規(guī)劃策略成為公交網(wǎng)絡(luò)優(yōu)化的重要研究方向之一，以乘客需求為導(dǎo)向，在最大限度滿足乘客需求的前提下，降低公交運營成本，增加公交收益，從而提升公交網(wǎng)絡(luò)的利用效率。其中，遺傳算法可作為路徑搜索和優(yōu)化的有效方法，適應(yīng)于公交路徑優(yōu)化問題。該文為提升遺傳算法的收斂速度和改善搜索效果，提出了一種基于優(yōu)質(zhì)選擇遺傳算法（Elitist Selection Genetic Algorithm，ESGA）的公交需求模型解算方法，并通過計算機仿真驗證了該算法的有效性和快速性。

1 公交網(wǎng)絡(luò)路徑數(shù)學建模

為了對公交網(wǎng)絡(luò)線路進行建模，需要設(shè)定一些必要的限制條件，在限定的研究區(qū)域內(nèi)，假定區(qū)域內(nèi)的乘客位置信息、乘車需求、出行費用預(yù)算等乘客信息已通過調(diào)研獲取[5]。公交公司依據(jù)所獲得的乘客信息規(guī)劃線路，以響應(yīng)乘客的出行需求，在車輛數(shù)量和容量的限制條件下，規(guī)劃公交路線的起點、終點、?？奎c以及途徑路徑，將運營利潤函數(shù)作為目標函數(shù)，通過路徑的優(yōu)化實現(xiàn)運營利潤的最大化[6-7]。建模限定條件如下：僅當乘客愿意支付的出行成本預(yù)算不小于公交公司限定最低成本時，乘客的出行需求才會得到響應(yīng)；假定乘客均會前往距離最近的站點乘車；假定區(qū)域內(nèi)的公交車輛均具有相同的起點和終點站[8]。

在公交路線數(shù)學建模中，將公交運營利潤最大化作為目標，建立目標函數(shù)公式為：

設(shè)定的約束條件一為線路中運行的公交車輛數(shù)目小于或等于區(qū)域內(nèi)擁有的車輛總數(shù)，約束公式表示為：

約束條件二為每輛公交車輛的載客人數(shù)小于或等于車輛允許乘載的最大人數(shù)，約束公式表示為：

式中，yai表示第a位乘客在第i個車站是否選擇乘車，1 表示肯定，0 表示否定；Qc表示車輛的最大載客數(shù)量。

約束條件三表示僅當乘客愿意支付的出行成本預(yù)算不小于公交公司限定最低成本時，乘客的出行需求才會得到響應(yīng)，約束公式表示為：

式中，p0表示公交公司限定的成本下限。

2 基于ESGA遺傳算法的模型求解

公交網(wǎng)絡(luò)路徑優(yōu)化主要包含站點規(guī)劃和路徑規(guī)劃兩方面的內(nèi)容，首先需要對區(qū)域內(nèi)的公交?？空军c進行優(yōu)化，這里采用K-means 聚類算法[9-10]規(guī)劃站點分布問題，該聚類算法可利用乘客所在的地理位置信息將區(qū)域分割為K個簇，將每個簇的中心位置作為站點位置，這樣可以保證每個乘客與其所在區(qū)域簇的站點距離是最短的?；贙-means 聚類算法的站點規(guī)劃流程如圖1 所示。

圖1 基于K-means算法的站點規(guī)劃流程

完成站點規(guī)劃之后，關(guān)鍵問題在于對公交線路的規(guī)劃，文中提出一種基于ESGA 遺傳算法的公交路徑模型求解方法，相對于較常用的RWSGA 遺傳算法，該方法具有更快的運算和收斂速度。ESGA 遺傳算法的主要原理是通過計算上一代群體的適應(yīng)度，按照群體的適應(yīng)度篩選出優(yōu)質(zhì)種群，然后在下一代的選擇過程中，將適應(yīng)度值較低的個體替換為優(yōu)質(zhì)種群。ESGA 遺傳算法的主要流程如圖2 所示。

圖2 ESGA遺傳算法主要流程

2.1 編 碼

在公交網(wǎng)絡(luò)中一般會存在若干條公交線路，公交線路上會分布若干站點，選用十進制的整數(shù)編碼方法對站點進行編號[11-13]，0 代表公交線路的起始站點，1，2，…,n代表對應(yīng)的站點編號。假如獲得的編碼序列號為0-2-4-5-0-4-7-0-6-8，則表示總共投入了三條公交線路，且每一條公交線路的起始站點均為始發(fā)站（0），三條公交線路經(jīng)過的路徑分別可表示為2-4-5、4-7 和6-8，最終路線均在相同終點站結(jié)束。

2.2 適應(yīng)度函數(shù)

ESGA 遺傳算法的核心問題在于利用個體的適應(yīng)度值對群體進行優(yōu)勝劣汰，實現(xiàn)優(yōu)化模型的目標值最大化，從而從中篩選出優(yōu)質(zhì)的個體，而個體的篩選主要采用適應(yīng)度值作為篩選的參考標準。在遺傳進化的過程中會出現(xiàn)一些超出約束條件的染色體，為實現(xiàn)對不良個體的篩選和剔除，主要采用的方法分為兩種，第一種是引入懲罰因子，通過增加不符合染色體的懲罰因子，以降低其在后續(xù)遺傳中的存活概率[14-15]；第二種方法是對于不滿足約束條件的染色體，對其部分基因片段進行修改，使其滿足約束條件。該文采用第一種方法，其適應(yīng)度函數(shù)表達式為：

式中，F(xiàn)代表適應(yīng)度函數(shù)，β代表固定的常數(shù)量，Qi代表在i站點上車的乘客數(shù)量，通過調(diào)節(jié)兩個參數(shù)的數(shù)值來控制懲罰因子的懲罰力度。

利用上一代群體的適應(yīng)度值，ESGA 遺傳算法篩選出適應(yīng)度值較高的個體，構(gòu)建出優(yōu)質(zhì)群體，將不滿足模型約束條件的個體適應(yīng)度置為0，在下一代篩選時，將適應(yīng)度為0 的個體替換為優(yōu)質(zhì)群體，從而通過這種選擇淘汰適應(yīng)度最低的個體。

2.3 交叉、變異和反轉(zhuǎn)操作

交叉主要通過染色體片段的交換以產(chǎn)生新的后代，交叉操作的表達式為：

變異操作是父染色體中的基因片段發(fā)生了新的變異，在種群中出現(xiàn)了新的基因信息，父染色體中的某個基因段發(fā)生變異，其表達式為：

交叉操作是隨機對兩個父體的部分片段進行互換；變異是隨機對父體的部分片段進行修改，從而提高算法對局部的搜索能力，例如原個體順序為0-2-3-5-8，隨機對站點3 和5 進行交換，交叉后的個體順序為0-2-5-3-8。反轉(zhuǎn)是將個體排列順序進行順序反轉(zhuǎn)，屬于變異的一種特殊形式，同樣可提高算法對局部的搜索能力，例如個體順序為0-2-3-5-8，反轉(zhuǎn)之后變?yōu)?-8-5-3-2。

3 仿真結(jié)果

為了驗證ESGA 遺傳算法的有效性和快速性，模擬一個限定區(qū)域，區(qū)域中的乘客總量為100 位，乘客的位置分布如圖3 所示。首先利用K-means 聚類算法將乘客劃分為10 個簇，將每個簇的中心位置設(shè)定為一個公交站點，從而得到10 個公交?？空军c的位置[16]。

圖3 乘客及站點位置分布

利用ESGA 遺傳算法對公交路徑進行解算，將種群的初始規(guī)模設(shè)定為200 個，總共進化迭代的次數(shù)設(shè)定為200 次，優(yōu)質(zhì)種群的占比設(shè)定為10%，交叉操作的隨機概率設(shè)定為85%，發(fā)生變異操作的隨機概率設(shè)定為15%，發(fā)生反轉(zhuǎn)操作的隨機概率也設(shè)定為15%，將該區(qū)域內(nèi)的公交總車輛上限設(shè)定為5 輛，每輛公交車的最大載客量設(shè)定為35 人，假設(shè)公交公司設(shè)定的最低成本為4 元，每輛車的固定成本設(shè)定為40 元，每輛車運行1 km 的單位成本設(shè)定為10 元。通過ESGA 遺傳算法的進化迭代，得到公交規(guī)劃路徑結(jié)果如圖4 所示，最終方案中共有三條公交路線。

圖4 公交規(guī)劃路徑

為了對比ESGA 遺傳算法的快速性，在相同乘客需求和群體初始條件下，對比ESGA 遺傳算法和FWSGA 遺傳算法[17-18]的收斂速度，兩種算法的迭代搜索結(jié)果如圖5 所示，由圖中曲線可以看出，ESGA遺傳算法在40 代內(nèi)完成了收斂，且搜索到最佳方案，而FWSGA 遺傳算法接近100 代才得到收斂，且最后未能收斂到最佳方案，測試結(jié)果表明相比于FWSGA 傳統(tǒng)遺傳算法，ESGA 遺傳算法具有更快的收斂速度和更優(yōu)的搜索結(jié)果。

圖5 兩種算法迭代搜索結(jié)果對比

為了進一步對比ESGA 遺傳算法和FWSGA 遺傳算法之間的差異，在相同的初始條件下，ESGA 遺傳算法分別選取不同的優(yōu)質(zhì)種群占比，優(yōu)質(zhì)種群的占比分別取5%、10%、15%，并與FWSGA 遺傳算法一起進行測試，共進行30 次相同重復(fù)實驗，不同優(yōu)質(zhì)種群占比下的測試統(tǒng)計結(jié)果如表1 所示。

表1 不同優(yōu)質(zhì)種群占比下的測試對比

由對比數(shù)據(jù)可知，ESGA遺傳算法相比于FWSGA遺傳算法，具有更高的最優(yōu)值，且隨著優(yōu)質(zhì)種群比例的增加，最優(yōu)值得到明顯的提升，ESGA 遺傳算法的平均運行時間僅略高于FWSGA 遺傳算法，當優(yōu)質(zhì)種群取15%時，兩種算法的運行時間基本相同，ESGA遺傳算法運行速度未受到較大影響。

4 結(jié)論

文中圍繞乘客需求響應(yīng)對公交路徑進行建模，將運營收益最大作為目標，同時引入多項約束條件，建立公交路徑規(guī)劃模型，使得模型更能反映公交運行時面臨的實際乘客需求問題，有利于公交路徑利用率的提升。路徑模型解算過程主要分為站點規(guī)劃和路徑規(guī)劃兩方面內(nèi)容，其中路徑規(guī)劃中創(chuàng)新性地引入ESGA 遺傳算法，通過實驗驗證了該算法的有效性和快速性。