隨著現(xiàn)代生活中的科技和工業(yè)的進(jìn)步,組合優(yōu)化問題作為一組經(jīng)典又實用的問題越發(fā)被廣泛關(guān)注。旅行商問題(Traveling Salesman Problem,TSP)是組合優(yōu)化中一個經(jīng)典的問題,也是一個NP-Hard問題,在計算機(jī)、數(shù)學(xué)和運籌學(xué)等領(lǐng)域中是熱點研究領(lǐng)域,且TSP具有極高的理論和應(yīng)用價值。在問題規(guī)模隨著城市規(guī)模擴(kuò)大時,時間和空間復(fù)雜度會呈現(xiàn)出指數(shù)級的增長,大多數(shù)算法都不能夠求出一個令人滿意的解,所以成為在此專業(yè)領(lǐng)域中被研究者們特重視的問題之一。TSP因時代的發(fā)展,類似技術(shù)的不斷進(jìn)步,如人工智能、計算機(jī)技術(shù)等,為該問題帶來越拉越多的解決方法。啟發(fā)式算法用于求解TSP時,運行時間較短,但普遍結(jié)果不夠精確。如今在求解TSP時,多用混合算法,各取其長,提高求解TSP的效率。在本文中,通過對多種求解TSP的算法進(jìn)行分析后,著重研究了貪婪隨機(jī)自適應(yīng)搜索算法(Greedy Randomized Adaptive Search Procedures,GRASP),并將其與其他算法相結(jié)合為混合算法。GRASP算法是一個經(jīng)常用于求解組合優(yōu)化問題的算法,它是一個二次迭代的過程,該算法在求解TSP時,若所得解陷入了局部最優(yōu)的情況,是由于其構(gòu)造階段的貪婪隨機(jī)性。針對該算法在求解TSP時對其進(jìn)行改進(jìn),根據(jù)其二次迭代的特性,在第一階段構(gòu)造通過控制候選表的長度,構(gòu)造一個可行的貪婪隨機(jī)初始解。在第二階段引入群智能算法灰狼優(yōu)化算法(GreyWolf Optimizer,GWO),對其進(jìn)行重新編碼,能夠用于求解TSP這類離散型問題。然而原始的GWO的初始解是隨機(jī)生成的,它的好壞極大程度上影響了整體的求解,故將構(gòu)造階段所得解作為GWO的初始解,利用GWO較強(qiáng)的全局搜索特性,對其進(jìn)行逼近搜索,從而避免陷入局部最優(yōu)的情況。對TSPLIB中的多個數(shù)據(jù)運用改進(jìn)的算法對其進(jìn)行大規(guī)模的算法性能實驗測試,分別對多個參數(shù)進(jìn)行多次調(diào)整,多方面對結(jié)果進(jìn)行分析�；旌纤惴ㄔ诘诙A段搜索后能改善初始解,并且?guī)缀踹_(dá)到全局最優(yōu),驗證了該算法解的質(zhì)量有大幅度的提升。大多數(shù)實例能夠求得最優(yōu)解,規(guī)模較大的實例所求解誤差較小,較其他算法在規(guī)模較大的實例下仍然能對其進(jìn)行求解。最后本文將生活中常見的物流配送路徑規(guī)劃問題作為應(yīng)用場景,該問題可以抽象為TSP的拓展問題,多旅行商問題。物流配送要求多位司機(jī)以盡短的路程快速完成配送,首先用K-means對各車輛配送的站點進(jìn)行劃分,再通過使用改進(jìn)的算法優(yōu)化配送路徑。驗證該算法能夠運用在實際問題中,提高司機(jī)的配送效率,簡短配送路程,節(jié)省所需時間,從而保證及時完成任務(wù),減少對公司造成的損失。
【學(xué)位單位】：太原理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2019
【中圖分類】：TP18
【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 課題背景與研究意義
    1.2 旅行商問題研究現(xiàn)狀
    1.3 論文的研究內(nèi)容
    1.4 論文章節(jié)安排
第二章 相關(guān)理論方法
    2.1 Hamilton回路
    2.2 旅行商問題
    2.3 旅行商問題的求解
        2.3.1 完全算法
        2.3.2 近似算法
        2.3.3 啟發(fā)式算法
    2.4 本章小結(jié)
第三章 基于GRASP算法對求解TSP的改進(jìn)
    3.1 GRASP算法初始化種群
    3.2 改進(jìn)灰狼優(yōu)化算法
        3.2.1 灰狼優(yōu)化算法簡介
        3.2.2 構(gòu)造狼群的編碼方式
    3.3 改進(jìn)策略的優(yōu)化算法
        3.3.1 基本原理
        3.3.2 算法流程
    3.4 本章小結(jié)
