一種改進(jìn)公交調(diào)度算法的研究

陳 艷，刁志剛

（淮安信息職業(yè)技術(shù)學(xué)院 江蘇 淮安 223002）

隨著世界城市化進(jìn)程的快速發(fā)展，城市人口逐漸增加、人們的社會(huì)生活和經(jīng)濟(jì)生活日益豐富，由此對(duì)交通的要求也越來(lái)越高，智能交通正在不斷改善人們的交通狀況。公共智能交通調(diào)度是近年來(lái)世界上受人矚目且發(fā)展迅猛的應(yīng)用研究開(kāi)發(fā)領(lǐng)域，所謂智能交通系統(tǒng)（Intelligent Transportation System，ITS），就是通過(guò)采用先進(jìn)的電子技術(shù)、信息技術(shù)、通信技術(shù)等高新技術(shù)，對(duì)傳統(tǒng)的交通運(yùn)輸系統(tǒng)及管理體制進(jìn)行改造，從而形成一種信息化、智能化、社會(huì)化的新型現(xiàn)代交通系統(tǒng)。ITS強(qiáng)調(diào)的是運(yùn)輸設(shè)備的系統(tǒng)性、信息交流的交互性以及服務(wù)的廣泛性。智能交通系統(tǒng)的7大領(lǐng)域包括:出行和交通管理系統(tǒng)、出行需求管理系統(tǒng)、公共交通運(yùn)營(yíng)系統(tǒng)、商用車(chē)輛運(yùn)營(yíng)系統(tǒng)、電子收費(fèi)系統(tǒng)、應(yīng)急管理系統(tǒng)、先進(jìn)的車(chē)輛控制和安全系統(tǒng)。由于ITS是將出行者、道路和交通運(yùn)輸工具三者作為一個(gè)整體系統(tǒng)來(lái)綜合考慮，因此使交通運(yùn)輸基礎(chǔ)設(shè)施得以發(fā)揮最大效能，車(chē)輛堵塞和交通擁擠得到有效解決，出行者的安全度和舒適度得到明顯改善，并通過(guò)節(jié)約能源和保護(hù)環(huán)境使全社會(huì)獲得巨大的社會(huì)經(jīng)濟(jì)效益。

文中提出了基于改進(jìn)遺傳算法的思想構(gòu)造了公共交通線(xiàn)網(wǎng)發(fā)車(chē)間隔優(yōu)化數(shù)學(xué)模型，將遺傳算法引入到模型求解中，重點(diǎn)對(duì)改進(jìn)遺傳算法應(yīng)用于城市公交運(yùn)營(yíng)優(yōu)化問(wèn)題的算法步驟進(jìn)行闡述。

1 遺傳算法基本原理

遺傳算法主要操作步驟如下:

1）選擇編碼策略，把參數(shù)集合X和域轉(zhuǎn)換為位串結(jié)構(gòu)空間S；

2）定義適應(yīng)度函數(shù) f（X）；

3）確定遺傳策略，包括群體規(guī)模，選擇、交叉、變異算子及其概率。

4）生成初始種群P；

5）計(jì)算群體中各個(gè)體的適應(yīng)度值；

6）按照遺傳策略，將遺傳算子作用于種群，產(chǎn)生下一代種群；

迭代終止判定。

遺傳算法涉及6大要素:參數(shù)編碼，初始群體的設(shè)定，適應(yīng)度函數(shù)的設(shè)計(jì)，遺傳操作的設(shè)計(jì)，控制參數(shù)的設(shè)定，迭代終止條件。

遺傳操作產(chǎn)生后代:遺傳算法在運(yùn)行早期個(gè)體差異較大，當(dāng)采用傳統(tǒng)的轉(zhuǎn)輪法時(shí)，即認(rèn)為后代產(chǎn)生的概率和適值大小成正比。這樣會(huì)使遺傳算法早期個(gè)別好的個(gè)體的后代充斥整個(gè)種群，造成早熟現(xiàn)象。而在遺傳算法后期，適值趨于一致，優(yōu)秀個(gè)體在后代中優(yōu)勢(shì)不明顯，從而使整個(gè)種群進(jìn)化速度趨于停滯。

計(jì)算某一代群體中某個(gè)染色體被復(fù)制產(chǎn)生下一代的概率:

