基于多目標遺傳算法的低碳公交網絡優化

譚 倩，常柱剛

(長沙市規劃設計院有限責任公司，湖南 長沙 410007)

隨著我國私人小汽車數量的迅速增長，城市交通擁堵與環境污染問題越來越嚴重.公共交通是緩解城市交通擁堵的有效途徑，但由于我國公交服務差，導致公交出行分擔率低，公共交通緩解城市交通壓力的作用沒有得到充分發揮.要提高城市公共交通出行分擔率，合理的公共交通網絡至關重要.公交網絡設計合理，可以減少出行者換乘次數，提高出行的便捷性，也會極大提高民眾公交出行的意愿.此外，盡管很多城市采用電動公交，由于電動公交續行能力有限，而且充電慢，目前還難以全面普及.混合動力的公交車更為實用.如何設計有效的公交網絡，同時盡可能減少公交碳排放量，是學者需要研究的課題.

國內眾多學者對公交網絡的設計從各個方面開展了研究.劉好德[1]以居民出行時間和無有效公交出行路徑出行量兩者出行成本最小為目標，提出了一種基于路線優選的優化模型,并引入模擬退火拉伸遺傳算法求解；滿英等[2]以居民出行時間和投資最少為目標函數，并用模擬退火-遺傳算法組合算法進行求解；趙德川等[3]以居民出行時間最短為目標函數，并提出了線路長度、非直線系數、乘客換乘系數、線路滿載率等約束條件，并用免疫遺傳算法求解；其他學者針對公交站距優化、網絡設計中考慮公交調度等方面開展研究[4-14].國外學者Lee和Vuchic先尋找出最短路，形成備選路段，再通過迭代淘汰效率低下的線路，達到優化線路目的[15]；Mariano Gallo等[16]考慮居民出行彈性需求這一因素，將出行外部成本內部化.Ceder等提出一種使公交系統時刻表同步的模型，它以發車間隔作為每條線路的變量，使不同線路的公交車同時到達換乘站點，模型較為復雜，適用于在小型網絡中求解[17]；Cevallos以線路現狀發車間隔和發車時間作為輸入，應用遺傳算法協同公交系統的時刻表，整個過程雖未建立數學模型，但通過算法使乘客換乘等待時間最短[18]；Shafahi和Fujita M，Dell等學者以公交網絡總的換乘時間最短為目標，建立了數學規劃模型達到優化公交網絡的目的[19-21].

本文引入低碳這一目標函數，兼顧居民出行和企業運營成本，綜合這三方面目標，優化公交路網.并建立雙層規劃模型，用遺傳算法進行求解.

1 問題描述與符號定義

1.1 問題描述

公交線路(公交線)一般是指在公交網絡中兩個節點間運行的一組車輛的線路，這些車輛的大小、運載能力及運營特征相同，并且每次運行所經過的節點和路段也相同.在已知城市公交客流OD以及城市路網結構情形下，考慮如何構建城市公交線路的走向，包括起點(首站)、終點(末站)以及公交線路的路徑，以實現采用盡可能少的公交車輛、乘客出行時間盡可能減少等目標.

1.2 符號定義

符號定義如下：

2 模型構建

2.1目標函數

城市公交線網的優化問題是個復雜的非線性問題，涉及因素很多，其問題的關鍵是目標函數的選取.在不同情況下，不同學者對公交線網優化的目標函數選取不同.本文從乘客利益、公交企業利益、公交可持續發展三個方面考慮，提出三個關鍵的公交線網優化目標函數.

(1)乘客總出行時間

在進行公交線網優化的過程中應首先考慮乘客利益，合理線網應盡量節約乘客出行時間，保證較低的換乘率，提高乘客公交出行的直達率.因此，乘客總出行時間最短是公交線網規劃社會整體效益最顯著的目標.

(1)

(2)公交運營成本

公交線網優化過程中，必須適當考慮公交企業的運營成本，使其能以低成本運營而獲得較好的收益，提高企業的運營活力.

(2)

(3)公共交通污染物排放量

公共交通污染物排放量反映了公交系統的環境負效應，在滿足一定的公共交通需求的前提下，污染物排放量越少，公交效率越高.

(3)

式中，h=1，2，3，4分別表示CO、CO2、NOx和CHx.

最后將三個目標函數進行加權，得到最終的目標函數：

(4)

式中，α、γ、θ為權重系數.

