基于匈牙利算法的物流運輸調度問題研究

張國輝，黨世杰

（鄭州航空工業管理學院　管理科學與工程學院，河南　鄭州　450015）

?

基于匈牙利算法的物流運輸調度問題研究

張國輝，黨世杰

（鄭州航空工業管理學院管理科學與工程學院，河南鄭州450015）

物流運輸調度問題是一類求解難度較高的運輸問題，在制定合理的調度方案時，實現物流運輸成本最低以及物流企業利潤最大是調度方案決策者迫切需要解決的問題。分析了物流運輸調度問題的特點，建立了以物流運輸成本最小為目標函數的物流運輸調度模型，并使用匈牙利算法求解該模型，得到物流運輸成本最低的調度方案，驗證了模型的可行性和算法的有效性。

匈牙利算法；物流運輸調度；MATLAB

1　引言

物流運輸成本不僅影響企業服務水平，還決定企業運作成本。據了解，發達國家的物流成本平均占成品最終成本的10%-15%，而我國的此項比重高達30%-40%。因此，降低物流運輸成本，可以使物流成本的組成更加合理、促進產業優化、提高企業競爭力，實現企業效益最大化。

物流運輸調度問題一般需要考慮運輸車輛和運輸工人等成本，比一般的運輸問題更加復雜，更加貼近實際情況。因此，有不少學者對其進行了研究，而且也取得了一些成果。安立軍等［1］使用線性規劃理論研究現代化物流運輸調度問題，得到了物流調度最優方案，但是沒有考慮到運輸的人工成本。黃戈文等［2］研發了基于云計算的煙草物流運輸調度問題，通過智能算法求解并優化配送線路。師凱等［3］將蟻群算法應用于一般運輸調度問題中，并分析了其今后的走向。于煥英等［4］分析車輛需求特性和車輛特征，建立了總油耗量最小為目標的車輛調度模型并使用匈牙利算法進行求解。

本文分析了某物流企業調度中心的物流運輸調度問題的特點，建立了以物流運輸成本最小為目標函數的物流運輸調度模型。然后利用匈牙利算法進行求解，得到了物流運輸成本最低的調度方案，提高物流中心調度效率，減少物流企業在運輸中因車輛調度不合理所造成的浪費，從而提升了企業效益。

2　物流運輸問題描述

在物流運輸調度問題中，物流企業需要對運輸車輛實時調度，然而運輸車輛具有較強的隨機性，造成物流配送中心對運輸車輛的數量和類型均無法精確預測并及時給出調度方案。動態規劃方法是現代企業高效管理的一種重要決策方法，物流企業的調度是連續進行的，將這個連續的過程根據執行配送的調度方案劃分為若干個相互聯系的階段，在每個階段執行一個調度方案，這些相互聯系的調度過程可以反映整個物流運輸調度決策。整個決策過程的目標是達到物流運輸成本最小，因此使用動態規劃的方式更加適合物流運輸調度，將動態規劃方法應用于物流運輸問題，將物流調度問題分為不同的階段，然后獨立處理不同階段，最終得出使整個運輸成本最低的調度方案。

假設物流運輸調度中心坐標為（X0，Y0），該中心有m輛車可供調用，每輛車每公里的綜合運輸費用為C1，由于車輛種類不同，不同類型車輛運送的人工成本也不相同，設該成本為C2，在某個時間段t內，物流運輸調度中心需要向n個地區分配車輛以完成相應的調度任務，這些地區的坐標分別為（Xi，Yi），其中i=1，2，…，n。

根據以上條件，可知在該時段內，物流運輸調度模型的配送總成本為Z，則目標函數為：

其中xij為相應車輛的調度情況，可表示為：

約束條件為：

約束條件（3）、（4）代表在某個時間段內一輛車只能完成一個配送任務，同時一個配送任務只能由一輛車完成配送。

3　匈牙利算法求解物流運輸調度問題

匈牙利算法［4］是基于匈牙利數學家康尼格的關于矩陣中獨立零元素定理的一種算法。這種算法的基本思想是從矩陣C的某行（列）減去一個常數k，得到一個新的矩陣C'，其中變化前后的矩陣系數均不為負。由于矩陣的這種變化并不影響模型的約束方程組，因此通過線性變化后仍然能保證兩個矩陣具有相同的最優解。對于這種情況的矩陣下的數學模型來說，若能在矩陣中找到n個位于不同行和不同列的零元素，就能使總費用最低，此時對應的配送方案也是最優的。在匈牙利算法中，模型中的矩陣有多少個零元素并不重要，關鍵在于在不同行和不同列的獨立零元素是否分布合理。

在利用匈牙利算法求解物流運輸調度問題時，在某一調度時間段內，有以下幾種情況：

（1）當調度車輛和配送任務相同時，可以直接根據模型進行求解。

（2）調度車輛大于配送任務時，可以設置虛擬配送任務，從而使矩陣行列相同。由于實際上不執行該調度，故設置該配送成本為零。

（3）當調度車輛小于配送任務時，此時需要考慮增加虛擬車輛來完成任務，這時的運價可以根據物流企業與客戶之間的協議中規定的拖期產生的費用進行設置，以便求得最小損失方案。

通過以上變換后即可得到滿足調度車輛m和配送任務n相同的矩陣，可知該矩陣為n×n的方陣，使用匈牙利算法求解物流運輸調度問題的流程如下：

Step 1：分別從該方陣的各行元素減去本行最小元素。

Step 2：分別從該方陣的各列元素減去本列最小元素。

