李雪　李茂軍　王鼎湘　成立　張家臣

摘 要：針對(duì)城市公共交通系統(tǒng)中公交優(yōu)化調(diào)度問(wèn)題的具體特征，提出一種基于狀態(tài)空間模型的實(shí)數(shù)編碼智能優(yōu)化算法（SIA）。SIA引入遺傳算法（GA）的基本理念。通過(guò)構(gòu)造狀態(tài)進(jìn)化矩陣來(lái)指導(dǎo)算法的搜索方向，再通過(guò)選種池的優(yōu)勝劣汰的選擇機(jī)理來(lái)實(shí)現(xiàn)算法朝最優(yōu)解逼近。將該算法與GA分別應(yīng)用到公交優(yōu)化調(diào)度問(wèn)題中，考慮發(fā)車(chē)時(shí)間間隔的約束，建立以企業(yè)和乘客的利益最大化為目標(biāo)的數(shù)學(xué)模型。實(shí)例仿真結(jié)果表明，SIA在尋優(yōu)精度和計(jì)算量方面優(yōu)于GA，驗(yàn)證了該算法的有效性。

關(guān)鍵詞：公交調(diào)度；時(shí)間間隔；狀態(tài)空間模型；狀態(tài)進(jìn)化矩陣；選種池

中圖分類號(hào)：U491.2TP18 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：An intelligent optimization algorithm with real strings based on state space model （SIA） was presented to solve bus dispatching problem in urban public transport system. The basic idea of genetic algorithm （GA） was introduced to SIA. The state evolution matrix was constructed to guide the search direction of the algorithm， then through the selection mechanism of selection pool to approach optimal solution. This algorithm and GA were applied to the public transport optimization dispatching problem. Mathematical model was set up by considering the time interval，and the benefit maximization of enterprises and passengers. The results of example simulation show that SIA is better than GA in optimization accuracy and amount of calculation.

Key words：pubic transport dispatching；time interval；state space model；state evolution matrix； selection pool

1 引 言

隨著現(xiàn)實(shí)世界中交通擁堵情況日趨嚴(yán)重，調(diào)節(jié)城市公共交通運(yùn)營(yíng)工作成為舒緩交通狀況、改善城區(qū)生活質(zhì)量的重要手段之一。城市公共交通運(yùn)營(yíng)工作可以轉(zhuǎn)化為公交優(yōu)化調(diào)度問(wèn)題進(jìn)行處理，而本文以公交線路發(fā)車(chē)間隔的設(shè)定來(lái)進(jìn)行公交優(yōu)化，即要求在一個(gè)調(diào)度周期（公交線路一天的運(yùn)營(yíng)時(shí)間）內(nèi)，根據(jù)車(chē)流情況，在滿足整體社會(huì)效益和經(jīng)濟(jì)效益的情況下，優(yōu)化各時(shí)段的發(fā)車(chē)時(shí)間間隔，以使得公交公司和乘客花費(fèi)成本最低。隨著對(duì)公交優(yōu)化調(diào)度問(wèn)題研究的不斷深入，國(guó)內(nèi)外許多學(xué)者提出了大量方法來(lái)解決該問(wèn)題，取得了一定的成果。如Qing和Han[1-2]等人從發(fā)車(chē)間隔對(duì)公交系統(tǒng)的影響出發(fā)，提出用遺傳算法進(jìn)行公交車(chē)發(fā)車(chē)時(shí)間間隔優(yōu)化；Gong和Cheng[3-5]等人了改進(jìn)型遺傳算法用以優(yōu)化發(fā)車(chē)頻率問(wèn)題；文獻(xiàn)[6]通過(guò)兩種算法融合，采用優(yōu)勢(shì)互補(bǔ)的特點(diǎn)為優(yōu)化公交調(diào)度問(wèn)題提供了一種有效途徑；文獻(xiàn)[7-9]則分別介紹了不同算法在求解公交調(diào)度問(wèn)題最優(yōu)解過(guò)程中的方法。

以上所提及的優(yōu)化方法對(duì)于本文進(jìn)行優(yōu)化公交車(chē)調(diào)度問(wèn)題具有重要的指導(dǎo)意義。本文提出一種基于離散系統(tǒng)狀態(tài)空間模型的實(shí)數(shù)編碼智能優(yōu)化算法[10]。由于狀態(tài)空間模型的引入不僅能把種群信息以最小信息形式描述出來(lái)，而且還能清楚顯示算法迭代尋優(yōu)過(guò)程中個(gè)體的狀態(tài)變化，因而該模型可以將問(wèn)題的求解過(guò)程表示為動(dòng)力學(xué)求解過(guò)程?；诖耍撍惴ㄍㄟ^(guò)構(gòu)造一個(gè)狀態(tài)進(jìn)化矩陣來(lái)替代遺傳算法中的交叉與變異算子功能來(lái)產(chǎn)生一組進(jìn)化解。通過(guò)選種池的選擇作用產(chǎn)生較優(yōu)解。相比于遺傳算法易陷入早熟停滯、計(jì)算量大和局部搜索能力差等缺點(diǎn)[11]，本文提出的算法具有計(jì)算量較小、計(jì)算精度較高、計(jì)算速度較快等特點(diǎn)。最后給出一個(gè)公交車(chē)發(fā)車(chē)時(shí)間間隔優(yōu)化實(shí)例，仿真結(jié)果驗(yàn)證了這種算法的有效性。

