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

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

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

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