陳 文

(福建船政交通職業(yè)學(xué)院，福州 350007)

購(gòu)物平臺(tái)、微商、自媒體等多種形式的線上購(gòu)物模式的迅速發(fā)展，使蔬菜、水果、水產(chǎn)、藥品等冷鏈運(yùn)輸產(chǎn)品也成功實(shí)現(xiàn)了網(wǎng)上交易。物流業(yè)的迅速發(fā)展以及民眾日益提升的服務(wù)需求，對(duì)冷鏈運(yùn)輸產(chǎn)品的配送速度提出了較高的要求，且冷鏈產(chǎn)品自身的性質(zhì)也決定了冷鏈運(yùn)輸必須由高效的運(yùn)輸配送策略[1-2]指導(dǎo)。但冷鏈產(chǎn)品配送受運(yùn)輸車輛、交通路況以及天氣狀態(tài)等因素的制約較多，因此，針對(duì)冷鏈產(chǎn)品的配送優(yōu)化仍然是物流行業(yè)的研究難點(diǎn)[3]。國(guó)外針對(duì)配送路徑優(yōu)化問題的研究一直處在持續(xù)發(fā)展階段，查理德[4]最早提出了用于商旅最佳路徑分派的求解算法，該算法可以提高搜索最佳節(jié)點(diǎn)的效率，但是需要較大的空間存儲(chǔ)算法的各個(gè)節(jié)點(diǎn)。Cattaruzza等[5-7]人提出了使用粗粒度模型改進(jìn)遺傳算法，用于冷鏈配送路徑優(yōu)化模型，進(jìn)一步提升路徑選擇算法的執(zhí)行效率，但是該方法并未考慮反復(fù)配送的多回路問題。國(guó)內(nèi)對(duì)于冷鏈產(chǎn)品的物流配送路徑的選擇及優(yōu)化問題的研究較少，劉振等[8]提出了將云計(jì)算與遺傳算法結(jié)合，綜合交通信息，結(jié)合運(yùn)輸、存儲(chǔ)成本的冷鏈產(chǎn)品配送模型，該算法從并行計(jì)算的角度提升效率，但是僅能解決一個(gè)供貨點(diǎn)的配送問題。本文研究的是業(yè)務(wù)場(chǎng)景為多回路、多供貨點(diǎn)、多配送點(diǎn)的復(fù)雜搜索空間及搜索路徑的優(yōu)化問題。

基于此，本文針對(duì)冷鏈產(chǎn)品運(yùn)輸配送的最佳路徑優(yōu)化問題，對(duì)于多回路、多配送點(diǎn)位、多供貨點(diǎn)的復(fù)雜路徑優(yōu)化，將啟發(fā)式搜索算法的應(yīng)用與拉格朗日松弛算法相結(jié)合，考慮綜合因素，對(duì)拉格朗日松弛算法進(jìn)行動(dòng)態(tài)自適應(yīng)調(diào)整，對(duì)冷鏈配送的網(wǎng)絡(luò)模型進(jìn)行動(dòng)態(tài)優(yōu)化調(diào)整，從而獲取最優(yōu)路徑解。仿真對(duì)比實(shí)驗(yàn)顯示，本文提出的算法對(duì)比貪婪算法、遺傳算法等常用的路徑搜索算法，獲得最佳路徑的時(shí)間更短、最佳路徑的求解能力更高。

1 問題描述與數(shù)學(xué)建模

1.1 問題描述

對(duì)比常規(guī)物品的物流運(yùn)輸，冷鏈產(chǎn)品的物流運(yùn)輸?shù)男室蟾撸蛟谟诶滏溸\(yùn)輸?shù)漠a(chǎn)品以果蔬生鮮、水產(chǎn)、藥品、冷凍食品為主，對(duì)運(yùn)輸時(shí)間有嚴(yán)格的要求，時(shí)間的延誤會(huì)導(dǎo)致產(chǎn)品變質(zhì)、損壞。對(duì)于運(yùn)輸?shù)能囕v有固定的要求，必須為冷藏車，能夠保持運(yùn)輸?shù)漠a(chǎn)品所需的低溫環(huán)境。因此，冷鏈產(chǎn)品的配送問題必須與最優(yōu)的運(yùn)輸路徑相結(jié)合，即為最優(yōu)路徑求解的問題。

本文的應(yīng)用存在多個(gè)產(chǎn)品和配送點(diǎn)位多次配送的情況，因此本文的建模思路是對(duì)多次出現(xiàn)的配送點(diǎn)位與庫(kù)房建立位置相同的若干個(gè)副本，建立庫(kù)房與配送點(diǎn)位之間唯一的點(diǎn)對(duì)點(diǎn)服務(wù)。具體模型如圖1所示。

