遺傳算法用于公交調(diào)度問題的研究

朱良學(xué)

（酒泉職業(yè)技術(shù)學(xué)院，甘肅 酒泉 735000）

公交調(diào)度[1，2]是公交企業(yè)效益的重要參照，也是衡量公交企業(yè)服務(wù)水平的一項重要指標。提升、優(yōu)化公交調(diào)度水平是增強公交企業(yè)核心競爭力、提高企業(yè)效益的一項重要舉措。

1 公交調(diào)度數(shù)學(xué)模型[3-5]

在加速推進城市化進程的過程中，激增的城市居住人口使城市規(guī)模漸趨龐大，城市居民的出行問題也日漸突出。過去一個簡單的解決問題的做法是：適時增加線路、車輛、車次。但當(dāng)城市規(guī)模達到一定程度時，結(jié)果就是帶來更嚴重的擁堵，居民工作生活更加不便。顯然，這種簡單落后的管理理念和經(jīng)營模式已無法滿足現(xiàn)代城市交通新環(huán)境的現(xiàn)實需求，當(dāng)然也無法實現(xiàn)乘客和公司的利益目標。

人工智能為公交車輛運營調(diào)度提供了一種新思路：對問題建立優(yōu)化數(shù)學(xué)模型，利用智能算法對問題解空間進行高效搜索，在有效時間內(nèi)找到滿意解,形成合理高效調(diào)度方案。通過實驗證明，在解決城市公共交通問題的探索過程中，這種思路是很有效的。

所謂高效的公交車輛調(diào)度,通俗的說，就是在一定的約束條件下, 在一條運營線路上，怎樣合理安排車輛資源、運營時間及運行次序, 從而使線路的運營效率（減低運輸成本，優(yōu)化作業(yè)時間）提高，也使得乘客和公司的雙方權(quán)益得到保證。

而在現(xiàn)實情況下，公交公司希望在發(fā)車時間段盡可能少發(fā)車次，增大發(fā)車時間間隔，提高每一車次車輛滿座率，以期減少運營成本，使收益最大化；乘客則希望等車時間盡可能短一點，發(fā)車更快捷。顯然利益訴求的不同導(dǎo)致了這一矛盾，解決矛盾的方法在于找到公交公司與乘客都能接受的一種方案，這個方案既能保證公司的合法收益，也能使乘客滿意。本文正是基于這一點，在考慮乘客與公交公司各自利益的基礎(chǔ)上，提出了反映乘客訴求的滿意度函數(shù)和保證公交公司收益的滿意度函數(shù)，建立了數(shù)學(xué)模型。

2 模型建立

2.1 模型

通過簡化研究對象把實際問題抽象為一個數(shù)學(xué)問題，是研究解決實際問題的一條基本思路。這里做以下簡化假定：該條行車線路為單行線路，共有n 站，每天的運營時間分為k 個時段；行車車輛為同一車型，滿載人數(shù)都一樣；乘客上下車時間短到可以忽略不計；車輛在各站之間以正常勻速行駛，每站之間運行時間也保持正常穩(wěn)定。

2.2 各站點候車乘客數(shù)分析

現(xiàn)在以J 城市的一條公交線路來舉例。對于這個具有n 個站點的線路來說，每天的運營時間可劃分為k 個時段，通過統(tǒng)計的手段可以獲得一個所謂最正常工作日內(nèi)n 個站點在k 個時段內(nèi)上車人數(shù)和下車人數(shù)的典型情形，這些數(shù)據(jù)是制訂車輛調(diào)度表的重要依據(jù)和基礎(chǔ)。

經(jīng)過統(tǒng)計，n 個站點中第i 個站點在k 個時段上車人數(shù)的分布可以應(yīng)用圖1 來描述，K 個時段分別t1，t2，……tK。

圖1 站點上車人數(shù)曲線（時間）

同樣的方法可以得到n 個站點中第i 個站點在k 個時段下車人數(shù)的分布。這樣我們就得到了n 個站點中第i 個站點在k 個時段乘客的流量分布情形。根據(jù)統(tǒng)計取得的數(shù)據(jù)，將這種情形擬合成一個函數(shù)Hji(t)，并且這個函數(shù)Hji(t)是可導(dǎo)的，即dji(t)=H'ji(t);Hji(t)表示從每天的起始時刻到t 時刻，第j 趟車在第i 個站點達到的總乘客人數(shù)，dji(t)表示t 時刻第j 趟車在第i 站的乘客人數(shù)到站率。

2.3 公交調(diào)度中乘客的滿意度函數(shù)

乘客的滿意度主要考慮的因素是候車時間，假定用L 表示最長候車時間，例如在高峰時段可取值為6 min，即L=6，平時一般時段為L=10 左右等。這樣，乘客人數(shù)中候車時間低于最長候車時間的人相對比較滿意。采用比較簡約的表示，乘客滿意度可用所有乘客中候車滿意人數(shù)所占的比例來描述。假定該線路n 個站點在K 個時段共發(fā)車m 趟，在t 時刻，第j 趟車到達第i 站的滿意人數(shù)可以表示為：

