基于網(wǎng)格的遺傳算法及其在公交運(yùn)行計(jì)劃編制中的應(yīng)用研究

1、基于網(wǎng)格的遺傳算法及其在公交運(yùn)行計(jì)劃編制中的應(yīng)用研究陳琛 洪流 陳學(xué)廣 郝語嘉（華中科技大學(xué) 系統(tǒng)工程研究所 武漢 430074）摘 要： 本文利用基于網(wǎng)格的遺傳算法解決城市公共交通運(yùn)營(yíng)中的運(yùn)行計(jì)劃編制問題。首先應(yīng)用有序樣本聚類算法對(duì)城市公交歷史客流量樣本數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，然后在綜合考慮乘客待車成本和公交公司運(yùn)營(yíng)虧損等因素的前提下構(gòu)造遺傳算法的適應(yīng)度函數(shù)、編碼方式和約束條件，最后在網(wǎng)格平臺(tái)上初始化算法種群，并分配不同的子種群到網(wǎng)格的各個(gè)集群、節(jié)點(diǎn)上并行的進(jìn)行選擇、交叉、變異及計(jì)算染色體的適應(yīng)度等進(jìn)化操作，同時(shí)以一定的規(guī)律在集群和集群、節(jié)點(diǎn)和節(jié)點(diǎn)之間交換優(yōu)秀染色體，從而能快速得出滿意的運(yùn)行計(jì)劃時(shí)

2、刻表；通過仿真試驗(yàn)，證明了該方法的有效性和實(shí)時(shí)性。關(guān)鍵詞： 公共交通；有序樣本聚類；遺傳算法；網(wǎng)格；運(yùn)行計(jì)劃 中圖分類號(hào)：TP Research on grid-based genetic algorithm and its application in public transport operation plan schedulingChen Chen Liu Hong XueGuang Chen YuJia Hao（Institute of System Engineering, Huazhong University of Science and Technology, Wuhan,

3、430074, P. R. China）Abstract: To solve the problem of public transport operation plan scheduling, this paper proposes a grid-based genetic algorithm. Firstly, we do data mining in the historical passenger flow samples of urban transportation by using sequential cluster algorithm. Secondly, we constr

4、uct the fitness function, coding method and constraint condition of genetic algorithm under considering the cost of passenger-waiting and operating loss of public transport company. Finally, we initialize the populations on the Grid platform, and then distribute the subpopulations to different Grid

5、clusters and nodes for selection, crossover, and mutation, calculate the fitness of chromosome in diverse directions simultaneously and exchange the excellent chromosome between clusters or nodes in order to get the satisfactory operation plan quickly. Experiments on real data demonstrate the benefi

6、ts of the method.Key words: public transport；sequential cluster；genetic algorithm；grid；operation plan引 言收稿日期： 最終修改稿收到日期： 本課題得到國(guó)家自然科學(xué)基金（60773188）和武漢市科技計(jì)劃（200710321090-2）資助陳琛，男，1984年生，湖南人，博士生。主要研究方向：決策支持系統(tǒng)、信息系統(tǒng)工程、網(wǎng)格計(jì)算。E-mail：datocc37洪流，男，1979年生，湖北人，博士,講師。主要研究方向：決策支持系統(tǒng)、信息系統(tǒng)工程、網(wǎng)格計(jì)算等。E-mail：newtorrent陳學(xué)廣

7、,男，1947年生，湖北人，教授，博士生導(dǎo)師。主要研究方向：決策支持系統(tǒng)、信息系統(tǒng)工程、網(wǎng)格計(jì)算等。E-mail：xgchen9郝語嘉，男，1985年生，湖北人，碩士研究生。主要研究方向：決策支持系統(tǒng)、網(wǎng)格計(jì)算。E-mail：yjhao2007 遺傳算法是一類借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰的遺傳機(jī)制)演化而來的隨機(jī)化搜索方法。實(shí)踐證明，運(yùn)行計(jì)劃編制優(yōu)化模型是一個(gè)復(fù)雜的多目標(biāo)規(guī)劃問題，它必須兼顧乘客和公交公司雙方的利益，在客流量規(guī)律、線路運(yùn)行條件、公交公司運(yùn)輸能力和社會(huì)經(jīng)濟(jì)效益等約束條件下，優(yōu)化公交車輛在各個(gè)時(shí)段的發(fā)車時(shí)刻，才能使得整個(gè)城市公交線路有規(guī)律有節(jié)奏的運(yùn)行，但是隨著公交網(wǎng)絡(luò)規(guī)