由圖1可知，左邊配送為車場(chǎng)負(fù)責(zé)將貨物運(yùn)送到廠家冷庫(kù)1，廠家冷庫(kù)1負(fù)責(zé)收貨點(diǎn)1和收貨點(diǎn)2的供貨；右邊配送為國(guó)場(chǎng)負(fù)責(zé)將貨物送到廠家冷庫(kù)2和廠家冷庫(kù)3，廠家冷庫(kù)2負(fù)責(zé)收貨點(diǎn)2的供貨，廠家冷庫(kù)3負(fù)責(zé)收貨點(diǎn)1的供貨，實(shí)際車場(chǎng)為同一位置的庫(kù)房，其構(gòu)建了每一次配送工作的唯一配送服務(wù)。

圖1 復(fù)制配送點(diǎn)模型圖

1.2 抽象建模

對(duì)應(yīng)圖1模型，其數(shù)學(xué)描述為：在有向圖空間G內(nèi)，N為配送空間內(nèi)包含存儲(chǔ)倉(cāng)庫(kù)Ns、收貨點(diǎn)位集合Nc和運(yùn)輸車隊(duì)o等的集合；Cij代表點(diǎn)間的運(yùn)輸路徑，路徑集合使用A表示。抽象建模過程中應(yīng)用的主要參數(shù)包括：Xijk代表了對(duì)于運(yùn)輸車K從點(diǎn)i到點(diǎn)j的路徑選擇標(biāo)志，1代表選擇路徑，0代表未選擇該路徑。對(duì)于有V個(gè)運(yùn)輸車的車隊(duì)o而言，每輛車設(shè)定的容量為Q，設(shè)置待配送訂單l的存儲(chǔ)倉(cāng)庫(kù)Sl內(nèi)待配送的總量為qi的貨物需要在ai時(shí)間內(nèi)完成，使用ETi、ETl代表配送時(shí)間的上下限值。使用Z代表物流配送的成本，即為尋求最低配送成本。

對(duì)應(yīng)的抽象模型：

(1)

(2)

(3)

(4)

(5)

(6)

asj

(7)

(8)

ETj≤aj≤ETl，?j∈Nc，

(9)

(10)

0≤lj≤Q，?j∈N。

(11)

式(1)為最小成本的計(jì)算方法；式(2)明確了庫(kù)房到收貨點(diǎn)的配送次數(shù)限制；式(3)明確了車輛配送完成后，緊急任務(wù)的外部配送要求；式(4)代表了配送車輛選擇站點(diǎn)的機(jī)率；式(5)代表配送車輛的車流量限值條件；式(6)～(7)主要確保目前庫(kù)房與收貨點(diǎn)及其副本的車輛不變，且按照庫(kù)房到收貨點(diǎn)的順序執(zhí)行送貨任務(wù)；式(8)代表了到達(dá)收貨點(diǎn)位的時(shí)間約束，其中M為常量參數(shù)；式(9)代表了收貨點(diǎn)取貨的時(shí)間要求；式(10)～(11)代表收貨點(diǎn)的容量以及運(yùn)輸車的裝載限制。

2 改進(jìn)拉格朗日松弛算法的配送方法

2.1 粒子群配送模型

粒子群算法的核心為通過群體中個(gè)體之間的協(xié)作和信息共享獲得最優(yōu)解。與冷鏈產(chǎn)品配送業(yè)務(wù)場(chǎng)景充分結(jié)合，具體體現(xiàn)為將待配貨的商品作為粒子群的個(gè)體粒子，構(gòu)建由配送點(diǎn)位、供貨倉(cāng)庫(kù)在內(nèi)的多層多分支樹。具體如圖2所示。

圖2 粒子群多層分支樹

在圖2所構(gòu)建的粒子群配貨網(wǎng)絡(luò)中，每個(gè)粒子構(gòu)成一顆多叉樹，同一種貨物存在多個(gè)收貨點(diǎn)位，收貨點(diǎn)位之間根據(jù)供貨商進(jìn)行關(guān)聯(lián)?；诖伺c粒子群算法結(jié)合，即為對(duì)不同貨物(個(gè)體粒子)的適應(yīng)度函數(shù)進(jìn)行比較、派活，對(duì)比個(gè)體粒子與群體的最優(yōu)位置，持續(xù)尋找最佳位置點(diǎn)，使用該樹狀圖的模式構(gòu)建了貨物與供貨商之間的關(guān)聯(lián)關(guān)系，其中每個(gè)個(gè)體粒子的初始位置點(diǎn)以及初始速度使用式(12)～(13)表示：

(12)

(13)

式中：D為粒子群的規(guī)模，即為空間維數(shù)；粒子群搜索的最大循環(huán)次數(shù)使用T表示；I為群體搜索算法中的粒子總數(shù)，即為待配送的貨物數(shù)量。

