二分圖多重匹配算法在煤礦物資平衡利庫中的研究

康鵬 劉長龍

摘要：本文通過建立標準的平衡利庫權值數據模型，并引入二分圖多重匹配算法，按照“先利庫、后采購”的原則，多層級開展煤礦物資平衡利庫工作。該平衡利庫功能動態通盤考慮利庫優先級、已利庫數量、剩余數量等信息，自動推薦最優利庫方案，提高利庫的匹配程度，從而實現的全過程平衡利庫。

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? 平衡利庫功能實現

基于二分圖多重匹配算法的平衡利庫功能根據物資分類確定利庫范圍以及根據運輸成本確定利庫權重等因素，確定可利庫匹配關系的邊權矩陣基礎數據。界定合理的利庫物資范圍，制定利庫地域優選級別和原則，實現二分圖多重匹配算法，將單一數量滿足匹配改造成累計數匹配，通盤考慮優先級、已占用數量、剩余數量等信息，并且自動推薦最優利庫方案，提高利庫的匹配程度?；贏BAP語言開發設計平衡利庫功能以及界面，能夠根據用戶要求動態設置利庫級別以及利庫物資范圍，在操作上實現一鍵執行利庫功能，提高界面操作便捷性。系統實現界面如圖4所示。

5? 結語

基于二分圖多重匹配算法的平衡利庫功能實現平衡利庫按最優方式自動匹配物資需求計劃與可利庫物資的關系，根據煤碳公司要求實現多級智能利庫，極大提高利庫的匹配程度，減少人工利庫的差錯。

由于能夠自動實現物資需求計劃與可利庫物資之間的多對多的多重匹配，充分利用煤碳公司庫存積壓物資，能夠提升現有積壓庫存物資利用率。優化現有平衡利庫功能以及利庫流程，實現一鍵式利庫，同時實現可視化平衡利庫結果以及自動進行平衡利庫調撥。

參考文獻：

[1]方泉，康永，董子玉.基于ERP的電力物資平衡利庫系統[J].計算機系統應用，2014（23）：70-73.

[2]孫波.淺談物資管理在現代企業管理中重要作用[J].煤礦現代化，2008（2）：65-66.

[3]王譽霖.加強物資管理 提高經濟效益[J].核經濟研究，1997（02）.