旅行商問題（Traveling Salesman Problem,TSP）是一個(gè)經(jīng)典的組合優(yōu)化問題,一直受到計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)界廣泛關(guān)注,在現(xiàn)代物流運(yùn)輸領(lǐng)域中發(fā)揮了重要的作用,具有重要的實(shí)際意義。本文研究了TSP文獻(xiàn)中四個(gè)經(jīng)典的旅行商擴(kuò)展問題,即帶酒店選擇的旅行商問題（TSPHS）、帶先進(jìn)先出規(guī)則的取貨派貨旅行商問題（TSPPDF）、多商品取貨派貨旅行商問題（m-PDTSP）和簇旅行商問題（CTSP）,為它們分別設(shè)計(jì)了高效的元啟發(fā)式算法,與文獻(xiàn)中最好的算法進(jìn)行對比,來評價(jià)所提出算法的性能和效率,并對提出算法的一些重要組成部分進(jìn)行分析和討論。本文的主要貢獻(xiàn)包括:（1）針對TSPHS問題,本文提出了一個(gè)高效的基于動態(tài)規(guī)劃的混合進(jìn)化算法（HEA）。該算法包括三個(gè)重要組成部分:動態(tài)規(guī)劃、三個(gè)交叉算子和兩階段的局部搜索。本文提出的動態(tài)規(guī)劃方法為一個(gè)給定顧客旅行序列尋找最優(yōu)的住宿酒店序列,將傳統(tǒng)的TSP解轉(zhuǎn)化為TSPHS解。同時(shí),HEA算法使用三個(gè)專門的交叉算子,用于生成高質(zhì)量的后代個(gè)體,在每次進(jìn)化中,算法會自適應(yīng)地選擇合適的交叉算子去產(chǎn)生子代解。此外,HEA算法使用基于合法解和非法解同時(shí)搜索的兩... 

【文章來源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：126 頁

【學(xué)位級別】：博士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究背景和意義
    1.2 研究目標(biāo)和方法
    1.3 本文的主要工作及其結(jié)構(gòu)
    1.4 本文的主要創(chuàng)新點(diǎn)
2 國內(nèi)外相關(guān)研究綜述
    2.1 帶酒店選擇的旅行商問題
    2.2 帶FIFO規(guī)則的取貨派貨旅行商問題
    2.3 多商品取貨派貨旅行商問題
    2.4 簇旅行商問題
    2.5 本章小結(jié)
3 基于動態(tài)規(guī)劃的混合進(jìn)化算法求解帶酒店選擇旅行商問題
    3.1 問題概述
    3.2 問題定義和數(shù)學(xué)模型
    3.3 求解TSPHS的混合進(jìn)化算法
    3.4 計(jì)算實(shí)驗(yàn)
    3.5 分析與討論
    3.6 本章小結(jié)
4 迭代搜索算法求解帶FIFO規(guī)則的取貨派貨旅行商問題
    4.1 問題概述
    4.2 問題定義和數(shù)學(xué)模型
    4.3 求解TSPPDF的迭代搜索算法
    4.4 計(jì)算實(shí)驗(yàn)
    4.5 分析與討論
    4.6 本章小結(jié)
5 隨機(jī)禁忌閾值搜索算法求解多商品取貨派貨旅行商問題
    5.1 問題概述
    5.2 問題定義和數(shù)學(xué)模型
    5.3 求解m-PDTSP的帶種群管理的隨機(jī)禁忌閾值搜索算法
    5.4 計(jì)算實(shí)驗(yàn)
    5.5 分析與討論
    5.6 本章小結(jié)
6 混合進(jìn)化算法求解簇旅行商問題
    6.1 問題概述
    6.2 問題定義和數(shù)學(xué)模型
    6.3 提出的方法
    6.4 計(jì)算實(shí)驗(yàn)
    6.5 分析與討論
    6.6 本章小結(jié)
7 總結(jié)和展望
    7.1 全文總結(jié)
    7.2 研究展望
致謝
參考文獻(xiàn)
附錄1 攻讀博士學(xué)位期間發(fā)表的學(xué)術(shù)論文
附錄2 攻讀博士學(xué)位期間參與的科研項(xiàng)目
附錄3 PRTTA算法在小算例集上的實(shí)驗(yàn)結(jié)果
附錄4 PRTTA算法在大算例集上的實(shí)驗(yàn)結(jié)果
附錄5 HEA算法在基準(zhǔn)算例集上的實(shí)驗(yàn)結(jié)果


【參考文獻(xiàn)】：
期刊論文
[1]求解配送\收集旅行商問題的模擬退火算法[J]. 謝秉磊,李良,郭耀煌.  系統(tǒng)工程理論方法應(yīng)用. 2002(03)



本文編號：3539167