基于混合遺傳算法的有時(shí)間窗車(chē)輛路徑問(wèn)題研究.pdf

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

2、質(zhì)量的啟發(fā)式算法成為研究該問(wèn)題的主要發(fā)展方向。本文重點(diǎn)研究了基于混合遺傳算法求解有時(shí)間窗車(chē)輛路徑問(wèn)題。 詳細(xì)分析了VRPTW的特點(diǎn)，界定了所研究VRPTW的基本條件，建立了相應(yīng)的數(shù)學(xué)模型。根據(jù)特定的時(shí)間窗、車(chē)輛容量等條件約束，設(shè)計(jì)了VRPTW的遺傳算法(Genetic Algorithm，GA)。通過(guò)對(duì)遺傳算法、禁忌搜索算法(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能夠同時(shí)接收較優(yōu)解和劣解，使得父代個(gè)體也參加競(jìng)爭(zhēng)

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