基于供求融合的計量物資智能調度匹配路徑優化研究

廖陽春　謝宏泉　周泉群　楊柳　雷書學

摘 要：為解決電力計量物資供應鏈配送供應環節中，車貨匹配與路徑規劃不科學不合理等，需進一步優化調度路徑、降低物流運輸成本、提高運作效率?；诠c需求融合的角度，提出了電力計量物資供應鏈智能調度算法。主要對路徑優化方面使用遺傳算法對混合粒子群算法進行優化，結合交叉運行和變異運算，對最佳適應度粒子求解，提高運算效率，降低局部最優解幾率，獲得最佳配送路徑。應用啟發式正交二叉樹搜索算法用于計量物資車輛的合理配備，最終從最優配送調度路徑和最優裝車方案相結合，形成基于實際調度物資需求的電網供應物資組合智能調度算法。通過與經典的調度算法比對實驗證明，提出的算法在行車路徑、派車數量以及裝載效率3方面均有大幅提升，具有一定的研究與推廣應用價值。

關鍵詞：物資配送；遺傳算法；路徑優化；正交二叉樹搜索算法；智能調度

中圖分類號：TP391.92 文獻標志碼：A文章編號：1001-5922（2023）06-0148-05

Optimization of path matching for intelligent scheduling of quantitative materials chain based on supply and demand fusion

LIAO Yangchun，XIE Hongquan，ZHOU Quanqun，YANG Liu，Lei Shuxue

（Hubei Huazhong Electric Power Technology Development Co.，LTD.，Wuhan 430070，China）

Abstract：In order to solve the problems of cyclic vehicle allocation，unreasonable vehicle cargo matching，and unreasonable path planning in the distribution and supply process of power metering materials supply chain，it is necessary to further optimize the scheduling path，reduce logistics transportation costs，and improve operational efficiency. An intelligent scheduling algorithm for the supply chain of electricity metering materials is proposed based on the integration of supply and demand. In terms of path optimization，genetic algorithm is mainly used to optimize the hybrid particle swarm optimization algorithm. The algorithm combines cross operation and mutation operation to solve the particle with the best fitness，improves the operation efficiency，reduces the probability of local optimal solution，and makes the best distribution path. Heuristic orthogonal binary tree search algorithm is applied to the reasonable distribution of electric power metering material vehicles. Finally，by combination of the optimal distribution scheduling path and the optimal loading scheme，an intelligent scheduling algorithm for the combination of power grid supply materials based on the actual demand for dispatching electric power metering materials is formed. Comparative experiments with classical scheduling algorithms demonstrate that the proposed algorithm exhibits improvements in travel paths，dispatching quantities，and loading efficiency，which has certain research and promotion application value.

Key words：material distribution;genetic algorithm;orthogonal binary tree search algorithm;intelligent scheduling

電力計量物資供應屬于電網物資管理的關鍵環節，物資供應鏈的主要成本為運輸成本，電力計量物資供應鏈配送工作中除了考慮最優路徑規劃問題，還需要結合物資合理配車問題，物資的形狀、質量、體積以及裝卸點等信息均會對運輸的車輛、路徑等智能調度產生重要影響[1]。同時兼顧物流配送路徑規劃及物資智能調度才能達到最適配車輛、最佳路徑，從而降低物流成本，解決電力計量物資配送供應過程中循環配車、車貨匹配不合理、路徑規劃不合理等核心問題[2]。目前，國內外學者已逐步將最短路徑與其他關鍵因素合并考慮，降低各行業運輸物流成本。從物流運輸的用戶需求出發，結合車輛的運力，提出了基于禁忌搜索模型與啟發式算法相結合的物流路徑規劃算法，兼顧了用戶的時間約束，但未結合車輛的運載能力[3]。提出了多任務并行條件基于優化蟻群算法的車輛調度算法，該算法充分考慮了時間約束，但車輛的數量未控制，運力成本方面受到一定影響[4]。提以減少物資運輸環節的燃料消耗為目標，將背包求解問題應用于物流運輸[5]，但未與路徑優化結合，僅實現了電力計量物資供應鏈最優車貨配比。