式中:Ri-第i個(gè)染色體的選擇概率；fi-第i個(gè)染色體的適值；N-種群中染色體個(gè)數(shù)；S-溫度；S0-初始溫度；l-遺傳代數(shù)。

計(jì)算各染色體的累計(jì)概率λk:

式（3）在[0，l]區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)ξ。如果ξ≤A，則選擇第一個(gè)染色體進(jìn)行復(fù)制；如果λk＜ξ≤A，則選擇第ξ個(gè)染色體。如此循環(huán)N次，就會(huì)產(chǎn)生種群規(guī)模同樣為N的下一代種群。

2 改進(jìn)優(yōu)化遺傳算法描述

在GA的應(yīng)用研究中，應(yīng)從兩個(gè)方面加以深入:1）如何充分利用GA的特長(zhǎng)和優(yōu)勢(shì)，在求解問(wèn)題時(shí)發(fā)揮這些優(yōu)勢(shì)作用。這其中也包括充分利用GA現(xiàn)有的改進(jìn)成果，如已提出的優(yōu)秀遺傳算子、參數(shù)設(shè)置方法、遺傳結(jié)構(gòu)及改進(jìn)的變形GA等；2）如何加強(qiáng)GA的優(yōu)勢(shì)，如提高GA的魯棒性、適應(yīng)性等?？傊蕴岣逩A搜索效率和魯棒性為目的，以GA的結(jié)構(gòu)、基因操作和參數(shù)設(shè)置都向自適應(yīng)、自組織形式發(fā)展，并進(jìn)行系統(tǒng)綜合為主要實(shí)現(xiàn)方式的GA綜合改進(jìn)算法的研究是GA應(yīng)用研究的主要方向。本章基于這一思想，提出一種綜合改進(jìn)遺傳算法，它的主要特點(diǎn)在于它充分利用已有各種改進(jìn)算法的優(yōu)點(diǎn)，將它們和各種優(yōu)秀遺傳算子綜合在一個(gè)GA結(jié)構(gòu)中，取長(zhǎng)補(bǔ)短，協(xié)同作用，使GA的性能得到大幅度提高。

文中的綜合改進(jìn)遺傳算法采用了并行結(jié)構(gòu)，共有3個(gè)子種群I，II，III。每個(gè)種群采用不同的遺傳策略，分別以各自的方式并行執(zhí)行進(jìn)化。種群II，III的進(jìn)化采用SGA結(jié)構(gòu)，分別利用實(shí)際應(yīng)用效果較好的自適應(yīng)遺傳算法（AGA）和模擬退火遺傳算法（SAGA）執(zhí)行微進(jìn)化。為了加快進(jìn)化速度，除了種群Ⅱ，Ⅲ各自單獨(dú)的微進(jìn)化外，加入了第二層種群間的宏進(jìn)化。它將微進(jìn)化過(guò)程產(chǎn)生的較好個(gè)體保留，組成新的個(gè)體集-種群I進(jìn)行強(qiáng)進(jìn)化。該個(gè)體集以較小的交叉率（足）、變異率（只）進(jìn)行本地進(jìn)化的遺傳操作，主要用于局部搜索，以盡快發(fā)現(xiàn)最優(yōu)解。

3 算法的實(shí)現(xiàn)

為了提高GA的搜索性能，人們提出了許多改進(jìn)GA。在以后的研究中，GA的結(jié)構(gòu)、基因操作和參數(shù)設(shè)置都會(huì)向自適應(yīng)、自組織形式發(fā)展并將進(jìn)行系統(tǒng)的綜合。因此，應(yīng)將各種不同的改進(jìn)的GA綜合到一個(gè)結(jié)構(gòu)中，取長(zhǎng)補(bǔ)短，協(xié)同作用，得到功能更強(qiáng)大、性能更優(yōu)越的綜合改進(jìn)GA。

在文中的改進(jìn)GA中，包含了采用不同方法得到兩種各具特色的改進(jìn)的GA。雖然兩種GA的實(shí)現(xiàn)方式不同，但它們的基本思想是一致的，即通過(guò)GA進(jìn)化過(guò)程中遺傳算子和參數(shù)的自適應(yīng)改變，使GA在求解不同問(wèn)題或同一問(wèn)題的不同階段自動(dòng)調(diào)整各種遺傳因素的作用強(qiáng)度，以更好的適應(yīng)復(fù)雜、變化的環(huán)境。首先初始化隨機(jī)產(chǎn)生兩個(gè)子種群II，Ⅲ。而種群I通過(guò)選取II，Ⅲ中的較好個(gè)體而產(chǎn)生。

