車(chē)輛路徑問(wèn)題的粒子群算法研究與應(yīng)用.pdf

1、物流被稱為“第三利潤(rùn)源泉”，越來(lái)越受到人們的關(guān)注，日益成為國(guó)民經(jīng)濟(jì)的基礎(chǔ)產(chǎn)業(yè)。運(yùn)輸是物流中的重要環(huán)節(jié)，占物流成本的60％以上。車(chē)輛路徑問(wèn)題主要研究物流配送中車(chē)輛線路優(yōu)化以降低運(yùn)輸成本。該問(wèn)題是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域中的著名NP問(wèn)題，在航班調(diào)度、列車(chē)編組等眾多領(lǐng)域都有應(yīng)用。由于NP問(wèn)題求解的復(fù)雜性，目前車(chē)輛路徑問(wèn)題的求解方法主要使用各種智能優(yōu)化算法。本文主要研究了以下四種模型的車(chē)輛路徑問(wèn)題：有能力約束的車(chē)輛路徑問(wèn)題，開(kāi)放式車(chē)輛路徑問(wèn)題，基于

2、客戶滿意度的開(kāi)放式車(chē)輛路徑問(wèn)題，開(kāi)放式動(dòng)態(tài)網(wǎng)絡(luò)車(chē)輛路徑問(wèn)題。研究了粒子群及其改進(jìn)算法對(duì)上述模型的求解。具體的研究?jī)?nèi)容如下： (1)首先介紹了本論文的研究背景及意義，給出了車(chē)輛路徑問(wèn)題的定義，分析了車(chē)輛路徑問(wèn)題的組成要素。然后在對(duì)國(guó)內(nèi)外大量文獻(xiàn)總結(jié)提煉的基礎(chǔ)上，從車(chē)輛路徑問(wèn)題的模型和求解算法兩方面，深入分析了車(chē)輛路徑問(wèn)題的國(guó)內(nèi)外研究現(xiàn)狀。 (2)系統(tǒng)研究了基于粒子群算法的有能力約束車(chē)輛路徑問(wèn)題(CapacityVehicl

3、e Routing Problem，CVRP)。提出了整數(shù)編碼、實(shí)數(shù)編碼兩種求解CVRP的方法。在整數(shù)編碼中，以交換數(shù)為基礎(chǔ)，對(duì)粒子的速度重新定義，并對(duì)速度的加、減等操作進(jìn)行了定義，提出了“換位減”算子作為整數(shù)編碼的速度計(jì)算方法：針對(duì)整數(shù)編碼算法存在的問(wèn)題，提出了一種實(shí)數(shù)編碼方法求解CVRP，用實(shí)數(shù)的整數(shù)部分表示客戶所在的車(chē)輛，小數(shù)部分表示在該車(chē)輛中配送的次序，融合遺傳算法的思想，引入交叉算子以增加種群的多樣性，詳細(xì)討論了粒子群算法的各

4、個(gè)參數(shù)對(duì)算法結(jié)果的影響。為了與其他智能優(yōu)化算法比較，研究了遺傳算法、人工魚(yú)群算法在CVRP中的應(yīng)用。將雙種群遺傳算法用于CVRP的求解；提出了人工魚(yú)群算法在CVRP中的應(yīng)用，針對(duì)車(chē)輛路徑問(wèn)題的特點(diǎn)，定義了魚(yú)群的距離、領(lǐng)域等概念，提出了人工魚(yú)根據(jù)自身在魚(yú)群中的排序，自適應(yīng)選擇移動(dòng)算子的策略。 (3)通過(guò)引入虛擬配送中心的概念，建立了開(kāi)放式車(chē)輛路徑問(wèn)題的三下標(biāo)數(shù)學(xué)模型。提出了開(kāi)放式車(chē)輛路徑問(wèn)題的粒子群求解方法，將最鄰近插入、最遠(yuǎn)插入

5、、2-Opt、3-Opt 等啟發(fā)式算法作為再優(yōu)化過(guò)程引入粒子群算法，通過(guò)這些啟發(fā)式算法調(diào)整線路內(nèi)和線路間的客戶來(lái)改進(jìn)解，從理論上分析了這些算法的計(jì)算復(fù)雜度。通過(guò)實(shí)驗(yàn)分析，找出合適的啟發(fā)式算子，并和其他的算法進(jìn)行了比較。 (4)以客戶滿意度為首要優(yōu)化目標(biāo)，建立了基于客戶滿意度的開(kāi)放式車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型，使用梯形模糊數(shù)表示客戶滿意度。綜合考慮距離、等待時(shí)間、客戶的滿意度等因素，定義了廣義的距離和節(jié)約費(fèi)用的概念，提出了改進(jìn)的最鄰近

6、法和最廉價(jià)插入法，將這兩個(gè)算法作為初始化和改進(jìn)算子結(jié)合粒子群算法進(jìn)行優(yōu)化求解。分析了算法的復(fù)雜度，對(duì)算法的各個(gè)參數(shù)進(jìn)行了討論，通過(guò)實(shí)驗(yàn)仿真對(duì)這幾種方法進(jìn)行了分析比較。 (5)動(dòng)態(tài)網(wǎng)絡(luò)車(chē)輛路徑問(wèn)題目前研究的熱點(diǎn)和難點(diǎn)問(wèn)題，將動(dòng)態(tài)網(wǎng)絡(luò)與開(kāi)放式兩個(gè)因素結(jié)合起來(lái)研究車(chē)輛路徑問(wèn)題還未見(jiàn)報(bào)道。本文針建立了開(kāi)放式動(dòng)態(tài)網(wǎng)絡(luò)車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型，提出了一種連續(xù)時(shí)間依賴函數(shù)模型。提出了自適應(yīng)慣性權(quán)重調(diào)整的粒子群算法，定義了粒子的“位置比”概念，充

7、分利用粒子的已有知識(shí)，動(dòng)態(tài)的調(diào)整慣性權(quán)重。在算法中，引入公告板策略，根據(jù)粒子適應(yīng)度的高低分類(lèi)更新粒子狀態(tài)，對(duì)于優(yōu)秀粒子使用一種新的狀態(tài)更新公式，以使其跳出局部極值點(diǎn)。對(duì)于適應(yīng)度低的粒子，通過(guò)統(tǒng)計(jì)其在公告板中出現(xiàn)的頻率，用新的粒子替換以保持種群的多樣性。通過(guò)實(shí)驗(yàn)討論了算法的參數(shù)設(shè)置，對(duì)幾種慣性權(quán)重方案進(jìn)行了分析比較，實(shí)驗(yàn)結(jié)果證明了算法的有效性。 (6)在上述理論工作的基礎(chǔ)上，針對(duì)第三方物流在國(guó)內(nèi)的迅速發(fā)展，而相應(yīng)的車(chē)輛調(diào)度軟件功能