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

郭美，肖敏

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

0 引言

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

1 配送車輛路徑問題

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

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

2 物流配送指標(biāo)體系建立

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

圖1 物流配送指標(biāo)體系

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

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

3.1 混合粒子群算法

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

3.2 算法過程描述

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）商品質(zhì)量水平。貨物的質(zhì)量是在運送過程中必須考慮的影響因素。通常，如果條件允許，應(yīng)首先派遣重物以減少總?cè)剂舷摹?/p>

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

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

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

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

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

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

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

5 結(jié)語

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