本文從物資供應鏈配送路徑規劃及物資合理配車角度及基于供應與需求融合方法[6]，提出了基于配送路徑與最優裝載組合的電力計量物資供應鏈智能調度算法。首先使用遺傳算法對混合粒子群算法進行優化，求解最佳配送路徑[7]。然后采用改進的啟發式正交二叉樹搜索算法用于配送車輛的合理配車，最終從最優配送路徑和最優裝車方案相結合，形成基于實際配送物資基本需求的供應鏈智能調度算法。

1 智能調度模型

1.1 業務描述

本文主要研究對象是指對于電力計量物資供應鏈配送中心與多個物資接收點的物資最優配送問題，由于電力物資具有形態各異、種類繁多，且各配電系統需求、物資智能調度車輛容量不同等現狀[8]，本文重點關注多種需求下運輸路徑選擇與車輛選型的問題，形成不同類型運輸車輛的最佳裝載方案和最優智能調度運輸路徑，建立基于供應與需求融合的車輛選型、運力和路徑規劃模型[9]，使用G=（U，E）代表物資運輸網絡，U為物資接收點（U0代表物資發放網點），E路徑。使用n（j=1，2…，n）標識不同類型的車輛，Z、V分別代表車輛的載重和體積，車輛的長、寬、高使用l、w、h代表。M代表配送物資的種類，m代表接收物資的供電所數量，Nj標識了第j類車的總數量以及運送物資的路徑選擇數量，tj標識第j類車中的第t個車[10]。cks標識了2個網絡節點k和s的距離，d～k標識了第k個網點的物資總量，D～tj標識了tj車的裝載物資總量[11]。貨物的長、寬、高使用li、wi、hi標識，貨物的體積和質量使用vi、zi表示。當車輛tj從網點k到達目標網點s后，標識xkstj=1，Rj代表第j類車輛的行車路徑方案，Qj代表j類車的裝載物資的總數量，RQj代表第j類車輛的最佳路徑-配合方案，X代表派車數量集合，QD代表各供電網點需要物資的數量集合[12]。

本文設計的智能調度模型主要基于最優路徑模型、最優配車模型，形成路徑-配車組合模型。

1.2 路徑優化建模

本文采用三角模糊數數標識配貨點對各個電力計量物資供應鏈所供應的物資總量、車輛裝載貨物量，即為d～k=（dk1，dk2，dk3），dk1、dk2、dk3分別代表物資最小需求量、一般需求量和最大物資需求量。Dt=（Dt1，Dt2，Dt3），Dt1、Dt2、Dt3分別代表車輛裝載貨物的最小量、常規量、最大量[13]。車輛可以容納的物資總量使用式（1）表示：

2 基于改進粒子群算法的組合模型最優求解算法

2.1 基于改進粒子群算法最佳路徑求解算法

使用基于遺傳算法對粒子群算法進行改進，獲得模型最優解。核心思想是使用遺傳算法中染色體代替粒子群算法中的粒子編碼形式，結合供應與需求融合需求，既要在粒子群尋優過程中獲得最新的可行解，同時還需要考慮在配送車輛最大容積約束，本文通過建立兩種不同的染色體分別標識配送車輛運行路徑、以及配送車輛的最佳配送點數量，二者結合，過程中結合最大容積約束確定配送的子路徑，形成最優路徑解[18-19]。首先，用A類染色體代表當前粒子解，與B類代表最優解的染色體進行遺傳較差處理，產生的子路徑新的染色體粒子解，將其與整個粒子群的最優解相結合，交叉處理得的種群最優解。同時，使用粒子群算法的記憶、迭代能力，更新最優解。如果最優解持續保持不變，則應用遺傳算法的變異操作，對最優解染色體進行變異，以避免陷入局部最優。

基于遺傳算法的混合粒子群優化算法的運算步驟：

步驟1：初始化粒子群算法數量、粒子群循環迭代次數、遺傳算法的變異操作條件。初始化兩種類型的臨時染色體X=［1，2，…，m］。

步驟2：根據各個配電站以往配電物資需求的數量確定模型相關的模糊變量的值，明確各個配送點k的需求數量的最小值、常規值和最大值：dk1、dk2、dk3。

步驟3：結合遺傳算法，確定粒子群每個粒子P的初始子值。

步驟4：循環迭代運算，更新粒子所在位置。

（1）首先依據隨機生產的x序列，明確臨時記錄粒子的染色體X*p；

（2）結合運貨車輛的最大容積，生成子路徑，確定對應的解Xp；

（3）帶入最優路徑目標函數，計算產生適應度值Zp；

