基于混合算法的電力物料車輛排隊服務(wù)優(yōu)化

王偉麗，張明偉

（天津仁愛學(xué)院，天津 301636）

0 引言

隨著經(jīng)濟加速發(fā)展，企業(yè)經(jīng)營規(guī)模迅速擴大，供應(yīng)鏈中各節(jié)點的物流運輸負擔加重，在企業(yè)倉儲園區(qū)中，經(jīng)常出現(xiàn)運輸車輛排隊等待服務(wù)的現(xiàn)象，由于出入庫訂單擾動大，無法預(yù)估倉庫裝卸時間，排隊等待服務(wù)時間不確定，較長的車輛排隊造成了巨大的人員與成本浪費。這種現(xiàn)象在電力物料類的運輸存儲過程中尤為明顯，因為電力物料種類繁多，體積重量大小不一，各類型的物料搬運裝卸工具差異較大，不同物料還需要適配車輛類型，所以車輛的排隊等待時間具有很大的不確定性。

借鑒經(jīng)典排隊理論，將倉庫看作服務(wù)臺，將車輛看作顧客，倉儲裝卸排隊服務(wù)屬于M/M/C排隊模型。此時很多管理人員需要利用排隊理論找到一種最佳資源配置方案[1]，因此有許多對排隊經(jīng)典理論M/M/C模型的深入研究和場景應(yīng)用，如醫(yī)療系統(tǒng)排隊模型[2-3]、停車場排隊模型[4]、道路交通排隊模型[5]等。對于模型的求解算法，較多學(xué)者建立狀態(tài)轉(zhuǎn)移圖和方程進行數(shù)值分析[6-7]，或者使用仿真軟件建立模型[8-9]。目前針對倉儲裝卸的排隊模型鮮有研究，但以上研究為本文關(guān)于電力物料車輛排隊服務(wù)優(yōu)化研究提供了理論參考和借鑒。

1 問題描述與假設(shè)條件

1.1 問題描述

企業(yè)一般將多個自有倉庫規(guī)劃在一個園區(qū)，倉庫存儲各種種類、型號、體積、重量等不一的物料，部分類型的產(chǎn)品在多個倉庫均有庫存，各種類型的物料裝載卸載方式不同，裝卸搬運的時間也有較大差異。將車輛分為入庫和出庫兩部分，對于入庫車輛，根據(jù)訂單和定位系統(tǒng)，可以對到達時間做出較為準確的預(yù)測，并且可以根據(jù)訂單獲取車輛運輸物料的相關(guān)信息。對于出庫車輛，需要根據(jù)需求訂單由第三方物流派遣車輛，車輛類型須滿足物料裝載要求，車輛的到達時間需要根據(jù)倉庫園區(qū)內(nèi)車輛排隊等待情況進行優(yōu)化。由于車輛裝載多種類型物料，物料存放倉庫不同，因此同一車輛需要在多個倉庫進行轉(zhuǎn)換，來裝卸與倉庫存儲匹配的物料。

當貨運需求較大時，隨著訂單和車輛單位時間內(nèi)集中到達，車輛排隊等待裝卸服務(wù)的現(xiàn)象較為突出，隨著訂單的不斷到達，對既定排隊服務(wù)調(diào)度方案也將產(chǎn)生較大擾動。在此情境下，如何減少車輛的排隊等待時間，減少排隊造成的成本浪費，提高作業(yè)效率，從而提高服務(wù)滿意度，是本文研究的目標問題。

本文將一定時間內(nèi)動態(tài)到達園區(qū)的入庫車輛和出庫訂單統(tǒng)一進行優(yōu)化，以確定出庫車輛的到達時間和次序，減少車輛排隊服務(wù)時間和成本。設(shè)定調(diào)度點對新加入訂單進行重新調(diào)度，以減少新到訂單對調(diào)度優(yōu)化結(jié)果的擾動。模型的優(yōu)化目標為所有車輛平均空閑時間最小和所有車輛最大空閑時間最小。

1.2 符號說明

k:貨運車輛，k ∈K；

p:不同種類或不同型號的產(chǎn)品，p ∈P；

m:不同的倉庫，m ∈M；

r：重調(diào)度的次數(shù)，r ∈{1,2,...,R}；

1.3 條件假設(shè)

（1）根據(jù)訂單和定位系統(tǒng)，入庫車輛到達時刻能夠確定；

（2）倉庫的裝載或卸載作業(yè)開始后不會中斷；

（3）出庫作業(yè)由第三方物流安排各種類型適配車輛且數(shù)量足夠；

