遺傳算法用于公交調度問題的研究

朱良學

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

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

1 公交調度數學模型[3-5]

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

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

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

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

2 模型建立

2.1 模型

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

2.2 各站點候車乘客數分析

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

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

圖1 站點上車人數曲線（時間）

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

2.3 公交調度中乘客的滿意度函數

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

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

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

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

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

3 遺傳算法

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

遺傳算法的步驟如下。

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

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

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

（4） 設計變異算子。將設計的變異算子運算于染色體，產生新個體。

（5） 生成新種群。

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

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

4 禁忌搜索算法

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

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

5 用遺傳算法與禁忌搜索算法結合解決公交調度問題

5.1 遺傳算法與禁忌搜索算法結合

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

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

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

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

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

（2） 產生初始種群。

（3） 設計適應度函數，并用適應度函數計算出當前代種群（解空間）中每個個體染色體的適應值。

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

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

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

②對每對雙親運行交叉算子，產生2 個子后代。

③調用新構造出的重組算子，對交叉后得到的子后代再進行交叉操作。

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

（7） 產生新的種群。

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

6 實例結果及分析

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

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

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

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

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

7 結論

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