3.1 種群II的進(jìn)化

種群II采用自適應(yīng)遺傳算法，在整個(gè)進(jìn)化過(guò)程中，Pc和Pm及適應(yīng)度函數(shù)調(diào)整方案都隨著遺傳進(jìn)程作自適應(yīng)改變。

1）適應(yīng)度函數(shù)的調(diào)整

為了保證整個(gè)進(jìn)化過(guò)程中適當(dāng)?shù)倪x擇壓力，在選擇操作之前，借鑒模擬退火思想對(duì)個(gè)體適應(yīng)度進(jìn)行調(diào)整，調(diào)整公式如下:

式中fi——調(diào)整前第i個(gè)個(gè)體的適應(yīng)度；

Fi——調(diào)整后第i個(gè)個(gè)體的適應(yīng)度；

M一種群規(guī)模；

n一遺傳代數(shù)；

T—退火溫度；

To——初始溫度，可根據(jù)具體情況選擇。

這樣在溫度高對(duì)（算法的前期），適應(yīng)度很高的個(gè)體優(yōu)勢(shì)不會(huì)特別突出以至產(chǎn)生超級(jí)

個(gè)體，適應(yīng)度相近的個(gè)體產(chǎn)生后代的概率相近。而溫度不斷下降后，拉伸作用加強(qiáng)，使

適應(yīng)度相近的個(gè)體適應(yīng)度差異放大，從而使優(yōu)秀的個(gè)體優(yōu)勢(shì)更加明顯，增加了進(jìn)化后期的選擇壓力，避免了進(jìn)化遲滯現(xiàn)象。

2）自適應(yīng)公式的確定

文中采用兩點(diǎn)交叉加高段位突變功能的交叉操作，變異操作采用簡(jiǎn)單的位點(diǎn)變異，

同時(shí)為防止超級(jí)個(gè)體的產(chǎn)生，加入了強(qiáng)制變異算子，并使用Sriavivas提出的自適應(yīng)交叉、變異率。當(dāng)算法提前收斂時(shí)，加大￡和己，而在算法初期減小只和己。同時(shí)為保持優(yōu)良個(gè)體，對(duì)于高適應(yīng)度個(gè)體采用較低的只和己；對(duì)低適應(yīng)度的個(gè)體采用較高的￡和己，以利于較好個(gè)體的產(chǎn)生。自適應(yīng)公式如下:

式中fmax-群體的最大適應(yīng)度；fˉ-該群體的平均適應(yīng)度；f′-交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f-參加變異的個(gè)體的適應(yīng)度值。

3.2 種群Ⅲ的進(jìn)化

種群Ⅲ采用模擬退火遺傳算法。模擬退火算法和遺傳算法兩種算法都是全局隨機(jī)優(yōu)化算法，它們?cè)趥鹘y(tǒng)的基于梯度的優(yōu)化方法難以解決的復(fù)雜優(yōu)化問(wèn)題中顯示了優(yōu)良的求解特性，得到廣泛研究和應(yīng)用。雖然遺傳算法有較強(qiáng)的全局搜索性能，但它的爬山能力弱，在實(shí)際應(yīng)用中容易產(chǎn)生早熟收斂的問(wèn)題，且在進(jìn)化后期搜索效率較低。而模擬退火算法卻具有擺脫局部最優(yōu)點(diǎn)的能力，能抑制遺傳算法的早熟現(xiàn)象。因此，考慮將模擬退火的思想引入遺傳算法，有效地緩解了遺傳算法的選擇壓力。為了保持GA的基本特點(diǎn)不變，保留GA的優(yōu)點(diǎn)，交叉算子未作任何改動(dòng)，仍然使用自適應(yīng)交叉率。只是在變異算子中引入模擬退火機(jī)制。對(duì)任一參與變異的個(gè)體，隨機(jī)產(chǎn)生一個(gè)新個(gè)體串，若新個(gè)體的適應(yīng)度高于變異個(gè)體，則接受新個(gè)體串（即以新個(gè)體代替變異個(gè)體）；否則，以下面的概率接受新個(gè)體