（4）倉庫中有足夠物料滿足出庫訂單需求；

（5）倉庫在同一時間只能容納一輛貨車進行裝載或者卸載作業(yè)；

（6）入庫車輛只執(zhí)行卸載任務(wù)，出庫車輛只執(zhí)行裝載任務(wù)。

2 模型構(gòu)建

2.1 裝載卸載時間

這里，車輛k的裝載時間Lk為：

車輛k的卸載時間Uk為：

2.2 模型建立

模型的目標函數(shù)為：

優(yōu)化目標式（3）表示車輛平均空閑時間最?。粌?yōu)化目標式（4）表示車輛最大空閑時間最小。

目標函數(shù)約束條件S.T.：

式（5）和式（6）表示h產(chǎn)品和l產(chǎn)品不能同時在倉庫m裝載和卸載；式（7）表示車輛同一時間只能在一個倉庫裝載或者卸載一種物料；式（8）表示車輛k在一次運輸過程只執(zhí)行出庫或者入庫其中一種任務(wù)；式（9）表示車輛在裝載或卸載過程中不中斷任務(wù)；式（10）表示卸載決策變量；式（11）表示裝載決策變量；式（12）表示重調(diào)度決策變量。

3 算法設(shè)計

由于車輛需要在倉庫間轉(zhuǎn)移，此類排隊服務(wù)問題為NP難度問題[10]，使用數(shù)學(xué)解析的方法求得最優(yōu)解。智能優(yōu)化算法對此類問題的求解具有良好的效果[11]。遺傳算法（Genetic Algorithm，GA）具有較強的優(yōu)良基因傳遞能力和良好的收斂性，粒子群算法（Particle Swarm optimization，PSO）具有較好的搜索方向性。本文將遺傳算法與粒子群算法結(jié)合，利用GA的染色體遺傳特性保留優(yōu)良解，利用粒子群算法的方向性，使得染色體能夠快速獲取局部最優(yōu)和全局最優(yōu)基因。并利用模擬退火算法中的Metropolis準則來防止陷入局部最優(yōu)和過早停滯現(xiàn)象?；旌纤惴鞒倘鐖D1所示。

圖1 GA-PSO混合算法流程圖

借助GA算法的優(yōu)良基因遺傳特性，利用PSO算法的搜索方向性，將PSO中本代最優(yōu)Pbest和全局最優(yōu)Gbest分別與其他粒子進行交叉操作，以保留良好的基因。為避免陷于局部最優(yōu)，本文提出采用模擬退火算法中的Metropolis抽樣準則來判斷是否接受Pbest或者Gbest，以避免算法的早熟，接受概率ψ按照式（13）計算。

其中，Γ為接受概率系數(shù)，與迭代次數(shù)成反比，與ψ成正比，即接受概率ψ隨著迭代次數(shù)增加逐漸減小。

3.1 算法編碼

為方便表達模型的實際信息含義，減少不可行解的產(chǎn)生，GA-PSO混合算法采用分層實數(shù)編碼。共分為4層代表不同信息變量，如圖2所示。

圖2 粒子編碼示意圖

圖2中，第一層為車輛信息，不同的數(shù)字對應(yīng)不同的運輸車輛，數(shù)字出現(xiàn)的順序表示運輸車輛裝卸不同類型物料的次序，如[1,2,1,3,2,1,3]中第一個“1”表示車輛1裝卸第一種物料，第一個“2”表示車輛2裝卸第一種物料，第二個“1”則表示車輛1裝卸第二種物料，以此類推；第二層表示運輸車輛對應(yīng)的裝卸物料信息；第三層表示運輸車輛裝卸物料選擇的倉庫。

3.2 個體更新

3.2.1 交叉算子：由于在智能優(yōu)化算法中，實數(shù)編碼在更新或者交叉等算子操作中經(jīng)常會產(chǎn)生大量不可行解，本文提出動態(tài)交叉算子的方法來避免在粒子交叉過程中產(chǎn)生不可行解，如圖3所示。

圖3 交叉算子操作示意圖

圖3 為交叉算子操作過程，首先在Pbesti(t)中隨機產(chǎn)生2個交叉點x1和x2，然后在Si(t)中自粒子起始位置，依次搜索與交叉點x1和x2之間含有相同數(shù)字（次序可以不同）的連續(xù)基因片段y1和y2，然后將x1、x2之間的基因片段與y1、y2之間的基因片段進行交換，完成交叉過程，產(chǎn)生新的粒子Pbest’i(t)和S’i(t)。如果交叉操作過程中，在Si(t)沒有找到與x1、x2之間基因片段對應(yīng)的y1、y2，則減小x1、x2之間的一位數(shù)字，繼續(xù)搜索，直到x1、x2之間基因片段減小到一位數(shù)字，則重新產(chǎn)生x1、x2交叉點，繼續(xù)重復(fù)上述過程，直到能夠執(zhí)行交叉操作為止。粒子的第二層和第三層編碼跟隨第一層交叉操作同時移動。

