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

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

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

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