8、模的擴(kuò)大，優(yōu)化問題的搜索空間急劇擴(kuò)張，利用常規(guī)方法尋找精確解已經(jīng)是一件很難或者不可能完成的任務(wù)。因此，通常人們把精力放在尋求運(yùn)行計(jì)劃滿意解的上面，而遺傳算法則是尋求這種滿意解的最佳工具。目前國(guó)內(nèi)外許多學(xué)者都致力于這方面的研究。Chales J.Malmborg等1將遺傳算法引入車輛調(diào)度系統(tǒng)中； Zhang Feizhou等2提出基于混合遺傳算法的公交智能排班方法； J. Herrera等3提出了面向網(wǎng)格的遺傳算法；2007年，D. Lim等4 又提出了基于網(wǎng)格計(jì)算的多層并行遺傳算法。在國(guó)內(nèi)，時(shí)敬梁5，賈以霞等6對(duì)公交調(diào)度的遺傳算法做了改進(jìn)。孫傳姣等7用遺傳算法研究解決快速公交中的調(diào)度優(yōu)化問題。

9、上述工作中，在網(wǎng)格平臺(tái)下使用遺傳算法的研究剛剛起步，而在使用傳統(tǒng)遺傳算法解決運(yùn)行計(jì)劃編制問題時(shí)，要么模型過于簡(jiǎn)單，使結(jié)果很難滿足公交公司對(duì)運(yùn)行計(jì)劃的有效性要求；要么模型非常復(fù)雜，求解過程緩慢，不能滿足實(shí)時(shí)性的要求。綜合考慮以上因素，本文提出了利用基于網(wǎng)格的遺傳算法來求解運(yùn)行計(jì)劃編制的新方法，其中改進(jìn)的遺傳算法保證了運(yùn)行計(jì)劃編制的有效性，而網(wǎng)格強(qiáng)大的計(jì)算平臺(tái)則保證了運(yùn)行計(jì)劃編制的實(shí)時(shí)性要求。本文第二節(jié)介紹利用基于網(wǎng)格的遺傳算法解決城市公共交通運(yùn)營(yíng)中的運(yùn)行計(jì)劃編制問題的總體思路及流程框圖；第三節(jié)闡述如何建立基于網(wǎng)格和遺傳算法的運(yùn)行計(jì)劃編制模型；第四節(jié)用實(shí)驗(yàn)對(duì)比驗(yàn)證所提模型和方法的有效性與實(shí)時(shí)性；第

10、五節(jié)總結(jié)全文工作并展望未來研究。新方法的基本思路運(yùn)用遺傳算法首選需要解決遺傳染色體的編碼問題。發(fā)車頻率的制定是公交系統(tǒng)日常運(yùn)營(yíng)工作的核心，它決定了運(yùn)行時(shí)刻表、車輛調(diào)度以及分派司機(jī)等其它的日常調(diào)度工作。傳統(tǒng)的發(fā)車頻率確定的最為重要的依據(jù)是線路客流的每日時(shí)段分布曲線，然后對(duì)客流量相似且相鄰的時(shí)段配置相同的運(yùn)力，即在這些時(shí)段內(nèi)發(fā)車間隔9固定，這里，我們對(duì)這些發(fā)車間隔進(jìn)行可變長(zhǎng)度的二進(jìn)制編碼來作為遺傳的染色體，其中使用二進(jìn)制符號(hào)0和1表示發(fā)車間隔的優(yōu)點(diǎn)在于編碼、解碼操作簡(jiǎn)單，選擇、交叉、變異等操作便于實(shí)現(xiàn)。由于公交線路客流狀況具有一定周期性和重復(fù)性，因此我們首先對(duì)城市公交的歷史客流量樣本數(shù)據(jù)進(jìn)行數(shù)據(jù)挖