式中，tij為第j 輛車到達第i 站的時間;t 為候車滿意時間上線；在t 時刻，在第i 站，第j 趟車的乘客到站率dji(t); 在t 時刻，在第i 站，等候第j 輛車的乘客數(shù)Wij=dji（t）dt；在t 時刻，在第i 站，登上第j 輛車的乘客數(shù)Cij。這樣，乘客候車滿意度函數(shù)就可以如下描述：

其中，總發(fā)車數(shù)用m 表示;首末班車時刻用T1、T2表示。

2.4 公交企業(yè)的滿意度函數(shù)

公交線路利潤=線路運營總收入-線路運營總成本，只有利潤＞=某個合理值時，企業(yè)才會滿意，否則企業(yè)就沒有經(jīng)營發(fā)展的動力。提高利潤的核心顯然在于提高公司的運營效率，具體反映在每天發(fā)車的數(shù)量和乘車的人數(shù)，只有發(fā)車的數(shù)量和乘車的人數(shù)達到一個均衡值，企業(yè)的效益才會最大化。從這個思路出發(fā)，先只考慮一天的情況如下：在第i 站，登上第j 輛車的乘客數(shù)Cij，線路n 個站點在K 個時段共發(fā)車m 趟，這天乘客總數(shù)即為：

3 遺傳算法

遺傳算法(GeneticAlgorithms，簡稱GA)，由J.Holland于1975 年基于自然選擇和遺傳原理提出。它的主要思想是：通過對問題編碼，先構(gòu)建一個初始種群，構(gòu)成問題初始解空間；解空間中每一個個體編碼就是一個染色體；根據(jù)問題實際情況設(shè)計復(fù)制、交叉和變異等算子；對解空間中每一個染色體施加復(fù)制、交叉和變異等操作，生成新的“進化”后問題解空間；用適應(yīng)度函數(shù)對種群中迭代“進化”后的染色體進行選擇，在此過程中，適應(yīng)度值低的個體被淘汰，適應(yīng)度值高的個體“延續(xù)”下來。經(jīng)過這樣多次對種群不斷迭代“進化”，直至最終種群收斂，找到“最適應(yīng)環(huán)境”的個體。這個個體即是求解問題的最優(yōu)解或者滿意解。顯然，它是對生物在大自然中遺傳進化過程的模擬，是一種具有高度并行性的隨機搜索算法。

遺傳算法的步驟如下。

（1） 產(chǎn)生初始種群。設(shè)定一個種群數(shù)，按這個數(shù)生成一定數(shù)量的遺傳個體，形成初始種群，亦即解空間，它包含了所有可能的解情形。

（2） 設(shè)計適應(yīng)度函數(shù)。對解空間中每個染色體個體計算其適應(yīng)度函數(shù)值；以適應(yīng)度函數(shù)值作為評價個體優(yōu)劣的標準，優(yōu)勝劣汰。

（3） 選擇。淘汰適應(yīng)度值低的個體，種群解空間中只留下那些適應(yīng)度值較高的染色體個體。

（4） 設(shè)計變異算子。將設(shè)計的變異算子運算于染色體，產(chǎn)生新個體。

（5） 生成新種群。

（6） 判斷是否滿足問題滿意條件。如果滿足,執(zhí)行步驟（7）；如果不滿足,執(zhí)行步驟（2）。

（7） 輸出最優(yōu)化結(jié)果。

4 禁忌搜索算法

禁忌搜索算法(TabuSearch,簡稱TS)是由Glover 等人于1986 年提出，其類似于模擬問題解決過程中在求解空間中摸索尋找答案的一個“爬山”過程，實現(xiàn)全局逐步搜索尋優(yōu)。它的基本思想是：在解空間的搜索過程中，對其中已經(jīng)搜索過的局部最優(yōu)解。

記錄下來；在后面進一步迭代搜索中，把搜索結(jié)果與局部最優(yōu)解記錄比較，凡是一致的，盡可能避開，這樣就消除了這些局部最優(yōu)解的欺騙性干擾；將搜索過程轉(zhuǎn)向解空間的其他區(qū)域。如此，完成一個“爬山”過程，從而避免解空間過早收斂，即所謂“早熟”，使獲得更好全局最優(yōu)解的可能性大大增加。

5 用遺傳算法與禁忌搜索算法結(jié)合解決公交調(diào)度問題

5.1 遺傳算法與禁忌搜索算法結(jié)合

GA 的優(yōu)點很顯著，并行搜索能力強,有良好的全局搜索能力，能快速找出解空間中的全部解。因此比較適合求解解空間規(guī)模龐大、目標函數(shù)簡潔啟發(fā)性好的全局優(yōu)化問題。GA 算法的局限性也很明顯，局部搜索能力不好，所花費的時間成本高，特別是在迭代后期，搜索效率低，易發(fā)生早熟收斂現(xiàn)象。