其中 g=1，2，3，…；

f-變異個(gè)體的適應(yīng)度；

f′-隨機(jī)產(chǎn)生個(gè)體的適應(yīng)度；

g-隨著進(jìn)化代數(shù)而增加；

T0-初始退火溫度。

3.3 種群I的進(jìn)化

種群I為保留種群，由種群Ⅱ，Ⅲ中最好的個(gè)體構(gòu)成，各子種群每經(jīng)過(guò)一定的間隔（實(shí)驗(yàn)中取進(jìn)化8次）選擇各種群中的最好個(gè)體構(gòu)成種群I。這樣，種群I的個(gè)體質(zhì)量將始終保持較高的水平。種群I的作用主要是將3個(gè)種群產(chǎn)生的較優(yōu)個(gè)體集中在一起進(jìn)行“強(qiáng)制進(jìn)化”，在它們所形成的較優(yōu)區(qū)域內(nèi)進(jìn)行小范圍精細(xì)搜索，以盡快找到最優(yōu)解。此時(shí)，最優(yōu)解的區(qū)域已基本確定，對(duì)算法探索新搜索空間的要求大大下降，應(yīng)加強(qiáng)算法的局部搜索能力，以算法的利用性為主，提高解的品質(zhì)。為了防止交叉、變異算子對(duì)較優(yōu)個(gè)體的破壞，種群I采用較低的交叉、變異率，以取得類(lèi)似爬山算子的效果。這里取Pc=0.4，Pm=0.002。由于采用多種群同時(shí)進(jìn)化策略，各子種群以不同的方式并行執(zhí)行進(jìn)化以獲得適應(yīng)不同環(huán)境的進(jìn)化種群；該綜合改進(jìn)遺傳算法可從不同方向進(jìn)行搜索，得到各種不同的性能優(yōu)異的模式和個(gè)體。 終止循環(huán)的條件采用設(shè)定最大代數(shù)的方法。

4 流程圖

該遺傳算法的流程圖如圖1所示。

5 模擬試驗(yàn)

文中以淮安市科技局2011年立項(xiàng)項(xiàng)目 “智能公交站臺(tái)預(yù)報(bào)系統(tǒng)”公交線(xiàn)路1為例。早上第一班車(chē)的發(fā)車(chē)時(shí)間是5:30，最后一班車(chē)的發(fā)車(chē)時(shí)間是21:30，全天一共運(yùn)行960分鐘，分為20個(gè)時(shí)段，每個(gè)時(shí)段48分鐘。1路車(chē)共有20個(gè)站點(diǎn)，線(xiàn)路總長(zhǎng)為n公里。1路公交車(chē)的車(chē)型定員為35人。初次選定 α=0.5，β=0.5，種群大小為 500，初始溫度為 500，最大遺傳代數(shù)為30。經(jīng)過(guò)多次的模擬實(shí)驗(yàn)，可以得到線(xiàn)路1的由南向北的最佳的發(fā)車(chē)間隔是6 4 3 2 4 2 4 5 3 4 5 5 2 4 2 5 3 4 5 8。即發(fā)車(chē)時(shí)間依次為:5:30 5:36 5:42 5:48 5:52 5:56 6:00……6:36 6:40 6:43……7:25 7:28 7:30……8:14 8:16 8:20……9:06 9:08 9:52......10:36 10:40 10:45……11:25 11:30 11:33……12:12 12:15 12:19……13:00 13:04 3:09……13:50 13:55 14:00……14:55 15:00 15:02……15:46 15:48 15:52……16:30 16:32 16:36 16:38……17:22 17:24 17:29……18:9 18:14 18:17……18:59 19:02 19:06……19:46 19:50 19:55……20:35 20:40 20:48 20:56……21:22 21:30

圖1 算法流程圖Fig.1 Flowchart of algorithm

