改進(jìn)遺傳算法在公交調(diào)度優(yōu)化中的應(yīng)用

龔成清

0 引言

公交調(diào)度是影響公交系統(tǒng)運(yùn)行效率和服務(wù)水平的主要方面，是智能公交系統(tǒng)研究的核心內(nèi)容。國(guó)內(nèi)外很多學(xué)者運(yùn)用信息技術(shù)從不同的方面對(duì)公交調(diào)度優(yōu)化進(jìn)行了研究，有學(xué)者從公交車的總體利益出發(fā)，兼顧乘客利益的同時(shí)，利用免疫克隆算法求解公交發(fā)車頻率【1】；有學(xué)者通過(guò)對(duì)固定公交車車次來(lái)保證公交公司的利益，建立以乘客等車時(shí)間最小為優(yōu)化目標(biāo)的公交優(yōu)化調(diào)度模型，然后應(yīng)用模擬退火算法對(duì)模型進(jìn)行求解【2,3】；有學(xué)者從社會(huì)總體效益最優(yōu)出發(fā)，利用遺傳算法求解公交調(diào)度的頻率【4,5】；有學(xué)者結(jié)合模擬退火算法和遺傳算法的優(yōu)點(diǎn)，給出了公交調(diào)度的求解方案【6】。 已有的研究基礎(chǔ)對(duì)公交車的調(diào)度優(yōu)化有很重要的指導(dǎo)意義，但大多數(shù)模型都只是考慮公交公司的運(yùn)營(yíng)成本最小和乘客的等待時(shí)間最小兩個(gè)主要的因素，缺乏其他因素的考量。

公交車輛智能調(diào)度是一類典型的運(yùn)輸排班優(yōu)化問(wèn)題，受到很多因素的影響。本文在充分考慮到公交公司的運(yùn)營(yíng)成本最小和乘客的等待時(shí)間最小的情況下，引入了乘客坐車舒適度來(lái)建立數(shù)學(xué)模型，并改進(jìn)傳統(tǒng)的遺傳算法對(duì)模型進(jìn)行了求解。

1 公交調(diào)度優(yōu)化模型的建立

公交調(diào)度問(wèn)題是一個(gè)約束多目標(biāo)優(yōu)化問(wèn)題，即在滿足調(diào)度限制的解空間內(nèi)，尋找出滿足調(diào)度問(wèn)題的目標(biāo)函數(shù)的優(yōu)化解?！?】公交調(diào)度主要要考慮公交公司的利益和乘客利益。對(duì)乘客而言，候車時(shí)間越短越好，坐車的人越少越好；但這也意味著公交公司在同一時(shí)間內(nèi)需要調(diào)動(dòng)的車輛也就越多，導(dǎo)致公交公司的成本增加，利潤(rùn)降低。公交公司利潤(rùn)和乘客的利益是一對(duì)矛盾體，,當(dāng)一個(gè)增加（或減少）必然導(dǎo)致另一個(gè)減少（或增加），因此需要找到兩者之間的一個(gè)最好平衡點(diǎn)。本文以此為目標(biāo)，只考慮單向線路運(yùn)行情況建立公交優(yōu)化調(diào)動(dòng)模型。

為了使模型簡(jiǎn)化，本文作出以下的假設(shè)：

（1） 乘客無(wú)論從哪個(gè)站上傳，票價(jià)一律相同（設(shè)定為 2元/ 人次）；

（2） 在同一時(shí)段無(wú)論乘客多少，每輛公交車發(fā)車的頻率相同，從始發(fā)站到終點(diǎn)站的運(yùn)輸成本相同；

（3） 公交車不準(zhǔn)等客，每輛公交車的核載人數(shù)相同；

（4） 乘客均勻到站，且所有的乘客只能乘坐公交車到達(dá)目的地；

（5） 所有的乘客均自覺(jué)排隊(duì)，按照先到先上車的原則，當(dāng)車上的乘客到達(dá)滿載上限時(shí)，公交車自動(dòng)停止上客；

（6） 公交車不準(zhǔn)越站，且不考慮公交車進(jìn)站所花費(fèi)的時(shí)間和乘客上下車所花費(fèi)的時(shí)間；

（7） 不考慮公交公司的線路配車，有足夠多的公交車供調(diào)度；

（8） 站點(diǎn)均勻分布。

