基于供求融合的計量物資智能調(diào)度匹配路徑優(yōu)化研究

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

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

關(guān)鍵詞：物資配送；遺傳算法；路徑優(yōu)化；正交二叉樹搜索算法；智能調(diào)度

中圖分類號：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

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

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

1 智能調(diào)度模型

1.1 業(yè)務(wù)描述

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

本文設(shè)計的智能調(diào)度模型主要基于最優(yōu)路徑模型、最優(yōu)配車模型，形成路徑-配車組合模型。

1.2 路徑優(yōu)化建模

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

2 基于改進粒子群算法的組合模型最優(yōu)求解算法

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

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

基于遺傳算法的混合粒子群優(yōu)化算法的運算步驟：

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

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

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

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

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

（2）結(jié)合運貨車輛的最大容積，生成子路徑，確定對應(yīng)的解Xp；

（3）帶入最優(yōu)路徑目標函數(shù)，計算產(chǎn)生適應(yīng)度值Zp；

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

（5）尋找gbest：當pbestp

步驟5：直至迭代次數(shù)或者取得最優(yōu)解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的基本前提下，結(jié)合模型的約束條件，獲得對應(yīng)的子路徑，確定X*1、 X*2、X*3、X*4對應(yīng)粒子群的最優(yōu)解；

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

（5）尋找pbestp，當Xp

（6）尋找gbestp，當pbestp

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

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

（9）計算Xtemp_gbest。的適應(yīng)度值，當Xtemp_gbest

（10）循環(huán)迭代執(zhí)行，直至到達最大次數(shù)，或者得到最佳適應(yīng)度值，結(jié)束。

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

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

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

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

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

3 試驗與結(jié)果分析

3.1 實驗數(shù)據(jù)

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

3.2 結(jié)果分析

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

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

4 結(jié)語

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

【參考文獻】

［1］付麗茹，解進強.“互聯(lián)網(wǎng)+”下的運輸服務(wù)變革[[J].商業(yè)經(jīng)濟研究，2017（3）：203-204.

[2］馬天舒，吳海泉，倪雋.電網(wǎng)物資供應(yīng)鏈智能運營指揮平臺搭建與實現(xiàn)[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聯(lián)合多目標優(yōu)化問題的模型及算法[J].控制與決策，2016，31 （5）：929-934.

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

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

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

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

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

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

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

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

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

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

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

[18］謝紅.基于數(shù)據(jù)挖掘技術(shù)的大型應(yīng)急物資調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)[J].現(xiàn)代電子技術(shù)，2017，40（8）：49-52.

[19］李娜.基于大數(shù)據(jù)的物資供應(yīng)鏈配送智能調(diào)度系統(tǒng)設(shè)計[J].現(xiàn)代電子技術(shù)，2020，43（22）：184-186.

[20］王延海.基于區(qū)塊鏈與物聯(lián)網(wǎng)標簽技術(shù)的電網(wǎng)物資追蹤溯源體系構(gòu)建研究[J].供應(yīng)鏈管理，2022，3（7）：26-36.

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

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

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