11、掘，得到與算法相關(guān)的歷史樣本數(shù)據(jù)，然后使用有序聚類fisher9算法優(yōu)化公交峰值曲線的方法10合并歷史樣本數(shù)據(jù)中客流量相似且相鄰的時(shí)段，從而得到若干個(gè)時(shí)段區(qū)間。最后采用這些時(shí)段區(qū)間的最大發(fā)車間隔的二進(jìn)制編碼長(zhǎng)度作為這些時(shí)段區(qū)間對(duì)應(yīng)染色體段的長(zhǎng)度和這些時(shí)段中的最小發(fā)車間隔和最大發(fā)車間隔作為對(duì)應(yīng)染色體段的約束條件。運(yùn)行計(jì)劃的好壞在很大程度上取決于是否能夠兼顧乘客和公交公司雙方的利益：對(duì)于乘客來說待車時(shí)間越短越好，而對(duì)于公交公司來說運(yùn)營(yíng)虧損越低越好。這里我們以乘客待車成本和公交公司運(yùn)營(yíng)虧損的加權(quán)最小值作為遺傳算法的適應(yīng)度函數(shù)來評(píng)價(jià)染色體的優(yōu)異性。采用傳統(tǒng)的串行遺傳算法在計(jì)算上述適應(yīng)度函數(shù)時(shí)非常耗時(shí)，

12、再加上需要不斷產(chǎn)生新一代個(gè)體，造成運(yùn)行計(jì)劃的編制過程難以滿足實(shí)時(shí)性的要求，因此提高整個(gè)算法的運(yùn)行速度顯得尤為重要。若對(duì)計(jì)算機(jī)硬件進(jìn)行升級(jí)，則意味著投入成本增加，而網(wǎng)格計(jì)算平臺(tái)能有效利用網(wǎng)絡(luò)上閑置的計(jì)算資源（Intranet內(nèi)的計(jì)算資源），使公交公司能夠在較少的投入下獲得超級(jí)計(jì)算能力,這樣使用基于網(wǎng)格的遺傳算法將能很好地解決計(jì)劃編制的實(shí)時(shí)性問題。首先網(wǎng)格服務(wù)器利用先前確定的編碼方式將相關(guān)的歷史樣本數(shù)據(jù)編碼，形成初始種群；然后將初始種群劃分成若干個(gè)子種群并分配到各個(gè)網(wǎng)格集群上，網(wǎng)格集群再根據(jù)其網(wǎng)格節(jié)點(diǎn)的處理能力將子種群分配到各個(gè)節(jié)點(diǎn)上，此時(shí)由節(jié)點(diǎn)的每個(gè)處理器在約束條件下獨(dú)立對(duì)染色體進(jìn)行選擇、交叉、

13、變異操作，并計(jì)算操作后的染色體適應(yīng)度；每等染色體進(jìn)化一定代數(shù)后，網(wǎng)格節(jié)點(diǎn)與相鄰節(jié)點(diǎn)交換適應(yīng)度高的染色體，并淘汰適應(yīng)度低的染色體，同時(shí)將這些高的染色體形成一個(gè)新的種群提交所在集群，這個(gè)種群將會(huì)被分配到每個(gè)集群中去進(jìn)行進(jìn)化。等到集群內(nèi)所有的子種群進(jìn)化完成后選取適應(yīng)度高的滿意染色體提交到網(wǎng)格服務(wù)器，服務(wù)器將比較所有集群提交的染色體適應(yīng)度，查看適應(yīng)度最高的染色體是否滿足終止條件，如果滿足，則此染色體則是最終染色體；如果不滿足，則重復(fù)進(jìn)行上面的操作直到得到滿足終止條件的最終染色體。最后將最終染色體轉(zhuǎn)換成發(fā)車間隔，并根據(jù)始末班發(fā)車時(shí)間，得到發(fā)車時(shí)刻表，即運(yùn)行計(jì)劃。整個(gè)的流程框圖如下圖所示：圖：基于網(wǎng)格的遺

14、傳算法解決運(yùn)行計(jì)劃編制問題的總體流程圖運(yùn)行計(jì)劃編制模型基于網(wǎng)格和遺傳算法的運(yùn)行計(jì)劃編制模型構(gòu)建及其求解方法如下。.模型假設(shè)本文主要是根據(jù)獲取適應(yīng)度最大的染色體來優(yōu)化發(fā)車間隔，為了更好的進(jìn)行研究工作，我們針對(duì)公交系統(tǒng)的實(shí)際情況做出如下假設(shè)：1) 只考慮單條線路，線路和線路之間不相互影響。2) 在制定計(jì)劃之前原型系統(tǒng)有相關(guān)歷史樣本數(shù)據(jù)。3) 公汽總是嚴(yán)格按照運(yùn)行計(jì)劃排定的發(fā)車時(shí)刻發(fā)車。4) 各時(shí)段乘客到站符合均勻分布。5) 每次公汽到站，不會(huì)有乘客遺落。6) 公汽為單一類型，票價(jià)，可載客量以及每公里運(yùn)營(yíng)成本都一致。.模型輸入 為能更好地貼近公交運(yùn)行實(shí)際情況，允許模型有如下的初始輸入：1) 為線路。

