最短路徑問題為圖論中的一個(gè)經(jīng)典問題,其算法的研究在優(yōu)化問題中有著重要的理論價(jià)值,很多現(xiàn)實(shí)優(yōu)化問題都可以轉(zhuǎn)化為最短路徑問題來進(jìn)行求解。隨著科學(xué)技術(shù)的飛速發(fā)展和日常生活的需要,傳統(tǒng)的最短路徑問題無法滿足人們的需求,由此衍生出了帶有各類資源約束的最短路徑問題,本文中所研究的問題模型就是其中的一種,為帶有時(shí)間窗和容量資源約束的基本最短路徑問題（ESPPRC）。本文針對帶有資源約束的基本最短路徑問題的精確算法進(jìn)行了研究,并發(fā)現(xiàn)現(xiàn)有精確算法的求解效率還無法滿足需要,因此嘗試提出了一種改進(jìn)算法來加快求得精確解的速率。本文通過對帶有資源約束的基礎(chǔ)最短路徑問題的三種求解思想的研究與分析,找到了每種算法各自的優(yōu)點(diǎn)和存在的問題,并提出了改進(jìn)的思路和方向。在原有方法的基礎(chǔ)上,提出了對ESPPRC問題的一種改進(jìn)算法,算法結(jié)合了脈沖算法中的下界矩陣的思想和標(biāo)號算法中利用label存儲局部路徑的思想,并利用分支定界、剪枝策略來縮小搜索空間。算法將下界矩陣的存儲內(nèi)容由局部路徑成本擴(kuò)充為完整的路徑信息,并利用這個(gè)矩陣設(shè)計(jì)了拼接路徑策略來提高算法的求解速率,并提出了兩種排序策略分別針對稀疏圖和稠密圖來優(yōu)化矩陣的生成順序,... 

【文章來源】：大連理工大學(xué)遼寧省 211工程院校 985工程院校 教育部直屬院校

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

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

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究背景及研究意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 主要研究內(nèi)容
    1.4 章節(jié)安排
2 相關(guān)問題介紹
    2.1 最短路徑問題分析
        2.1.1 最短路徑問題定義
        2.1.2 經(jīng)典算法分析
    2.2 多約束最短路徑問題
        2.2.1 問題概述
        2.2.2 問題分析
        2.2.3 相關(guān)算法介紹
    2.3 本章小結(jié)
3 ESPPRC問題模型與算法分析
    3.1 問題描述和數(shù)學(xué)模型
        3.1.1 ESPPRC問題描述
        3.1.2 車輛路徑問題的列生成算法
        3.1.3 ESPPRC問題數(shù)學(xué)模型
    3.2 算法分析
        3.2.1 求解思路分析
        3.2.2 改進(jìn)算法介紹
    3.3 pulse算法
        3.3.1 pulse算法主要思想
        3.3.2 pulse算法計(jì)算實(shí)例與缺陷分析
    3.4 本章小結(jié)
4 ESPPRC問題的改進(jìn)算法
    4.1 問題定義
    4.2 改進(jìn)算法設(shè)計(jì)
        4.2.1 改進(jìn)思路
        4.2.2 路徑拼接
        4.2.3 優(yōu)化下界矩陣生成順序
    4.3 算法可行性分析
    4.4 算法實(shí)現(xiàn)
    4.5 本章小結(jié)
5 數(shù)值實(shí)驗(yàn)
    5.1 實(shí)驗(yàn)結(jié)果
        5.1.1 環(huán)境和實(shí)例分析
        5.1.2 實(shí)驗(yàn)結(jié)果
    5.2 結(jié)果對比
    5.3 ESPPRC問題的其他應(yīng)用
    5.4 本章小結(jié)
結(jié)論
參考文獻(xiàn)
致謝


【參考文獻(xiàn)】：
期刊論文
[1]復(fù)雜約束條件下求解帶權(quán)最短路徑方法[J]. 楊瀾,段卓輝,鄧宏濤.  江漢大學(xué)學(xué)報(bào)(自然科學(xué)版). 2018(04)
[2]帶時(shí)間窗的車輛路徑問題的精確算法研究[J]. 答家瑞,鄭瀾波.  物流技術(shù). 2017(06)
[3]過必經(jīng)節(jié)點(diǎn)集的動(dòng)態(tài)剪枝搜索算法[J]. 姚博,馮宏偉,高原,馬佳麗,馮筠.  計(jì)算機(jī)工程與應(yīng)用. 2017(15)
[4]移動(dòng)對等網(wǎng)絡(luò)中的感知蟻群路由算法[J]. 曲大鵬,王興偉,黃敏.  計(jì)算機(jī)學(xué)報(bào). 2013(07)



本文編號：3152533