（4）確定pbest的本輪迭代最佳適應值Zp，設置pbest的臨時粒子染色體Xpbest*p=X*p，得到pbest的解Xp；

（5）尋找gbest：當pbestp

步驟5：直至迭代次數或者取得最優解gbest。

（1）首先，進行交叉操作，將染色體對染色體Xpbest*p和Xp*進行交叉處理，得到X*a和X*b；

（2）其次，將X*a、X*b分別與Xgbest*p完成交叉處理，獲得交叉子染色體X*1與X*2、X*3與X*4；

（3）在（1）、（2）中已交叉生成的X*1、 X*2、X*3、X*4的基本前提下，結合模型的約束條件，獲得對應的子路徑，確定X*1、 X*2、X*3、X*4對應粒子群的最優解；

（4）對于X1、 X2、X3、X4分別循環的迭代，并基于供應與需求融合尋找最佳適應度值，在其中選擇最小的適應度值，即為染色體X；

（5）尋找pbestp，當Xp

（6）尋找gbestp，當pbestp

（7）粒子群內的全部粒子按步驟1～步驟6計算尋找最佳解；

（8）當gbest已經到達大的迭代次數，但仍未發生改變，則此采用變異操作，對gbest的臨時染色體Xgbest*p變異，獲得臨時最優解gbest及其對應的臨時粒子染色體Xtemp_gbest*p、子路徑Xtemp_gbest；

（9）計算Xtemp_gbest。的適應度值，當Xtemp_gbest

（10）循環迭代執行，直至到達最大次數，或者得到最佳適應度值，結束。

2.2 基于啟發式正交二叉樹搜索算法求解最佳裝載

本文基于供應與需求融合思路，采用啟發式正交二叉樹搜索算法，求解配送車物資裝載最大數量，核心思想是將背包求解問題應用于該模型，并在求解過程中引入分支定界算法來降低求解次數，提升運算速度，降低運算時間。

在車輛最佳行駛路徑下，結合配送點位的配送數量以及各個需求配電站的各類為物資數量，形成待配送的物資集合A，結合以往各配電站物資需求數量進行分析，得到該電力計量物資結合的數量d，結合優條生成的約束條件及供應與需求融合思路，按照不同類型車輛的車廂高度、寬度等形成排列組合的多種情況，實現車廂三位模型降維，簡化處理難度，具體如圖1所示。

在此基礎上，基于供應與需求融合方法創建正交啟發式二叉樹，節點代表車輛的裝載方案，根節點代表無貨時的裝載方案，中間節點按照車廂的寬度排列有條層級，形成中間節點車輛裝載方案，并反復迭代、擴展，逐步生成新的二叉樹，直至所有葉子節點已完成所有物資集合A的裝載，得出最佳轉載數量；具體如圖2所示。

通過最佳路徑以及在此基礎上的車輛最佳裝載數量形成后，按照裝載量、形式路徑、車型組合，形成各個車型的最優配送方案。

3 試驗與結果分析

3.1 實驗數據

實驗階段，本文選擇行業內常用的運力計算測試集進行數據測試，該測試集共計含有12個算例300個配送點位，每個配送點位間距在100 km以內，電力計量供應物資種類約800種，物資包裝箱種類586個，物資數量未5 321個。平均需要配送的物資數量在18個左右，4種配送車輛。

3.2 結果分析

針對實驗數據集中的12個算例使用本文提出的組合算法進行求解，并對當前研究中具有典型代表的電力計量物資供應鏈車輛配送算法進行比對實驗，每個算例的行駛路徑長度、車輛的裝載量以及配車數量等關鍵點比對如圖3～圖5所示。

對比分析可以發現：對于測試的12個案例，使用對比算法SDVRLH2進行物資配送，篩選的車輛為單一類型的車輛[20]。使用本文的算法則為多種車型組合的優化后的多類型車隊。完成同一批配送任務時，本文的算法派車數量平均少4輛，最大時少用9輛，裝載率提升15%，性能提升較大。同時，對于完成同一派車任務，本文基于供應與需求融合方法從路徑和裝載量量較多優化，本文在行車里程和裝載量方面優化效果非常明顯，其中總里程數平均降低了35%，裝載量提升了約27%。

4 結語

