車(chē)輛路徑問(wèn)題的啟發(fā)式算法研究.pdf

1、物流配送中的車(chē)輛路徑問(wèn)題是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的研究前沿與熱點(diǎn)問(wèn)題。車(chē)輛路徑問(wèn)題是對(duì)一系列已知需求量的客戶，組織適當(dāng)?shù)男熊?chē)線路進(jìn)行服務(wù)，在不違反任何約束條件下，優(yōu)化路線使得總成本達(dá)到最小。有效地解決該問(wèn)題可以提高車(chē)輛的利用率，降低配送成本，提高配送時(shí)間的準(zhǔn)確率，從而提高物流服務(wù)水平。由于車(chē)輛路徑問(wèn)題是典型的NP難題，使用傳統(tǒng)的優(yōu)化方法很難得到問(wèn)題的最優(yōu)解或滿意解，因此構(gòu)造高質(zhì)量的啟發(fā)式算法成為研究該問(wèn)題的主要發(fā)展方向。 本文針對(duì)

2、有時(shí)間窗的車(chē)輛路徑問(wèn)題提出了兩種求解算法——基于λ-交換的局部下降搜索算法和基于自然數(shù)編碼的遺傳算法。前者是一個(gè)兩階段啟發(fā)式算法，可以有效地獲得該問(wèn)題的可行解。然而局部搜索算法易于陷入局部極小，因此具有一定的全局搜索能力的遺傳算法在求解組合優(yōu)化問(wèn)題時(shí)顯示出了優(yōu)越性。遺傳算法是基于“適者生存”的一種高度并行、隨機(jī)和自適應(yīng)的優(yōu)化算法。雖然遺傳算法沒(méi)有傳統(tǒng)的優(yōu)化算法復(fù)雜的運(yùn)行機(jī)制，但是遺傳算法具有很強(qiáng)的搜索能力，能以很大概率找到問(wèn)題的全局最優(yōu)

3、解，并且由于它固有的并行性，能有效地處理大規(guī)模的優(yōu)化問(wèn)題。因此，與基于λ-交換的局部下降搜索算法相比，基于自然數(shù)編碼的遺傳算法可以更好的解決有時(shí)間窗的車(chē)輛路徑問(wèn)題。 本文研究?jī)?nèi)容的一個(gè)重點(diǎn)和難點(diǎn)是集貨和送貨一體化的車(chē)輛路徑問(wèn)題。本文采用了新穎的自然數(shù)編碼方法，設(shè)計(jì)了遺傳算法對(duì)該問(wèn)題進(jìn)行求解。在求解過(guò)程中，對(duì)集送一體化、多種配送車(chē)輛類型的問(wèn)題進(jìn)行了有效處理，同時(shí)考慮了車(chē)輛載重量和時(shí)間窗等約束。 通過(guò)求解Solomon提出的