本文關(guān)鍵詞：基于Hama的并行蟻群算法公交駕駛員排班問(wèn)題研究，由筆耕文化傳播整理發(fā)布。

【摘要】：論文對(duì)公交駕駛員排班問(wèn)題進(jìn)行論述,并研究了相關(guān)的數(shù)學(xué)模型和求解算法。針對(duì)求解算法中蟻群算法求解時(shí)間過(guò)長(zhǎng)的不足,在基于開(kāi)放的分布式計(jì)算平臺(tái)Hama的基礎(chǔ)上,設(shè)計(jì)與實(shí)現(xiàn)了基于Hama的兩種并行蟻群算法模型以提高算法執(zhí)行效率。論文的主要工作如下：本文首先研究了公交駕駛排班問(wèn)題的現(xiàn)狀,分析了集成調(diào)度法、構(gòu)建與優(yōu)化和法生成與選擇法三種思路的優(yōu)缺點(diǎn),討論了蟻群算法和并行蟻群算法原理,確定了求解公交駕駛員排班問(wèn)題的技術(shù)路線。其次在研究Hama平臺(tái)的基礎(chǔ)上,提出了兩種求解公交駕駛排班問(wèn)題并行蟻群算法模型：粗粒度主從式并行蟻群算法模型和粗粒度最優(yōu)解并行蟻群算法模型。這兩種模型的基本算法均采用MMAS算法,粗粒度主從式并行蟻群算法模型中使用信息素矩陣作為交互內(nèi)容,并通過(guò)設(shè)置主從節(jié)點(diǎn)的方式減少發(fā)送信息次數(shù)；粗粒度最優(yōu)解并行以子蟻群的當(dāng)前最優(yōu)解及其路徑作為交互內(nèi)容。論文建立兩種并行蟻群算法模型以期提高求解效率和得到更優(yōu)結(jié)果,并詳細(xì)闡述了實(shí)現(xiàn)過(guò)程中的重點(diǎn)問(wèn)題。最后論文選取北京市典型公交線路進(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)榇至６戎鲝氖讲⑿胁捎眯畔⑺鼐仃嚱换サ牟呗?可以使搜索空間更大,在搜索過(guò)程中更有可能找到較優(yōu)解。本文研究的基于Hama的并行蟻群算法在選擇并行計(jì)算模型,設(shè)計(jì)并行蟻群交互策略等方面上具有一定的指導(dǎo)意義。
【關(guān)鍵詞】：公交駕駛員排班問(wèn)題 蟻群算法 并行 Hama 粗粒度主從式 粗粒度最優(yōu)解
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：U491.17;TP18
【目錄】：

• 致謝5-6
• 中文摘要6-7
• ABSTRACT7-15
• 1 引言15-19
• 1.1 研究背景與意義15
• 1.2 研究方法15-16
• 1.3 研究路線16-19
• 2 國(guó)內(nèi)外研究現(xiàn)狀19-31
• 2.1 公交駕駛員排班問(wèn)題綜述19-20
• 2.2 蟻群算法研究綜述20-25
• 2.3 并行計(jì)算模型與框架發(fā)展綜述25-29
• 2.4 本章小結(jié)29-31
• 3 公交駕駛員排班問(wèn)題模型與求解方法31-41
• 3.1 駕駛員排班問(wèn)題的相關(guān)概念31-33
• 3.2 公交駕駛員排班問(wèn)題的模型33-34
• 3.3 公交駕駛員排班問(wèn)題的求解34-39
• 3.3.1 生成可行班型35-36
• 3.3.2 基于蟻群算法求解的基本步驟36-39
• 3.4 本章小結(jié)39-41
• 4 基于HAMA的并行蟻群算法設(shè)計(jì)與實(shí)現(xiàn)41-61
• 4.1 BSP模型與Hama框架平臺(tái)簡(jiǎn)介41-45
• 4.1.1 BSP模型41-45
• 4.1.2 Hama框架平臺(tái)45
• 4.3 基礎(chǔ)蟻群算法選擇45-46
• 4.4 并行策略的選擇46-48
• 4.5 粗粒度主從式互并行蟻群算法48-53
• 4.5.1 消息傳遞與處理49-51
• 4.5.2 信息素更新策略51
• 4.5.3 算法流程設(shè)計(jì)51-53
• 4.6 粗粒度最優(yōu)解并行蟻群算法53-58
• 4.6.1 消息傳遞與處理54-55
• 4.6.2 信息素更新策略55
• 4.6.3 算法流程設(shè)計(jì)55-58
• 4.7 兩種并行蟻群算法主要數(shù)據(jù)結(jié)構(gòu)58-60
• 4.8 本章小結(jié)60-61
• 5 公交駕駛員排班問(wèn)題案例分析61-79
• 5.1 構(gòu)建并行運(yùn)算環(huán)境61-65
• 5.1.1 Hama編程思路61-62
• 5.1.2 構(gòu)建Hama集群運(yùn)算平臺(tái)62-63
• 5.1.3 平臺(tái)功能性測(cè)試63-65
• 5.2 可行班型生成65-69
• 5.3 問(wèn)題求解與結(jié)果對(duì)比69-77
• 5.3.1 基本蟻群算法求解70-73
• 5.3.2 并行蟻群算法求解與效果對(duì)比73-77
• 5.4 本章小結(jié)77-79
• 6 總結(jié)與展望79-81
• 6.1 論文總結(jié)79-80
• 6.2 研究展望80-81
• 參考文獻(xiàn)81-87
• 附錄A87-95
• 附錄B95-103
• 作者簡(jiǎn)歷及攻讀碩士學(xué)位期間取得的研究成果103-107
• 學(xué)位論文數(shù)據(jù)集107

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 高麗萍;彭敦陸;鄧桂英;陳慶奎;;面向企業(yè)應(yīng)用的“算法設(shè)計(jì)與分析”課程建設(shè)改革探索[J];中國(guó)電力教育;2011年20期

