基于匈牙利算法的物流運輸調(diào)度問題研究

張國輝，黨世杰

（鄭州航空工業(yè)管理學(xué)院　管理科學(xué)與工程學(xué)院，河南　鄭州　450015）

?

基于匈牙利算法的物流運輸調(diào)度問題研究

張國輝，黨世杰

（鄭州航空工業(yè)管理學(xué)院管理科學(xué)與工程學(xué)院，河南鄭州450015）

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

匈牙利算法；物流運輸調(diào)度；MATLAB

1　引言

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

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

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

2　物流運輸問題描述

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

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

根據(jù)以上條件，可知在該時段內(nèi)，物流運輸調(diào)度模型的配送總成本為Z，則目標(biāo)函數(shù)為：

其中xij為相應(yīng)車輛的調(diào)度情況，可表示為：

約束條件為：

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

3　匈牙利算法求解物流運輸調(diào)度問題

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

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

（1）當(dāng)調(diào)度車輛和配送任務(wù)相同時，可以直接根據(jù)模型進行求解。

（2）調(diào)度車輛大于配送任務(wù)時，可以設(shè)置虛擬配送任務(wù)，從而使矩陣行列相同。由于實際上不執(zhí)行該調(diào)度，故設(shè)置該配送成本為零。

（3）當(dāng)調(diào)度車輛小于配送任務(wù)時，此時需要考慮增加虛擬車輛來完成任務(wù)，這時的運價可以根據(jù)物流企業(yè)與客戶之間的協(xié)議中規(guī)定的拖期產(chǎn)生的費用進行設(shè)置，以便求得最小損失方案。

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

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

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

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

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

4　案例分析

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

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

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

表2　物流運輸調(diào)度成本

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

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

然后開始從零元素個數(shù)最少的地方標(biāo)記，當(dāng)某行（列）的零元素大于1個時，標(biāo)記一個零元素后將其他的零元素劃去，直至所有零元素被標(biāo)出。若獨立零元素有等于方陣的秩時即表示此為最優(yōu)調(diào)度方案。否則按匈牙利算法進行調(diào)整，直至得到成本最低的調(diào)度方案，本文所使用的匈牙利算法通過MATLAB程序?qū)崿F(xiàn)，通過運行MATLAB程序解得案例中的最優(yōu)調(diào)度矩陣X*，如圖1所示。

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

圖1　最優(yōu)調(diào)度矩陣X*

5　結(jié)束語

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

.

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

［2］黃戈文，蔡延光，湯雅連.基于云計算的煙草物流運輸調(diào)度系統(tǒng)設(shè)計與實現(xiàn)［J］.工業(yè)控制計算機，2015，（10）：114-116.

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

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

［5］《運籌學(xué)》教材編寫組.運籌學(xué)［M］.北京：清華大學(xué)出版社，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

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

張國輝（1980-），男，河南新鄉(xiāng)人，副教授，博士，主要研究方向：生產(chǎn)管理、工業(yè)工程。