基于匈牙利算法的物資運(yùn)輸?shù)能囕v分派問題研究

摘要：針對(duì)物資運(yùn)輸?shù)能囕v分派問題本文利用匈牙利算法，從使得運(yùn)輸總費(fèi)用最小的角度出發(fā)，構(gòu)建了運(yùn)輸車輛模型及車輛分派模型，以求得最佳的車輛運(yùn)輸分派方案。

關(guān)鍵詞：匈牙利算法；運(yùn)輸車輛分派；優(yōu)化

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-864X（2016）03-0000-01

一、武警部隊(duì)物資運(yùn)輸車輛分派問題的由來

運(yùn)輸武警部隊(duì)后勤部的車輛運(yùn)輸成本是年度財(cái)政計(jì)劃的重要部分，其合理的開支也是關(guān)系部隊(duì)科學(xué)發(fā)展、高效轉(zhuǎn)型的關(guān)鍵因素。然而在實(shí)際的運(yùn)輸過程中，武警部隊(duì)運(yùn)輸成本居高不低，這除了國內(nèi)形勢(shì)日趨復(fù)雜、運(yùn)輸頻率和數(shù)量增加的原因外，還與指揮人員合理安排運(yùn)輸車輛，采取最優(yōu)的運(yùn)輸分配方案息息相關(guān)。要想降低車輛運(yùn)輸?shù)幕境杀颈仨殢倪\(yùn)輸方式的選擇、運(yùn)輸路線的規(guī)劃、車輛任務(wù)的分派三個(gè)方面考慮。

二、分配問題及匈牙利法的相關(guān)理論研究

運(yùn)籌學(xué)中的分配問題，或稱指派問題（AssignmentProblem），是一種特殊的整數(shù)規(guī)劃問題，在許多應(yīng)用領(lǐng)域中會(huì)經(jīng)常遇到，例如：有N項(xiàng)任務(wù)，分配給N個(gè)人完成，并指定每人完成其中的一項(xiàng)，每項(xiàng)任務(wù)只交給一個(gè)人去完成，應(yīng)如何分配，使得費(fèi)用最低。這是經(jīng)典分配問題的一個(gè)實(shí)例，問題中的任務(wù)可能是任何類型的活動(dòng)，人可能是任何類型的資源，費(fèi)用可能是任何類型的效能。

分配問題最簡單的處理方法，就是進(jìn)行所有可能的分配，共有N 的全排列個(gè)（N?。┓峙浞桨?，再從中選出最優(yōu)解，但當(dāng)N較大時(shí)，分配數(shù)將產(chǎn)生組合爆炸，當(dāng)今的高速計(jì)算機(jī)也都無法處理。分配問題也是個(gè)線型規(guī)劃問題，若用正規(guī)的單純形法，或借助于運(yùn)輸問題特點(diǎn)的一些特殊方法，也可以用來解決這個(gè)問題，但效果不好。

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

三、武警部隊(duì)物資運(yùn)輸路線的選擇

武警部隊(duì)物資運(yùn)輸路線的選擇，主要是選擇出發(fā)城市到任務(wù)城市的最短路徑。不同運(yùn)輸方式的路線選擇也不同。最短路徑的度量單位可能是時(shí)間最短、距離最短或費(fèi)用最小等。運(yùn)輸路線選擇是將運(yùn)輸模式和路線選擇結(jié)合在一起，因?yàn)槁肪€選擇的可能性在很大程度上取決于運(yùn)輸模式。一般而言路線選擇問題可以分為以下幾類：（1）中間點(diǎn)相同，起訖點(diǎn)不同；（2）中間點(diǎn)不同，但起訖點(diǎn)相同；（3）多個(gè)起點(diǎn)，多個(gè)終點(diǎn)，沒有中間點(diǎn)；（4）多個(gè)起點(diǎn)，多個(gè)終點(diǎn)，有中間點(diǎn)或轉(zhuǎn)運(yùn)點(diǎn)。

假設(shè)某軍工廠從生產(chǎn)站點(diǎn)A運(yùn)輸防爆武器裝備器材，服務(wù)三個(gè)不同地點(diǎn)的軍需地B、C、D。

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

現(xiàn)求解最佳的運(yùn)輸路線。

求解步驟如下：軍需地B距離A最近，故先選軍需地B；軍需地C距離B最近，故選擇C；只剩下軍需地D沒選，故選擇D，然后返回軍需地A，形成一條回路：A—B—C—D—A?？偫锍虨?23公里。需要說明的是，由于軍需地D點(diǎn)與最后返回的軍需地A點(diǎn)實(shí)際上并非最優(yōu)選擇，所有這種方法球的解也并不一定是最優(yōu)解，只能是近似最優(yōu)解。

關(guān)于一輛車一條路線上的任務(wù)安排，相當(dāng)比較容易。而對(duì)于若干輛車服務(wù)于若干個(gè)任務(wù)的齊次運(yùn)輸任務(wù)的分派，則需要借助于運(yùn)輸模型的構(gòu)建和求解。

四.基于匈牙利算法的最優(yōu)方案求解

假定一個(gè)軍工廠公司有兩輛（A和B）載重量為5噸和三輛（C，D，E）載重量為lO噸的卡車，某天有5項(xiàng)防爆武器裝備器材運(yùn)輸任務(wù)，不同的車輛完成任務(wù)的費(fèi)用關(guān)系如表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）。

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

（1）將表1構(gòu)成矩陣形式，找出每一行中最小的費(fèi)用元素，并用每一行減去對(duì)應(yīng)的最小元素，構(gòu)成每行都出現(xiàn)0元素的新矩陣。然后找出新矩陣中每一列的最小元素（包括0），用每一列將去該列對(duì)應(yīng)的最小元素，這樣便構(gòu)成了每一行每一列都有0元素的新矩陣。

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

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

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

對(duì)于擁有較多軍用運(yùn)輸車輛、任務(wù)較多的情況，必須合理安排好每一輛車的任務(wù)分派。構(gòu)建好齊次運(yùn)輸?shù)馁M(fèi)用計(jì)算模型，可以較為準(zhǔn)確、快速地求出最優(yōu)解，使得單次運(yùn)輸總成本最低。

參考文獻(xiàn)：

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

[2] 范鳴玉，張瑩.最優(yōu)化技術(shù)基礎(chǔ)[M].北京：清華大學(xué)出版社，1982.

[3] 郭耀煌.運(yùn)籌學(xué)與工程系統(tǒng)分析[M].北京：中國建筑工業(yè)出版社，1986.

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