Step 3：在變換后的方陣中找出獨立零元素，若獨立零元素個數為該方陣的行數n，則得到最優解，算法結束；若獨立零元素少于該方陣的行數n，則做能覆蓋所有零元素的最小直線數，然后轉Step 4。

Step 4：從方陣未被直線覆蓋的元素中找到一個最小元素，然后令所有未被覆蓋直線的元素都減去該最小元素，這樣未被覆蓋的元素將出現零元素，在直線相交處元素會出現負數，然后在該元素的行或列上加上最小元素以抵消負數，最后轉到Step 3進行判斷，直至得到最優解。

4　案例分析

本文以S物流公司的調度中心為例，建立了物流運輸調度問題模型。該物流公司擁有A、B、C、D四種運輸車型，每種車型均有3輛。四種車輛運送貨物的每公里運價分別為5元、5.5元、6元、6.5元，四種車型的運輸者的一次配送成本分別為50元、55元、60元、65元。該物流調度中心在時間t內需要向7個地點執行配送任務。由于車輛大小不同，因此使用不同車輛配送同一配送任務時的行駛距離可能也不同，根據該物流企業所搜集的歷史配送數據，得到使用配送車輛和配送任務地點的距離見表1，其中“-”表示該種車型無法完成該配送任務，A1表示A車型的第一輛車，以此類推。

考慮到車輛運輸成本和運輸者成本，得到單車單次運輸成本為：C=C1·Dis+C2，結合配送距離可以得到運輸調度成本，見表2，不能配送的運輸成本為非常大的數M。

表1　不同車輛從配送中心到配送地點的行駛距離

表2　物流運輸調度成本

由于調度車輛數量大于配送任務，為了使用匈牙利算法進行求解，故添加虛擬配送任務，在該案例中增加5個虛擬配送任務得到調度矩陣C。

首先需要變換矩陣C，由于矩陣C中每列均存在零元素，故對每行元素作減去本行中的最小元素以保證每行均出現零元素，經過操作后的矩陣為C'。

然后開始從零元素個數最少的地方標記，當某行（列）的零元素大于1個時，標記一個零元素后將其他的零元素劃去，直至所有零元素被標出。若獨立零元素有等于方陣的秩時即表示此為最優調度方案。否則按匈牙利算法進行調整，直至得到成本最低的調度方案，本文所使用的匈牙利算法通過MATLAB程序實現，通過運行MATLAB程序解得案例中的最優調度矩陣X*，如圖1所示。

根據最優調度矩陣X*可知：車輛D2執行配送任務1，車輛B1執行配送任務2，車輛C3執行配送任務3，車輛A1執行配送任務4，車輛D1執行配送任務5，車輛A3執行配送任務6，車輛D3執行配送任務7，其余車輛仍處于空閑狀態。最后根據該調度方案計算出該物流配送中心完成配送任務的最低成本為：Z=123.5+132+174+125+130+145+84.5=914元。將結果和物流運輸調度成本對比可知，使用匈牙利算法求解物流運輸調度問題得到了最優解，使調度成本最低，有利于在物流運輸調度問題中快速求解，驗證了匈牙利算法在物流運輸調度問題中的適用性。

圖1　最優調度矩陣X*

5　結束語

減少物流配送環節成本對降低物流企業整體成本具有不可低估的作用，本文考慮了物流運輸過程中的不同種類成本，建立了物流運輸調度問題模型。然后介紹了匈牙利算法，該算法可以減少矩陣運算的復雜度，提高運算速度。最后以某物流企業的配送中心為例，使用基于MATLAB的匈牙利算法求得物流運輸調度問題成本最低的方案，驗證了使用匈牙利算法求解物流運輸調度問題的可行性。

.

［1］安立軍，劉進，郝建林.基于線性規劃模型的物流運輸調度問題研究［J］.物流技術，2014，（10）：195-197.

［2］黃戈文，蔡延光，湯雅連.基于云計算的煙草物流運輸調度系統設計與實現［J］.工業控制計算機，2015，（10）：114-116.

［3］師凱，蔡延光，鄒谷山，王濤.運輸調度問題的蟻群算法研究［J］.計算技術與自動化，2005，（3）：42-44.

［4］于煥英，孫晚華，何峣.基于匈牙利算法的多車型配送問題［J］.物流技術，2010，29（6）：74-75.

［5］《運籌學》教材編寫組.運籌學［M］.北京：清華大學出版社，2005.

Study on Logistics Transportation Scheduling Problem Based on Hungarian Algorithm

Zhang Guohui， Dang Shijie
（School of Management Science Engineering， Zhengzhou University of Aeronautics， Zhengzhou 450015， China）

In this paper， we analyzed the characteristics of the logistics transportation scheduling problem， built the logisticstransportation scheduling model with cost minimization as the objective function， and at the end， used the Hungarian algorithm to solve it toobtain the scheduling plan with the minimal logistics transportation cost， thus demonstrating the feasibility and validity of the model.

Hungarian algorithm； logistics transportation scheduling； MATLAB

F252；F224

A

1005-152X（2016）01-0117-03

10.3969/j.issn.1005-152X.2016.01.030

2015-12-18

國家自然科學基金（61203179）；河南省高校科技創新人才支持計劃資助（14HASTIT006）；河南省高等學校青年骨干教師資助計劃（2014GGJS-105，2014GGJS-197）；航空科學基金（2014ZG55016）

張國輝（1980-），男，河南新鄉人，副教授，博士，主要研究方向：生產管理、工業工程。