遺傳算法在帶時間窗的車輛路徑問題中的應(yīng)用.pdf

1、經(jīng)濟(jì)的發(fā)展使得物流成為了一門重要的產(chǎn)業(yè),車輛路徑問題(VRP, Vehicle Routing Problem)是物流中最重要的一部分,引起了學(xué)者與企業(yè)管理者的高度重視。由于消費者對配送時間的要求越加嚴(yán)格,因而對帶時間窗的車輛路徑問題(VRPTW, Vehicle Routing Problem with Time Windows)的研究具有重要的現(xiàn)實意義。
　　本文針對基本遺傳算法的不足作了一系列的改進(jìn),并用C語言進(jìn)行了編程實現(xiàn)

2、。用程序?qū)唧w的帶時間窗的車輛路徑問題實例進(jìn)行求解,證實了本文改進(jìn)算法的有效性。
　　本文的主要工作包括:
　　(1)建立了有懲罰函數(shù)的VRPTW的數(shù)學(xué)模型。設(shè)置懲罰函數(shù),對車輛提前到達(dá)或延后到達(dá)加以懲罰,根據(jù)客戶不同的服務(wù)要求,設(shè)置了兩類懲罰函數(shù),一類是線性函數(shù),一類是二次函數(shù),其中二次函數(shù)的模型更符合實際,因為當(dāng)配送車輛提前或延后送達(dá)的時間較小時對顧客的滿意度不會有太大的影響,而當(dāng)提前或延后的時間較大時則會嚴(yán)重降低客戶的

3、滿意度。
　　(2)提出了一種新的交叉算子。新交叉算子將已尋優(yōu)的部分路徑段(優(yōu)良基因段)作為一個整體,交叉后不會破壞優(yōu)良的基因段。此外,比較了交叉前后的染色體適應(yīng)度的變化,若交叉后的染色體更差則保留交叉前的染色體。通過與其他交叉算子如順序交叉、部分匹配交叉(PMX)算子的求解效率作比較,證實了該新交叉算子的科學(xué)合理性。
　　(3)對遺傳算法的選擇操作進(jìn)行了改進(jìn),引出了一種優(yōu)化的輪盤賭選擇方法,并保留了每次迭代時的最優(yōu)個體。采