基于ESGA 遺傳算法的公交網絡模型設計與仿真

武可心

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

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

1 公交網絡路徑數學建模

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

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

設定的約束條件一為線路中運行的公交車輛數目小于或等于區域內擁有的車輛總數，約束公式表示為：

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

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

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

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

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

公交網絡路徑優化主要包含站點規劃和路徑規劃兩方面的內容，首先需要對區域內的公交停靠站點進行優化，這里采用K-means 聚類算法[9-10]規劃站點分布問題，該聚類算法可利用乘客所在的地理位置信息將區域分割為K個簇，將每個簇的中心位置作為站點位置，這樣可以保證每個乘客與其所在區域簇的站點距離是最短的。基于K-means 聚類算法的站點規劃流程如圖1 所示。

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

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

圖2 ESGA遺傳算法主要流程

2.1 編 碼

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

2.2 適應度函數

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

式中，F代表適應度函數，β代表固定的常數量，Qi代表在i站點上車的乘客數量，通過調節兩個參數的數值來控制懲罰因子的懲罰力度。

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

2.3 交叉、變異和反轉操作

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

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

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

3 仿真結果

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

圖3 乘客及站點位置分布

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

圖4 公交規劃路徑

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

圖5 兩種算法迭代搜索結果對比

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

表1 不同優質種群占比下的測試對比

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

4 結論

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