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

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

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

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