基于混合遺傳算法的有時間窗車輛路徑問題研究.pdf

1、車輛路徑問題(Vehicle Routing Problem，VRP)是對一系列己知需求量的客戶，組織適當?shù)男熊嚲€路進行服務(wù)，在不違反約束條件下，優(yōu)化路線使總成本最小。有時間窗的車輛路徑問題(Vehicle Routing Problem with Time Windows，VRPTW)因其重要的現(xiàn)實意義備受關(guān)注，所謂時間窗即客戶接受服務(wù)的時間范圍。由于車輛路徑問題是典型的NP難題，傳統(tǒng)的優(yōu)化方法很難得到問題的最優(yōu)解或滿意解，因此構(gòu)造高

2、質(zhì)量的啟發(fā)式算法成為研究該問題的主要發(fā)展方向。本文重點研究了基于混合遺傳算法求解有時間窗車輛路徑問題。 詳細分析了VRPTW的特點，界定了所研究VRPTW的基本條件，建立了相應(yīng)的數(shù)學模型。根據(jù)特定的時間窗、車輛容量等條件約束，設(shè)計了VRPTW的遺傳算法(Genetic Algorithm，GA)。通過對遺傳算法、禁忌搜索算法(Tabu Search，TS)及模擬退火算法(Simulated．Annealing，SA)的分析比較，

3、以遺傳算法為框架，融合其它兩者，提出了用于VRPTW的混合遺傳模擬退火算法(Genetic-SimulatedAnnealing Algorithm，GSA)及混合遺傳禁忌搜索模擬退火算法(Genetic-TabuSearch-Simulated Annealing Algorithm，GTSA)。 在GSA中，將模擬退火算法的Metropolis規(guī)則應(yīng)用到GA的交叉操作中，讓GA能夠同時接收較優(yōu)解和劣解，使得父代個體也參加競爭

4、，這樣不但避免了GA陷入局部最優(yōu)，同時又消除了基本遺傳算法由于無選擇的接收新解而可能會出現(xiàn)的隨機搜索現(xiàn)象；在GTSA中，把TS引入到GA的復制操作中產(chǎn)生新的個體，使得遺傳算法中每代個體具有盡可能的多樣性，從而避免了GA陷入局部最優(yōu)而出現(xiàn)“早熟”現(xiàn)象，在遺傳操作產(chǎn)生新的種群后，對新種群使用SA，以大大增加接受較優(yōu)解的概率，進而提高GA的收斂性能，加速了算法的收斂。 通過實例，用MATLAB編程實現(xiàn)了所提出的GA、GSA、GTSA三