1. 引言
随着社会的不断进步和用电需求的飞速发展，物资管理作为电网建设和运维过程中不可或缺的一个重要环节，对电网企业的安全生产运行起着决定性的作用，物资管理水平的高低直接影响着电网企业的发展进程。电力企业物资管理的核心业务主要包括物资需求管理、采购管理、合同管理、库存管理和供应商管理等工作，并且保证企业物资采购和库存资源的合理使用，实现收益最大化。
由于电力企业的电网生产运行具有高度的连续性，由此决定了电力物资供应必须保证电网生产和建设需求。此外，供电的安全和质量具有广泛的社会影响，由此电力企业肩负着较大的社会责任，面对各种突发应急抢修工作，电力企业要求物资供应部门必须及时组织电力生产运行所需要的各种电力物资。因此，加强电力企业物资管理，对保证电力生产的安全经济运行和基建工程的顺利投产，提高企业经济效益和社会效益，都有着不可替代的作用 [1] 。
对于电力企业来说，由于其项目的特殊性，物资管理过程中可能会存在库存积压物资过多、调拨困难的情况。本文致力于解决物资利库过程中出现的匹配不合适、调拨困难等问题，将运用二分图原理，参考二分图多重匹配算法的计算规则，在需求和可利库库存之间寻求最优的调拨距离及匹配方案，在设定业务流程范围内求取最优解，简化利库配比流程，得出最优利库方案 [2] 。
2. 平衡利库及存在问题
以某省级电力公司为例，平衡利库作为国网公司物资集约化管理的重要组成部分和管理手段，已上线运行多年，截至目前系统中含有4千多条可利库物资数据，单位数量达到93万以上。该省级电力公司已经实现了简单的平衡利库模式(方式为单条匹配、手工操作)，已实现全省各级供电公司在需求计划提报环节、需求计划县、市、省三级汇总审批环节进行平衡利库，根据库存物资和物资扩展编码将需求物资与库存物资进行比对，利库成功的物资条目不再进行后续采购，实现物资的简单利库。
业务用户在多年平衡利库使用过程中，对系统易用性、匹配精准度提出了更高的要求，当前平衡利库中主要问题如下：
一、利库逻辑机械单一匹配效果低下：
要求单条可利库数量必须大于等于需求数量情形下，才允许执行利库，不支持累计数匹配。执行过程中，未考虑可利库先后顺序，未考虑匹配过程的已被占用的利库数量等情况。
二、未考虑调拨经济效益：
系统中缺乏合理调拨原则，如可利库物资种类、距离远近，无法给予系统使用者最大、最优判断，造成不经济或不合理调拨。
三、系统操作方式繁琐：
依赖计划员人工逐条判断并逐行点击“是否执行利库方案”操作，方式繁琐，造成工作效率低下，使用者体验差、利用率低。由于平衡过程中可利库数量不更新，界面中显示的可以利库的条目在实际利库时，可能会存在利库物资不够的情况。
3. 二分图及主要算法介绍
二分图(Bipartite Graph)：
二分图，是图论中的一种特殊模型。简单的说，一个图被分成了两部分，相同的部分没有边，那这个图就是二分图，二分图是特殊的图，在二分图中，顶点可以分为两个集合，每一条边的端点都分别位于这两个集合。对应到平衡利库业务中，这两个集合分别为需求集合和可利库库存集合。
二分图匹配(Bipartite Matching)：
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。详细匹配见图1所示：
极大匹配是指在当前已完成的匹配下，无法在通过增加未完成匹配的边的方法来增加匹配的边数。最大匹配是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集程伟图的最大匹配问题。
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
最佳匹配又称为最大权值匹配，就是在是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同，最优匹配也是一个完备匹配，即每个顶点都被匹配。如果个数不相等，可以通过补点加0边实现转化。求一个二分图的最佳匹配的普遍算法是KM (Kuhn-Munkres)算法。KM算法的基本思想是，把权值转化为可行顶标，再用匈牙利算法求出一组完备匹配，如果无法求出完备匹配，则修改可行顶标，直至找到完备匹配为止，这时的完备匹配为最佳匹配。
KM算法步骤：
1) 用邻接矩阵来存储图，注意：如果只求最大权值匹配而不要求完全匹配，请把各个不相连的边的权值设置为0。
2) 运用贪心算法初始化标杆。
3) 用匈牙利算法找到完备匹配。
4) 如果找不到，则通过修改标杆，增加一些边。
5) 重复3) 4)步骤，直到完备匹配时可结束。
4. 基于平衡利库的二分图多重匹配算法
4.1. 平衡利库功能需求分析
一、进一步细化并明确平衡利库先决条件。
物资利库级别明确：不同物资可能有不同的利库范围。
大部分通用物资均可在本工厂、本地区、全省范围三个层级内基于平衡利库的二分图多重匹配算法进行利库。
部分消耗类物资只在本工厂进行利库。比如水泥杆(大类编码14、中类编码01、小类编码002)、金具(大类编码14、中类编码01、小类编码003)、电缆附件(大类编码14、中类编码08)等物资。
部分特殊物资不纳入平衡利库范围。比如铁附件(大类编码14、中类编码06)、环网柜(大类编码10、中类编码16、小类编码006)等物资。
县市利库级别明确：维护不同地市之间的距离权重关系，两地市间权重越大，利库越优先。
在省平衡利库汇总环节，优先本地市平衡利库，不满足条件再按地市公司之间的距离权重优先进行片区范围内的平衡利库，最后再考虑全省范围内的利库：
例：
1、南京、无锡、常州、苏州和镇江为同一片区。
2、泰州、南通、扬州和淮安为同一片区。
3、徐州、连云港、宿迁和盐城为同一片区。
二、按照二分图多重匹配算法进一步优化利库方案。
根据平衡利库的需求，根据平衡利库基础数据、按照二分图多重匹配算法根据物料主数据和扩展编码，用物资需求计划集匹配可利库库存物资集，最终完成多条物资同时利库、自动匹配、最优选择、自动生成调拨单等一系列利库操作。
4.2. 二分图多重匹配算法设计
1、需求归集
将需要进行县平衡利库的数据全部写入需求集，县市A编码为工厂的3，4位，并按照物资编码 + 扩展编码排序。
2、需求匹配基础表
物资利库级别：维护不同类型物资的利库级别。
县市利库级别(原始路径集)：维护不同县市之间的距离权重及利库级别。
3、需求匹配可利库库存
将找到的数据按物资编码 + 扩展编码 + 县市B编码 + 可利库级别为筛选条件在利库库存对应表中去找符合的数据，将找到的数据全部写入库存集。
4、平衡利库匹配
需求集和库存集写入后，将需求集根据物资分类，每一类物资单独进行利库。每类物资按照二分法匹配原则将需求集和库存集进行最优匹配。匹配过程中，遵循权重最大化原则，选取调拨最优路径完成物资平衡利库。匹配成功后，需求集更新已利库数量，库存集更新已利库数量和可利库数量，同一组物资匹配完成后，按需生成相关后续凭证。
5、根据匹配结果生成相关后续凭证
物资匹配后，需求集的已利库数量 = 需求数量，即完全平衡利库，则更新采购申请已结算标识；若该条物资匹配后，需求集的已利库数量 < 需求数量或不能平衡利库，则物资继续进入下一级采购汇总。
每条需求匹配运行完成后，若完全平衡利库，自动创建冻结物料凭证、创建转储订单、更新采购申请已结算标识。若未完全平衡利库，则不创建后续凭证。
4.3. 基于平衡利库的二分图多重匹配算法实现
一、匹配算法实现原理说明
为方便描述，将需求集记为A，其中每一个需求为Ai。将库存集记为B，其中每一个库存为Bj。
1、循环需求集A。
2、对第一条需求Ai，在原始路径集中查找与当前Ai相关联的权值最大的Bj，如果Bj数量大于0，将路径集Ai-Bj添加进结果路径集Z。如果Bj数量大于等于Ai数量，则匹配结束，执行步骤1；如果Bj数量小于Ai数量，则在原始路径集中按权值从大到小依次查找与Ai相关联的Bj，直到Bj的数量和大于等于Ai，或者循环结束。
3、对非第一条需求Ai，在原始路径集中查找与当前Ai相关联的权值最大的Bj，如果Bj数量大于0，将路径集Ai-Bj添加进结果路径集Z。如果Ai数量等于0，则匹配结束，执行步骤1；如果仍大于0，则执行步骤3.1。
3.1、循环原始路径集，查找与当前需求Ai相关联的Bj，放入计算路径集J。
3.2、循环计算路径集J中的Bj，在原始路径集中查找与Bj相关联的Am，放入可断开路径集D。
3.3、循环可断开路径集D中的Am，在原始路径集中查找与Am关联的Bn，放入计算路径集J。
3.4、循环计算路径集J，依次计算“预计权值” = “当前Ai与Bj的权值” – “可断开路径(Bj-Am)的权值” + “可添加路径(Am-Bn)的权值”。并按“预计权值”的倒叙排序。
3.5、取计算路径集J中，计算后预计权值最大的路径，作为实际添加/断开–添加路径。
4、执行步骤1，直到循环结束。
二、简单图例举证展示匹配原理：
1、假设有需求集A和库存集B，红线表示对应的需求可与库存匹配，即可进行平衡利库(如A1计划可由B1或B2的库存调拨)，见图2所示。
2、按照顺序依次将需求A和库存B匹配，发现需求A1可以匹配库存B1，则认为A1和B1匹配成功，连上一条蓝线，见图3所示。
3、接着将需求A2匹配，发现可以匹配库存B2，则认为A2和B2匹配成功，连上一条蓝线，见图4所示。
Figure 2. Step 1 figure for illustration
图2. 步骤1图例说明
Figure 3. Step 2 figure for illustration
图3. 步骤2图例说明
Figure 4. Step 3 figure for illustration
图4. 步骤3图例说明
4、接下来为需求A3匹配，发现可以匹配的库存B1和B2均已被其他需求匹配，无法匹配A3，尝试将之前的需求A1匹配另一个库存，将A1-B1的匹配蓝色拆除，变成虚线，表示这条边被临时拆掉，见图5所示。
Figure 5. Step 4 figure for illustration
图5. 步骤4图例说明
5、与A1可匹配的另一个库存是B2，但是B2已经匹配了A2，尝试将A2-B2拆除(变为虚线)，并为A2再匹配一个库存B3 (连上一条蓝线)，见图6所示。
Figure 6. Step 5 figure for illustration
图6. 步骤5图例说明
6、A2匹配B3后，之前的问题都可以迎刃而解，回溯回去，A1可以匹配B2，而A3可以匹配B1，从而使需求集A和库存集B在匹配过程当中尽可能得到最优匹配(A1-B2, A2-B3, A3-B1)，见图7所示 [3] 。
5. 平衡利库功能实现
基于二分图多重匹配算法的平衡利库功能根据物资分类确定利库范围以及根据运输成本确定利库权重等因素，确定可利库匹配关系的边权矩阵基础数据。界定合理的利库物资范围(如图2所示)，制定利库地域优选级别和原则(如图3所示)，实现二分图多重匹配算法，将单一数量满足匹配改造成累计数匹配(如图4所示)，通盘考虑优先级、已占用数量、剩余数量等信息，并且自动推荐最优利库方案，提高利库的
Figure 7. Step 6 figure for illustration
图7. 步骤6图例说明
匹配程度(如图5所示)。基于ABAP语言开发设计平衡利库功能以及界面，能够根据用户要求动态设置利库级别以及利库物资范围，在操作上实现一键执行利库功能，提高界面操作便捷性。系统实现ERP系统中对应的主要功能如下：
1) 二分图多重算法平衡利库基础数据维护(见图8、图9所示)，进行平衡利库的县市所对应的利库级别及县市利库级别。
2) 二分图多重匹配算法平衡利库计算过程(见图10所示)，在县、市、省三级物资需求计划汇总时，根据二分图原理创建最优匹配算法模型进行物资平衡利库。
3) 平衡利库报表(见图11所示)，按照工厂、物资唯一码等信息查询二分图多重匹配算法的平衡利库相关情况。
Figure 8. Maintain material inventory balance level
图8. 维护物资利库级别
Figure 9. Maintain relationship between cities inventory balance level
图9. 维护县市利库级别
6. 电力行业平衡利库二分图多重匹配算法多维度对比分析
一、横向比对-电力行业与其他行业(如煤炭行业)比对：
对比电力行业和其他行业(如煤炭行业)平衡利库匹配算法 [4] ，二图多重匹配算法架构见图12所示：
Figure 12. Algorithm architecture of bipartite graph optimal matching in mine materials
图12. 煤矿物资二分图最优匹配算法架构
二分图匹配原则在其他行业平衡利库功能中也有运用，但电力行业的运用更为细致。由于原先业务中已经实现了一对多的匹配，故在运用二分图匹配原则时，仍将一条需求对应多个可利库库存条目的结果予以保留，实现最大限度的平衡利库匹配结果。电力行业在煤炭行业算法的相同点与区别见表1所示：
Table 1. Comparison between electric and other enterprises
表1. 电力行业与其他行业对比
二、纵向对比-电力行业平衡利库发展历程对比
对比电力行业原先平衡利库匹配算法，二分图多重匹配算法更为智能、灵活、全面、快捷。以某省级电力公司为例，平衡利库的信息化发展历经3个阶段，分别为一对一逐条匹配、一对多逐条匹配、多对多多重匹配(即二分图多重匹配)，整体发展历程见表2所示。
Table 2. Comparison of balanced liquidity ways in electric power industry at different stages
表2. 电力行业各阶段平衡利库方式对比
7. 结语
基于二分图多重匹配算法的平衡利库功能实现了平衡利库按最优方式自动匹配物资需求计划与可利库物资的关系，根据用户要求实现了多级智能利库，极大提高了利库的匹配程度，减少了人工利库的差错。由于能够自动实现物资需求计划与可利库物资之间的多对多的多重匹配，充分利用库存积压物资，能够提升现有积压库存物资利用率，优化现有平衡利库功能以及利库流程，实现一键式利库，同时实现可视化平衡利库结果以及自动进行平衡利库调拨，从而实现“智能、快捷、全面、合理”的全过程平衡利库。
参考文献