15、2) 為限制最大發(fā)車間隔；為限制最小發(fā)車間隔。3) 為限制最大發(fā)車總數(shù)。4) 為公汽的可載客量；為公汽的票價(jià)。5) 為時(shí)段分區(qū)精度，單位分鐘。6) 為首班發(fā)車時(shí)間；為末班發(fā)車時(shí)間。7) 為公交公司期望車輛平均滿載率。8) 為乘客每分鐘等待的時(shí)間成本。9) 為公交車的每公里平均運(yùn)行成本。10) 為目標(biāo)函數(shù)中公交公司運(yùn)營(yíng)虧損的加權(quán)系數(shù)。11) 為目標(biāo)函數(shù)中乘客待車成本的加權(quán)系數(shù)。.模型變量 以下是模型中出現(xiàn)的相關(guān)變量定義：1) 為時(shí)段區(qū)間集。其中k表示第k時(shí)段區(qū)間，K表示時(shí)段區(qū)間總數(shù)。2) 為發(fā)車車次集。表示第k時(shí)段區(qū)間發(fā)的第i次車，表示第k時(shí)段區(qū)間發(fā)的第m次車，同時(shí)也表示第k時(shí)段區(qū)間的總的發(fā)車車

16、次。3) 為車站集。表示第個(gè)車站，表示第個(gè)車站，同時(shí)也表示線路的車站總數(shù)，可從系統(tǒng)里獲得。4) 為查找匹配輸入的歷史樣本數(shù)據(jù)。其中表示第條數(shù)據(jù)，表示第n條數(shù)據(jù)分鐘內(nèi)的客流量；為的配車數(shù)；為的最大發(fā)車間隔；為的最小發(fā)車間隔；為在第段時(shí)段分區(qū)內(nèi)最大發(fā)車間隔；為在第段時(shí)段分區(qū)內(nèi)的最小發(fā)車間隔；為所有歷史樣本在第段時(shí)段分區(qū)內(nèi)最大發(fā)車間隔；為所有歷史樣本在第段時(shí)段分區(qū)內(nèi)的最小發(fā)車間隔；為的首班發(fā)車時(shí)間；為的末班發(fā)車時(shí)間。為第條的車子滿載率。為第條在k時(shí)段j站點(diǎn)的乘客平均到達(dá)率。5) 為第j個(gè)站臺(tái)和第j+1個(gè)站臺(tái)的距離。6) 為第k時(shí)段區(qū)間的發(fā)車間隔。7) 為第k時(shí)段區(qū)間的發(fā)車數(shù)量。8) 為第k時(shí)段區(qū)間的

17、染色體編碼位數(shù)。9) 為第k時(shí)段區(qū)間的長(zhǎng)度。10) 為第k時(shí)段區(qū)間的第一車次發(fā)車時(shí)刻，也是各時(shí)段區(qū)間的開始時(shí)刻，即為首班車發(fā)車時(shí)刻。11) 為第k時(shí)段第j站的乘客平均到達(dá)率。.模型構(gòu)建1) 從樣本數(shù)據(jù)中查找滿足以下約束的L線路歷史樣本，即： (1)2) 分別累加分鐘內(nèi)歷史樣本的客流量。即公式： (2)3) 計(jì)算類直徑有序聚類法用“類直徑”來表示段內(nèi)的差異程度,段內(nèi)差異愈小,直徑就愈小。類的直徑記為,一般多采用“離差平方和”作為直徑,即： (3)其中4) 定義損失函數(shù)有序聚類法用“損失函數(shù)”來表示分割的好壞,損失函數(shù)定義為各段直徑之和，即： (4)損失函數(shù)愈小,說明段內(nèi)的差異愈小,同時(shí)也說明段間

