Research of Multidimensional Matching Algorithm Based on Bipartite Graph in Mine
Materials Inventory Balance
康鹏 KANG Peng；刘长龙 LIU Chang-long
（中国煤炭科工集团太原研究院有限公司，太原 030006）
（Taiyuan Research Institute of China Coal Technology & Engineering Group Corp，Taiyuan 030006，China）
摘要：本文通过建立标准的平衡利库权值数据模型，并引入二分图多重匹配算法，按照“先利库、后采购”的原则，多层级开展煤矿物资平衡利库工作。该平衡利库功能动态通盘考虑利库优先级、已利库数量、剩余数量等信息，自动推荐最优利库方案，提高利库的匹配程度，从而实现的全过程平衡利库。
Abstract: In the materials inventory balance system, the inventory models and multiple matching algorithm for two partite graph are used to manage the inventory dynamically in multi-level based on the considering of priority, quantity and other factors and help to recommend the best inventory plan in multi-level, multi-component, trans-region and whole process.
关键词：二分图；多重匹配；平衡利库；ERP
Key words: bipartite graph；multidimensional matching；inventory balance；ERP
中图分类号：F251 文献标识码：A 文章编号：1006-4311（2018）36-0029-03
0 引言
近年来，随着社会的不断进步和煤炭需求的飞速发展，确保煤矿稳定高效运行成为各大煤碳公司工作的重中之重。物资管理作为煤矿建设和生产过程中不可或缺的一个重要环节。大型煤碳集团公司的生产设备分布地域广泛，导致煤矿企业在不同煤矿形成多个库存地点，各级仓库保管着各类项目物资、检修物资、抢修物资和可再利用的拆旧物资等，其中不乏长期未使用的结余物资，这些物资中常常会因为长期保存而导致使用价值降低或报废，因此大型煤碳企业如何减少库存物资储备，提高库存物资利用率，一直是煤碳企业物资管理部门所追求的目标。
1 平衡利库及存在问题
大型煤碳企业按照传统的异地分散的多库存管理模式，由于仓库间的信息交互贫乏，不能最大效率利用存库间的信息资源, 导致形成了多个库存物资的信息孤岛。平衡利库针对现有库存和预计需求情况, 结合安全库存量来决定采购数量, 其中涉及物资需求管理、库存管理、采购管理等多个环节。
以某大型煤炭集团公司为例， ERP系统已稳定运行多年，系统中含有大量的可利库物资，不仅占用了大量的企业库存资金，而且对于仓储管理也增加了很多工作，不利于企业的正常运营。考虑到可利库物资与需求计划的匹配情况来看，平衡利库的匹配功能还有待加强，以便能够更大程度减少库存物资数量，为此不仅能够充分利用现有库存物资，增加资金流动性，同时也能降低仓库的运维成本。通过改造现有平衡利库功能，利用二分图匹配算法，寻找最佳路径，实现最大匹配，从而实现 “多层级、多环节、跨地区”的全面平衡利库，提高库存物资可利用率，优先考虑在库物资满足需求计划，合理安排利库匹配数据，实现企业利益最大化[1-2]。
2 二分图及主要算法简介
二分图（G）又称作二部图，是图论中的一种特殊模型，其所有顶点可以分为两个集合（U，V），并且同一集合中所有点都不相连，并且所有的边都关联在两个不同的集合中，这种边称为二分图的匹配。
选择这样的边数最大的子集称为图的最大匹配问题，最大匹配的边数称为最大匹配数。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。
求最大匹配的最显而易见的算法是:首先找出全部匹配，然后保留匹配数最多的那种方案。但是这个算法的计算量为指数级计算，极其耗时，因此，需要寻求一种更加高效的算法。目前，求一个二分图的最佳匹配的普遍算法是KM（Kuhn-Munkres）算法，该算法流程如下：
①初始化可行顶标的值；
②用匈牙利算法寻找完备匹配；
③若未找到完备匹配则修改可行顶标的值；
④重复②③直到找到相等子图的完备匹配为止。
匈牙利算法基于Hall定理中充分性证明的思想，它是二分图匹配最常见的算法，该算法的核心就是寻找增广路径，然后用增广路径求二分图最大匹配的算法。
3 基于平衡利库的二分图多重匹配算法
3.1 平衡利库功能需求分析
根据实际调研结果，某煤碳集团公司的平衡利库需求主要包括以下几方面要求。按照组织结构和地域就近原则。煤矿范畴内优先平衡利库，再考虑全公司范围内的平衡利库。常用的消耗类物资只在本地煤矿进行利库。其他大型物资根据不同物资可能有不同的利库范围。根据当前用户操作权限控制可利库范围。
系统要求分析煤矿物资仓储特点，通盘考虑库存现有量、安全库存量，深入研究库存物资品类、安全库存、可互替参数、平衡范围、调配距离、运输方式、堆放养护条件、维护保管年限、淘汰率等利库影响因素，形成多维度物资平衡利库的二分图最优匹配算法模型。模拟监控实际采购业务运转情形，跟踪业务变化，抽象新因子，修正模型，促进模型优化。透过该算法，制定调配原则，实现物资需求计划自动匹配调整、增加积压物资消耗，具体匹配架构如图2所示。
3.2 二分图多重匹配算法设计
根据平衡利库的需求，主要输入数据包括平衡利库的初始数据、物资需求计划集、可利库库存物资集、当前用户利库需求等，通过二分图多重匹配算法能够计算出平衡利库最优匹配结果，并根据仓库间利库物资的数量自动生成仓库物资调拨单，系统业务流程图如图3所示。
根据平衡利库的需求，主要输入数据包括平衡利库的初始数据、物资需求计划集、可利库库存物资集、当前用户利库需求等，通过二分图多重匹配算法能够计算出平衡利库最优匹配结果，并根据仓库间利库物资的数量自动生成仓库物资调拨单。
根据实际平衡利库的需求以及工作情况，定义平衡利库的级别分为五个层次，定义为利库级别表，高级别利库可以兼容低级别的利库范围。根据需求需要对不同的物资类型有利库范围的限制，因此需要根据物资类型定义可利库范围，定义为物资利库级别表，高级别利库可以兼容低级别的利库范围。考虑地域交通等原因，需要记录仓库间允许平衡利库权值的基础数据，定义为仓库间利库级别表。
根据信息系统可以随时获取不同仓库有可平衡利库的物资集，可利库物资集包括所在仓库、物资类型、数量、单价等信息。在实际工作中，汇总物资需求计划之后获得物资需求计划集，物资需求计划集包括需求单位、计划入库仓库、物资类型、需求数量等信息。根据需求计划集的物资类型进行分组，即可遍历需求计划集的不同物资类型，即可获取某类型的物资需求计划集，设为物资A的需求计划集。根据物资利库级别表、仓库间利库级别表、用户当前平衡利库等级可获取所有仓库间该类型物资的可利库路径，再根据可平衡利库物资表，即能获取到物资A的需求计划集与可平衡利库物资的边权矩阵。根据边权矩阵关系、库存数量、需求数量即可根据二分图多维匹配算法获取到最优匹配结果。
3.3 基于平衡利库的二分图多重匹配算法实现
由于平衡利库必须确保物资类型精确匹配，因此对于可利库的物资集以及需求物资集根据物资类型进行分类，针对每类物资分别进行利库，为描述简单，以下算法假设针对每种相同物资A进行匹配。基于权矩阵关系、库存数量、需求数量，以及根据当前用户利库级别，通过二分图多重匹配算法能够获取到平衡利库结果集。
①根据物资需求计划集按照仓库进行分组，并根据原始路径集的权值进行排序。
②假设当前平衡利库结果为权值乘以利库数量的结果之和为最大，即当前利库结果为最优的情况，如果按照顺序增加一条可利库路径以后，利库结果仍旧为最优结果，直到增加完所有路径即可获取最优匹配结果。具体步骤如下：
1）根据当前需要利库的路径取当前利库的仓库，从该仓库出发，根据可断开利库关系以及断开后可再利库的路径，直到损失的权值大于当前利库路径的权值为止。
2）根据权重损失最少的关系获取该路径可以利库的最大数量，如果可断开关系的利库最大数量大于等于需要利库关系的数量完成利库，否则执行第三步。
3）根据可以利库的最大数量现行利库，调整需要利库路径的需求数量，重复执行第一步，直到需要利库数量为0或者权重衰减数据集为空。
4 平衡利库功能实现
基于二分图多重匹配算法的平衡利库功能根据物资分类确定利库范围以及根据运输成本确定利库权重等因素，确定可利库匹配关系的边权矩阵基础数据。界定合理的利库物资范围，制定利库地域优选级别和原则，实现二分图多重匹配算法，将单一数量满足匹配改造成累计数匹配，通盘考虑优先级、已占用数量、剩余数量等信息，并且自动推荐最优利库方案，提高利库的匹配程度。基于ABAP语言开发设计平衡利库功能以及界面，能够根据用户要求动态设置利库级别以及利库物资范围，在操作上实现一键执行利库功能，提高界面操作便捷性。系统实现界面如图4所示。
5 结语
基于二分图多重匹配算法的平衡利库功能实现平衡利库按最优方式自动匹配物资需求计划与可利库物资的关系，根据煤碳公司要求实现多级智能利库，极大提高利库的匹配程度，减少人工利库的差错。
由于能够自动实现物资需求计划与可利库物资之间的多对多的多重匹配，充分利用煤碳公司库存积压物资，能够提升现有积压库存物资利用率。优化现有平衡利库功能以及利库流程，实现一键式利库，同时实现可视化平衡利库结果以及自动进行平衡利库调拨。
参考文献：
[1]方泉，康永，董子玉.基于ERP的电力物资平衡利库系统[J].计算机系统应用，2014（23）：70-73.
[2]孙波.浅谈物资管理在现代企业管理中重要作用[J].煤矿现代化，2008（2）：65-66.
[3]王誉霖.加强物资管理 提高经济效益[J].核经济研究，1997（02）. |
