基于匈牙利算法的物資運輸的車輛分派問題研究

摘要：針對物資運輸的車輛分派問題本文利用匈牙利算法，從使得運輸總費用最小的角度出發，構建了運輸車輛模型及車輛分派模型，以求得最佳的車輛運輸分派方案。

關鍵詞：匈牙利算法；運輸車輛分派；優化

中圖分類號：TP18 文獻標識碼：A 文章編號：1671-864X（2016）03-0000-01

一、武警部隊物資運輸車輛分派問題的由來

運輸武警部隊后勤部的車輛運輸成本是年度財政計劃的重要部分，其合理的開支也是關系部隊科學發展、高效轉型的關鍵因素。然而在實際的運輸過程中，武警部隊運輸成本居高不低，這除了國內形勢日趨復雜、運輸頻率和數量增加的原因外，還與指揮人員合理安排運輸車輛，采取最優的運輸分配方案息息相關。要想降低車輛運輸的基本成本必須從運輸方式的選擇、運輸路線的規劃、車輛任務的分派三個方面考慮。

二、分配問題及匈牙利法的相關理論研究

運籌學中的分配問題，或稱指派問題（AssignmentProblem），是一種特殊的整數規劃問題，在許多應用領域中會經常遇到，例如：有N項任務，分配給N個人完成，并指定每人完成其中的一項，每項任務只交給一個人去完成，應如何分配，使得費用最低。這是經典分配問題的一個實例，問題中的任務可能是任何類型的活動，人可能是任何類型的資源，費用可能是任何類型的效能。

分配問題最簡單的處理方法，就是進行所有可能的分配，共有N 的全排列個（N！）分配方案，再從中選出最優解，但當N較大時，分配數將產生組合爆炸，當今的高速計算機也都無法處理。分配問題也是個線型規劃問題，若用正規的單純形法，或借助于運輸問題特點的一些特殊方法，也可以用來解決這個問題，但效果不好。

而一種稱為“匈牙利法”的分配算法，是目前被認為是用來解決分配問題的最有效算法，“運籌學”和“最優化技術”等專著，都將它作為標準的算法進行介紹。 “匈牙利法”的計算基礎和前提是：從效能矩陣的每一行（每一列）元素中分別減去（或加上）一個常數，使得每一行（每一列）里至少有一個0元素，得到新的效能矩陣，用它來取代原效能矩陣，將不改變分配問題的最優解。

三、武警部隊物資運輸路線的選擇

武警部隊物資運輸路線的選擇，主要是選擇出發城市到任務城市的最短路徑。不同運輸方式的路線選擇也不同。最短路徑的度量單位可能是時間最短、距離最短或費用最小等。運輸路線選擇是將運輸模式和路線選擇結合在一起，因為路線選擇的可能性在很大程度上取決于運輸模式。一般而言路線選擇問題可以分為以下幾類：（1）中間點相同，起訖點不同；（2）中間點不同，但起訖點相同；（3）多個起點，多個終點，沒有中間點；（4）多個起點，多個終點，有中間點或轉運點。

假設某軍工廠從生產站點A運輸防爆武器裝備器材，服務三個不同地點的軍需地B、C、D。

從站點生產A到各軍需地的距離為AB=22，AC=31，AD=45，BC=18，BD=27，CD=38。

現求解最佳的運輸路線。

求解步驟如下：軍需地B距離A最近，故先選軍需地B；軍需地C距離B最近，故選擇C；只剩下軍需地D沒選，故選擇D，然后返回軍需地A，形成一條回路：A—B—C—D—A。總里程為123公里。需要說明的是，由于軍需地D點與最后返回的軍需地A點實際上并非最優選擇，所有這種方法球的解也并不一定是最優解，只能是近似最優解。

關于一輛車一條路線上的任務安排，相當比較容易。而對于若干輛車服務于若干個任務的齊次運輸任務的分派，則需要借助于運輸模型的構建和求解。

四.基于匈牙利算法的最優方案求解

假定一個軍工廠公司有兩輛（A和B）載重量為5噸和三輛（C，D，E）載重量為lO噸的卡車，某天有5項防爆武器裝備器材運輸任務，不同的車輛完成任務的費用關系如表1所示。WA=（5，13，9，6，7），WB=（8，2，7，9，5），WC=（7，6，8，4，10）， WD=（9，7，10，3，6）， WE=（10，11，3，8，9）。

上述的軍用運輸車輛分派模型要求分派方案的總費用最小。可用匈牙利法求解，具體步驟如下：

（1）將表1構成矩陣形式，找出每一行中最小的費用元素，并用每一行減去對應的最小元素，構成每行都出現0元素的新矩陣。然后找出新矩陣中每一列的最小元素（包括0），用每一列將去該列對應的最小元素，這樣便構成了每一行每一列都有0元素的新矩陣。

（2）在新矩陣中，畫出能覆蓋所有0元素的最少直線（橫線或豎線，不含斜線）。如果直線的數目等于行或列的數目（n=5）便停止，得到最優解。如果直線數小于行或列的數目（n<5），則需進行第三步。本例新矩陣中，只需4條直線便可覆蓋所有0元素，故有待進一步求解。

（3）在畫完直線的新矩陣中，找出沒有被直線覆蓋的非0元素最小值（本例中最小非0元素為1），然后再沒有畫直線的各行上都減去這個非0元素，同時，再已畫直線的各列上加上這個非0最小元素，得到新的矩陣。

（4）此時，能覆蓋所有0元素的最少直線等于行或列數（n=5），得到了最優解，即最有車輛分派方案：第A輛車分派任務1，第B輛車分派任務2，第C輛車分派任務4，第D輛車分派任務5，第E輛車分派任務3。這種情況下，車輛任務分派總費用為20，為最優解。

對于擁有較多軍用運輸車輛、任務較多的情況，必須合理安排好每一輛車的任務分派。構建好齊次運輸的費用計算模型，可以較為準確、快速地求出最優解，使得單次運輸總成本最低。

參考文獻：

[1]徐小林.基于匈牙利算法的多車型車輛調度問題.火力與指揮控制，2009.2

[2] 范鳴玉，張瑩.最優化技術基礎[M].北京：清華大學出版社，1982.

[3] 郭耀煌.運籌學與工程系統分析[M].北京：中國建筑工業出版社，1986.

作者簡介：黎珂佚（1986.06-），武警警官學院管理系，講師，碩士，研究方向：武警管理學。