2 基于狀態(tài)空間模型的智能優(yōu)化算法

2.1 概述

近年來(lái)，國(guó)內(nèi)外有不少學(xué)者熱衷于用不同的方法來(lái)解決公交調(diào)度優(yōu)化問(wèn)題。其中，遺傳算法成為人們尋求解決優(yōu)化問(wèn)題的重要途徑，它通過(guò)迭代執(zhí)行選擇、交叉、變異三個(gè)遺傳算子的遺傳操作，使問(wèn)題的解逐步向最優(yōu)解方向靠近。本文提出的基于狀態(tài)空間模型的實(shí)數(shù)編碼智能優(yōu)化算法是一種以離散系統(tǒng)狀態(tài)空間模型為基礎(chǔ)，引入遺傳算法理念的優(yōu)化算法。它將實(shí)數(shù)編碼問(wèn)題的解方便地以狀態(tài)空間模型的方式表示，使得問(wèn)題的求解過(guò)程更直觀、高效。

基于狀態(tài)空間模型的智能優(yōu)化算法將問(wèn)題的求解過(guò)程表示為離散系統(tǒng)的動(dòng)力學(xué)求解過(guò)程，即X′（k+1）=GX（k）（1）其中，狀態(tài)向量X（k）表示為第k代群體，它是一個(gè)N×M矩陣（N表示為種群中個(gè)體總數(shù)量，M為每個(gè)個(gè)體包含的變量數(shù)）。G為狀態(tài)進(jìn)化矩陣（N×N方陣），G的構(gòu)造是本算法研究的核心內(nèi)容，可以依照遺傳算法的基本思想構(gòu)造。本文以遺傳算法的基本理念構(gòu)造G，此矩陣替代了在遺傳算法中起交叉、變異的遺傳操作。本算法采用在約束范圍內(nèi)隨機(jī)生成的方式來(lái)產(chǎn)生初始群體X（0），再通過(guò)G矩陣生成群體X′（1），即種群X（k）通過(guò)G矩陣生成新的種群X′（k+1）（k=0，1，….）。在種群X′（k+1）中判斷其個(gè)體是否滿足算法約束條件，若不滿足，則需進(jìn)行約束處理，再將包含X（k）與X′（k+1）的共2N個(gè)投入選種池。選種池是依照遺傳算法中優(yōu)勝劣汰的思想啟發(fā)而設(shè)計(jì)，通過(guò)計(jì)算2N個(gè)個(gè)體適應(yīng)度函數(shù)值選擇適應(yīng)度值較大的N個(gè)個(gè)體組成新一代群體X（k+1），再置X（k+1）為X（k），如此循環(huán)迭代，直到滿足停機(jī)條件后結(jié)束，如圖1所示。

3 SIA用于公交優(yōu)化調(diào)度

3.1 公交優(yōu)化調(diào)度問(wèn)題的數(shù)學(xué)描述

1）模型假設(shè)條件

