基于混合粒子群算法的物流配送路徑優(yōu)化問題研究

郭美，肖敏

（湘南學院軟件與通信工程學院，湖南 郴州 4230000）

0 引言

標準的車輛路徑問題（VRP）意味著物流中心可以為多個客戶提供服務。每個用戶都有一定的需求，但只能可以獲得一部車服務。車輛從配送中心開始，最終返回配送中心。運送車輛不可避免的面臨裝載量、運送時長、運送路程等方面的限制，物流公司對這些因素充分關注的目標是使總運輸成本或總時間最小化。對于這類組合問題，很難獲得最優(yōu)解，特別是對于大尺寸問題，要在合理的時間內獲得最優(yōu)解是不可能的。針對這種情況相關研究人員嘗試了模擬退火算法、遺傳算法等各種啟發(fā)式方法來解決該問題，取得了一定成果。然而，關于車輛路徑選擇中多目標問題的研究很少，只有很少的研究是通過權重的方法來解決的[1-2]。

1 配送車輛路徑問題

車輛配送路徑的優(yōu)化方案繁瑣且形式多樣，不同的優(yōu)化方案具有不同的要素，這些要素影響著不同方案的分類標準。優(yōu)化配送車輛路徑時要將同批次每個客戶的貨物同等對待。此外，還應該將運輸車輛的運送時間、客戶收貨時間等綜合納入路徑優(yōu)化的考量內容。配送中心是車輛的起點和終點，某一區(qū)域的物流配送中心可以有多個，位置也可以相對不確定，而且配送的貨物也可以涉及到更多種類，以此來提升配送中心的經(jīng)濟和社會功能。

當多輛配送運輸車從物流配送中心出發(fā)以后，其方向和行程皆不相同，每輛運輸車都具有獨立的行駛路線，這些不同分支的車輛行駛路線相互交叉連接就形成了物流交通網(wǎng)絡。在整體的交通網(wǎng)絡中，要根據(jù)路徑優(yōu)化問題的具體狀況來因地制宜地設置滿足優(yōu)化方案的條件，可以根據(jù)用戶對貨物的種類、數(shù)目和規(guī)格的需求來設置商品的交貨期限，在交付過程中要確保貨物的實際負荷既在運送車輛和物流中心的承受范圍內，又要確保滿足不同客戶的個性化需求。

2 物流配送指標體系建立

在實際物流配送中，影響因素很多，包括配送貨物的重量、配送及時性、客戶的不同要求和需要、總運送路徑和耗油量等，這些都與物流配送路徑的改善有著密切的關系。因此需要建立科學合理的物流配送指標體系，來準確的反應路徑優(yōu)化的不同階段存在的具體問題。

圖1 物流配送指標體系

物流配送指標體系的建立是在集合物流配送評估指標中具體影響因子的基礎上完成的，體系內主要包括以下指標：商品質量水平、貨物配送時效性水平、用戶對配送產(chǎn)業(yè)的重要程度、用戶取件時間安排、總配送路線、總配送油耗等。

3 粒子群優(yōu)化算法及其改進

3.1 混合粒子群算法

基礎的混合粒子群算法（PSO）根據(jù)不同數(shù)據(jù)組之間的交叉對比和分析來在問題空間中尋求最優(yōu)化的解決方案。粒子本身不存在選擇、交叉和變異等能力，因此當粒子簇位于某個局部極值附近時就不可能搜索問題空間的其余位置，混合PSO采取更改總體初始化方案并導入交叉、突變等功能來提高基本PSO的算力。將基本PSO與其他的算法進行高效有機融合不僅能夠增加粒子群的多樣化程度，也能夠提高粒子算力以及準確性。算法結合一般有兩種方法：一種是使用其他優(yōu)化手段調整慣性權重和加速度等數(shù)值；另外一種則是把PSO與其他優(yōu)化算法方案或其他技術手段進行有機融合。如果使用基本PSO，則其速度難以表達，因此使用遺傳算法對其進行求解[3]。

3.2 算法過程描述

（1）算法初始化。導入配送物流網(wǎng)絡中的有關數(shù)據(jù)信息，計算不同粒子群的規(guī)模與有關參數(shù)，也就是慣性權重因子、學習因子和最大迭代次數(shù)。

（2）初始化粒子群。隨機產(chǎn)生多個n維向量，利用混沌的特征對初始值敏感，在初始值上分配很小的差異以獲得初始粒子群。

（3）將混沌變量反向映射到發(fā)貨的值區(qū)間。

（4）適應性評估。通過解碼粒子來制定車輛運送計劃，并基于每個客戶點的方位來計算每個粒子的適應度函數(shù)值，也就是運輸車輛需要經(jīng)過的總路程，計算完成后需要核驗計算結果是否滿足算法的約束條件。客戶點的總需求超出了此路線上送貨車輛的容量，或者有尚未分配給客戶點的車輛等，需要再次搜索。

（5）若是粒子的適應性高于單個極值，就把單個極值設定成系統(tǒng)的新數(shù)值。若是粒子的適應性高于整體極值，就把整體極值設定成系統(tǒng)的新數(shù)值。

