TSP問題即旅行商問題,是運籌學的著名問題之一,也是物流行業(yè)關鍵問題之一。隨著客戶對服務時間的要求,進而發(fā)展為帶時間窗約束的旅行商問題(TSPTW),然而隨著環(huán)境保護和節(jié)約能源的思想慢慢滲透到物流行業(yè),該行業(yè)所要考慮的成本不再單單是時間、車輛行駛路程長度,還需要考慮車輛的油耗,這樣考慮實時載重與當前載重行駛距離的變體TSPTW應運而生,該問題可在幫助物流行業(yè)控制成本的基礎上控制油耗,為物流行業(yè)節(jié)約運輸成本的同時滿足其對減少碳排放量的需求。本文對以上問題構建數(shù)學模型并研究其求解算法。首先對該問題建立整數(shù)線性規(guī)劃模型,但隨著規(guī)模的增加,其求解時間急劇增大,因此,本文采用以下四種啟發(fā)式算法求解該問題:采用改變了轉移到下一節(jié)點期望函數(shù)的蟻群算法;采用輪盤賭選擇算子、PMC交叉算子、倒位變異算子和適用于上述模型的適應度函數(shù)的遺傳算法;采用Metropolis接受準則的模擬退火算法;采用以模型目標函數(shù)為適應度函數(shù)的粒子群算法;最后,應用SolomonTSPTW數(shù)據(jù)包中的rc₂08.3算例和rc₂03.2算例進行仿真試驗,利用MATLAB 2017a軟件對...

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景及意義
    1.2 旅行商問題起源、發(fā)展及其研究現(xiàn)狀
    1.3 本文的研究方法及主要內容
    1.4 本章小結
第二章 變體TSPTW概述
    2.1 旅行商問題(TSP)
        2.1.1 TSP問題的定義
        2.1.2 TSP問題數(shù)學模型
    2.2 帶時間窗的旅行商問題(TSPTW)
        2.2.1 帶時間窗的旅行商問題的組成要素
        2.2.2 帶時間窗的旅行商問題的數(shù)學模型
    2.3 帶時間窗的流旅行商問題(變體TSPTW)
        2.3.1 帶時間窗流旅行商問題的定義
        2.3.2 帶時間窗流旅行商問題的數(shù)學模型準備
    2.4 本章小結
第三章 變體TSPTW求解算法研究
    3.1 精確算法
    3.2 啟發(fā)式算法
        3.2.1 傳統(tǒng)啟發(fā)式算法
        3.2.2 現(xiàn)代啟發(fā)式算法
    3.3 蟻群優(yōu)化算法
        3.3.1 蟻群算法解決TSP問題的數(shù)學模型
        3.3.2 蟻群優(yōu)化算法流程圖
    3.4 遺傳算法
        3.4.1 遺傳算法的相關概念
        3.4.2 遺傳算法工作流程
    3.5 粒子群算法
        3.5.1 粒子群算法的數(shù)學模型
        3.5.2 粒子群算法的算法流程圖
    3.6 模擬退火算法
        3.6.1 模擬退火過程描述
        3.6.2 Metropolis接受準則
        3.6.3 模擬退火算法的基本流程
    3.7 常用算法概括與比較
    3.8 本章小結
第四章 變體TSPTW的模型建立與算法設計
    4.1 變體TSPTW模型構建
        4.1.1 問題描述
        4.1.2 基本假設
        4.1.3 懲罰函數(shù)
        4.1.4 定義變量
        4.1.5 模型建立
    4.2 蟻群算法設計
        4.2.1 信息素調整策略
        4.2.2 具體求解步驟
    4.3 遺傳算法設計
        4.3.1 編解碼
        4.3.2 初始群體
        4.3.3 選擇算子
        4.3.4 交叉算子
        4.3.5 變異算子
        4.3.6 適應度函數(shù)
        4.3.7 終止進化規(guī)則
    4.4 粒子群算法設計
        4.4.1 粒子速度、位置和適應度函數(shù)的設計
        4.4.2 粒子群算法具體求解步驟
    4.5 模擬退火算法設計
        4.5.1 算法環(huán)節(jié)及接受準則設計
        4.5.2 模擬退火算法流程
    4.6 本章小結
第五章 算例分析
    5.1 算例說明
    5.2 測試數(shù)據(jù)
    5.3 模型參數(shù)設定
    5.4 蟻群算法求解結果
        5.4.1 參數(shù)設定
        5.4.2 rc₂08.3算例試驗結果
        5.4.3 rc₂03.2算例試驗結果
    5.5 遺傳算法求解結果
        5.5.1 參數(shù)設定
        5.5.2 rc₂08.3算例試驗結果
        5.5.3 rc₂03.2算例試驗結果
    5.6 粒子群算法求解結果
        5.6.1 參數(shù)設定
        5.6.2 rc₂08.3算例試驗結果
        5.6.3 rc₂03.2算例試驗結果
    5.7 模擬退火算法求解結果
        5.7.1 參數(shù)設定
        5.7.2 rc₂08.3算例試驗結果
        5.7.3 rc₂03.2算例試驗結果
    5.8 結果分析
    5.9 本章小結
第六章 總結及展望
    6.1 全文總結
    6.2 研究展望
參考文獻
附錄
作者簡介
致謝



本文編號：3758819