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

在審

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

一種快遞物流背包優化方法，用于對配送點的待配送訂單進行裝載優化，使得車輛滿載率達到最大的同時提高車輛所裝載訂單的總收益。算法通過二進制粒子群算法，每次迭代保留粒子的全局最優解，并結合粒子間的相互作用擴大粒子群的搜索范圍。并引入模擬退火算法，利用模擬退火算法的Metropolis準則提高算法局部搜索的能力同時加快迭代后期算法的收斂速度。算法以配送車輛的平均載重率，平均容積率，以及所裝載訂單的總郵費為子目標函數，通過歸一化處理得到總目標函數，以總目標函數的值來衡量優化的效果。實驗結果表明，采用本發明方法，相比于其他算法可以得到更滿意的優化效果。

技術領域

本發明涉及數據挖掘，背包優化等技術，特別是涉及一種快遞物流背包優化方法。

背景技術

背包問題是運籌學中一個典型的NP完全問題，即多項式復雜程度的非確定性問題。目前，解決背包問題的常規算法包括窮舉法、動態規劃法和遞歸回溯法等，但只能解決小規模背包問題。啟發式算法是模擬自然界和生物行為的新型算法，具有模型靈活，求解速度快，解的質量高等優點。在這些啟發式算法中，遺傳算法、蟻群算法、差分進化算法等優化算法收斂速度慢、全局收斂性差。粒子群算法簡單易實現，參數設置較小，收斂速度較快，但是也具有收斂精度和收斂效率較低，收斂過程中易于停滯，易陷入局部最優的缺點。而模擬退火算法(Simulated Annealing Algorithm，簡稱SA)能改善陷入局部最優解的缺陷，使算法快速地收斂于全局最優解。因此，有必要把模擬退火的思想引入粒子群算法中，優化粒子群的進化過程，從而提高粒子群算法的收斂精度和收斂效率，幫助粒子群跳出局部極值。

發明內容

本發明提供了一種綜合優化方法，以解決基礎優化算法在解決物流背包問題時容易陷入局部最優及后期迭代速度慢的問題。本發明的實質是：把物流配送中心的車輛載重率，車輛容積率以及總郵費作為子目標函數，并經過歸一化得到綜合目標函數，利用模擬退火和粒子群相結合的算法對其進行尋優。

本發明采用的技術方案的步驟如下：

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

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。