（6）對粒子群的整體最優(yōu)化數(shù)值做混合優(yōu)化處理。首先把整體最優(yōu)化數(shù)值導入進粒子群算法的定義域，然后迭代生成n個混合變量序列，最后通過逆映射將得到的變量序列反回到最優(yōu)數(shù)值區(qū)間內，獲得n個新粒子，然后對每個粒子進行適應性函數(shù)運算來獲得系統(tǒng)最優(yōu)解，并用其替代混合粒子群中的任一粒子的位置。

（7）確定粒子群是否會過早收斂。粒子群過早收斂后選取優(yōu)等粒子進行優(yōu)化，未收斂則進行粒子群算法。過早收斂主要體現(xiàn)在以下兩個方面：一是粒子群存在緊密聚集現(xiàn)象；二是最優(yōu)化粒子群在經(jīng)過若干次迭代算法之不受影響或受影響極小。計算全局最優(yōu)粒子位置不連續(xù)變化的迭代次數(shù)，當達到預設閾值時，意味著粒子群的進化緩慢而停滯。過早收斂進行步驟8；否則，請轉到步驟9。

（8）一些更好的粒子群的混沌優(yōu)化與全局最優(yōu)極值相同。由于某些粒子適應性很強并且?guī)缀踹_到最優(yōu)解，因此通過對這些粒子做混合演算就很方便地獲得全新的優(yōu)化粒子。因此，為了加快搜索過程，只允許部分粒子參與搜索。混沌優(yōu)化完成后，這部分粒子將更新，粒子群的多樣性增加。在經(jīng)過數(shù)次迭代演算后，轉到步驟9。

（9）輸出最佳解，算法操作結束。

4 建立物流配送路徑優(yōu)化目標函數(shù)

圖2 基于混合PSO的配送車輛路徑優(yōu)化流程

落實物流配送路徑優(yōu)化方案的核心問題就是建立客觀的、科學的、能夠反映真實物流配送信息的數(shù)字模型，即建立綜合、合理、高效的路徑優(yōu)化目標函數(shù)。物流配送路徑優(yōu)化目標函數(shù)的構建需要以物流配送評估的指標體系為基礎，同時也要注重考慮實際運送過程可能會出現(xiàn)的問題，如天氣和交通路況干擾等。配送指標體系中，商品質量水平、貨物配送時效性水平、用戶對配送產(chǎn)業(yè)的重要程度、用戶取件時間安排和配送貨物或用戶的客觀屬性相關。一旦具體的商品或用戶確定以后，這些參數(shù)就固定不變了。但是分配順序的變化會影響總體目標函數(shù)，并且總體路徑指標是可變的，與貨物配送次序和貨物的種類性質直接相關[4]。

4.1 物流配送指標函數(shù)

（1）商品質量水平。貨物的質量是在運送過程中必須考慮的影響因素。通常，如果條件允許，應首先派遣重物以減少總燃料消耗。

（2）貨物配送時效性指標。隨著電商的飛速發(fā)展和物流運輸網(wǎng)絡的深入建設，以及人們對冷鮮類物品需求量的不斷增加，物流配送行業(yè)及工作人員面臨的挑戰(zhàn)日益嚴峻，如何提高配送效率、減少配送時間是每個從業(yè)者都應思考的，這直接影響著物流業(yè)的未來發(fā)展。

（3）用戶對配送產(chǎn)業(yè)的重要程度。用戶的多少與消費水平對配送產(chǎn)業(yè)具有深刻的影響，為了提高用戶對物流配送公司的消費率，提升物流公司的口碑，在貨物運輸過程中要優(yōu)先派送高級客戶的物品。

（4）用戶取件時間安排。該指標能夠反映每個客戶的取件時間要求，有益于提升物流企業(yè)的派件精確度和用戶的取件成功率，確保客戶保持對物流公司的消費滿意度，因此具體貨物的物流交付必須考慮到客戶的時間安排。

（5）總配送路線。不同地區(qū)、不同時間的具體物流配送的路線是不盡相同的，因此總配送路線里程也存在差異，如果想增加物流配送工作的實際效率，總路程是不得不考慮的方面之一。

（6）總配送油耗。物流配送路程中的總耗油量也是配送產(chǎn)業(yè)需要考慮的指標之一。油耗水平直接影響到配送所需要的資金，這和配送車輛的載貨量、配送里程，以及配送過程中的路況、天氣等客觀因素相關[5]。

4.2 物流配送路徑優(yōu)化目標函數(shù)

該目標函數(shù)是根據(jù)配送指標評估函數(shù)和權重信息來建立的，它能夠將商品質量水平、貨物配送時效性水平、用戶對配送產(chǎn)業(yè)的重要程度、用戶取件時間安排、總配送路線、總配送油耗等指標的權重信息和正比例增益數(shù)值進行綜合運算，并通過混合粒子群算法做一定的優(yōu)化，以此來設計出最優(yōu)的物流配送路徑。

5 結語

本文提出了一種新的混合粒子群算法來解決物流配送路線優(yōu)化問題，以期為該問題的改進研究提供研究思路和理論支持。與其他算法的計算結果相比，混合粒子群算法在提高解的質量和速度方面優(yōu)于單獨的PS0算法和其他算法，是解決物流配送路線優(yōu)化問題的較好方法。