張國(guó)輝，黨世杰

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

?

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

張國(guó)輝，黨世杰

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

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

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

1　引言

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

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

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

2　物流運(yùn)輸問題描述

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

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

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

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

約束條件為：

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

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

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

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

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

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

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

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

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

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

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

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

4　案例分析

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

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

表1　不同車輛從配送中心到配送地點(diǎn)的行駛距離

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

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

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

然后開始從零元素個(gè)數(shù)最少的地方標(biāo)記，當(dāng)某行（列）的零元素大于1個(gè)時(shí)，標(biāo)記一個(gè)零元素后將其他的零元素劃去，直至所有零元素被標(biāo)出。若獨(dú)立零元素有等于方陣的秩時(shí)即表示此為最優(yōu)調(diào)度方案。否則按匈牙利算法進(jìn)行調(diào)整，直至得到成本最低的調(diào)度方案，本文所使用的匈牙利算法通過MATLAB程序?qū)崿F(xiàn)，通過運(yù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)度方案計(jì)算出該物流配送中心完成配送任務(wù)的最低成本為：Z=123.5+132+174+125+130+145+84.5=914元。將結(jié)果和物流運(yùn)輸調(diào)度成本對(duì)比可知，使用匈牙利算法求解物流運(yùn)輸調(diào)度問題得到了最優(yōu)解，使調(diào)度成本最低，有利于在物流運(yùn)輸調(diào)度問題中快速求解，驗(yàn)證了匈牙利算法在物流運(yùn)輸調(diào)度問題中的適用性。

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

5　結(jié)束語

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

.

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

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

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

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

［5］《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(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

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

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