廖陽(yáng)春　謝宏泉　周泉群　楊柳　雷書(shū)學(xué)

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

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

中圖分類號(hào)：TP391.92 文獻(xiàn)標(biāo)志碼：A文章編號(hào)：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

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

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

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

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

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

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

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

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

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

2.1 基于改進(jìn)粒子群算法最佳路徑求解算法

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

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

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

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

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

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

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

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

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

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

（5）尋找gbest：當(dāng)pbestp

步驟5：直至迭代次數(shù)或者取得最優(yōu)解gbest。

（1）首先，進(jìn)行交叉操作，將染色體對(duì)染色體Xpbest*p和Xp*進(jìn)行交叉處理，得到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é)合模型的約束條件，獲得對(duì)應(yīng)的子路徑，確定X*1、 X*2、X*3、X*4對(duì)應(yīng)粒子群的最優(yōu)解；

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

（5）尋找pbestp，當(dāng)Xp

（6）尋找gbestp，當(dāng)pbestp

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

3.2 結(jié)果分析

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

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

4 結(jié)語(yǔ)

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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