18、的差異愈大。當(dāng)固定時(shí),使值最小的那一種分割,就是最優(yōu)分割，即： (5)5) 確定最優(yōu)分段數(shù)，計(jì)算比值，當(dāng)值比較大時(shí),就說明分成段顯然比分為段好。而且值接近于1時(shí)即可不必再往下分。6) 劃分時(shí)段區(qū)間根據(jù)和，合并客流量類似相鄰時(shí)段，可確定時(shí)段分區(qū)7) 獲得各個(gè)時(shí)段分區(qū)的發(fā)車間隔約束取得所有歷史樣本數(shù)據(jù)的在各個(gè)時(shí)段分區(qū)的最大和最小發(fā)車間隔作為時(shí)段分區(qū)的發(fā)車間隔約束，即： (6)8) 獲得各個(gè)時(shí)段區(qū)間的到達(dá)各個(gè)站點(diǎn)的乘客平均到達(dá)率，即: (7)9) 確定染色體編碼長(zhǎng)度將發(fā)車間隔的二進(jìn)制編碼作為染色體編碼，編碼位數(shù)由K時(shí)段區(qū)間的最大發(fā)車間隔決定，即： (8)其中表示取整10) 確定適應(yīng)度函數(shù)第k個(gè)時(shí)段區(qū)

19、間的派車數(shù)由該時(shí)段區(qū)間的時(shí)間長(zhǎng)度和發(fā)車間隔決定，即： (9)對(duì)于乘客來說，就是平均等待時(shí)間最少，為了方便計(jì)算，我們?cè)谶@里將他折合成費(fèi)用，即乘客的平均等待成本最低，即： (10)對(duì)于公交公司來說，就是運(yùn)營(yíng)收入最高，即客票收入減去運(yùn)營(yíng)成本最高，但考慮到目前中國(guó)公交公司一般都是虧本運(yùn)營(yíng)，則考慮運(yùn)營(yíng)虧損最低，即： (11)適應(yīng)度函數(shù)則是求兩者的加權(quán)值的最小值，即： (12)其中(12) 確定約束條件每個(gè)時(shí)段區(qū)間必須滿足該區(qū)間發(fā)車間隔約束，即： (13)發(fā)車總數(shù)應(yīng)不大于限制最大發(fā)車數(shù)，即： (14)車子的滿載率應(yīng)不小于期望滿載率，即： (15)3.5 模型求解 網(wǎng)格處理首先網(wǎng)格服務(wù)器根據(jù)按照染色體編碼方

20、式對(duì)進(jìn)行編碼形成初始種群，再將初始種群劃分成若干個(gè)子種群并分配到各個(gè)網(wǎng)格集群上，接下來網(wǎng)格集群根據(jù)其網(wǎng)格節(jié)點(diǎn)的處理能力將子種群分配到各個(gè)節(jié)點(diǎn)上，此時(shí)由節(jié)點(diǎn)的處理器在模型的約束條件下獨(dú)立計(jì)算由節(jié)點(diǎn)分配到它的染色體的適應(yīng)度，并進(jìn)行如下操作：1）選擇：此處，采用按比例的適應(yīng)度分配（proportional fitness assignment）方法，根據(jù)各個(gè)個(gè)體適應(yīng)度的概率決定其子孫遺留的可能性。若某個(gè)個(gè)體i的適應(yīng)度為,則它被選取的概率為 （16）2）重組：選擇單點(diǎn)交叉（One-point Crossover）作為遺傳算法的交叉運(yùn)算，其基本過程如下：首先將群體中的 個(gè)體以隨機(jī)方式組成 對(duì)配對(duì)個(gè)體組，

21、然后對(duì)每個(gè)個(gè)體組以概率進(jìn)行交叉運(yùn)算，先在個(gè)體編碼串中隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。交叉點(diǎn)的選擇必須保證新的個(gè)體符合約束條件。如果隨機(jī)選取的交叉點(diǎn)不能使新的個(gè)體滿足約束條件，即新產(chǎn)生的個(gè)體基因可能不完全是按升序排列的。則將交叉點(diǎn)向某個(gè)方向移動(dòng)，直到可以產(chǎn)生符合條件的新個(gè)體為止。為加快收斂速度，采用局部選擇策略，將交叉產(chǎn)生的新個(gè)體和原個(gè)體進(jìn)行比較，選擇適應(yīng)度最大的兩個(gè)作為交叉運(yùn)算的結(jié)果。3）變異：變異運(yùn)算采用均勻變異(Uniform Mutation)操作。依次指定個(gè)體編碼串當(dāng)中的個(gè)體基因座為變異點(diǎn)，對(duì)每個(gè)變異點(diǎn)以很小的變異概率從對(duì)應(yīng)基因的取值范圍內(nèi)取一個(gè)均勻分布