2 姜楓;;“算法設(shè)計(jì)與分析”課程教學(xué)改革探索[J];中國(guó)電力教育;2013年26期

3 蘇安婕;吳志剛;;關(guān)鍵步分解法在算法設(shè)計(jì)與描述中的應(yīng)用[J];成組技術(shù)與生產(chǎn)現(xiàn)代化;2011年03期

4 雷小園;;排列組合的算法設(shè)計(jì)與C++實(shí)現(xiàn)[J];中國(guó)新技術(shù)新產(chǎn)品;2010年10期

5 肖建華,何宏,陳展,歐陽(yáng)湘江;算法中數(shù)學(xué)策略的應(yīng)用與研究[J];湖南工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2004年02期

6 余嶸華,張?chǎng)?張?jiān)?票證結(jié)存算法設(shè)計(jì)[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2000年S1期

7 馮平;黃名選;;由頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則的算法設(shè)計(jì)和實(shí)現(xiàn)[J];廣西工學(xué)院學(xué)報(bào);2007年01期

8 王卿;路曉偉;;高等院校學(xué)分制教學(xué)排考問(wèn)題算法設(shè)計(jì)[J];上海理工大學(xué)學(xué)報(bào);2007年06期

9 劉永廣;葉梧;馮穗力;莊宏成;;基于蟻群算法的無(wú)線Mesh網(wǎng)公平路由算法[J];華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年01期

10 邢春峰,柳重堪;聯(lián)想記憶系統(tǒng)的學(xué)習(xí)算法設(shè)計(jì)(I)[J];北京聯(lián)合大學(xué)學(xué)報(bào);1998年03期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前10條

1 雷詠梅;;橢圓曲線密碼體制的算法設(shè)計(jì)與實(shí)現(xiàn)[A];西部大開(kāi)發(fā) 科教先行與可持續(xù)發(fā)展——中國(guó)科協(xié)2000年學(xué)術(shù)年會(huì)文集[C];2000年

2 楊盤(pán)洪;朱軍祥;趙建安;楊靜;;機(jī)動(dòng)目標(biāo)跟蹤的模糊變結(jié)構(gòu)交互多模算法[A];2007'中國(guó)儀器儀表與測(cè)控技術(shù)交流大會(huì)論文集（二）[C];2007年

3 徐子珊;;《算法設(shè)計(jì)與分析》課程中的工程教育[A];2005年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

4 王輝;劉治昌;;用一種新算法設(shè)計(jì)的安全系統(tǒng)[A];2007年中國(guó)智能自動(dòng)化會(huì)議論文集[C];2007年

5 舒輝;柳清峰;杜祝平;周蓓;;實(shí)踐教學(xué)模式在本科專業(yè)課程教學(xué)中的應(yīng)用[A];中國(guó)電子教育學(xué)會(huì)高教分會(huì)2010年論文集[C];2010年

6 彭小宏;陽(yáng)東升;劉忠;;基于聚類算法的組織協(xié)作網(wǎng)設(shè)計(jì)[A];2006中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2006年

7 李皓;羅熊;;云存儲(chǔ)部署優(yōu)化的進(jìn)化算法設(shè)計(jì)[A];2013年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第三分冊(cè)）[C];2013年

8 羅長(zhǎng)政;李熙瑩;王鎮(zhèn)波;羅東華;;一種大流量交叉路口的背景提取與更新算法[A];第十五屆全國(guó)圖象圖形學(xué)學(xué)術(shù)會(huì)議論文集[C];2010年

9 楊利;李霖;昌月樓;陽(yáng)國(guó)貴;;對(duì)稱位向量及啟發(fā)式并行散列連接算法[A];數(shù)據(jù)庫(kù)研究與進(jìn)展95——第十三屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集[C];1995年

10 張晉;;嵌入式電腦鼠運(yùn)行算法的研究[A];全國(guó)第20屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議（CACIS·2009）暨全國(guó)第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];2009年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