為了確保粒子個(gè)體在指定的空間內(nèi)搜索，需要對(duì)移動(dòng)的速度和位置進(jìn)行限制，由于粒子群優(yōu)化算法的收斂過程受粒子群的初始參數(shù)影響較大，如果初始速度太快或者太慢，容易出現(xiàn)局部超優(yōu)或者收斂過慢等問題。因此，經(jīng)過反復(fù)測(cè)試，初始速度置為110，具體的取值范圍和速度變化上下限用式(14)～(17)表示：

(14)

(15)

(16)

(17)

整體的尋優(yōu)過程為：在粒子初始位置的基礎(chǔ)上持續(xù)更新位置坐標(biāo)，獲得滿足條件的新的個(gè)體粒子后，替換新的粒子及其位置作為最佳位置，計(jì)算適應(yīng)度函數(shù)(配送成本)，比較當(dāng)前的適應(yīng)度函數(shù)與新的個(gè)體粒子的最優(yōu)粒子群位置以及整個(gè)種群的最佳解位置，如當(dāng)前最優(yōu)則進(jìn)行更新和替換。

使用式(18)～(19)代表個(gè)體粒子更新過程：

(18)

(19)

式中：V代表粒子個(gè)體的移動(dòng)讀數(shù)；Lpbest代表該粒子在群里的最佳位置；Zgbest代表整個(gè)種群的最佳位置；X是該粒子目前所在位置；C1與C2為粒子飛行的加速度；ω代表了控制種群飛行的慣性常量。該權(quán)重值取值過大會(huì)造成種群的搜索范圍變大，可以提高全局搜索能力，但是收斂速度會(huì)變慢，取值太小則縮小種群的搜索范圍而出現(xiàn)局部最優(yōu)解。由于權(quán)重因子以及種群的加速度對(duì)于粒子群算法的尋優(yōu)過程影響較為關(guān)鍵，為了確保整個(gè)配送過程路徑選擇最優(yōu)化、成本最低化，并兼顧種群的多樣性，本文采用拉格朗日松弛算法對(duì)于粒子群的更新速度進(jìn)行調(diào)節(jié)，當(dāng)全局最佳位置與該種群的歷史最優(yōu)解之間差距較為明顯時(shí)，引入自適應(yīng)調(diào)整因子加速移動(dòng)，相反的，則采用降速的方式，延緩更新速度。

2.2 改進(jìn)拉格朗日松弛算法的配送方法

拉格朗日松弛算法作為求解邊界值域范圍的經(jīng)典算法，算法流程如圖3所示。

其使用松弛因子識(shí)別可能會(huì)造成問題難的復(fù)雜約束條件，若將其作為懲罰因子與目標(biāo)函數(shù)相結(jié)合，則使得目標(biāo)函數(shù)的求解變得更容易，進(jìn)一步簡(jiǎn)化求解的約束條件。

將拉格朗日松弛算法與粒子群算法相結(jié)合應(yīng)用于商品配送問題，通過粒子群優(yōu)化過程中產(chǎn)生的局部最優(yōu)解以及整個(gè)群體的全局最優(yōu)解來(lái)完成松弛因子的動(dòng)態(tài)更新，使該因子具有彈性可變的使用能力，調(diào)節(jié)群體的搜索步長(zhǎng)以及粒子群的運(yùn)動(dòng)方向，進(jìn)一步改善整體算法的靈活性。改進(jìn)算法的整體流程如圖4所示。

首先完成粒子群的初始化，明確種群規(guī)模D、尋優(yōu)的最大迭代次數(shù)T以及代配送的商品X，即為種群中的個(gè)體數(shù)量。使用式(12)～(13)完成粒子群算法的初始化，生成粒子群，并使用2.1節(jié)方法對(duì)個(gè)體粒子的飛行速度、邊界溢出位置、粒子移動(dòng)速度使用式(14)～(17)進(jìn)行初始設(shè)置。使用公式(18)～(19)完成粒子群歷史最好位置、最佳適應(yīng)度位置的以及前進(jìn)步長(zhǎng)的計(jì)算。

圖3 拉格朗日松弛算法執(zhí)行流程圖

圖4 改進(jìn)拉格朗日松弛算法執(zhí)行流程

對(duì)于粒子群種群個(gè)體的更新速度采用拉格朗日松弛算法進(jìn)行調(diào)節(jié)，使群體的更新速度具有自動(dòng)調(diào)節(jié)能力，對(duì)應(yīng)的粒子群速度更新公式如式(20)：

(20)

式中λ為自適應(yīng)調(diào)節(jié)松弛因子，該值與粒子群的更新迭代過程相輔相成，最終獲得最優(yōu)解后，該值不再變化。λ的初始值為0.1，后續(xù)的調(diào)整過程包括持續(xù)比較新的粒子的位置與歷史最優(yōu)解的位置值，其步長(zhǎng)調(diào)整公式如式(21)：

(21)