TS 算法具有的記憶能力和設(shè)定藐視準則。由于記住了在前面搜索過程中獲得的以往的局部最優(yōu)解，在后續(xù)搜索時就能夠跳出這些局部最優(yōu)解，搜索過程中又可以接受劣解，這就極大地提高了獲得更好的全局最優(yōu)解的可能性。另一點是TS 彌補了GA 局部搜索能力不好的不足，因此是一種較優(yōu)的全局迭代尋優(yōu)算法。

因此，在解決實際問題的過程中，如果能將遺傳算法與禁忌搜索算法有效結(jié)合, 這樣既能保留遺傳算法全局搜索能力強的優(yōu)點，又能發(fā)揮禁忌算法可“爬山”、局部搜索能力好的長處，就能極大地提高在解決實際問題的過程中獲得最優(yōu)解的能力。具體思路是：在遺傳算法進化搜索過程中,利用禁忌算法的記憶能力，構(gòu)造出一個新的重組算子；再通過一個禁忌表，用來記錄種群各染色體個體的適應(yīng)值；在搜索過程中，這個新重組算子使用禁忌表，減少適應(yīng)值較小的染色體個體出現(xiàn)的次數(shù)，這樣就使種群盡可能保持染色體結(jié)構(gòu)的多樣性；通過在遺傳算法中“插入”禁忌算法以提高遺傳算法的“爬山”能力, 在局部搜索中用禁忌搜索算法作為遺傳算法的變異算子，抑制早熟，加速收斂。

5.2 遺傳算法與禁忌搜索算法結(jié)合的求解步驟

（1） 參數(shù)設(shè)定。本算法中最大迭代次數(shù)為CMax，種群規(guī)模為Zqun，交叉概率用pc表示，變異概率為pm表示。

（2） 產(chǎn)生初始種群。

（3） 設(shè)計適應(yīng)度函數(shù)，并用適應(yīng)度函數(shù)計算出當(dāng)前代種群（解空間）中每個個體染色體的適應(yīng)值。

（4） 選擇。按照截斷方式選出Zqun個染色體,放入交叉池。

（5） 交叉。具體操作如下：

①在[0，1]之間生成一個隨機數(shù)ri，其中i=1，2，…Zqun；如果該生成的隨機數(shù)ri≤pc，則選擇交叉池中第i個染色體作為交叉的父代，產(chǎn)生pc×Zqun個父代染色體。

②對每對雙親運行交叉算子，產(chǎn)生2 個子后代。

③調(diào)用新構(gòu)造出的重組算子，對交叉后得到的子后代再進行交叉操作。

（6） 變異。具體操作如下：在[ 0，1]之間生成一個隨機數(shù)ri，其中i= 1，2，…，Zqun；如果ri≤pm，則調(diào)用新構(gòu)造出的重組算子對交叉池中第i 個染色體運行變異操作。

（7） 產(chǎn)生新的種群。

（8） 如果還未達到最大迭代次數(shù)CMax，返回執(zhí)行步驟（3），否則，輸出最優(yōu)解，算法結(jié)束。

6 實例結(jié)果及分析

J 城市該線路全線共18 個站點，線路全長10 km；線路首班車6:30 發(fā)車，末班車20:20 收車；車輛統(tǒng)一為普通車輛，額載24 人，最大載客數(shù)為40 人；單車成本R=17 元;單一票價為1 元。

考慮到計算量和實驗條件的局限，通過測試確定參數(shù)值如下：變異概率取pm=0.01，交叉概率取pc=0.8，群體規(guī)模取Zqun=200，迭代次數(shù)取Ngen=300，禁忌表的大小為Zqun×0.6，破禁策略根據(jù)適應(yīng)值確定。

表1 是遺傳算法與禁忌搜索算法結(jié)合實驗所得的結(jié)果。

表1 發(fā)車間隔及滿意度

從實驗可以看出，在所有時間段，要使兩者滿意度都達到最高或較高值是比較有難度的，尤其在6:30～7:00，12:00～16:30，18:00～20:20 這些時間段，還需要調(diào)整發(fā)車間隔和發(fā)車次數(shù)，以避免一方滿意度較高另一方滿意度極低的情況發(fā)生。

7 結(jié)論

本文構(gòu)建的模型考慮了乘客和企業(yè)雙方的利益，建立了乘客滿意度、企業(yè)滿意度目標函數(shù)。將遺傳算法與禁忌搜索算法相結(jié)合，設(shè)計了新的重組算子和變異算子；通過將禁忌搜索算法作為遺傳算法的變異算子，克服了傳統(tǒng)遺傳算法“過早收斂”和“爬山”能力差的缺點。從仿真實驗結(jié)果可以看出，對于公交調(diào)度優(yōu)化問題，通過合理設(shè)計兩者滿意度函數(shù)，將遺傳算法和禁忌搜索算法相結(jié)合，在合理的種群規(guī)模和進化代數(shù)下，能夠找到使乘客和企業(yè)雙方都滿意的調(diào)度方案，有效地解決公交調(diào)度優(yōu)化問題。