[發明專利]基于離散粒子群優化算法的智能物流配送

無效

• 申請號: 201010566908.0
• 申請日: 2010-11-29
• 公開（公告）號: CN102117441A
• 公開（公告）日: 2011-07-06
• 發明（設計）人: 張軍;龔月姣
• 申請（專利權）人: 中山大學
• 主分類號: G06Q10/00
• 分類號: G06Q10/00;G06Q50/00;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.針對物流配送業中帶時間窗的車輛路徑規劃問題，提出了一種智能化的基于離散粒子群優化算法的調度方案，其特征是：應用粒子群優化算法的主框架，以及基于集合和概率的編碼方式和運算符，對車輛路徑問題進行求解，本發明提出的算法包括以下步驟和操作：

(1)基于集合和概率的編碼方式：粒子群體的搜索空間為車場和客戶節點定義的完全圖的邊集；粒子的位置為完全圖的邊集的一個子集，這個子集中的邊首尾相連構成一個有向漢密爾頓回路，該漢密爾頓回路可通過一個基于車載和時間窗約束的解碼器得到一組派送路線，即問題的一個可行解；粒子的速度是帶概率的邊集，速度集合中的邊可能被選中構建粒子的新位置，每條邊所關聯的概率則表示該邊在位置更新時被選中構建粒子新位置的可能性；

(2)粒子的適應度值采用如下函數進行計算

fitness(X_i)＝NV(X_i)+normalize(TD(X_i))

其中NV表示運輸所需要的車輛數，TD表示所有路線的總運輸距離，normalize(x)＝arctan(x)/(π/2)是反余切歸一化函數；粒子群體在優化過程中以最小化車輛數為第一目標，以最小化運輸距離為第二目標；

(3)在算法初始化階段和粒子位置更新過程中所使用的啟發式信息定義如下：

timespan(i，j)＝max{currtime+t_ij，e_j}-currtime

它表示的是從當前節點i出發到能為下一客戶j開始服務所需要的時間；其中currtime表示系統當前時間，t_ij是車輛在i、j節點間行駛所需要花費的時間，e_j表示客戶j的開始服務時間窗；

(4)初始化：在算法的初始化階段，粒子的速度被隨機賦初值；粒子的位置以概率?使用貪心算法賦初值，以概率?隨機賦初值；粒子的歷史最優值設為粒子的當前位置；

(5)速度更新：粒子根據如下公式進行速度更新

ω和c分別是慣量權重和加速因子參數，f_i(d)∈{1，2，...，M}(M為群體規模)被稱之為模范，定義了粒子i的第d維將向種群中哪個粒子的歷史最優值進行學習；f_i(d)由一個學習概率Pc決定：在速度更新時，種群中的每個粒子的每一維均有Pc的概率向自己的歷史最優位置學習，另外(1-Pc)的概率利用錦標賽選擇策略選擇某個同伴粒子歷史最優位置的這一維進行學習；

速度更新公式中的運算符是建立在集合和概率的基礎上的，“常數×速度”運算符和“速度+速度”運算符定義為速度集合中邊的概率的改變；“位置-位置”運算符定義為邊集的減操作；“常數×位置”運算符定義為將邊集轉化為帶概率的邊集；

(6)位置更新：粒子的位置更新是構建性的，構建粒子位置的邊的選擇來自于三個集合：粒子的當前速度集、粒子的當前位置集、完全圖邊集，優先級依次降低；在同等優先級的集合中，則依靠啟發式信息貪心地選擇消耗時間最小的邊；

(7)局部搜索：在每個粒子位置更新后，引入一個局部搜索策略；選擇經過客戶數最少的汽車的行駛路線，將由它負責的所有客戶嘗試插入其余汽車的周游路線中，插入前提是不影響其余客戶的原本服務時間，且滿足的時間窗和車載約束；如果某汽車經過的所有客戶均能被插入其余汽車的周游路線中進行服務，則撤銷該輛周游汽車，并根據新的總周游方案給粒子賦值；

(8)評估種群，如果優化達到停止條件，則終止整個算法并得到最優解；否則，返回第(4)步繼續優化種群。

2.根據權利要求1所述的用于求解車輛路徑問題的離散粒子群優化算法，其特征是：采用一種基于集合和概率的粒子編碼方式，求解一個組合優化問題的過程可以被認為是選擇一些元素構成通用集的一個子集以優化目標函數的過程。

3.根據權利要求1所述的用于求解車輛路徑問題的離散粒子群優化算法，其特征是：采用了一種綜合學習策略，在速度更新時，同一個粒子的不同維?是向不同的模范進行學習的，加之模范的選擇覆蓋了整個粒子群體，而不是單純的粒子自身以及當前最優的粒子。

4.根據權利要求1所述的用于求解車輛路徑問題的離散粒子群優化算法，其特征是：采用一種歸一化加權和的決策思想，同時考慮最小化車輛數和最小化路徑距離兩個目標；每個粒子的適應值是它所表示的解所關聯的車輛數和運輸距離的加權和；其中，對運輸距離進行了歸一化處理，使得最小化車輛數優先于最小化運輸距離。?