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

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

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

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

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

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