發(fā)布時間：2020-11-03 04:35

　　 作為現(xiàn)代物流中的重要環(huán)節(jié),物流配送路徑優(yōu)化是有效降低配送成本和提高配送效率的重要手段。本文研究配送路徑優(yōu)化中的兩點配送路徑選擇問題和多點配送車輛路徑優(yōu)化問題,在綜述了國內(nèi)外路徑優(yōu)化研究現(xiàn)狀的基礎(chǔ)上,著重對路徑優(yōu)化的求解方法、考慮顧客需求隨機性和負載變化的多點配送綠色車輛路徑優(yōu)化問題、不確定多因素下的兩點配送路徑選擇問題進行了研究,并提出了相關(guān)的解決方法。本文研究工作包括以下三個方面:(1)針對帶容量約束的多點配送車輛路徑優(yōu)化問題(Capacitated Vehicle Routing Problem,CVRP),提出了一種基于禁忌搜索的混合模擬退火算法(Hybrid Simulated Annealing Algorithm,HSAA)求解。相比于傳統(tǒng)的模擬退火算法,本文提出的HSAA算法具有以下改進:不同于傳統(tǒng)隨機初始化方法,通過引入k-means聚類算法進行簇劃分和使用插入法進行簇調(diào)整,得到能考慮顧客地理分布特性的初始可行解;借鑒禁忌搜索算法的思想,使用K-近鄰算法生成禁忌表,通過4種鄰域搜索方法遍歷禁忌表的全局逐步尋優(yōu)搜索方式,在擴展鄰域搜索范圍的同時,提升鄰域搜索過程的有效性。為驗證HSAA算法的性能,本文使用20個標準CVRP算例進行測試,并與文獻中已有算法進行對比。實驗結(jié)果表明,本文提出HSAA算法的尋優(yōu)能力和同等溫度衰減次數(shù)下的收斂速度均優(yōu)于已有的具有重啟策略的模擬退火算法。(2)針對綠色節(jié)能路徑優(yōu)化問題,提出了同時考慮隨機需求和負載變化的多點配送車輛路徑優(yōu)化模型,并在本文提出的HSAA算法基礎(chǔ)上給出了相應(yīng)的求解方法。在實際配送場景中,車輛負載與其能耗率具有正比關(guān)系。傳統(tǒng)的車輛路徑優(yōu)化模型僅考慮配送距離最短,忽略了車輛負載對能耗的影響,其所得最優(yōu)路徑在能耗上并不是最小的。同時,已有研究一般只考慮確定的顧客需求,而忽視了其隨機性。本文以最小化配送運輸能耗為目標,考慮隨機需求對車輛負載的影響,并引入風險概率約束來描述因隨機需求而導(dǎo)致車輛出現(xiàn)超載的概率,還提出了風險概率的簡化策略,以降低算法求解復(fù)雜度。實驗結(jié)果表明:相比于傳統(tǒng)路徑優(yōu)化模型,考慮車輛負載變化和顧客需求隨機性的路徑優(yōu)化方法可以有效避免車輛超載并且降低能耗,進而提升優(yōu)化結(jié)果的實用性并降低配送成本。(3)針對不確定多因素下的兩點配送路徑選擇問題,提出了基于證據(jù)推理的路徑選擇方法。目前,已有路徑選擇研究多集中于靜態(tài)運輸網(wǎng)絡(luò),不符合實際場景下運輸網(wǎng)絡(luò)的動態(tài)隨機特性。另外,實際交通場景中車輛的配送路徑選擇結(jié)果往往受多種因素影響,其結(jié)果也往往是不確定的,因此僅考慮運輸網(wǎng)絡(luò)中的某一單個因素是難以得到合理滿意的路徑選擇結(jié)果。本文考慮實際動態(tài)隨機運輸網(wǎng)絡(luò)中的多條候選路徑選擇問題,提出了基于證據(jù)推理的不確定多因素路徑選擇方法。首先將影響候選路徑的因素數(shù)據(jù)通過隸屬度函數(shù)構(gòu)建簡單支持證據(jù),再使用Dempster組合規(guī)則融合所有因素的證據(jù)體獲取全局基本信度分配,最終選擇具有最大信度的路徑作為最優(yōu)結(jié)果。通過北京市實際配送場景驗證提出的方法的有效性,并給出了詳細的運算結(jié)果。結(jié)果表明,相比于模糊層次分析法,本文提出的方法所得到的評估結(jié)果具有更高的區(qū)分度,因此能更有效地消除決策結(jié)果的不確定性。
【學位單位】：北京交通大學
【學位級別】：博士
【學位年份】：2019
【中圖分類】：F252.1;TP18
【部分圖文】：