1 ;算法設(shè)計(jì)的策略[N];電腦報(bào);2003年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 谷偉哲;齊次光滑算法及其應(yīng)用[D];天津大學(xué);2010年

2 龍海俠;進(jìn)化算法及其在生物信息中的應(yīng)用[D];江南大學(xué);2010年

3 譚躍;具有混沌局部搜索策略的粒子群優(yōu)化算法研究[D];中南大學(xué);2013年

4 尤海峰;求解隱式目標(biāo)優(yōu)化問(wèn)題的交互式進(jìn)化算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

5 張常淳;基于MapReduce的大數(shù)據(jù)連接算法的設(shè)計(jì)與優(yōu)化[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

6 郭崇慧;地區(qū)中長(zhǎng)期發(fā)展規(guī)劃若干定量模型、算法及應(yīng)用研究[D];大連理工大學(xué);2002年

7 蔣蔚;粒子濾波改進(jìn)算法研究與應(yīng)用[D];哈爾濱工業(yè)大學(xué);2010年

8 孫賀;算法設(shè)計(jì)中的若干前沿問(wèn)題[D];復(fù)旦大學(xué);2009年

9 陳寧濤;基于二分技術(shù)的高效算法設(shè)計(jì)及其應(yīng)用[D];華中科技大學(xué);2006年

10 婁曉文;無(wú)符號(hào)基因組切割再粘貼重組問(wèn)題的算法研究[D];山東大學(xué);2010年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 李欣園;基于選擇偏好的組合聚類算法研究與實(shí)現(xiàn)[D];內(nèi)蒙古大學(xué);2015年

2 楊瀟;界約束非線性最小二乘問(wèn)題的無(wú)導(dǎo)數(shù)算法[D];上海交通大學(xué);2015年

3 王曉璐;基于Zynq的LS-SVM算法加速器設(shè)計(jì)[D];哈爾濱工業(yè)大學(xué);2015年

4 樓磊磊;醫(yī)療保險(xiǎn)數(shù)據(jù)異常行為檢測(cè)算法和系統(tǒng)[D];浙江大學(xué);2015年

5 齊海龍;基于改進(jìn)人工蜂群算法的非線性系統(tǒng)辨識(shí)方法研究[D];北京化工大學(xué);2015年

6 蔡平梅;結(jié)構(gòu)化稀疏信號(hào)的恢復(fù)算法研究[D];上海大學(xué);2015年

7 趙晨陽(yáng);基于蟻群算法的高階圖匹配方法研究[D];西安電子科技大學(xué);2014年

8 茍清松;多目標(biāo)粒子濾波檢測(cè)前跟蹤算法研究[D];電子科技大學(xué);2015年

9 李枝勇;蝙蝠算法及其在函數(shù)優(yōu)化中的應(yīng)用研究[D];上海理工大學(xué);2013年

10 李蓮;基于蜂群和粗糙集的聚類算法研究[D];長(zhǎng)沙理工大學(xué);2014年

  本文關(guān)鍵詞：基于Hama的并行蟻群算法公交駕駛員排班問(wèn)題研究，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：311056