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

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

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

3、　最后論文選取北京市典型公交線路進(jìn)行實證分析，試驗環(huán)境采用四臺虛擬機構(gòu)造的并行計算集群，實驗結(jié)果表明，在單機運算方面，普通蟻群算法求解結(jié)果與線路實際情況相比，可減少1個班型的使用，結(jié)果更優(yōu);在集群運算方面，同普通蟻群算法相比，兩種并行算法均具有更好的求解效率，粗粒度主從式并行與粗粒度最優(yōu)解并行的可達(dá)到最大加速比分別為2.90與3.41，其中，粗粒度主從式并行的求解質(zhì)量要優(yōu)于粗粒度最優(yōu)解并行，因為粗粒度主從式并行采用信息素矩陣交互的策略，