多目標遺傳算法在車輛路徑優(yōu)化中的應用研究.pdf

1、車輛問題（Vehicle Routing Problem，VRP）是近二十年來運籌學、應用數學、網絡分析、圖論、計算機應用及交通運輸等學科研究的一個熱點問題,是物流系統(tǒng)調度中關鍵的一環(huán)。對車輛路徑進行優(yōu)化調度，可以提高物流經濟效益，實現(xiàn)物流科學化。 車輛路徑問題是組合優(yōu)化中的帶多個約束條件的NP-完全問題,難以用常規(guī)方法求解，人們常致力于智能優(yōu)化算法的研究，如遺傳算法，禁忌搜索，蟻群最優(yōu)化等。這些方法在多項式時間內獲得一個近似解

2、，而不是以高昂的時間開銷來獲取一個精確解。對于該問題中的車輛數和總行車路程這兩個目標而言，以往的研究多數是優(yōu)先考慮最小化車輛數，再考慮最小化總行車路程，這實際上是一種帶偏好的單目標最優(yōu)化方法。而本文同等地對待車輛數和總行車路程這兩個目標，將車輛路徑問題描述成一個多目標最優(yōu)化問題(Multi-Objective Optimization, MOP)。通過返回一個非支配解的集合而非單一的一個非支配解，為決策者提供了更有力的決策支持。

3、 本文首先介紹了車輛路徑問題的研究現(xiàn)狀和多目標最優(yōu)化的相關理論知識。其次在此基礎上提出了帶時間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows, VRPTW）的多目標數學模型，設計出一種求解該問題的高效的多目標遺傳算法。采納了擂臺法則作為快速構造非支配集的方法以加快算法的運行效率。提出了可變概率的λ-interchange局部搜索法以增強遺傳算法的局部搜索能力。設計了一種具有最佳費用的