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

【摘要】：論文對公交駕駛員排班問題進行論述,并研究了相關的數學模型和求解算法。針對求解算法中蟻群算法求解時間過長的不足,在基于開放的分布式計算平臺Hama的基礎上,設計與實現了基于Hama的兩種并行蟻群算法模型以提高算法執(zhí)行效率。論文的主要工作如下：本文首先研究了公交駕駛排班問題的現狀,分析了集成調度法、構建與優(yōu)化和法生成與選擇法三種思路的優(yōu)缺點,討論了蟻群算法和并行蟻群算法原理,確定了求解公交駕駛員排班問題的技術路線。其次在研究Hama平臺的基礎上,提出了兩種求解公交駕駛排班問題并行蟻群算法模型：粗粒度主從式并行蟻群算法模型和粗粒度最優(yōu)解并行蟻群算法模型。這兩種模型的基本算法均采用MMAS算法,粗粒度主從式并行蟻群算法模型中使用信息素矩陣作為交互內容,并通過設置主從節(jié)點的方式減少發(fā)送信息次數；粗粒度最優(yōu)解并行以子蟻群的當前最優(yōu)解及其路徑作為交互內容。論文建立兩種并行蟻群算法模型以期提高求解效率和得到更優(yōu)結果,并詳細闡述了實現過程中的重點問題。最后論文選取北京市典型公交線路進行實證分析,試驗環(huán)境采用四臺虛擬機構造的并行計算集群,實驗結果表明,在單機運算方面,普通蟻群算法求解結果與線路實際情況相比,可減少1個班型的使用,結果更優(yōu)；在集群運算方面,同普通蟻群算法相比,兩種并行算法均具有更好的求解效率,粗粒度主從式并行與粗粒度最優(yōu)解并行的可達到最大加速比分別為2.90與3.41,其中,粗粒度主從式并行的求解質量要優(yōu)于粗粒度最優(yōu)解并行,因為粗粒度主從式并行采用信息素矩陣交互的策略,可以使搜索空間更大,在搜索過程中更有可能找到較優(yōu)解。本文研究的基于Hama的并行蟻群算法在選擇并行計算模型,設計并行蟻群交互策略等方面上具有一定的指導意義。
【關鍵詞】：公交駕駛員排班問題 蟻群算法 并行 Hama 粗粒度主從式 粗粒度最優(yōu)解
【學位授予單位】：北京交通大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：U491.17;TP18
【目錄】：

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

【相似文獻】

中國期刊全文數據庫 前10條

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

2 姜楓;;“算法設計與分析”課程教學改革探索[J];中國電力教育;2013年26期

3 蘇安婕;吳志剛;;關鍵步分解法在算法設計與描述中的應用[J];成組技術與生產現代化;2011年03期

4 雷小園;;排列組合的算法設計與C++實現[J];中國新技術新產品;2010年10期

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

6 余嶸華,張霆,張云;票證結存算法設計[J];合肥工業(yè)大學學報(自然科學版);2000年S1期

7 馮平;黃名選;;由頻繁項集生成關聯(lián)規(guī)則的算法設計和實現[J];廣西工學院學報;2007年01期

8 王卿;路曉偉;;高等院校學分制教學排考問題算法設計[J];上海理工大學學報;2007年06期

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

10 邢春峰,柳重堪;聯(lián)想記憶系統(tǒng)的學習算法設計(I)[J];北京聯(lián)合大學學報;1998年03期

中國重要會議論文全文數據庫 前10條

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

2 楊盤洪;朱軍祥;趙建安;楊靜;;機動目標跟蹤的模糊變結構交互多模算法[A];2007'中國儀器儀表與測控技術交流大會論文集（二）[C];2007年

3 徐子珊;;《算法設計與分析》課程中的工程教育[A];2005年全國理論計算機科學學術年會論文集[C];2005年

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

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

6 彭小宏;陽東升;劉忠;;基于聚類算法的組織協(xié)作網設計[A];2006中國控制與決策學術年會論文集[C];2006年

7 李皓;羅熊;;云存儲部署優(yōu)化的進化算法設計[A];2013年中國智能自動化學術會議論文集（第三分冊）[C];2013年

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

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

10 張晉;;嵌入式電腦鼠運行算法的研究[A];全國第20屆計算機技術與應用學術會議（CACIS·2009）暨全國第1屆安全關鍵技術與應用學術會議論文集（上冊）[C];2009年

中國重要報紙全文數據庫 前1條

1 ;算法設計的策略[N];電腦報;2003年

中國博士學位論文全文數據庫 前10條

1 谷偉哲;齊次光滑算法及其應用[D];天津大學;2010年

2 龍海俠;進化算法及其在生物信息中的應用[D];江南大學;2010年

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

4 尤海峰;求解隱式目標優(yōu)化問題的交互式進化算法研究[D];中國科學技術大學;2011年

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

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

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

8 孫賀;算法設計中的若干前沿問題[D];復旦大學;2009年

9 陳寧濤;基于二分技術的高效算法設計及其應用[D];華中科技大學;2006年

10 婁曉文;無符號基因組切割再粘貼重組問題的算法研究[D];山東大學;2010年

中國碩士學位論文全文數據庫 前10條

1 李欣園;基于選擇偏好的組合聚類算法研究與實現[D];內蒙古大學;2015年

2 楊瀟;界約束非線性最小二乘問題的無導數算法[D];上海交通大學;2015年

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

4 樓磊磊;醫(yī)療保險數據異常行為檢測算法和系統(tǒng)[D];浙江大學;2015年

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

6 蔡平梅;結構化稀疏信號的恢復算法研究[D];上海大學;2015年

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

8 茍清松;多目標粒子濾波檢測前跟蹤算法研究[D];電子科技大學;2015年

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

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

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

，

本文編號：311056