第四章 實驗及結(jié)果分析
    4.1 TSPLIB經(jīng)典數(shù)據(jù)
    4.2 參數(shù)設(shè)置
        4.2.1 RCL長度設(shè)置
        4.2.2 狼群數(shù)量設(shè)置
        4.2.3 局部搜索
    4.3 實驗結(jié)果
    4.4 實驗對比
    4.5 本章小結(jié)
第五章 TSP相關(guān)拓展研究
    5.1 物流配送路徑規(guī)劃問題研究
    5.2 算法設(shè)計
    5.3 實驗及結(jié)果
        5.3.1 實驗數(shù)據(jù)
        5.3.2 實驗結(jié)果
    5.4 本章小結(jié)
第六章 總結(jié)與展望
    6.1 總結(jié)
    6.2 展望
參考文獻(xiàn)
致謝
攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文

【相似文獻(xiàn)】

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

1 黃逸;;算法結(jié)構(gòu)與設(shè)計教學(xué)中的若干思考[J];中學(xué)數(shù)學(xué)雜志;2008年05期

2 何永生;;算法結(jié)構(gòu)考查“三角度”[J];中學(xué)生數(shù)理化(高一);2017年01期

3 丁忒;;“算法的概念”教學(xué)設(shè)計[J];中國數(shù)學(xué)教育;2017年Z2期

4 王靖亞;;算法結(jié)構(gòu)對其性能的影響研究[J];計算機(jī)教育;2005年10期

5 裴承鳴;黎中偉;;ARMA過程的遞推線性估計及其應(yīng)用[J];西北工業(yè)大學(xué)學(xué)報;1987年02期

6 胡平;;試論濾波器的算法結(jié)構(gòu)[J];河北機(jī)電學(xué)院學(xué)報;1987年01期

7 黃繼進(jìn);;快速DFT計算——基于遞歸割圓因式分解的新算法[J];計算機(jī)應(yīng)用與軟件;1988年05期

8 鄭容;;時域加權(quán)FFT算法(WTTA)[J];信號處理;1988年04期

9 乞敬換;王秀峰;;具有阻塞的串行生產(chǎn)線“線性”狀態(tài)方程描述及擾動分析新算法[J];系統(tǒng)工程學(xué)報;1989年02期

10 王靖亞;;算法結(jié)構(gòu)對其性能的影響研究[J];中國人民公安大學(xué)學(xué)報(自然科學(xué)版);2005年04期

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

1 鐘軼君;分片稀疏恢復(fù)理論及算法[D];大連理工大學(xué);2018年

2 張慧君;三元M/B/Si功能化合物的第一性原理計算方法研究[D];燕山大學(xué);2017年

3 熊丙章;高中生的算法理解水平及其教學(xué)策略研究[D];西南大學(xué);2013年

4 楊樂嬋;基于GEP算法和高光譜數(shù)據(jù)的植物主要理化參數(shù)估算研究[D];南京大學(xué);2017年

5 張超;混合群智能優(yōu)化算法研究及應(yīng)用[D];北京科技大學(xué);2018年

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

1 高珊;基于貪婪隨機(jī)自適應(yīng)灰狼優(yōu)化算法求解TSP的研究與應(yīng)用[D];太原理工大學(xué);2019年

2 楊忠保;復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)算法研究與應(yīng)用[D];武漢理工大學(xué);2018年

3 崔利娟;基于深度森林的交通標(biāo)志識別算法研究[D];北方工業(yè)大學(xué);2019年

4 王一捷;柔性直流輸電技術(shù)數(shù)�；旌戏抡婀β式涌谒惴ㄑ芯縖D];東北電力大學(xué);2019年

5 吳亞桐;北斗B1頻點信號捕獲算法研究與實現(xiàn)[D];哈爾濱工程大學(xué);2018年

6 吳瓊;基于SSD算法的車輛和行人的檢測[D];華中師范大學(xué);2018年

7 丁宗元;基于度量學(xué)習(xí)的行人重識別若干算法研究[D];常州大學(xué);2018年

8 涂亮杰;基于改進(jìn)蟻群算法的果園移動機(jī)器人路徑規(guī)劃研究[D];南華大學(xué);2018年

9 陳志國;基于OpenCL的多曝光融合算法并行優(yōu)化[D];西安電子科技大學(xué);2018年

10 郭章建;高動態(tài)擴(kuò)頻接收機(jī)的捕獲與跟蹤算法研究[D];華中科技大學(xué);2017年

本文編號：2837598