其中次梯度值計(jì)算如式(22)：

(22)

在整個(gè)最優(yōu)配送成本尋優(yōu)的過程中，配送網(wǎng)絡(luò)的樹狀結(jié)果會(huì)不斷的變化，需要在約束條件的控制范圍內(nèi)，持續(xù)調(diào)整配送貨位與供貨庫(kù)位以及配送點(diǎn)位的關(guān)系，并在每一輪迭代的過程中，綜合庫(kù)房的供應(yīng)能力、車隊(duì)的配送能力以及收貨點(diǎn)位的接受能力等的約束條件以及迭代次數(shù)的要求，直至獲得全局最優(yōu)解。

3 實(shí)證結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

3.1.1 實(shí)驗(yàn)環(huán)節(jié)設(shè)定的算法參數(shù)

粒子群的種群規(guī)模為100，尋優(yōu)過程的最大迭代次數(shù)為100，群體尋優(yōu)過程的慣性參數(shù)取值為0.9，速度調(diào)節(jié)因子取值為1，拉格朗日動(dòng)態(tài)調(diào)整因子值設(shè)置為0.1。

3.1.2 實(shí)驗(yàn)環(huán)節(jié)選定的數(shù)據(jù)集

以大連某物流企業(yè)配送冷凍厄瓜多爾白蝦為例，設(shè)置物流配送貨場(chǎng)的編號(hào)為1，i代表客戶，其所需配貨數(shù)量為qi，配送運(yùn)輸車卸貨的時(shí)間為si，測(cè)試配送的工單數(shù)分布在15、20、25、30、35、40不同情況下的最佳路徑的選擇算法的執(zhí)行效能，即測(cè)試運(yùn)輸車分別對(duì)同一客戶承擔(dān)15～40次運(yùn)輸任務(wù)的全部最佳運(yùn)輸成本(路徑)的尋優(yōu)性能。

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)過程中，選擇貪婪算法作為比對(duì)實(shí)驗(yàn)，比較使用粒子群優(yōu)化算法與拉格朗日算法得到的適應(yīng)度函數(shù)求解的質(zhì)量和性能。在同樣的配送工單數(shù)量上，求解的性能對(duì)比如圖5所示。

圖5 不同算法運(yùn)行時(shí)間對(duì)比圖

數(shù)據(jù)顯示，隨著訂單數(shù)的增加，算法的求解能力會(huì)出現(xiàn)明顯下降，但是本文提出的算法的求解時(shí)間上升幅度明顯比優(yōu)化算法低，尤其是訂單數(shù)超過25以后，算法性能下降較為明顯，二者之間的差距愈發(fā)顯著。出現(xiàn)這個(gè)情況的原因在于拉格朗日算法的自適應(yīng)調(diào)整能力，極大地改善了尋優(yōu)的性能，縮小了求解的時(shí)間，在多個(gè)任務(wù)并行的情況下，自適應(yīng)調(diào)整能力的優(yōu)勢(shì)凸顯。

圖6 自適應(yīng)調(diào)整因子對(duì)算法性能的影響

實(shí)驗(yàn)過程中，重點(diǎn)對(duì)自適應(yīng)調(diào)節(jié)因子的變化值對(duì)求解時(shí)間的影響進(jìn)行了論證，當(dāng)λ在0.1～1變化時(shí)，選擇實(shí)驗(yàn)數(shù)據(jù)集的兩個(gè)較為復(fù)雜的算例進(jìn)行測(cè)試，求解時(shí)間如圖6所示，當(dāng)λ取值在0.2時(shí)，求解性能最高，且整體隨著λ的變化求解的時(shí)間也持續(xù)變化。進(jìn)一步論證了本文引入自適應(yīng)調(diào)節(jié)因子對(duì)整體算法的性能提升明顯。

4 結(jié)論

本文針對(duì)冷鏈產(chǎn)品的配送受到的制約較多、運(yùn)輸效率要求比較高等問題，針對(duì)多回路、多配送點(diǎn)位、多供貨點(diǎn)的冷鏈產(chǎn)品的配送最佳路徑求解的業(yè)界難題，將啟發(fā)式搜索算法的應(yīng)用與拉格朗日松弛算法相結(jié)合用于冷鏈產(chǎn)品的復(fù)雜路徑求解問題，結(jié)合綜合因素對(duì)拉格朗日松弛算法進(jìn)行動(dòng)態(tài)自適應(yīng)的調(diào)整，對(duì)冷鏈配送的網(wǎng)絡(luò)模型進(jìn)行動(dòng)態(tài)優(yōu)化調(diào)整，獲取最優(yōu)路徑解。仿真對(duì)比實(shí)驗(yàn)顯示，本文提出的算法對(duì)比原始的粒子群優(yōu)化算法，獲得最佳路徑的時(shí)間更短、最佳路徑的求解能力更高。