本文關(guān)鍵詞： 駕駛員排班問(wèn)題 遺傳算法 Hama BSP模型 并行遺傳算法 粗粒度最優(yōu)解　出處：《北京交通大學(xué)》2017年碩士論文　論文類(lèi)型：學(xué)位論文

【摘要】：隨著我國(guó)城市交通機(jī)動(dòng)化進(jìn)程的加快,交通需求和交通供給之間的矛盾也越來(lái)越突出,解決該問(wèn)題的一個(gè)重要途徑就是大力發(fā)展公共交通。運(yùn)營(yíng)組織與調(diào)度作為公共交通系統(tǒng)的核心內(nèi)容,是實(shí)現(xiàn)運(yùn)營(yíng)任務(wù)的基本保證;而駕駛員排班作為公共交通企業(yè)管理調(diào)度工作中的重要組成部分,對(duì)公共交通的運(yùn)行效率和運(yùn)營(yíng)成本有著決定性作用�？茖W(xué)合理的排班計(jì)劃不僅可以提高企業(yè)的服務(wù)質(zhì)量,還可以有效的減少企業(yè)的運(yùn)營(yíng)成本。駕駛員排班問(wèn)題是世界公認(rèn)的NP-hard問(wèn)題,其難點(diǎn)在于如何在合理的時(shí)間內(nèi)找到該問(wèn)題的最優(yōu)解或者近似最優(yōu)解。最優(yōu)解通常需要借助整數(shù)規(guī)劃方法求得,實(shí)際問(wèn)題中,問(wèn)題規(guī)模通常較大,使得整數(shù)規(guī)劃方法的求解時(shí)間難以評(píng)估:啟發(fā)式算法雖然無(wú)法保證解的最優(yōu)性,但卻很好的平衡了求解時(shí)間和解的質(zhì)量。遺傳算法作為啟發(fā)式算法中一種,具有很好的全局搜索能力和并行能力,但該算法也存在進(jìn)化時(shí)間長(zhǎng),早熟的缺點(diǎn)。針對(duì)遺傳算法的不足,設(shè)計(jì)了基于Hama的粗粒度最優(yōu)解并行模型(Optimal Solution of Corse-Grained Parallel Model Based on Hama,H-OSCGPM)來(lái)提高算法的求解效率和求解質(zhì)量。本文的研究?jī)?nèi)容和創(chuàng)新點(diǎn)如下:首先,論文介紹了公共交通領(lǐng)域的駕駛員排班問(wèn)題,揭示了駕駛員排班問(wèn)題的求解難點(diǎn),并總結(jié)了駕駛員排班問(wèn)題已有的研究成果。在已有研究的基基礎(chǔ)上建立了數(shù)學(xué)模型。其次,論文設(shè)計(jì)了面向駕駛員推班的遺傳算法(Crew Scheduling Orirented Genetic Algorithm,CSOGA),本文對(duì)CSOGA中的變異操作進(jìn)行了改進(jìn),以提高并行算法在進(jìn)行串行迭代時(shí)的求解質(zhì)量,并用實(shí)例驗(yàn)證了CSOGA的有效性。隨后,以粗粒度并行思想為指導(dǎo),設(shè)計(jì)了基于 Hama的粗粒度最優(yōu)解模型,對(duì)并行過(guò)程中的遷移策略、消息的交互處理進(jìn)行了詳細(xì)闡述,并對(duì)遷移個(gè)體的數(shù)量和遷移周期進(jìn)行了確定。最后,論文選取了 6條典型公交線路進(jìn)行實(shí)例驗(yàn)證分析。實(shí)驗(yàn)結(jié)果表明,并行算法的求解效率和求解質(zhì)量更優(yōu)。并行計(jì)算結(jié)果中,在求解質(zhì)景得到改善前提條件下,6條線路的加速比可分別達(dá)到3.47,2.96,2.96,2.45,2.34和3.20;且加速比與所求問(wèn)題的規(guī)模呈正相關(guān)關(guān)系,問(wèn)題的規(guī)模越大,獲得的加速比越高。綜上所述,卡文提出的并行遺傳算法,能夠在合理的時(shí)間能找到駕駛員排班問(wèn)題的較優(yōu)解,并為其在其他領(lǐng)域的應(yīng)用提供了理論支持。
[Abstract]:With the acceleration of motorization of urban traffic in China, the contradiction between traffic demand and traffic supply is becoming more and more prominent. One of the important ways to solve this problem is to develop public transportation vigorously. As the core content of public transportation system, operation organization and dispatch is the basic guarantee to realize the operation task. As an important part of the management and scheduling of public transport enterprises, driver scheduling is an important part. It plays a decisive role in the operation efficiency and operation cost of public transportation. Scientific and reasonable scheduling can not only improve the service quality of enterprises. Can also effectively reduce the operating costs of enterprises. Driver scheduling problem is recognized in the world as a NP-hard problem. The difficulty lies in how to find the optimal solution or approximate optimal solution of the problem in a reasonable time. The optimal solution usually needs to be obtained by means of integer programming. In practical problems, the scale of the problem is usually large. It is difficult to evaluate the solving time of integer programming. Although heuristic algorithm can not guarantee the optimality of solution, it balances the quality of solution time and solution. Genetic algorithm is one of the heuristic algorithms. It has good global search ability and parallel ability, but the algorithm also has the shortcomings of long evolutionary time and premature. The parallel model of coarse-grained optimal solution based on Hama is designed. Optimal Solution of Corse-Grained Parallel Model Based on Hama. H-OSCGPM) is used to improve the efficiency and quality of the algorithm. The contents and innovations of this paper are as follows: firstly, the paper introduces the problem of driver scheduling in the field of public transport. This paper reveals the difficulty of solving the driver scheduling problem, and summarizes the existing research results of the driver scheduling problem. Based on the previous research, the mathematical model is established. Secondly. This paper designs the genetic algorithm crew Scheduling Orirented Genetic algorithm (CSOGA). In this paper, the mutation operation in CSOGA is improved to improve the solution quality of parallel algorithm in serial iteration, and the effectiveness of CSOGA is verified by an example. Under the guidance of coarse-grained parallelism, the coarse-grained optimal solution model based on Hama is designed, and the migration strategy and message interactive processing in parallel process are described in detail. Finally, six typical bus routes are selected for verification and analysis. The experimental results show that. The efficiency and quality of the parallel algorithm are better. The speedup ratio of six lines can reach 3.47 / 2.96 respectively under the condition that the quality of the solution is improved. 2.45, 2.34 and 3.20; And the speedup ratio is positively correlated with the scale of the problem, the larger the problem scale, the higher the speedup ratio. In conclusion, Carvin proposed parallel genetic algorithm. The optimal solution of driver scheduling problem can be found in a reasonable time, and it provides theoretical support for its application in other fields.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：U492.21;TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 陳仕軍;沈吟東;;加速列生成法求解乘務(wù)調(diào)度問(wèn)題[J];交通運(yùn)輸系統(tǒng)工程與信息;2014年01期

