基于模擬退火算法的啟發(fā)式算法在VRP中的應(yīng)用.pdf

1、VRP問題在現(xiàn)實(shí)生活中應(yīng)用廣泛，很多領(lǐng)域的問題都可以抽象成VRP問題進(jìn)行解決，其研究和應(yīng)用一直是熱點(diǎn)。
　　 本文首先詳細(xì)介紹了VRP問題的分類，常見的約束條件及基本的研究技術(shù)和方法。給出了幾個(gè)基本VRP問題的介紹及其數(shù)學(xué)模型。
　　 模擬退火算法(SA)相對(duì)于其它智能算法在求解VRP問題時(shí)具有收斂速度快且能找到全局最優(yōu)解的優(yōu)點(diǎn)。因此本文詳細(xì)介紹了模擬退火算法的數(shù)學(xué)模型及其尋優(yōu)方法，證明了模擬退火算法可以找到全局最優(yōu)解，

2、研究了模擬退火算法優(yōu)缺點(diǎn)。基于模擬退火算法給出了固定車輛數(shù)單目標(biāo)VRP問題的MATLAB語(yǔ)言算法。
　　 本文對(duì)一個(gè)中心倉(cāng)庫(kù)的不確定車輛數(shù)的有時(shí)間窗的閉合VRP問題結(jié)合案例進(jìn)行了研究，給出了兩種求解方法。第一種方法，利用優(yōu)先處理時(shí)間窗口策略大大簡(jiǎn)化了VRP問題，接著結(jié)合圖形，通過排列組合給出了所有可能的VRP路徑，其中最短VRP路徑即為所求。第二種方法，首先把VRP轉(zhuǎn)化成圖論語(yǔ)言，構(gòu)造了圖G;其次通過時(shí)間窗口限制，利用圖論染色算

3、法對(duì)G進(jìn)行染色，得到了圖G的最大獨(dú)立集，其中獨(dú)立集集階最大數(shù)為K，則K即為VRP問題最小車輛數(shù)。接著，固定最小車輛數(shù)K，給出了基于圖論貪心搜索算法的固定車輛數(shù)單目標(biāo)VRP問題算法，并結(jié)合該案例給出了求解結(jié)果。
　　 本文對(duì)多中心倉(cāng)庫(kù)確定車輛數(shù)的閉合VRP問題結(jié)合案例進(jìn)行了研究。主要研究成果即分兩個(gè)階段實(shí)現(xiàn)了問題求解。第一個(gè)階段實(shí)現(xiàn)了將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，給出了圓域擴(kuò)充算法;第二階段求解了多車輛數(shù)的單目標(biāo)VRP問題。求解分

4、為四個(gè)過程:第一過程，首先，研究了基于模擬退火算法的最短TSP路徑算法。第二過程，首先利用該算法給出了中心倉(cāng)庫(kù)3的最短TSP路徑。接著基于TSP最短路徑，給出了客戶集相對(duì)中心倉(cāng)庫(kù)分布均勻且中心倉(cāng)庫(kù)較集中的基于模擬退火的啟發(fā)式算法，并進(jìn)行了求解，給出了中心倉(cāng)庫(kù)3的較優(yōu)VRP路徑。第三過程，首先利用基于模擬退火算法的最短TSP路徑算法求解了中心倉(cāng)庫(kù)1的最短TSP路徑，接著給出了基于掃描法的多車輛數(shù)單目標(biāo)VRP問題啟發(fā)式算法，并進(jìn)行了求解，給