3.2.2 變異算子。GA-PSO中的變異算子操作采用多對變異、多層變異的方式，即在粒子中隨機生成兩點，兩點的車輛信息、物料信息、倉庫信息之間互相交換。在交換完畢后，針對第三層倉庫信息，重新隨機生成一個裝卸物料倉庫，以保證變異操作能夠充滿解空間。

3.3 適應(yīng)度計算

GA-PSO混合算法中適應(yīng)度值取越大越優(yōu)，雙優(yōu)化目標為所有車輛平均空閑時間Tw最小和車輛最大空閑時間Tv最小。兩個優(yōu)化目標的權(quán)重系數(shù)根據(jù)企業(yè)偏好確定。適應(yīng)度函數(shù)為：

式（14）中的λ1和λ2為雙目標的權(quán)重系數(shù)，即為企業(yè)對車輛平均空閑時間和車輛最大空閑時間的偏好系數(shù)。

4 仿真算例

4.1 算例數(shù)據(jù)

以國家電網(wǎng)天津市電力物資公司智慧物流園區(qū)的實際物料出入庫記錄作為算例數(shù)據(jù)。物流園區(qū)經(jīng)常運輸配送的電力物料主要有19種，各種物料存放在園區(qū)的7個倉庫中。園區(qū)5號庫、6號庫為智能立體倉庫，1號庫和7號庫為露天堆場，其他倉庫為平庫。受倉庫大門和通道限制，立體庫和平庫同時只能允許一輛運輸車輛進行裝卸作業(yè)。堆場主要存放電力電纜等大型物料，受裝卸搬運工具限制，同時只能為一輛運輸車輛進行裝卸作業(yè)服務(wù)。物流園區(qū)中的倉庫類型、序號及存儲的常見電力物料見表1。

表1 倉庫及物料信息表

表1中，同一個物料裝載和卸載時間可能不同。有的電力物料體積、重量較大，一般沒有外包裝，如物料1、8、9等，一般在露天倉庫存放，裝卸需要借助吊車或者門式起重機，裝載后需要固定和檢查，需要耗費較長時間。有些物料包裝規(guī)格為多個物料裝紙箱或者木箱，如2、3、12等，企業(yè)一般使用叉車進行裝卸，裝載、卸載時間近似相等。

實際生成過程中，同一輛車輛有時裝載或者卸載多個種類的電力物料，由于不同物料存儲倉庫不同，所以車輛需要在各個倉庫之間轉(zhuǎn)移。

表2為裝卸運輸車輛在智慧物流園區(qū)的7個倉庫之間轉(zhuǎn)移的時間，主要包括行駛時間、調(diào)整到裝卸位置時間、手續(xù)交接時間等。任兩個倉庫之間往返時間相等。

表2 轉(zhuǎn)移倉庫時間(min)

由于區(qū)域電力物料公司物流園區(qū)經(jīng)常有采購收貨、退貨，成本中心發(fā)貨、項目發(fā)貨、工單發(fā)貨，工廠間和工廠內(nèi)轉(zhuǎn)移，甚至拍賣銷售等，各種車輛每日進出倉庫裝卸貨物頻繁，若到達時間集中則會造成大量等待和成本浪費。以天津電力物料公司某一天實際物料出入庫記錄為數(shù)值算例，見表3。表3中，入庫車輛到達時間可以由發(fā)車時間、在途時間和衛(wèi)星定位等做出較為準確的預(yù)估，并且入庫車輛裝載的電力物料信息可以由訂單獲取。出庫物料由第三方物流公司派遣車輛，現(xiàn)公司已經(jīng)擁有三維裝箱優(yōu)化系統(tǒng)，可以根據(jù)出庫訂單中物料的種類、數(shù)量、體積和質(zhì)量等約束，優(yōu)化派遣車輛的類型與數(shù)量。因此，物流公司根據(jù)與智慧物流園區(qū)的距離和道路擁堵情況，可以安排裝箱優(yōu)化后的出庫車輛準時到達。為減少車輛空閑等待時間，本文根據(jù)以上算例的信息和數(shù)值，對車輛排隊等待服務(wù)進行優(yōu)化，并給出出庫車輛最優(yōu)到達時間，使出庫和入庫的所有車輛的平均空閑時間與最大空閑時間最小。