公交發(fā)車(chē)時(shí)間間隔模型的建立要考慮到多種因素的影響，如公交公司滿意度、乘客滿意度、運(yùn)行環(huán)境等。在同一時(shí)段內(nèi)，若發(fā)車(chē)間隔較短，公交公司發(fā)車(chē)次數(shù)較多，平均每輛車(chē)的載客量減少，環(huán)境污染指數(shù)升高，不利于公交公司的經(jīng)濟(jì)效益和社會(huì)效益；若發(fā)車(chē)間隔較長(zhǎng)，乘客平均等待時(shí)間較長(zhǎng)，乘客的時(shí)間損失較大，會(huì)影響乘客的情緒，車(chē)內(nèi)人流擁擠，也會(huì)影響乘客的舒適度，從而進(jìn)一步影響乘客一天的生活和工作質(zhì)量，乘客損失費(fèi)用較高；若公交車(chē)運(yùn)行環(huán)境擁擠，平均每輛車(chē)走完全程耗時(shí)相對(duì)較多，影響公交公司和乘客的整體利益，應(yīng)適當(dāng)?shù)恼{(diào)整發(fā)車(chē)間隔，以舒緩城市交通環(huán)境。綜上所述，本文對(duì)此模型作如下假設(shè)：

（1）公車(chē)各時(shí)段運(yùn)行環(huán)境良好，且營(yíng)運(yùn)期間無(wú)特殊狀況發(fā)生；

（2）公車(chē)運(yùn)行期間為恒速行駛；

（3）公車(chē)額定載客人數(shù)相同；

（4）公車(chē)運(yùn)營(yíng)一趟的成本為固定值；

（5）同一時(shí)段公車(chē)發(fā)車(chē)頻率相同；

（6）各時(shí)段內(nèi)到達(dá)站點(diǎn)的乘客服從均勻分布；

（7）將乘客上下車(chē)時(shí)間算入等車(chē)時(shí)間；

（8）全程實(shí)行統(tǒng)一票價(jià)，票價(jià)2元/人。

2）數(shù)學(xué)模型的建立

從以上仿真結(jié)果可以看出，在α=0.7的情況下，即充分考慮公交公司利益時(shí)，發(fā)車(chē)間隔明顯比其他兩種情況大；α=0.3時(shí)，充分考慮乘客利益，發(fā)車(chē)間隔明顯比其他兩種情況小，符合現(xiàn)實(shí)情況。同時(shí)，根據(jù)表2中的客流情況可以看出，時(shí)段1和時(shí)段4的客流量相對(duì)較大，在仿真結(jié)果中，這兩個(gè)時(shí)段的發(fā)車(chē)間隔整體較其他時(shí)段小，達(dá)到了根據(jù)客流合理分配發(fā)車(chē)間隔的目的。對(duì)比GA和SIA優(yōu)化的發(fā)車(chē)間隔及其對(duì)應(yīng)的目標(biāo)函數(shù)，可以看出SIA的優(yōu)化結(jié)果明顯優(yōu)于GA，SIA有效性得到驗(yàn)證。

相較于傳統(tǒng)遺傳算法，SIA的優(yōu)勢(shì)在于，通過(guò)狀態(tài)空間模型中矩陣的乘法操作來(lái)搜索可行域區(qū)間，替代了GA的交叉和變異操作，也在一定程度上減小了算法的計(jì)算量。同時(shí)，SIA采用實(shí)數(shù)編碼，雖然需要對(duì)連續(xù)的可行域區(qū)間進(jìn)行離散化，但離散化的計(jì)算量較小。而一般情況下，GA采用二進(jìn)制編碼，編碼長(zhǎng)度決定了算法的尋優(yōu)精度，精度要求越高，算法編碼越長(zhǎng)，過(guò)長(zhǎng)的二進(jìn)制編碼在解碼的過(guò)程中大大增加了算法的計(jì)算量，影響算法效率。故在對(duì)尋優(yōu)精度要求更高的情況下，SIA的優(yōu)勢(shì)更加突出。

5 結(jié) 論

本文針對(duì)公交車(chē)調(diào)度優(yōu)化中傳統(tǒng)智能算法的不足，提出了一種基于離散系統(tǒng)狀態(tài)空間模型的實(shí)數(shù)編碼智能優(yōu)化算法。主要分析了SIA相較于GA在尋優(yōu)精度和計(jì)算量方面的優(yōu)勢(shì)。仿真結(jié)果表明，在相同的算法條件下，SIA的優(yōu)化結(jié)果明顯優(yōu)于GA，驗(yàn)證了SIA的有效性。參考文獻(xiàn)

[1] 韓印.基于遺傳算法的智能公交發(fā)車(chē)頻率優(yōu)化研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（33）：243-245.

[2] 覃運(yùn)梅，王玲玲.基于遺傳算法的公交發(fā)車(chē)間隔模型[J].交通標(biāo)準(zhǔn)化，2009，（2）：190-192.

[3] 龔成清.改進(jìn)遺傳算法在公交調(diào)度優(yōu)化中的應(yīng)用[J].微型電腦應(yīng)用，2012，28（10）：48-51.

[4] 陳玲玲，蘇勇.改進(jìn)遺傳算法在公交車(chē)優(yōu)化調(diào)度中的應(yīng)用[J].科學(xué)技術(shù)與工程，2009，9（12）：3567-3569.

[5] Jinling Du， Chunxiao Wang， Feng Zhang. Multi-objective Optimization of Bus Dispatching Based on Improved Genetic Algorithm[C]//2011 Seventh International Conference on Computational Intelligence and Security.China：IEEE，2011.

[6] Minan TANG， Enen REN， Chunyan ZHAO. Route Optimization for Bus Dispatching Based on Genetic Algorithm-Ant Colony Algorithm[C]//2009 International Conference on Information Management， Innovation Management and Industrial Engineering.China：IEEE，2009.

[7] 付阿利，雷秀娟.粒子群優(yōu)化算法在公交車(chē)智能調(diào)度中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（15）：239-241.

[8] 王敏.免疫克隆算法求解公交發(fā)車(chē)頻率問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究，2010，27（12）：4483-4485.

[9] 白子健.快速公交線路組合頻率優(yōu)化的禁忌模擬退火算法仿真[J].計(jì)算機(jī)應(yīng)用研究，2008，25（2）：355-358.

[10]李茂軍，賈玲. 一種基于狀態(tài)空間模型的進(jìn)化算法[J]. 計(jì)算技術(shù)與自動(dòng)化. 2014，33（2）：85-88.

[11]江中央.求解全局優(yōu)化問(wèn)題的混合自適應(yīng)正交遺傳算法[J].軟件學(xué)報(bào)，2010，21（6）：1296-1307.