一種求解多目標車輛路徑問題的遺傳算法研究.pdf

1、車輛路徑問題(Vehicle routing problem，VRP)是一個經典的運籌學問題，它是指若干個客戶各自有著不同的貨物需求，若干個配送中心向客戶提供貨物，由車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。VRP問題在科學和工程應用領域具有非常廣泛的應用，很多實際的物流運輸問題都可以轉化成各種VRP問題來進行解決。由于VRP已經被證明是NP難

2、的，所以對于大規(guī)模VRP問題往往考慮利用各種智能優(yōu)化算法來進行求解。
　　隨著經濟的發(fā)展、科學技術的進步以及人們需求的日益多元化，越來越多實際應用問題往往需要考慮多個優(yōu)化目標，多目標優(yōu)化正在成為近年來運籌學領域一個研究熱點。需要注意的是目前關于多目標VRP問題的研究文獻并不多，在很多方面尤其是求解算法設計方面亟需開展進一步深入的研究。
　　本文采納系統(tǒng)工程的思想，利用運籌學、進化計算等領域的相關研究成果，設計和開發(fā)一種能夠有

3、效求解多目標VRP問題的遺傳算法(Genetic algorithm，GA)。本文的主要內容可以歸納如下幾個方面:
　　(1)相關工作綜述部分。主要介紹了VRP問題及求解算法、多目標優(yōu)化理論與方法等方面的研究工作。
　　(2)問題建模部分。在給出一般VRP以及帶有時間窗約束VRP問題數學模型的基礎上，建立一個以最小化配送成本和最大化客戶滿意度為目標函數的多目標VRP問題的數學模型。
　　(3)算法設計部分。研究一般VR

4、P問題的求解算法，考慮到編碼和解碼是求解VRP問題的GA設計中所面臨的主要挑戰(zhàn)，對三種不同編碼方法的有效性進行對比仿真實驗。在上述研究結論的基礎上，通過結合一種經典多目標進化算法(MOEA/D)的相關思想，提出一種能夠求解多目標VRP問題的新型多目標GA算法。
　　(4)仿真實驗部分。利用一組根據VRPLIB中標準測試問題構造的多目標VRP問題，對所提出的多目標GA算法進行仿真實驗以檢驗其性能。此外，還在仿真實驗中分析所提出的算法