22、的隨機(jī)數(shù)來代替原來的基因。從可見決策變量的約束條件已經(jīng)包含在遺傳算子的設(shè)計(jì)過程中，經(jīng)過選擇、交叉、變異產(chǎn)生的新一代群體中的所有個(gè)體的表現(xiàn)型都是滿足約束條件的。當(dāng)染色體進(jìn)化到十的倍數(shù)代后，網(wǎng)格節(jié)點(diǎn)與相鄰節(jié)點(diǎn)交換適應(yīng)度高的染色體，并淘汰適應(yīng)度低的染色體，同時(shí)將這些高的染色體形成一個(gè)新的種群提交所在集群，這個(gè)種群將會(huì)被分配到每個(gè)集群中去進(jìn)行進(jìn)化。等到集群內(nèi)所有的子種群進(jìn)化完成后選取適應(yīng)度高的滿意染色體提交到網(wǎng)格服務(wù)器，服務(wù)器將比較所有集群提交的染色體適應(yīng)度，查看適應(yīng)度最高的染色體是否滿足終止條件，如果滿足，則此染色體則是最終染色體，如果不滿足，則重復(fù)進(jìn)行上面的操作直到得到滿足終止條件的最終染色體。

23、染色體解碼根據(jù)將最終染色體分為若干個(gè)區(qū)間，并利用以下二進(jìn)制轉(zhuǎn)換成轉(zhuǎn)化成十進(jìn)制的計(jì)算公式可得到各區(qū)間的發(fā)車間隔，即：= = (17)再根據(jù)始末班時(shí)間和計(jì)算得到發(fā)車時(shí)刻表，即： (18) 4 仿真試驗(yàn)為了驗(yàn)證上述模型和算法的有效性和可靠性，我們?cè)诨诰W(wǎng)格的城市公交信息管理與決策支持系統(tǒng)上實(shí)現(xiàn)了該模型和算法，并進(jìn)行了仿真試驗(yàn)。根據(jù)我們掌握的某市公交公司的歷史樣本數(shù)據(jù)及其運(yùn)營(yíng)實(shí)際特點(diǎn)，給出了如下模型輸入條件：為536線路；為20分鐘；為3分鐘；為100次；為80人；為1.2元；為60分鐘；為6：00；為23：00；為75%；為2.3133元/分鐘；為3.2元/公里。根據(jù)輸入條件，可得用于有序聚類的客流

24、數(shù)據(jù)，如表1所示： 時(shí)間段客流人數(shù)時(shí)間段客流人數(shù)時(shí)間段客流人數(shù)6:007:0030617:018:0033128:019:0045599:0110:00422610:0111:00443211:0112:00415712:0113:00399113:0114:00396314:0115:00437315:0116:00345616:0117:00369517:0118:00510818:0119:00499019:0120:00471220:0121:00312421:0122:00276522:0123:002542表1 各時(shí)間段的累加客流量對(duì)上述客流量數(shù)據(jù)進(jìn)行有序聚類，可得時(shí)段區(qū)間及其發(fā)車

25、間隔約束，如表2所示時(shí)段區(qū)間最大間隔最小間隔時(shí)段區(qū)間最大間隔最小間隔6:018:0012分鐘7分鐘8:0115:0011分鐘5分鐘15:0117:009分鐘4分鐘17:0120:008分鐘3分鐘20:0123:0013分鐘9分鐘表2 時(shí)段區(qū)間及其發(fā)車間隔約束接下來在網(wǎng)格上計(jì)算，最終可得如下時(shí)段區(qū)間發(fā)車間隔，并與該公交公司傳統(tǒng)制定發(fā)車間隔進(jìn)行對(duì)比，節(jié)省了一定的折合成本，證明了該方法的有效性，如表3所示：時(shí)段區(qū)間使用前使用后節(jié)省平均發(fā)車間隔折合成本發(fā)車間隔折合成本6:018:0011.2分鐘86336.129分鐘71321.8717.39%8:0115:008.6分鐘239481.346分鐘182

