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

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

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

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

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