2 陳明明;�；菝�;;多車(chē)場(chǎng)公交乘務(wù)排班問(wèn)題優(yōu)化[J];交通運(yùn)輸系統(tǒng)工程與信息;2013年05期

3 李建江;崔健;王聃;嚴(yán)林;黃義雙;;MapReduce并行編程模型研究綜述[J];電子學(xué)報(bào);2011年11期

4 李康順;李茂民;張文生;;一種基于改進(jìn)遺傳算法的圖像分割方法[J];計(jì)算機(jī)應(yīng)用研究;2009年11期

5 鄭鋒;李名世;蔡佳佳;;基于OpenMP的并行遺傳算法探討[J];心智與計(jì)算;2007年04期

6 謝超,麥聯(lián)叨,都志輝,馬群生;關(guān)于并行計(jì)算系統(tǒng)中加速比的研究與分析[J];計(jì)算機(jī)工程與應(yīng)用;2003年26期

相關(guān)碩士學(xué)位論文 前10條

1 余明捷;基于Hama的并行蟻群算法公交駕駛員排班問(wèn)題研究[D];北京交通大學(xué);2016年

2 王志剛;大規(guī)模圖增量迭代處理技術(shù)的研究與實(shí)現(xiàn)[D];東北大學(xué);2013年

3 劉濤;公交駕駛員排班與輪班問(wèn)題的模型與算法研究[D];北京交通大學(xué);2013年

4 王健;公交司售人員排班集合覆蓋問(wèn)題的求解算法研究與實(shí)現(xiàn)[D];北京交通大學(xué);2011年

5 王銀年;遺傳算法的研究與應(yīng)用[D];江南大學(xué);2009年

6 楊尚;基于螞蟻算法的公交駕駛員調(diào)度問(wèn)題研究[D];華中科技大學(xué);2009年

7 翟東偉;基于GATS的公交駕駛員調(diào)度算法研究[D];北京交通大學(xué);2008年

8 張斐斐;公共交通駕駛員調(diào)度問(wèn)題研究[D];北京交通大學(xué);2007年

9 占書(shū)芳;并行遺傳算法在帶軟時(shí)間窗車(chē)輛路徑問(wèn)題中的應(yīng)用研究[D];武漢理工大學(xué);2006年

10 吳昊;并行遺傳算法的研究與應(yīng)用[D];安徽大學(xué);2001年

，

本文編號(hào)：1483706