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

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

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

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