設(shè)某條線路的總長(zhǎng)度是L，調(diào)度周期為T(mén)k(k=1,2,3…K，設(shè)全天有K個(gè)調(diào)度時(shí)段)，在調(diào)度周期內(nèi)乘客的到達(dá)率是P，線路上的公交車站為M，共有N輛公交車在運(yùn)行，運(yùn)行速度為V，每輛公交車運(yùn)行一趟的成本為C，則周期Tk內(nèi)，公交車的總運(yùn)營(yíng)成本為：

公交車發(fā)車時(shí)間間隔為：

（Smin為最小發(fā)車時(shí)間間隔，Smax為最大發(fā)車時(shí)間間隔）

某乘客在第i站（1≤i≤M）等待第j輛公交車（1≤j≤N）的時(shí)間為：

設(shè)Ri,j是第i站第j輛公交車乘客到達(dá)的數(shù)量，則線路上乘客的總候車時(shí)間為：

把乘客的候車時(shí)間轉(zhuǎn)換為候車成本，設(shè)乘客的單位候車時(shí)間成本為a元，則乘客的總候車成本是：

則公交車調(diào)度調(diào)度模型滿足：

然而，乘客的利益除了受候車時(shí)間的影響外，乘客乘車的舒適度也是一個(gè)重要的指標(biāo)。如果車上的人太擁擠，乘客的滿意度就會(huì)降低，相當(dāng)于損害了乘客的利益，因此，把乘客的舒適度考慮進(jìn)來(lái)對(duì)模型進(jìn)行改進(jìn)。設(shè)每輛公交車的核定載客量為O，Ei,j是第i站第j輛公交車下車的乘客數(shù)量，xij為在第i站第j輛公交車乘客的坐車擁擠度，則：

設(shè)車輛的最大滿載率大于等于核定載客量的50%，且小于等于核定載客量的120%（即0.5≤xij≤1.2），根據(jù)統(tǒng)計(jì)，當(dāng)車上乘客的人數(shù)小于或等于車輛核載率時(shí)，乘客的舒適度y=1;否則y= xij;如式（8）：

加上乘客舒適度后，乘客候車的成本為：

則公交調(diào)度的優(yōu)化模型轉(zhuǎn)換為求以下問(wèn)題的最小解：

2 改進(jìn)遺傳算法求解公交車調(diào)度

遺傳算法（Genetic Algorithm）是模擬生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。遺傳算法具有較高的全局快速搜索能力，己被廣泛應(yīng)用于解決多變量的非線性問(wèn)題。但基本遺傳算法采用的是最簡(jiǎn)單的遺傳算子進(jìn)行運(yùn)算，在實(shí)際應(yīng)用中仍暴露出進(jìn)化緩慢和提前收斂等問(wèn)題。本文結(jié)合實(shí)際問(wèn)題對(duì)基本遺傳算法進(jìn)行了改進(jìn)來(lái)提高算法的運(yùn)算效率和計(jì)算的準(zhǔn)確性。

2.1 染色體編碼

根據(jù)公交調(diào)度模型特點(diǎn)，把發(fā)車時(shí)間間隔看成是遺傳算法中的染色體的基因，并采用二進(jìn)制編碼方法對(duì)其編碼。設(shè)置發(fā)車時(shí)間間隔的單位是分鐘，本文設(shè)置最長(zhǎng)的發(fā)車間隔不得大于15分鐘，因此采用4位的二進(jìn)制對(duì)其編碼，則其編碼表，如表1所示：

表1 染色體編碼

由于全天共有K個(gè)調(diào)度時(shí)段，所以每個(gè)染色體的長(zhǎng)度是4K。本文設(shè)K=4，則每個(gè)染色體的長(zhǎng)度是16。

2.2 約束條件的處理

為了使算法具有自適應(yīng)的能力，因此，必須對(duì)模型的約束條件進(jìn)行處理。罰函數(shù)是遺傳算法中有效處理約束條件的方法。按照式子（10）中的約束條件，設(shè)1λ，2λ，3λ，4λ是各個(gè)約束條件的罰函數(shù)作用強(qiáng)度的系數(shù)，則加上約束條件的新目標(biāo)函數(shù)為：

2.3 定義適應(yīng)函數(shù)和適應(yīng)值

通過(guò)建立適應(yīng)函數(shù)與目標(biāo)函數(shù)的映射關(guān)系，保證映射后的適應(yīng)值非負(fù)，而且目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)于適應(yīng)值增大的方向，也為以后計(jì)算各個(gè)體的入選概率打下基礎(chǔ)．

