郭美，肖敏

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

0 引言

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

1 配送車(chē)輛路徑問(wèn)題

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

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

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

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

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

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

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

3.1 混合粒子群算法

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

3.2 算法過(guò)程描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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