基于Hama的并行蟻群算法公交駕駛員排班問題研究.pdf

1、論文對(duì)公交駕駛員排班問題進(jìn)行論述，并研究了相關(guān)的數(shù)學(xué)模型和求解算法。針對(duì)求解算法中蟻群算法求解時(shí)間過長(zhǎng)的不足，在基于開放的分布式計(jì)算平臺(tái)Hama的基礎(chǔ)上，設(shè)計(jì)與實(shí)現(xiàn)了基于Hama的兩種并行蟻群算法模型以提高算法執(zhí)行效率。論文的主要工作如下:
　　本文首先研究了公交駕駛排班問題的現(xiàn)狀，分析了集成調(diào)度法、構(gòu)建與優(yōu)化和法生成與選擇法三種思路的優(yōu)缺點(diǎn)，討論了蟻群算法和并行蟻群算法原理，確定了求解公交駕駛員排班問題的技術(shù)路線。
　　其

2、次在研究Hama平臺(tái)的基礎(chǔ)上，提出了兩種求解公交駕駛排班問題并行蟻群算法模型:粗粒度主從式并行蟻群算法模型和粗粒度最優(yōu)解并行蟻群算法模型。這兩種模型的基本算法均采用MMAS算法，粗粒度主從式并行蟻群算法模型中使用信息素矩陣作為交互內(nèi)容，并通過設(shè)置主從節(jié)點(diǎn)的方式減少發(fā)送信息次數(shù);粗粒度最優(yōu)解并行以子蟻群的當(dāng)前最優(yōu)解及其路徑作為交互內(nèi)容。論文建立兩種并行蟻群算法模型以期提高求解效率和得到更優(yōu)結(jié)果，并詳細(xì)闡述了實(shí)現(xiàn)過程中的重點(diǎn)問題。
　

3、　最后論文選取北京市典型公交線路進(jìn)行實(shí)證分析，試驗(yàn)環(huán)境采用四臺(tái)虛擬機(jī)構(gòu)造的并行計(jì)算集群，實(shí)驗(yàn)結(jié)果表明，在單機(jī)運(yùn)算方面，普通蟻群算法求解結(jié)果與線路實(shí)際情況相比，可減少1個(gè)班型的使用，結(jié)果更優(yōu);在集群運(yùn)算方面，同普通蟻群算法相比，兩種并行算法均具有更好的求解效率，粗粒度主從式并行與粗粒度最優(yōu)解并行的可達(dá)到最大加速比分別為2.90與3.41，其中，粗粒度主從式并行的求解質(zhì)量要優(yōu)于粗粒度最優(yōu)解并行，因?yàn)榇至６戎鲝氖讲⑿胁捎眯畔⑺鼐仃嚱换サ牟呗裕?/p>