用同樣的方法模擬由北向南的調(diào)度時(shí)間，和由南向北的發(fā)車(chē)時(shí)間大概是一致的，這主要是因?yàn)椴煌较虻目土髁渴遣畈欢嗟?，這是因力1路車(chē)的南邊終點(diǎn)站是汽車(chē)南站，北邊終點(diǎn)站是汽車(chē)北站和火車(chē)站，這于現(xiàn)實(shí)情況也是相符的。通過(guò)以上簡(jiǎn)單的模擬試驗(yàn)，可以看出，綜合改進(jìn)的遺傳算法應(yīng)用在公交調(diào)度系統(tǒng)中，可以快速得出調(diào)度結(jié)果，具有一定的使用價(jià)值。

6 結(jié)束語(yǔ)

公共交通線(xiàn)發(fā)車(chē)調(diào)度時(shí)長(zhǎng)主要集中在優(yōu)化發(fā)車(chē)間隔、車(chē)次多少等。目前任何城市全面構(gòu)筑智能公共交通系統(tǒng)，特別是公共交通智能化調(diào)度系統(tǒng)還有一定的困難，因此實(shí)時(shí)地確定所有線(xiàn)路的發(fā)車(chē)間隔還比較困難。如果智能公共交通系統(tǒng)建立在優(yōu)化的網(wǎng)絡(luò)基礎(chǔ)上，會(huì)使其發(fā)揮更加突出的作用。本文是從公共交通線(xiàn)網(wǎng)發(fā)車(chē)間隔的調(diào)度為出發(fā)點(diǎn)，對(duì)公交網(wǎng)絡(luò)系統(tǒng)進(jìn)行優(yōu)化，提出了公共交通線(xiàn)網(wǎng)發(fā)車(chē)間隔優(yōu)化數(shù)學(xué)模型，將遺傳算法引入到模型求解中，實(shí)例證明模型和算法具有實(shí)用性和可靠性。

[1]Brouwer D R，Jansen J D，Vefring E H，et a1.Improved reservoir mangement through optimal control and continuous model updat—ing[C]//SPE Annual Technical Conference and Exhibition，Houston，Texas，U S A，2004.

[2]Sarma P，Aziz K，Durlofsky L J.Implementation of adjoint solution for optimal control of smart wells[C]//2005 SPE Resevoir Simulaiton Symposium，Houston，Texas，U S A，31 January，2005.

[3]楊曉光.先進(jìn)的公共汽車(chē)交通優(yōu)先系統(tǒng)結(jié)構(gòu) （ABPS）[C]//城市交通研究中心，2005.

[4]楊新苗.城市公交發(fā)展技術(shù)保障體系關(guān)鍵技術(shù)研究[D].南京：東南大學(xué)，2002.

[5]郭振宇.上海巴士公交信息化中的關(guān)鍵技術(shù)[D].上海：上海交通大學(xué)，2005.

[6]高自友，吳建軍，毛保華，等.交通運(yùn)輸網(wǎng)絡(luò)復(fù)雜性及其相關(guān)問(wèn)題的研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2005，5（2）：79-84.

GAO Zi-you，WU Jian-jun，MAO Bao-hua.Study on the complexity of traffic networks and related problems[J].Journal ofTransportation SystemsEngineering and Information Technology，2005，5（2）：79-84.

[7]高自友，趙小梅，黃海軍，等.復(fù)雜網(wǎng)絡(luò)理論與城市交通復(fù)雜性問(wèn)題的相關(guān)研究[J].交通運(yùn)輸系統(tǒng)與信息，2006，6（3）：41-47.

GAO Zi-you，ZAO Xiao-mei，HUANG Hai-jun.Reasearch on problems related to complex networks and urban traffic systems[J].Journal of Transportation Systems Engineering and Information Technology，2006，6（3）：41-47.

[8]張晨，張寧.上海公交網(wǎng)絡(luò)拓?fù)湫再|(zhì)研究[J].上海理工大學(xué)學(xué)報(bào)，2006，28（5）：489-494.

ZHANG Chen，ZHANG Ning.Topology research on shanghai public traffic network[J].Journal of University of Shanghai for Science and Technology，2006，28（5）：489-494.

[9]崔寶俠，姚艷君，段勇.基于改進(jìn)遺傳算法的公交智能高度[J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2010，32（4）：405-410.

CUI Bao-xia，YAO Yan-jun，DUAN Yong. Intelligent scheduling of public traffic vehicle based on improved genetic algorithm[J].Journal of Shenyang Un iversity of Technology，2010，32（4）：405-410.