發(fā)布時間：2021-04-22 00:46

　　帶時間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows,VRPTW）作為物流行業(yè)中最常見的組合優(yōu)化問題之一,其模型結(jié)構(gòu)及算法都具有普遍性和拓展性。通過特定的轉(zhuǎn)化與變形,VRPTW的模型及算法同樣也適用于其他大多數(shù)的組合優(yōu)化場景,公交線路規(guī)劃、港口設(shè)備協(xié)同調(diào)度等資源分配問題都與其有著相似的數(shù)學結(jié)構(gòu)。因此,對車輛路徑問題的研究同樣有助于推動其他相關(guān)領(lǐng)域的發(fā)展,如何有效提升該問題的求解效率對物流行業(yè)的發(fā)展有直接且重大的影響。本文將以精確算法作為研究方向,對VRPTW進行較為全面的理論探究。目前針對VRPTW精確算法的研究主要分為兩個方向:整數(shù)規(guī)劃以及動態(tài)規(guī)劃。因VRPTW的求解屬于強NP-hard問題,大多數(shù)學者更傾向于選擇可在偽多項式時間內(nèi)完成求解的動態(tài)規(guī)劃來進行探究。而動態(tài)規(guī)劃所求得的最優(yōu)解的理論下界質(zhì)量較差。且在時間窗約束較寬的情況下,其求解性能并不優(yōu)于整數(shù)規(guī)劃。相比之下,整數(shù)規(guī)劃則更加靈活,它可以通過合并分支決策或加入有效不等式來實現(xiàn)高效求解。因此,本文將以整數(shù)規(guī)劃為理論基礎(chǔ),對VRPTW進行算法優(yōu)化。主要提出并實現(xiàn)的創(chuàng)新點及研究成... 

【文章來源】：武漢理工大學湖北省 211工程院校 教育部直屬院校

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景及意義
        1.1.1 研究背景
        1.1.2 研究意義
    1.2 課題來源
    1.3 國內(nèi)外研究現(xiàn)狀
        1.3.1 車輛路徑問題研究
        1.3.2 帶時間窗的車輛路徑問題研究
    1.4 研究內(nèi)容及結(jié)構(gòu)安排
第2章 相關(guān)理論及技術(shù)
    2.1 多面體理論
        2.1.1 仿射集
        2.1.2 多面體及小平面
    2.2 最短路徑問題
    2.3 帶時間窗的車輛路徑問題描述
        2.3.1 問題定義與假設(shè)
        2.3.2 數(shù)學描述
    2.4 整數(shù)線性規(guī)劃
        2.4.1 分支定界
        2.4.2 列生成
        2.4.3 割平面
    2.5 基于三維多商品網(wǎng)絡(luò)流的數(shù)學模型
    2.6 基于路徑不等式的數(shù)學模型
    2.7 本章小結(jié)
第3章 帶時間窗車輛路徑問題的模型研究
    3.1 基于集合劃分的數(shù)學模型
        3.1.1 主問題
        3.1.2 子問題
    3.2 基于二維車流的數(shù)學模型
    3.3 本章小結(jié)
第4章 帶資源約束的基本最短路問題
    4.1 ESPPRC問題描述與數(shù)學模型
        4.1.1 問題描述
        4.1.2 數(shù)學模型
    4.2 統(tǒng)治規(guī)則
        4.2.1 動態(tài)規(guī)劃的統(tǒng)治規(guī)則
        4.2.2 整數(shù)規(guī)劃的統(tǒng)治規(guī)則
    4.3 多面體理論分析
        4.3.1 兩點加強割集不等式
        4.3.2 三點加強割集不等式
    4.4 有效不等式
        4.4.1 點邊不等式
        4.4.2 時間前后不等式
        4.4.3 順序前后不等式
    4.5 本章小結(jié)
第5章 實驗設(shè)計與結(jié)果分析
    5.1 ESPPRC實驗設(shè)計與結(jié)果分析
        5.1.1 數(shù)據(jù)來源與實驗環(huán)境
        5.1.2 實驗設(shè)置與參數(shù)說明
        5.1.3 結(jié)果分析
    5.2 VRPTW實驗設(shè)計與結(jié)果分析
        5.2.1 數(shù)據(jù)來源與實驗環(huán)境
        5.2.2 實驗設(shè)置與參數(shù)說明
        5.2.3 結(jié)果分析
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 全文總結(jié)
    6.2 研究展望
致謝
參考文獻
攻讀碩士期間研究成果和參與項目
    一、發(fā)表論文
    二、參與項目


【參考文獻】：
期刊論文
[1]求解帶時間窗取送貨問題的遺傳算法[J]. 潘立軍,符卓.  系統(tǒng)工程理論與實踐. 2012(01)
[2]一種改進的Dijkstra算法在嵌入式GIS中的應(yīng)用[J]. 劉志宇,楊柳.  計算機應(yīng)用與軟件. 2009(12)
[3]帶時間窗和隨機時間車輛路徑問題:模型和算法[J]. 李相勇,田澎.  系統(tǒng)工程理論與實踐. 2009(08)
[4]用單親遺傳算法求解配送車輛調(diào)度問題的研究[J]. 郎茂祥.  交通與計算機. 2006(01)
[5]車輛路徑問題（VRP）的螞蟻搜索算法[J]. 崔雪麗,馬良,范炳全.  系統(tǒng)工程學報. 2004(04)
[6]基于模擬退火遺傳算法的車輛路徑問題研究[J]. 許國平,葉效鋒,鮑立威.  工業(yè)控制計算機. 2004(06)
[7]有時間窗的集貨送貨一體化車輛路徑規(guī)劃啟發(fā)式算法研究[J]. 霍佳震,張磊.  物流技術(shù). 2004(05)
[8]帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究[J]. 符卓.  系統(tǒng)工程理論與實踐. 2004(03)
[9]有時間窗車輛路徑問題的改進遺傳算法[J]. 張麗萍,柴躍廷,曹瑞.  計算機集成制造系統(tǒng)-CIMS. 2002(06)
[10]供應(yīng)鏈中車輛路徑問題的研究進展及前景[J]. 祝崇雋,劉民,吳澄.  計算機集成制造系統(tǒng)-CIMS. 2001(11)

碩士論文
[1]帶時間窗車輛路徑問題的精確算法研究[D]. 答家瑞.武漢理工大學 2017



本文編號：3152824