車輛路徑問題的粒子群算法研究與應(yīng)用

《車輛路徑問題的粒子群算法研究與應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

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

2、徑問題，開放式動態(tài)網(wǎng)絡(luò)車輛路徑問題。研究了粒子群及其改進算法對上述模型的求解。具體的研究內(nèi)容如下：(1)首先介紹了論文的研究背景及意義，給出了車輛路徑問題的定義，分析了車輛路徑問題的組成要素。然后在對國內(nèi)外大量文獻總結(jié)提煉的基礎(chǔ)上，從車輛路徑問題的模型和求解算法兩方面，深入分析了車輛路徑問題的國內(nèi)外研究現(xiàn)狀。(2)系統(tǒng)研究了基于粒子群算法的有能力約束車輛路徑問題(CapacityVehicleRoutingProblem，CVRP)。提出了整數(shù)編碼、實數(shù)編碼兩種求解CVRP的方法。在整數(shù)編碼中，以交換數(shù)為基礎(chǔ)，對粒子的速

3、度重新定義，并對速度的加、減等操作進行了定義，提出了“換位減”算子作為整數(shù)編碼的速度計算方法；針對整數(shù)編碼算法存在的問題，提出了一種實數(shù)編碼方法求解CVRP，用實數(shù)的整數(shù)部分表示客戶所在的車輛，小數(shù)部分表示在該車輛中配送的次序，融合遺傳算法的思想，引入交叉算子以增加種群的多樣性，詳細討論了粒子群算法的各個參數(shù)對算法結(jié)果的影響．為了與其他智能優(yōu)化算法比較，研究了遺傳算法、人工魚群算法在CVRP中的應(yīng)用。將雙種群遺傳算法用于CVRP的求解；提出了人工魚群算法在CVRP中的應(yīng)用，針對車輛路徑問題的特點，定義了魚群的距離、領(lǐng)域等

4、概念，提出了人工魚根據(jù)自身在魚群中的排序，自適應(yīng)選擇移動算子的策略。(3)通過引入虛擬配送中心的概念，建立了開放式車輛路徑問題的三下標數(shù)學模型。提出了開放式車輛路徑問題的粒子群求解方法，將最鄰近插入，最遠■要插入、2-Opt、3-opt等啟發(fā)式算法作為再優(yōu)化過程引入粒子群算法，通過這些啟發(fā)式算法調(diào)整線路內(nèi)和線路間的客戶來改進解，從理論上分析了這些算法的計算復(fù)雜度。通過實驗分析，找出合適的啟發(fā)式算子，并和其他的算法進行了比較。(4)以客戶滿意度為首要優(yōu)化目標，建立了基于客戶滿意度的開放式車輛路徑問題的數(shù)學模型，使用梯形模糊

5、數(shù)表示客戶滿意度。綜合考慮距離、等待時間、客戶的滿意度等因素，定義了廣義的距離和節(jié)約費用的概念，提出了改進的最鄰近法和最廉價插入法，將這兩個算法作為初始化和改進算子結(jié)合粒子群算法進行優(yōu)化求解。分析了算法的復(fù)雜度，對算法的各個參數(shù)進行了討論，通過實驗仿真對這幾種方法進行了分析比較．(5)動態(tài)網(wǎng)絡(luò)車輛路徑問題目前研究的熱點和難點問題，將動態(tài)網(wǎng)絡(luò)與開放式兩個因素結(jié)合起來研究車輛路徑問題還未見報道。本文針建立了開放式動態(tài)網(wǎng)絡(luò)車輛路徑問題的數(shù)學模型，提出了一種連續(xù)時間依賴函數(shù)模型。提出了自適應(yīng)慣性權(quán)重調(diào)整的粒子群算法，定義了粒子的

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

7、圖的顯示等功能。該系統(tǒng)可以處理有時間窗、有能力約束等多種情況的車輛調(diào)度問題，提供遺傳算法、粒子群算法等多種優(yōu)化算法供用戶使用。系統(tǒng)在杭州某物流公司應(yīng)用，取得了良好的效果。最后，對全文研究工作進行了總結(jié)，展望了車輛路徑問題的模型和算法研究的前景．關(guān)鍵詞：車輛路徑問題粒子群算法遺傳算法人工魚群算法客戶滿意度開放式動態(tài)網(wǎng)絡(luò)第三方物流組合優(yōu)化Ⅱ浙江工業(yè)大學博士學位論文ParticleSwarmOptimizationforVelaicleRoutingProblemanditsApplicationLogistics，whleh

8、is陀鏟rdedas"thethirdprofitSOI,II'∞”，h硒obviousimpactoneconomicactivityoftheworlddaybyday,andc勰people’Smoreandmoreattentiontoo．Tramportafionanddeliveryisthekeypar