基于混合算法的電力物料車輛排隊服務優化

王偉麗，張明偉

（天津仁愛學院，天津 301636）

0 引言

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

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

1 問題描述與假設條件

1.1 問題描述

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

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

本文將一定時間內動態到達園區的入庫車輛和出庫訂單統一進行優化，以確定出庫車輛的到達時間和次序，減少車輛排隊服務時間和成本。設定調度點對新加入訂單進行重新調度，以減少新到訂單對調度優化結果的擾動。模型的優化目標為所有車輛平均空閑時間最小和所有車輛最大空閑時間最小。

1.2 符號說明

k:貨運車輛，k ∈K；

p:不同種類或不同型號的產品，p ∈P；

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

r：重調度的次數，r ∈{1,2,...,R}；

1.3 條件假設

（1）根據訂單和定位系統，入庫車輛到達時刻能夠確定；

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

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

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

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

（6）入庫車輛只執行卸載任務，出庫車輛只執行裝載任務。

2 模型構建

2.1 裝載卸載時間

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

車輛k的卸載時間Uk為：

2.2 模型建立

模型的目標函數為：

優化目標式（3）表示車輛平均空閑時間最??；優化目標式（4）表示車輛最大空閑時間最小。

目標函數約束條件S.T.：

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

3 算法設計

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

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

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

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

3.1 算法編碼

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

圖2 粒子編碼示意圖

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

3.2 個體更新

3.2.1 交叉算子：由于在智能優化算法中，實數編碼在更新或者交叉等算子操作中經常會產生大量不可行解，本文提出動態交叉算子的方法來避免在粒子交叉過程中產生不可行解，如圖3所示。

圖3 交叉算子操作示意圖

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

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

3.3 適應度計算

GA-PSO混合算法中適應度值取越大越優，雙優化目標為所有車輛平均空閑時間Tw最小和車輛最大空閑時間Tv最小。兩個優化目標的權重系數根據企業偏好確定。適應度函數為：

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

4 仿真算例

4.1 算例數據

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

表1 倉庫及物料信息表

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

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

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

表2 轉移倉庫時間(min)

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

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

4.2 仿真結果

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

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

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

表4 模型優化結果

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

取其中的一個優化結果進行分析，其優化調度甘特圖如圖4所示。

圖4 車輛排隊服務優化調度甘特圖

最優粒子的三層信息編碼為：

根據公司歷史資料數據，當日實際車輛出入庫排隊服務調度甘特圖如圖5所示。

圖5 當日實際車輛排隊服務調度甘特圖

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

表5 當日實際數據與模型優化結果

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

5 結語

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

后續研究擬根據企業實際需求，通過企業運營大數據，對電力物料出入庫歷史數據進行統計分析預測，科學合理分派物料存儲倉庫及庫位，并減小調度點間隔時間，建立智能動態電力物料倉儲運輸排隊服務模型。