當(dāng)今世界經(jīng)濟(jì)的迅猛發(fā)展大大促進(jìn)了物流運(yùn)輸?shù)陌l(fā)展,物流產(chǎn)業(yè)作為各國(guó)經(jīng)濟(jì)的重要組成部分,已經(jīng)廣泛的引起了人們的重視。目前物流的發(fā)展程度決定了一個(gè)國(guó)家的發(fā)展水平,它可以提高一個(gè)國(guó)家的國(guó)民生產(chǎn)總值,引導(dǎo)國(guó)家經(jīng)濟(jì)的發(fā)展方向。減少運(yùn)輸成本可以有效提高物流行業(yè)的效益,最常用的方法就是使運(yùn)輸路徑最短。傳統(tǒng)的車輛路徑問(wèn)題（Vehicle Routing Problem,VRP）就是研究運(yùn)輸路徑最小化的問(wèn)題。因?yàn)樗竺總€(gè)顧客的需求必須由一輛運(yùn)輸車進(jìn)行配送,所以當(dāng)一些顧客的需求量大于車輛容量時(shí),就會(huì)出現(xiàn)無(wú)法滿足所有顧客需求的情況。為了解決這個(gè)問(wèn)題,相關(guān)學(xué)者開始考慮對(duì)顧客的需求進(jìn)行拆分,并提出了需求可拆分車輛路徑問(wèn)題（Split Delivery Vehicle Routing Problem,SDVRP）。本文在研究SDVRP問(wèn)題的過(guò)程中發(fā)現(xiàn)它沒(méi)有考慮到在運(yùn)輸途中消耗物資的情況,因此本文將路徑消耗加入到SDVRP問(wèn)題的約束條件中,提出了運(yùn)輸途中貨物消耗的需求可拆分車輛路徑問(wèn)題（Split Delivery Vehicle Routing Problem with Goods Consumed during... 

【文章來(lái)源】：吉林大學(xué)吉林省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：61 頁(yè)

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

【部分圖文】：

SDVRP和SDVRP-GCT示例圖

第4章三種擴(kuò)展蟻群算法的實(shí)現(xiàn)19第4章三種擴(kuò)展蟻群算法的實(shí)現(xiàn)4.1蟻群算法概述蟻群算法是MarcoDorigo受到蟻群覓食行為的啟發(fā)后，于1992年在博士論文中提出的一種智能仿生算法，它能在合理計(jì)算時(shí)間內(nèi)得到組合優(yōu)化問(wèn)題的近似最優(yōu)解。在大量的研究中人們發(fā)現(xiàn)蟻群之所以能很快的聚集在一條尋找食物的最短路徑上，是因?yàn)橄伻褐械奈浵佋趯ふ衣窂綍r(shí)通過(guò)釋放一種微量的化學(xué)物質(zhì)-信息素進(jìn)行交流。每只螞蟻都會(huì)在途經(jīng)過(guò)的路上釋放信息素，其他螞蟻在尋找食物的時(shí)候可以根據(jù)路徑上信息素的殘留程度選擇出信息素濃度高的路徑，這樣一來(lái)該路徑被選擇的次數(shù)越多，信息素的濃度就越高，螞蟻越有可能選擇這條路徑，因此在一段時(shí)間后所有的螞蟻都會(huì)聚集在尋找食物的最短或者近似最短路徑上。如果在最短路徑上突然放置一個(gè)障礙物，蟻群也能很快的適應(yīng)新的環(huán)境，迅速改變路徑，找到食物的最優(yōu)路徑。下圖4.1[39]展示了蟻群的搜索機(jī)制。圖4.1蟻群覓食行為示意圖[39]4.2求解SDVRP-GCT問(wèn)題的蟻群算法提出背景起初相關(guān)學(xué)者們提出蟻群算法是為了解決旅行商（TSP）問(wèn)題，后來(lái)大量研究都證明了蟻群算法在離散優(yōu)化問(wèn)題，組合優(yōu)化問(wèn)題上都有非常好的性能。由于SDVRP-GCT是一個(gè)首次被提出的問(wèn)題，沒(méi)有現(xiàn)成的算法可以直接使用，蟻群算

第5章實(shí)驗(yàn)設(shè)計(jì)與分析32圖5.1三種擴(kuò)展算法在不同h時(shí)的最短路徑長(zhǎng)度比較正如預(yù)期的那樣，隨著h的逐漸增加，車輛在運(yùn)輸?shù)倪^(guò)程中消耗的貨物量逐漸增加，此時(shí)用于裝載顧客需求的容量逐漸減小，所以總的路徑長(zhǎng)度在增加。為了進(jìn)一步評(píng)估三個(gè)擴(kuò)展算法在新的SDVRP-GCT問(wèn)題上的性能，本文以h=0.1為例進(jìn)行實(shí)驗(yàn)然后詳細(xì)的分析所得到的實(shí)驗(yàn)結(jié)果，并將結(jié)果展示在下表5.5中，最后從實(shí)驗(yàn)得到的最短路徑長(zhǎng)度，所需車輛數(shù)目，以及算法運(yùn)行時(shí)間幾個(gè)方面分別進(jìn)行分析。表5.5三種擴(kuò)展算法在14個(gè)轉(zhuǎn)化后的SDVRP-GCT上的結(jié)果比較NameASGCTACGCTMMGCTMinAvg(std)MinAvg(std)MinAvg(std)S51D1490.21499.16(5.20)481.85487.98(4.61)473.34483.90(6.46)S51D2824.08847.30(8.39)806.78816.91(6.33)789.19811.26(12.52)S51D31065.511082.15(6.98)1036.601056.46(17.97)1043.191064.91(11.17)S51D41815.091830.01(8.92)1801.441819.24(7.67)1773.701805.31(15.31)S51D51502.251532.60(10.21)1479.221506.42(11.26)1485.071515.06(13.23)S51D62443.972479.82(14.47)2434.712450.68(7.92)2428.952474.72(13.99)S76D1705.44716.60(5.77)665.23681.37(8.79)655.56680.21(16.07)S76D21263.201278.18(7.89)1221.401260.07(13.66)1216.701243.99(17.10)S76D31661.411685.88(12.53)1643.981668.23(11.63)1620.521662.03(17.92)S76D42396.632421.87(12.43)2321.082361.50(16.82)2344.622377.14(18.50)S101D1813.45837.38(8.66)803.16820.23(9.38)793.60813.49(12.41)S101D21596.011629.53(11.26)1593.211613.29(11.81)1565.731598.78(21.42)S101D32109.012134.06(11.93)2086.622108.90(9.85)2088.622111.64(17.35)S101D53142.763204.34(30.51)3098.823121.55(11.31)3057.73


本文編號(hào)：2925200