表3 運輸車輛到達及物料出庫信息

4.2 仿真結(jié)果

針對4.1節(jié)算例數(shù)據(jù)，使用GA-PSO混合算法進行仿真優(yōu)化。以Matlab2022a為運算工具，多目標模型的帕累托解與目標的權(quán)重系數(shù)相關(guān)，模型中兩個優(yōu)化目標為一定時間內(nèi)所有車輛平均空閑時間最小和車輛最大空閑時間最小，其值與企業(yè)對兩者的重視程度相關(guān)，由于兩個目標性質(zhì)相近，故兩者的權(quán)重系數(shù)采用λ1=λ2=1。

采用均勻設(shè)計試驗[12]的方法來確定GA-PSO 中參數(shù)取值，初始種群規(guī)模設(shè)置為1 000，交叉率為0.35，變異率為0.08，變異對數(shù)為3。算法的終止條件為：當進行200次迭代運算后，若算法的適應(yīng)度函數(shù)值不再變化，則算法終止。

將表1、表2中的電力物料公司物料、倉儲和倉庫信息，以及表3中公司某一日的物料出入庫數(shù)據(jù)，輸入電力物料裝卸排隊服務(wù)優(yōu)化模型，并對模型仿真30次，對優(yōu)化結(jié)果取平均值，即“模型優(yōu)化”的值，并且與“當日實際”發(fā)生的值進行對比分析，得到優(yōu)化結(jié)果見表4。

表4 模型優(yōu)化結(jié)果

由表4可知，模型優(yōu)化后比當時實際的車輛平均空閑時間、最大空閑時間和總空閑時間都有大幅度減少。

取其中的一個優(yōu)化結(jié)果進行分析，其優(yōu)化調(diào)度甘特圖如圖4所示。

圖4 車輛排隊服務(wù)優(yōu)化調(diào)度甘特圖

最優(yōu)粒子的三層信息編碼為：

根據(jù)公司歷史資料數(shù)據(jù)，當日實際車輛出入庫排隊服務(wù)調(diào)度甘特圖如圖5所示。

圖5 當日實際車輛排隊服務(wù)調(diào)度甘特圖

表5給出了圖4中優(yōu)化解的具體數(shù)值，并與當日車輛的實際到達排隊次序和空閑時間進行對比。

表5 當日實際數(shù)據(jù)與模型優(yōu)化結(jié)果

由表5可知，優(yōu)化后的平均空閑時間和最大空閑時間相比實際數(shù)據(jù)分別減少了55.2%和41.1%，可以看出模型對電力物資出入庫車輛的排隊服務(wù)時間優(yōu)化效果明顯。

5 結(jié)語

針對電力物料類產(chǎn)品的出庫入庫排隊服務(wù)調(diào)度有其固有屬性和特征，如產(chǎn)品種類繁多、重量體積不一，裝卸時間差異大，且裝卸方式、工具各不相同，極易造成集中排隊，等待服務(wù)，浪費大量時間和成本。本文建立了電力物料出庫入庫排隊服務(wù)模型，考慮了車輛倉庫轉(zhuǎn)換時間對排隊服務(wù)時間的影響。提出了將遺傳算法與粒子群算法結(jié)合的GA-PSO混合算法，并引入了Metropolis抽樣準則以提高算法跳出局部最優(yōu)的能力。最后對國家電網(wǎng)天津市電力物資公司智慧物流園區(qū)實際數(shù)據(jù)算例進行仿真優(yōu)化分析，結(jié)果表明了算法的高效性和模型的可行性，相關(guān)研究模型已在企業(yè)物流智慧園區(qū)供應(yīng)鏈多環(huán)節(jié)協(xié)同關(guān)鍵技術(shù)研究項目中進行分析與驗證，并應(yīng)用于企業(yè)實際倉儲服務(wù)信息系統(tǒng)，極大地減小了企業(yè)運輸車輛排隊等待服務(wù)現(xiàn)象，減少了時間與成本浪費，具有較強實際意義與應(yīng)用價值。

后續(xù)研究擬根據(jù)企業(yè)實際需求，通過企業(yè)運營大數(shù)據(jù)，對電力物料出入庫歷史數(shù)據(jù)進行統(tǒng)計分析預(yù)測，科學(xué)合理分派物料存儲倉庫及庫位，并減小調(diào)度點間隔時間，建立智能動態(tài)電力物料倉儲運輸排隊服務(wù)模型。