本文提出了以物流配送路徑規劃及電力計量物資合理配車綜合考慮的電力資源智能調度算法。主要對路徑優化方面使用遺傳算法對混合粒子群算法進行優化，結合交叉運行和變異運算，對最佳適應度粒子求解，提高運算效率，降低局部最優解幾率，獲得最佳智能調度路徑?；诠c需求融合思路，進一步應用啟發式正交二叉樹搜索算法用于智能調度電力計量車輛的合理配車，最終從最優配送路徑和最優裝車方案相結合，形成基于實際配送物資基本需求的電網供應物資組合智能調度算法。同時考慮兩個因素，使用配送車輛更少，運送總里程和裝載率更高，但本方案還存在優化的空間，主要是時間限制為考慮，后續將持續優化。

【參考文獻】

［1］付麗茹，解進強.“互聯網+”下的運輸服務變革[[J].商業經濟研究，2017（3）：203-204.

[2］馬天舒，吳海泉，倪雋.電網物資供應鏈智能運營指揮平臺搭建與實現[J].粘接，2021，45（3）：158-162.

[3］RUAN Q，ZHANG Z，MIAO L，et al.A hybrid approach for the vehicle routing problem with threedimensional loading constraints[J].Computers&Operations Research，2018，40（6）：1579-1589.

[4］JUNQUEIRA L，MORABITO R.Heuristic algorithms for a threedimensional loading capacitated vehicle routing problem in a carrier[J].Computers&tndustrial Engineering，2019，88（32）：110-130.

[5］ZHANG Z，WEI L，LIM A.An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under threedimensional loadingconstraints[J].Transportation Research Part B：Methodological，2015，82（46）：20-35.

[6］王超，金淳，韓慶平.三維裝載與CVRP聯合多目標優化問題的模型及算法[J].控制與決策，2016，31 （5）：929-934.

[7］張侃，張浩海，顧新橋，等.基于A-Workflow的電力倉儲化資產盤活方法研究[J].粘接，2021，46（5）：164-168.

[8］李穎.物流配送網點選址PSO算法的研究[[J].微型電腦應用， 2019，35（10）：90-92.

[9］常連玉，胡大偉，陳海蓉，等.基于PCA-AHP模型的無車承運人合作伙伴選擇研究[J].計算機應用研究，2017，34（8）：2340-2344.

[10］詹超，李祖健，鄭建寧，等.構建信息化智能物資管理采購體系的關鍵技術分析[J].粘接，2019，40（9）：143-147.

[11］范厚明，劉鵬程，吳嘉鑫，等.集貨需求隨機的同時配集貨VRP及混合變鄰域搜索算法[J］.系統工程理論與實踐，2019，39（10）：2646-2659.

[12］李卓，李引珍，李文霞.應急物資運輸路徑多目標優化模型及求解算法[J].計算機應用，2019，39（9）：2765-2771.

[13］劉帥，姜麗.基于PCA-BP神經網絡的無車承運人合作伙伴選擇研究[J].鐵道運輸與經濟，2018，40（10）：45-50.

[14］陸建山，周鴻波，謝偉東.基于量子粒子群優化的動態標定辨識方法[J].傳感器與微系統2016，35 （6）：27-30.

[15］葉平. 基于粒子群算法的最優物流運輸線路規劃方法研究[J].微型電腦應用， 2021，37（12）：158-161.

[16］俞虹，程文美，代洲，等.基于強化學習的電力系統應急物資倉儲控制算法[J].粘接，2021，48（11）：173-178.

[17］張茂君，李俊華，邢海濤，等.基于Hadoop和Flink的電力供應鏈數據中臺建設與應用[J].電力大數據，2022，25（2）：55-63.

[18］謝紅.基于數據挖掘技術的大型應急物資調度系統的設計與實現[J].現代電子技術，2017，40（8）：49-52.

[19］李娜.基于大數據的物資供應鏈配送智能調度系統設計[J].現代電子技術，2020，43（22）：184-186.

[20］王延海.基于區塊鏈與物聯網標簽技術的電網物資追蹤溯源體系構建研究[J].供應鏈管理，2022，3（7）：26-36.

收稿日期：2023-02-24；修回日期：2023-05-27

作者簡介：廖陽春（1983-），男 ，碩士，高級工程師，研究方向：高頻數據采集；E-mail：liaoyqchh@tom.cn。

引文格式：廖陽春，謝宏泉，周泉群，等.基于供應與需求融合的電力計量物資供應鏈智能調度算法的研究[J].粘接，2023，50（6）：148-152.