《車輛路徑問題的粒子群算法研究與套用》研究了基於以下四種模型的車輛路徑問題的粒子群及其改進算法及其求解：1.有能力約束的車輛路徑問題；2.開放式車輛路徑問題3.基於客戶滿意度的開放式車輛路徑問題；4.開放式動態網路車輛路徑問題。
基本介紹
- 中文名：車輛路徑問題的粒子群算法研究與套用
- 作者：吳斌
- 學科專業：控制理論與控制工程
- 導師姓名：王萬良、趙燕偉
基本信息,中文摘要,
基本信息
論文作者： 吳斌
導 師：王萬良、趙燕偉
學科專業：控制理論與控制工程
學位級別：博士論文
學位授予單位：浙江工業大學
學位授予時間：2007
關鍵字：物流 ；物資配送 ；車輛 ；運輸調度 ；粒子群最佳化算法(PSO)
館藏號：F253.4
館藏目錄：2009\F253.4\7
中文摘要
物流被稱為“第三利潤源泉”，越來越受到人們的關注，日益成為國民經濟的基礎產業。運輸是物流中的重要環節，占物流成本的60%以上。車輛路徑問題主要研究物流配送中車輛線路最佳化以降低運輸成本。該問題是運籌學和組合最佳化領域中的著名NP問題，在航班調度、列車編組等眾多領域都有套用。由於NP問題求解的複雜性，目前車輛路徑問題的求解方法主要使用各種智慧型最佳化算法。本文主要研究了以下四種模型的車輛路徑問題：有能力約束的車輛路徑問題，開放式車輛路徑問題，基於客戶滿意度的開放式車輛路徑問題，開放式動態網路車輛路徑問題。研究了粒子群及其改進算法對上述模型的求解。具體的研究內容如下： (1)首先介紹了論文的研究背景及意義，給出了車輛路徑問題的定義，分析了車輛路徑問題的組成要素。然後在對國內外大量文獻總結提煉的基礎上，從車輛路徑問題的模型和求解算法兩方面，深入分析了車輛路徑問題的國內外研究現狀。 (2)系統研究了基於粒子群算法的有能力約束車輛路徑問題(Capacity Vehicle Routing Problem，CVRP)。提出了整數編碼、實數編碼兩種求解CVRP的方法。在整數編碼中，以交換數為基礎，對粒子的速度重新定義，並對速度的加、減等操作進行了定義，提出了“換位減”運算元作為整數編碼的速度計算方法；針對整數編碼算法存在的問題，提出了一種實數編碼方法求解CVRP，用實數的整數部分表示客戶所在的車輛，小數部分表示在該車輛中配送的次序，融合遺傳算法的思想，引入交叉運算元以增加種群的多樣性，詳細討論了粒子群算法的各個參數對算法結果的影響。為了與其他智慧型最佳化算法比較，研究了遺傳算法、人工魚群算法在CVRP中的套用。將雙種群遺傳算法用於CVRP的求解；提出了人工魚群算法在CVRP中的套用，針對車輛路徑問題的特點，定義了魚群的距離、領域等概念，提出了人工魚根據自身在魚群中的排序，自適應選擇移動運算元的策略。 (3)通過引入虛擬配送中心的概念，建立了開放式車輛路徑問題的三下標數學模型。提出了開放式車輛路徑問題的粒子群求解方法，將最鄰近插入、最遠插入、2-Opt、3-Opt等啟發式算法作為再最佳化過程引入粒子群算法，通過這些啟發式算法調整線路內和線路間的客戶來改進解，從理論上分析了這些算法的計算複雜度。通過實驗分析，找出合適的啟發式運算元，並和其他的算法進行了比較。 (4)以客戶滿意度為首要最佳化目標，建立了基於客戶滿意度的開放式車輛路徑問題的數學模型，使用梯形模糊數表示客戶滿意度。綜合考慮距離、等待時間、客戶的滿意度等因素，定義了廣義的距離和節約費用的概念，提出了改進的最鄰近法和最廉價插入法，將這兩個算法作為初始化和改進運算元結合粒子群算法進行最佳化求解。分析了算法的複雜度，對算法的各個參數進行了討論，通過實驗仿真對這幾種方法進行了分析比較。 (5)動態網路車輛路徑問題目前研究的熱點和難點問題，將動態網路與開放式兩個因素結合起來研究車輛路徑問題還未見報導。本文針建立了開放式動態網路車輛路徑問題的數學模型，提出了一種連續時間依賴函式模型。提出了自適應慣性權重調整的粒子群算法，定義了粒子的“位置比”概念，充分利用粒子的已有知識，動態的調整慣性權重。在算法中，引入公告板策略，根據粒子適應度的高低分類更新粒子狀態，對於優秀粒子使用一種新的狀態更新公式，以使其跳出局部極值點。對於適應度低的粒子，通過統計其在公告板中出現的頻率，用新的粒子替換以保持種群的多樣性。通過實驗討論了算法的參數設定，對幾種慣性權重方案進行了分析比較，實驗結果證明了算法的有效性。 (6)在上述理論工作的基礎上，針對第三方物流在國內的迅速發展，而相應的車輛調度軟體功能不夠完善，開發了智慧型車輛調度系統。該系統包括智慧型車輛調度、承運單的管理、電子地圖的顯示等功能。該系統可以處理有時間窗、有能力約束等多種情況的車輛調度問題，提供遺傳算法、粒子群算法等多種最佳化算法供用戶使用。系統在杭州某物流公司套用，取得了良好的效果。 最後，對全文研究工作進行了總結，展望了車輛路徑問題的模型和算法研究的前景。
