[發明專利]一種快遞物流背包優化方法

在審

• 申請號: 201710033654.8
• 申請日: 2017-01-10
• 公開（公告）號: CN108288105A
• 公開（公告）日: 2018-07-17
• 發明（設計）人: 李哲以;張艷
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種快遞物流背包優化方法，用于對配送中心產生的訂單進行裝載優化。包括步驟：

A.采集配送點的詳細訂單情況，并運用初始解生成公式初始化粒子群，獲得一系列隨機的初始化種群pop(n)。

B.運用約束檢驗條件對生成的初始化種群是否符合約束條件，如果有不可行的粒子pop_i，則運用調整公式對不可行解pop_i進行約束調整。

C.計算粒子群中各粒子的適應度值fit(i)(目標函數值)，對粒子群中的個體最優解pb_i以及種群的全局最優解gb進行保留。

D.運用位置更新公式和速度更新公式，對粒子群中各粒子的位置和速度進行更新，得到粒子新的狀態。

E.再次計算粒子群中各粒子的適應度值fit(i)(目標函數值)，同時對粒子群中的個體最優解pb_i和全局最優解gb進行更新。

F.運用模擬退火操作對粒子群的全局最優解進行更新。

G.運用權重和學習因子更新公式對算法的慣性權重ω，學習因子c1，c2進行更新。

H.若達到迭代終止條件，則輸出粒子群的全局最優解為算法的最終解sol。否則跳轉到步驟D，循環執行步驟D～H。

2.根據權利要求1所述一種物流背包問題的解決方法，其特征在于：所述步驟A采集終端配送點的訂單數據，每個訂單的屬性包括訂單的起點，終點，質量，體積，郵費。根據配送點的訂單數量以及種群規模生成初始化粒子群pop(n)。粒子采用二進制編碼的方式進行表示pop_i＝(x₁，x₂，...，x_n-1，x_n)。其中，x_i＝0表示第j個訂單沒有裝入背包，n表示配送點的訂單數。

3.根據權利要求1所述一種快遞物流背包優化方法，其特征在于：所述步驟B運用約束條件對生成的初始化粒子群進行檢測，是否符合背包的質量限制，體積限制。如果粒子不符合約束條件，則對粒子進行約束性調整，使其最終符合背包的約束條件。

4.根據權利要求1所述一種快遞物流背包優化方法，其特征在于：所述步驟C運用適應度計算公式(即目標函數)計算各個粒子的適應度值。比較各個粒子的適應度值，保留最大的適應度值并將其相應的解作為粒子群的全局最優解gb，同時保留粒子的個體最優解pb_i。

5.根據權利要求1所述一種物流背包問題的解決方法，其特征在于：所述步驟D運用速度與位置更新公式對粒子群中每個粒子的速度與位置進行更新操作，從而得到每個粒子新的狀態，實現種群的進化過程。

6.根據權利要求1所述一種快遞物流背包優化方法，其特征在于：所述步驟E運用適應度更新公式計算各個粒子的適應度值，比較前后兩代的適應度值得大小，完成對粒子群的全局最優解和各粒子的個體最優解進行更新。

7.根據權利要求1所述一種快遞物流背包優化方法，其特征在于：所述步驟F利用模擬退火算法的Metropolis準則對粒子群的全局最優解進行更新，得到新的全局最優解，作為本次迭代的全局最優解參與下次的進化過程。

8.根據權利要求1所述一種快遞物流背包優化方法，其特征在于：所述步驟G使用相應的更新公式對算法的慣性權重ω和學習因子c1，c2進行更新。較大的慣性權重有利于搜索時跳出局部所處的極值點，同時較小的慣性權重有利于算法快速收斂與提高搜索范圍的精度。學習因子分別調整粒子的局部搜索能力和全局搜索能力，在種群進化的過程中，如何通過更新權重和學習因子來平衡粒子的局部搜索和全局搜索過程顯得尤為重要。

9.根據權利要求1所述一種快遞物流背包優化方法，其特征在于：所述步驟H判斷是否達到了迭代終止條件，如果達到了迭代終止條件，則將最后一次迭代得到的全局最優解作為最終的算法最優解sol輸出。否則，跳轉到步驟D，循環執行步驟D～H，直到達到迭代終止條件。