對(duì)于公交調(diào)度中的最小化問(wèn)題，定義適應(yīng)函數(shù)Fk，采用下述方法：

2.4 初始群體

用啟發(fā)式方法產(chǎn)生初始群體中各個(gè)個(gè)體的基因值。依次按照如下規(guī)則選擇n個(gè)染色體作為初始群體：

（1）按整個(gè)調(diào)度周期內(nèi)的最高斷面通過(guò)量確定一個(gè)染色體;

（2）隨機(jī)確定。

2.5 進(jìn)行遺傳操作產(chǎn)生后代

2.5.1 選擇

這里我們用到了適應(yīng)值的比例來(lái)作為選擇的標(biāo)準(zhǔn)，得到的每個(gè)個(gè)體的適應(yīng)值比例叫作入選概率．其計(jì)算公式如下：對(duì)于給定的規(guī)模為n的群體pop={F1, F2, F3,…, Fn}，個(gè)體Fi的適應(yīng)值為g(Fi)，則其入選概率為

利用式子（13）我們可以計(jì)算出各個(gè)個(gè)體的入選概率。計(jì)算完了入選概率后，就將入選概率大的個(gè)體選入種群，淘汰概率小的個(gè)體，并用入選概率最大的個(gè)體補(bǔ)入種群，得到與原群體大小同樣的種群。

2.5.2 交叉

交叉也就是將一組染色體上對(duì)應(yīng)基因段的交換得到新的染色體，然后得到新的染色體組，組成新的群體。單點(diǎn)交叉(One-pointCrossover)是常用的方式，即在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新個(gè)體。具體步驟為:①以隨機(jī)配對(duì)的配對(duì)策略對(duì)染色體進(jìn)行配對(duì)。把群體中的n個(gè)個(gè)體以隨機(jī)的方式配成n/2對(duì)。為了避免兩個(gè)相同的染色體交叉（重復(fù)繁殖）或兩個(gè)相近的染色體進(jìn)行交叉（近親繁殖），在給一個(gè)染色體配對(duì)時(shí)，先把還未被配對(duì)的染色體逐一判斷與該染色體之間的差異性，再選擇差異性最大的染色體與之配對(duì)。②以Pc的概率選擇配對(duì)好的染色體進(jìn)行交叉操作。對(duì)要進(jìn)行交叉操作的染色體對(duì)隨機(jī)選擇交叉點(diǎn)的位置，互換交叉點(diǎn)之后的基因。兩個(gè)個(gè)體的在9號(hào)基因的位置交叉過(guò)程，如表2所示：

表2 兩個(gè)個(gè)體交叉的過(guò)程

2.5.3 變異

在基本遺傳算法中，變異算子通常采用對(duì)群體中的個(gè)體碼串隨機(jī)挑選一個(gè)或多個(gè)基因值做變異，變異操作是隨機(jī)的，這樣會(huì)阻礙搜索效率的提高，有時(shí)甚至?xí)霈F(xiàn)大量無(wú)為的冗余迭代。本文利用蟻群算法具有局部搜索能力強(qiáng)和收斂速度比較快等優(yōu)點(diǎn)，【8，9】通過(guò)蟻群算法來(lái)引導(dǎo)變異，加快遺傳算法的收斂速度，提高算法的效率。蟻群算法在遺傳變異中的應(yīng)用具體如下：

經(jīng)過(guò)選擇和交叉操作，首先在當(dāng)前群體n中找出最優(yōu)染色體X0，并將其視為較優(yōu)解，然后從X0出發(fā)，利用蟻群算法，用m（m＞16）只螞蟻來(lái)尋找更優(yōu)秀的染色體。每只螞蟻根據(jù)信息素的濃度，以的概論選擇X0的一個(gè)基因：

2.6 終止條件

傳統(tǒng)的遺傳算法終止條件是通過(guò)固定遺傳代數(shù)，到達(dá)后即中止。固定遺傳代數(shù)若設(shè)置不當(dāng)，會(huì)出現(xiàn)遺傳代數(shù)過(guò)多，增加迭代的次數(shù)，遺傳代數(shù)過(guò)少，可能得到的是局部最優(yōu)解的情況。本文以判斷種群是否己經(jīng)成熟并不再有進(jìn)化趨勢(shì)作為終止條件，即判斷迭代的過(guò)程中，若出現(xiàn)連續(xù)10代的染色體均小于或等于固定閥值ε時(shí)，則終止算法的運(yùn)行。

