基于供求融合的计量物资智能调度匹配路径优化研究

2023-07-12廖阳春谢宏泉周泉群杨柳雷书学

粘接 2023年6期

廖阳春　谢宏泉　周泉群　杨柳　雷书学

摘要：为解决电力计量物资供应链配送供应环节中，车货匹配与路径规划不科学不合理等，需进一步优化调度路径、降低物流运输成本、提高运作效率。基于供应与需求融合的角度，提出了电力计量物资供应链智能调度算法。主要对路径优化方面使用遗传算法对混合粒子群算法进行优化，结合交叉运行和变异运算，对最佳适应度粒子求解，提高运算效率，降低局部最优解几率，获得最佳配送路径。应用启发式正交二叉树搜索算法用于计量物资车辆的合理配备，最终从最优配送调度路径和最优装车方案相结合，形成基于实际调度物资需求的电网供应物资组合智能调度算法。通过与经典的调度算法比对实验证明，提出的算法在行车路径、派车数量以及装载效率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 结语

本文提出了以物流配送路径规划及电力计量物资合理配车综合考虑的电力资源智能调度算法。主要对路径优化方面使用遗传算法对混合粒子群算法进行优化，结合交叉运行和变异运算，对最佳适应度粒子求解，提高运算效率，降低局部最优解几率，获得最佳智能调度路径。基于供应与需求融合思路，进一步应用启发式正交二叉树搜索算法用于智能调度电力计量车辆的合理配车，最终从最优配送路径和最优装车方案相结合，形成基于实际配送物资基本需求的电网供应物资组合智能调度算法。同时考虑两个因素，使用配送车辆更少，运送总里程和装载率更高，但本方案还存在优化的空间，主要是时间限制为考虑，后续将持续优化。

【参考文献】

［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.