改進(jìn)變鄰域搜索算法在動(dòng)態(tài)車輛路徑問題中的研究.pdf

1、物流調(diào)度在現(xiàn)代社會(huì)經(jīng)濟(jì)活動(dòng)中的地位越來越重要。隨著物流活動(dòng)在經(jīng)濟(jì)活動(dòng)中的比重越來越大，降低物流成本已經(jīng)成為企業(yè)降低運(yùn)營成本的一個(gè)核心。車輛路徑問題(VRP,VehicleRouteProblem)由旅行商問題（TSP,TravellingSalesmanProblem）發(fā)展而來，自提出以來，引起了眾多學(xué)者的廣泛關(guān)注和深入研究。經(jīng)過數(shù)十年的研究，眾多的車輛路徑問題模型以及它們的解決算法已被提出。
　　車輛路徑問題是組合優(yōu)化領(lǐng)域中典型

2、的NP-hard(NP-Hard,non-deterministicpolynomialhard)問題，可分為靜態(tài)車輛路徑問題(SVRP,StaticVehicleRouteProblem)和動(dòng)態(tài)車輛路徑問題(DVRP,DynamicVehicleRouteProblem)。動(dòng)態(tài)車輛路徑問題是一種需求實(shí)時(shí)送達(dá)的，由靜態(tài)車輛路徑問題發(fā)展而來的新的車輛路徑問題模型，是對(duì)現(xiàn)實(shí)物流更加真實(shí)的抽象。動(dòng)態(tài)車輛路徑問題也是比靜態(tài)車輛路徑問題更加復(fù)雜的

3、一類NP-hard問題，目前的計(jì)算機(jī)和確定性算法無法在合理的時(shí)間范圍內(nèi)得到車輛路徑問題的最優(yōu)解。因此，針對(duì)動(dòng)態(tài)車輛路徑問題的研究，現(xiàn)主要集中在采用啟發(fā)式算法求其近似解。
　　幾乎所有的啟發(fā)式算法都是在全局搜索和局部搜索之間尋求一種平衡，以使得算法的效率和性能盡可能優(yōu)化。變鄰域搜索算法是一種快速有效的啟發(fā)式算法，但易陷入局部最優(yōu)化。采用變鄰域搜索算法解決動(dòng)態(tài)車輛路徑問題，即需尋找一種全局搜索與局部搜索的一種平衡，使動(dòng)態(tài)車輛路徑問題的

4、目標(biāo)函數(shù)盡可能小，且保持可接受的算法速度。變鄰域搜索算法的鄰域結(jié)構(gòu)代表了所求問題的搜索空間或解空間，對(duì)鄰域結(jié)構(gòu)的表示是變鄰域搜索算法的核心。對(duì)搜索空間解進(jìn)行搜索時(shí)，搜索策略對(duì)算法效率的具有很大的影響。在局部搜索算法中，多采用類似爬山法（hill-climbingmethod）的搜索策略，以盡快找到優(yōu)化解，而此方法很容易陷入局部最優(yōu)。據(jù)此，文章提出改進(jìn)基本變鄰域搜索算法的鄰域結(jié)構(gòu)，保證所求問題的最優(yōu)解包含在搜索空間中。另外，通過調(diào)整搜索策

5、略即調(diào)整變鄰域搜索算法的局部搜索方法，使算法能夠盡快找到局部最優(yōu)解。應(yīng)用改進(jìn)變鄰域搜索算法求解動(dòng)態(tài)車輛路徑問題時(shí)，根據(jù)動(dòng)態(tài)車輛路徑問題本身的特點(diǎn)，為加快搜索速度，在搜索的過程中加入了粒度搜索。實(shí)驗(yàn)結(jié)果顯示，改進(jìn)的算法對(duì)解決動(dòng)態(tài)車輛路徑問題具有較好的有效性。本文主要做了如下工作：
　　（1）回顧車輛路徑問題模型，分析其特點(diǎn)，并詳細(xì)介紹了動(dòng)態(tài)車輛路徑問題模型；
　?。?）介紹基本變鄰域搜索算法的結(jié)構(gòu)和特點(diǎn)，并分析其優(yōu)缺點(diǎn)，提出需