3 實(shí)例應(yīng)用

本文選取我國(guó)一座特大城市某條公交線路為例子，該條公交線路里程共14公里，設(shè)14站，公交公司配給該線路同一型號(hào)的大客車，每輛標(biāo)準(zhǔn)載客 100人，據(jù)統(tǒng)計(jì)客車在該線路上運(yùn)行的平均速度為20公里／小時(shí)。下面給出的是典型的一個(gè)工作日早上 5點(diǎn)到9點(diǎn)從A13到 A0上下車的乘客數(shù)量統(tǒng)計(jì)，如表3所示：

表3 某條公交線路的客流調(diào)查和運(yùn)營(yíng)資料

A7 A8下 81 800 1793 971上 48 315 523 271下 45 542 1097 621上 90 594 868 549 A9 A10 A11下 48 588 1058 634上 76 589 948 477下 20 239 461 300上 43 256 447 235下 13 164 272 169上 52 333 528 305下 9 105 227 123 A12上 60 376 634 322下 8 99 205 106 A13上 371 1990 3626 2064下 0 0 0 0

根據(jù)統(tǒng)計(jì)的數(shù)據(jù)和結(jié)合表3中的數(shù)據(jù)，設(shè)置算法的主要參數(shù)，如表4所示：

表4 算法的主要參數(shù)

在 matlab中，對(duì)模型分別用基本遺傳算法和本文改進(jìn)的遺傳算法進(jìn)行求解，得到的數(shù)據(jù)，如表5所示：

表5 不同算法求解模型對(duì)比

7：00—8：00 8：00—9：00基本遺傳算法 1 380本文算法 1 265基本遺傳算法 3 320本文算法 2 246

由算法的結(jié)果可以看出，隨著客流數(shù)據(jù)量的增大，兩種算法的迭代次數(shù)都增加?；具z傳算法在5：00—6：00發(fā)車時(shí)段出現(xiàn)了提前收斂的現(xiàn)象，求解結(jié)果只是局部最優(yōu)，有較大的誤差。而引入了蟻群引導(dǎo)變異的遺傳算法不僅可以加快算法收斂的速度，比基本的遺傳算法求解模型不僅要更快，更高效，而且具有更高的精確度。實(shí)驗(yàn)結(jié)果也證明了這一點(diǎn)。

結(jié)語(yǔ)

公交車調(diào)度問(wèn)題的研究是十分復(fù)雜的。[10]把調(diào)度問(wèn)題抽象成為一個(gè)數(shù)學(xué)模型，通過(guò)加入了乘車的舒適度這一因素的考量，以求模型能更全面地反映乘客坐車的感受。利用蟻群算法的正反饋原理，在傳統(tǒng)的遺傳算法中融入蟻群算法，建立了自適應(yīng)的遺傳算法來(lái)有利于模型的求解。模型還沒(méi)有考慮乘客上下車的延時(shí)和站點(diǎn)的不均勻分布的情況，這是今后要改進(jìn)的方向。

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

[2]鄭小花,陳淑燕,武林芝. 模擬退火算法在公交調(diào)度中的應(yīng)用[J].信息化研究,2009,35(9):45-47

[3]白子建，宋瑞，賀國(guó)光．快速公交線路組合頻率優(yōu)化的禁忌模擬退火算法仿真[J].計(jì)算機(jī)應(yīng)用研究,2008,25(2):355—358

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

[5]CEVALLOS F, ZHAO Fang. A genetic algorithm for bus schedule synchronization[C]//Proc ofAATT 2006.2006:737-742

[6]任傳祥．混合遺傳一模擬退火算法在公交智能調(diào)度中的應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2005，17(9)：2075-2081

[7]王琳,王蕾云,王潔琳,潘 峰.城市公交調(diào)度優(yōu)化模型及算法研究[J].城市公共交通，2010.10：37-39

[8]肖宏峰,譚冠政. 基于遺傳算法的混合蟻群算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2008,44(16):42-45

[9]方旺盛,肖琴. 蟻群算法的收斂性分析及其在TSP上的求解[J]. 計(jì)算機(jī)與數(shù)字工程,2007,35(9):46-48

[10]賀學(xué)海， 劉永建. 公交車調(diào)度問(wèn)題的數(shù)學(xué)模型[J].河南科學(xué),2009,27(6):653-659