１．３技術(shù)路線和論文結(jié)構(gòu)??１．３．１技術(shù)路線??根據(jù)本文的研宄內(nèi)容，本文的技術(shù)路線如圖１－２所示。??（??１?ｉ?提出?｜??第丨章緒論??研宄背景和研究意義?ｉ問題：??１?Ｊ?Ｉ??ｊ?；階段；??＼??ｙ?ｌ?；??路徑優(yōu)化問題國內(nèi)外文獻綜述ｉ?理論基礎(chǔ)?????Ｉ；?ｊ???ｉ！??Ｃ?第２章?Ｈ多點配送車輛路徑優(yōu)化問題１丨聚類算法??文獻綜述和理論基礎(chǔ)?｜！?丨丨模擬退火?｜ｉ?＇：問題：??Ｖ?Ｊ?！??１丨林已油，去?層次分析丨丨：＇????！?兩點配送路徑選擇問題?丨！禁忌搜索?｜｜丨階段：??１１?！?！?１１??！??Ｉ??ｖ??模型構(gòu)建?算法設(shè)計??Ｉ?Ｉ??廣?第５章?｜?｜???１?｜??帶容量約束的多點配送車輛ＣＶＲＰ問題模型?一？?ＨＳＡＡ算法??、?路徑優(yōu)化問題?」???ｊ；??Ｉ?Ｉ??Ｉ?Ｉ???ｊｒ??１?ｉ?ｊ?１??第４?章?１??考慮隨機需求和負載變化的ＬＶＧＶＲＰＳＤ問題模型?—?ＨＳＡＡ算法?＾?Ｉ問題：??＾多點配送車輛路徑優(yōu)化問題＾）?Ｊ＼＼?ｊ階段｜??ｌ?ｉ??Ｉ?Ｉ???ｙ?ｒ??ｊ?ｒ?｜?ｊ??Ｌ■占基于證據(jù)理論的不確定多?基于證據(jù)推理的不確定??卜點配，—－評估模型—．＾—多—徑選擇方法一；｜

綜合上述冷卻進度表的參數(shù)，ＳＡＡ算法一般的求解步驟如下：??Ｓｔｅｐｌ：初始化。設(shè)置初始溫度，終止溫度７＾及哀減函數(shù)７Ｘ／）的哀減因卞以，??Ｍａｒｋｏｖ鏈的長度；??Ｓｔｅｐ２：從可行解空間隨機選取一初始解，作為當前解計算目??標函數(shù)八義）；??Ｓｔｅｐ３：從當前解的鄰域中隨機擾動產(chǎn)生一個新解Ｘ，計算新解的目標函數(shù)??／（Ｘ），并計算目標函數(shù)增量Ａ／?＝?／（義）－／（々）；??Ｓｔｅｐ４：若Ａ／＜０，則接受新解Ｘ作為當前解，令否則以概率??；？?＝?ｅｘｐ?接受欠作為新的當前解；??Ｖ?Ｔ?）??２３??

ｓ＝ｍ（２－１２）??所定義的函數(shù)：２ｅ?－＞［０，１］為框架Ｇ）上的似真度函數(shù)（Ｐｌａｕｓｉｂｉｌｉｔｙ?Ｆｕｎｃｔｉｏｎ）。??反映的是對所有不懷疑命題Ｊ的子集所對應(yīng)的信度之和。??信度函數(shù)價／（七和似真度函數(shù)之間有如下的關(guān)系：??Ｐｌｓ（Ａ）?＝?＼－Ｂｅｌ（Ａ）?（２－１３）??Ｐｌｓ＾Ａ）?＞?Ｂｅｌ＾Ａ）?（２－１４）??其中，２為命題ｄ的補集，從式（２－１４）可知ＰｈＭ）是比價／（ｄ）更寬松的一種??估計。??證據(jù)理論就是通過價／（七和他（七這兩個函數(shù)來描述不確定性，＆／（七和??分別表示假設(shè)ｄ所對應(yīng)的信度的下界和上界，由二者組成的區(qū)間??稱為命題ｄ的信度區(qū)間，表征假設(shè)Ｊ的不確定性程度的范圍，也稱為不確??定區(qū)間。而他（七－５？描述了假設(shè)Ｊ的無知程度的大小，外（七和價／（」）之??間的差值越大，假設(shè)Ｊ所對應(yīng)的無知度越大，證據(jù)的可靠性越低。＆／ｐ）和??對不確定性的描述如圖２－３所示：??
【參考文獻】

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

1 李進;傅培華;李修琳;張江華;朱道立;;低碳環(huán)境下的車輛路徑問題及禁忌搜索算法研究[J];中國管理科學;2015年10期

2 張曉楠;范厚明;;混合分散搜索算法求解帶容量約束車輛路徑問題[J];控制與決策;2015年11期

3 葛顯龍;苗國慶;譚柏川;;開放式污染路徑問題優(yōu)化建模與算法研究[J];工業(yè)工程與管理;2015年04期

4 蔡延光;湯雅連;;關(guān)聯(lián)運輸調(diào)度問題帶遺傳算子的自適應(yīng)蟻群算法[J];計算機應(yīng)用研究;2015年08期

5 劉萬峰;李霞;;車輛路徑問題的快速多鄰域迭代局部搜索算法[J];深圳大學學報(理工版);2015年02期

6 楊浩雄;王丹;張敬蕤;;基于蟻群算法的擁堵交通最短路徑研究[J];計算機仿真;2015年03期

7 李進;張江華;;基于碳排放與速度優(yōu)化的帶時間窗車輛路徑問題[J];系統(tǒng)工程理論與實踐;2014年12期

8 李鋒;魏瑩;;求解隨機旅行時間的C-VRP問題的混合遺傳算法[J];系統(tǒng)管理學報;2014年06期

9 潘義勇;孫璐;;交通網(wǎng)絡(luò)最優(yōu)路徑問題分類研究[J];交通運輸工程與信息學報;2014年03期

10 鄭建湖;伍雄斌;黃明芳;文子娟;;有偏好的多屬性灰色關(guān)聯(lián)路徑選擇模型[J];交通運輸系統(tǒng)工程與信息;2014年04期

本文編號：2868101