2.2 約束條件

考慮到城市公交的服務屬性要求，兼顧其效率與優先兩個方面的約束條件，城市城際公交網絡設計優化目標的約束條件如下：

2.2.1 公交線長度約束

公交線不宜過長也不宜過短，線路太長，會影響車輛的運行時間，增加駕駛員疲勞度，會影響到乘客等車時間.線路太短，則會增加乘客的換乘次數，相對增加了起終點的?？繒r間，影響企業效益.另外，純電動公交車還具有更加嚴格的長度限制.公交線長度約束為：

LminLmax

(5)

(6)

2.2.2 線路非直線系數的限制

如果線路拐彎過多，行駛不便，也易引起道路阻塞和交通事故頻發，但由于城市地理形勢實際限制，所有線路不可能都是直線.所以通過綜合分析，線路非直線系數不宜大于1.4.

非直線系數為：

(7)

2.2.3 直達率的限制

不能直達則會增加乘客途中時間和精力的消耗，使之感到不便，但由于經濟發展的限制，不可能讓每個乘客都直接到達目的地，所以一般需要要求直達率不能低于γmin.

(8)

2.2.4 線路負載效率系數的限制

一條線路不同部分的負載要均勻，才能提高線路運能的利用率，降低營運成本，一般情況下要求線路負載效率系數達到60%以上.

線路負載效率系數為：

(9)

式中，n為路段的總數.

2.3 雙層規劃模型

通過以上分析，建立了基于多目標的城市公交網絡設計雙層模型，上層為一個NDP問題，下層為一個基于隨機用戶平衡的公交客流分配問題.模型表示如下：

(10)

St：

LminLmax

(11)

(12)

(13)

ρ1.4

(14)

(15)

(16)

ηminηηmax

(17)

g

(18)

[TAP]：

(19)

St：

(20)

(21)

(22)

3 算法設計

雙層規劃模型是NP完全問題，路網復雜時，難以得到最優解，一般可通過智能算法求近優解.因此,本論文采用遺傳算法求解以上雙層規劃模型.

3.1 編碼

本文的遺傳算法編碼部分采用二進制方式編碼.這個模型中，先確定每條公交線路的首末站點，結合約束條件，生成多條較短路徑并編號，即各個候選路線的編號；將編號轉化為二進制，再根據線網規模大小決定編碼長度.

3.2 算法設計流程

Step1:隨機產生N個初始解，即初始種群，這一過程相當于在所有可行路線當中隨機選擇編號組合作為初始解；

Step2:設置最大進化代數，輸入交叉變異等概率參數,以及OD數據、節點距離等網絡數據；

Step3:轉到下層求解基于路徑隨機用戶平衡的公交客流分配；

Step4:根據下層的客流分配結果,轉到上層求解目標函數；

Step5:計算各個染色體的適應度，并進行選擇；

Step6:根據交叉變異參數進行染色體交叉和變異操作,并判斷是否達到結束進化條件，未達到結束條件則返回step3；

Step7:輸出結果.

4 算例分析

算例模擬在城市道路確定的情況下，公交線網的優化算法的仿真過程.算例中所使用的路網圖如下圖所示，圖中一共設置了16個節點，27條路段，并假設節點1-11、8-13、2-16和13-11四對首末站.通過模型計算出優化的公交線網組合.

圖1 仿真路網圖

給出所有節點的OD數據、距離等基礎網絡數據，每一對首末站先找出最符合約束條件的距離最短的9條線路，再將其編號轉為二進制，用Matlab編程軟件編程，利用其中遺傳算法工具箱，結合模型中的目標函數和約束條件，計算出公交線網的最優線路和組合.如圖所示：

圖2 遺傳算法計算結果

可以得到其最優解組合路線，如下表：

表1 公交路網計算結果

5 結束語

本文在現有的公交網絡設計研究的基礎上，將公交車分為純汽油/柴油公交車、混合動力公交車，建立了一個多目標公交網絡設計模型，上層模型綜合考慮了網絡的時間成本、企業運營成本以及交通網絡的CO2等碳排放總量三方面因素，下層模型為隨機用戶平衡分配模型，利用遺傳算法對模型進行求解，最后用一個簡單算例進行驗算，從這三個方面綜合考慮得出最優方案.由于影響公交出行的因素很多，模型還需考慮更多約束條件，在算法上也需進一步改善.