【摘要】：最小延時問題是旅行商問題的變體,目的是求解路線中所有客戶的累計等待時間,最小延時問題相比于旅行商問題更難以解決。目前的求解方法,只能在客戶數(shù)量較小時具有較高的性能,當客戶數(shù)量變大時算法很難兼顧運行時間與求解質(zhì)量�；谏鲜鰡栴},對如何在較短時間內(nèi)獲得大數(shù)據(jù)量最小延時問題的優(yōu)質(zhì)解這一問題進行以下研究。1.對于大數(shù)據(jù)量的最小延時問題,目前主要使用元啟發(fā)式算法求解,在此基礎(chǔ)上提出一種混合元啟發(fā)式算法。將遺傳算法與變鄰域搜索算法細粒度結(jié)合,在遺傳算法的框架內(nèi)實現(xiàn)變鄰域搜索。當算法陷入局部最優(yōu)解時,可以在遺傳算法的交叉過程中改變子代染色體的鄰域結(jié)構(gòu);并對遺傳算法的變異過程進行改進,子代染色體可以在增加多樣性的同時有較大概率發(fā)生優(yōu)化。然后對算法進行數(shù)據(jù)預處理,通過為每個染色體構(gòu)建基因節(jié)點索引列表,降低生成子代染色體的時間復雜度。2.為了進一步加快算法運行,使用GPU實現(xiàn)算法的并行化,并根據(jù)GPU運行特點對并行算法做出改進。將并行算法的交叉與變異過程以線程束為單位分開同步運行,每個線程具有固定的染色體選取位置與生成位置。算法整體上以線程塊為單位并行運行,以保證并行算法避免產(chǎn)生線程發(fā)散問題并且減少線程通信開銷,同時實現(xiàn)染色體的動態(tài)選擇。此外將算法與擾動機制相結(jié)合,增強并行算法全局搜索能力,并使用多重改進方式生成最終解。通過上述方法進一步提升算法性能。為驗證算法的實際運行情況,對算法進行對比實驗,測試數(shù)據(jù)的節(jié)點個數(shù)從51到10150不等。實驗結(jié)果表明,提出的算法在CPU環(huán)境中,相對于其它元啟發(fā)式算法,可以在較短的時間內(nèi)取得優(yōu)質(zhì)解;在CPU-GPU環(huán)境中,當數(shù)據(jù)規(guī)模較大時,并行算法可以取得明顯的加速效果,數(shù)據(jù)規(guī)模越大,加速效果越明顯。并且該并行算法相較于實驗中其它的并行算法,具有更好的性能。因此,對于大數(shù)據(jù)量的最小延時問題,并行混合元啟發(fā)式算法可以在相對較短的時間內(nèi)獲得優(yōu)質(zhì)解。
【學位授予單位】：河北大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP301.6
【圖文】：

基本圖展示

圖 2-2 當節(jié)點數(shù)=11 時的最小延時問題中，并沒有將返回倉庫作為限制條件考慮在內(nèi)，在這種，意味著 ( 1) 0sl n 。時問題的描述公式與旅行商問題十分相似，但卻比旅行

-opt操作

【相似文獻】

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

1 郭戈;賈二娜;;網(wǎng)絡(luò)化控制系統(tǒng)中的延時問題:分析與展望[J];控制與決策;2009年01期

2 王浩;;關(guān)于力士德SC3620行走延時問題處理[J];流體傳動與控制;2017年03期

3 黃郴;數(shù)據(jù)庫的延時問題及技術(shù)解決辦法[J];圖書情報工作;2001年03期

4 劉振鵬;薛雷;張彬;王雪峰;;最小延時問題GPU并行加速變鄰域搜索方法[J];科學技術(shù)與工程;2018年29期

5 甘朝欽,張寒崢;IP網(wǎng)絡(luò)性能與分組傳送延時問題及其解決方案[J];電信科學;2003年10期

6 周強;;60MN臥式鋼管熱擠壓機擠壓力延時問題簡析[J];科技風;2018年03期

7 Gordon oliver;解決當今全球語音網(wǎng)絡(luò)的延時問題[J];當代通信;2004年17期

8 來五星,李巍華,史鐵林,楊叔子;遠程監(jiān)測診斷系統(tǒng)中延時問題處理[J];計算機應(yīng)用;2000年05期

9 解寶琦;賀萬華;;增加DNS緩存服務(wù)器消除延遲[J];網(wǎng)絡(luò)安全和信息化;2017年01期

10 汪國華;;今天你“PUSH”了嗎?[J];個人電腦;2007年04期

相關(guān)重要報紙文章 前1條

1 唐建生;煤礦井下職工超點延時問題須解決[N];陜西日報;2008年

相關(guān)碩士學位論文 前2條

1 薛雷;最小延時問題的并行混合元啟發(fā)式算法[D];河北大學;2019年

2 賈二娜;信道受限的網(wǎng)絡(luò)化控制系統(tǒng)延時問題研究[D];大連海事大學;2008年

本文編號：2784689