26、455.1023.81%15:0117:007.0分鐘99034.678分鐘89141.309.99%17:0120:005.3分鐘118934.517分鐘104729.3211.94%20:0123:0012.5分鐘99211.7010分鐘77431.9521.95%表3 最終發(fā)車間隔及成本對(duì)比最終可得到發(fā)車時(shí)刻表。我們對(duì)同樣的模型分別在單臺(tái)計(jì)算機(jī)和網(wǎng)格下計(jì)算，模型求解的時(shí)間分別為173.11秒和19.24秒，后者比前者節(jié)約了大量時(shí)間，證明了該方法的實(shí)時(shí)性。5 結(jié) 語本文探討了基于網(wǎng)格的遺傳算法及其在城市公交運(yùn)行計(jì)劃編制中的應(yīng)用，其中我們建立了綜合考慮乘客待車成本與公交公司運(yùn)營(yíng)成本之間的多目

27、標(biāo)規(guī)劃模型以及設(shè)計(jì)了基于網(wǎng)格的遺傳算法計(jì)算模型。通過仿真試驗(yàn)，對(duì)模型和算法的有效性進(jìn)行了驗(yàn)證和分析，結(jié)果表明該模型和算法能較好地滿足公交公司運(yùn)行計(jì)劃編制的有效性與實(shí)時(shí)性要求，可對(duì)改進(jìn)公交運(yùn)營(yíng)質(zhì)量提供較好的決策支持。但是在實(shí)際使用過程中，還存在對(duì)乘客待車成本與公交公司運(yùn)行成本間的權(quán)重因子的確定、如何克服遺傳算法的算子選擇單一以及如何選擇合適遺傳代數(shù)來進(jìn)行網(wǎng)格節(jié)點(diǎn)之間優(yōu)秀染色體交換等問題，尚需做進(jìn)一步的研究。 參 考 文 獻(xiàn)：1 Chales J.Malmborg. A genetic algorithm for service level based vehicle scheduling. Eu

28、ropean Journal of Operational Research,1996,93:121-1342 Zhang Feizhou,Yang Dongkai,Chen Xiuwan. Intelligent scheduling of public traffic vehicles based on hybrid genetic algorithm. Intelligent Transportation Systems,2003.Proceedings 2003 IEEE Volume 2:1674-16783 J. Herrera, E. Huedo, R. Montero, and

29、 I. Llorente. A grid-oriented genetic algorithm. In Advances in Grid Computing- EGC, 2005: 3153224 D. Lim, Y. Ong, Y. Jin, B. Sendhoff, and B. Lee. Efficient hierarchical parallel genetic algorithms using grid computing. Future Gener. Comput. Syst., 2007,23(4):6586705 Shi Jing-Liang, Tian shi-feng.I

30、ntelligent dispatch for public traffic vehicles based on genetic algorithm. Pattern Recognition and Artificial Intelligence.2007(5): 1679-1681(5): 1679-1681)6 Jia Yi-Xia.The application of synthetically improved genetic algorithm in public traffic dispatch system.Dalian university of technology Mast

31、er's Thesis.2007()7 Sun Chuan-Jiao, Zhou Wei, Wang Yuan. Scheduling combination and headway optimization of Bus rapid transit. Journal of transportation systems engineering and information technology,2008(10): 5-11(孫傳姣,周偉.快速公交車輛調(diào)度組合及發(fā)車間隔優(yōu)化研究.交通運(yùn)輸系統(tǒng)工程與信息,2008(10): 5-11)8 Sun Fu-Ling.The research

32、of methods for determining Bus headway. Journal of Xian highway university,1997.17(2):44-48()9 Massimo G,Annamaria N.The Kalman Fisher Approach For Time-Varying Estimation.Systems Analysis Modeling Simulation.2003,43(8):1033-104210 Yang Xin-Miao, Wang Wei.A new method for transit peak value curve op

33、timization. Journal of southeast university(natural science edition).2001,31(3)：40-43(楊新苗,王煒.公交調(diào)度峰值曲線的優(yōu)化方法.東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2001,31(3)：40-43)CHEN Chen, born in 1984, Ph.D. His research interests include decision support system, information system and grid computing.HONG Liu, born in 1979, Ph.D, lecturer. His research interests include decision support system, information system and grid com