基于線性規(guī)劃模型的物流運(yùn)輸調(diào)度問(wèn)題研究

安立軍，劉 進(jìn)，郝建林,2

（1.承德石油高等?？茖W(xué)校，河北 承德 067000；2.河北大學(xué) 管理學(xué)院，河北 保定 071000）

1 引言

物流運(yùn)輸調(diào)度問(wèn)題是指物流企業(yè)在一定數(shù)量車(chē)輛的情況下，通過(guò)靜態(tài)或動(dòng)態(tài)的方法求解滿足客戶需求的車(chē)輛調(diào)度問(wèn)題。在物流產(chǎn)業(yè)發(fā)展初期，由于物流企業(yè)的規(guī)模較小、管理方式落后以及經(jīng)驗(yàn)缺乏等原因，導(dǎo)致物流運(yùn)輸?shù)恼{(diào)度成本偏高，從而抑制了物流運(yùn)輸調(diào)度的發(fā)展，也導(dǎo)致客戶滿意度普遍偏低?，F(xiàn)代物流產(chǎn)業(yè)的發(fā)展，采用先進(jìn)的運(yùn)輸技術(shù)和高效的管理方法，能夠?qū)崟r(shí)根據(jù)客戶的需求來(lái)制定相應(yīng)的物流運(yùn)輸調(diào)度方案。因此，物流運(yùn)輸調(diào)度是降低物流企業(yè)成本、提高其運(yùn)行效率的有效方法。

基于此，本文將現(xiàn)代化無(wú)線通訊技術(shù)和GPS技術(shù)相結(jié)合，運(yùn)用動(dòng)態(tài)的線性規(guī)劃模型，建立現(xiàn)代化物流運(yùn)輸調(diào)度管理系統(tǒng)，利用匈牙利算法求解物流運(yùn)輸中的調(diào)度問(wèn)題，并運(yùn)用實(shí)例來(lái)分析這種算法的有效性。

2 線性規(guī)劃理論

線性規(guī)劃問(wèn)題（LP）是指在一定的人力、物力、財(cái)力等的條件下，設(shè)計(jì)一種運(yùn)輸方案，以達(dá)到某個(gè)目標(biāo)（如成本最小化）。用數(shù)學(xué)語(yǔ)言描述為：求一個(gè)線性函數(shù)在一組線性的等式或不等式條件約束情況下的最小值或最大值問(wèn)題。由于線性規(guī)劃問(wèn)題可采用對(duì)偶方法求解，因此可將最小值問(wèn)題轉(zhuǎn)化為最大值問(wèn)題。本文以最大值為例，規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式是：

改寫(xiě)成累加的形式，具體如下所示：

其中c1x1+c2x2+…+cnxn為目標(biāo)函數(shù)；x1,x2,…,xn分別代表n種不同的資源，也就是求解變量，其值均不能為負(fù)值；c1,c2,…,cn是價(jià)值系數(shù)向量，由aij組成的矩陣為約束矩陣，向量bi表示資源的限制，標(biāo)準(zhǔn)形式的定義規(guī)定等式右邊的bi≥0，否則要進(jìn)行相應(yīng)的轉(zhuǎn)化才能成為線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型。

線性規(guī)劃問(wèn)題解法有很多種，可采用坐標(biāo)軸畫(huà)圖、分析可行域和可行解得到。但由于物流調(diào)度的約束條件太多，導(dǎo)致這種方法并不可行。此外，單純形法也不適合求解約束條件過(guò)多的調(diào)度問(wèn)題。因此，本文采用匈牙利方法來(lái)求解此類問(wèn)題。

3 物流運(yùn)輸調(diào)度的數(shù)學(xué)模型

物流運(yùn)輸調(diào)度問(wèn)題是一種特殊的運(yùn)輸問(wèn)題，調(diào)度問(wèn)題的約束條件比一般的物流運(yùn)輸問(wèn)題多，且更需要結(jié)合實(shí)際，導(dǎo)致其復(fù)雜程度也遠(yuǎn)大于運(yùn)輸問(wèn)題。物流調(diào)度的對(duì)象一般是運(yùn)輸車(chē)輛，且調(diào)度問(wèn)題涉及的行程也較長(zhǎng)，因此需要選擇最佳的調(diào)度路徑。

在物流運(yùn)輸調(diào)度時(shí)，由于車(chē)輛選擇具有較強(qiáng)的隨機(jī)性，導(dǎo)致很難預(yù)測(cè)下一時(shí)刻需求的車(chē)輛數(shù)量、車(chē)輛類型以及需求所在地點(diǎn)。因此，物流運(yùn)輸調(diào)度需要采用動(dòng)態(tài)線性規(guī)劃的方法，將調(diào)度問(wèn)題按時(shí)間分為若干個(gè)階段，每個(gè)階段需要做出相應(yīng)的決策，最終實(shí)現(xiàn)最優(yōu)的調(diào)度結(jié)果。在車(chē)輛的調(diào)度問(wèn)題中，本文將車(chē)輛分為大（L）、中（M）、?。⊿）三種類型，在每一個(gè)時(shí)間段t內(nèi)，根據(jù)客戶需求對(duì)車(chē)輛進(jìn)行一次規(guī)劃，得出最佳的調(diào)度方案。為了簡(jiǎn)化物流運(yùn)輸調(diào)度問(wèn)題，需要在每個(gè)階段的前期對(duì)車(chē)輛使用情況進(jìn)行檢查，根據(jù)車(chē)輛調(diào)度的約束條件，排除一些無(wú)法完成任務(wù)的車(chē)輛，對(duì)剩余的車(chē)輛進(jìn)行調(diào)度處理，將任務(wù)的運(yùn)輸調(diào)度成本降到最低。

假定物流運(yùn)輸中心共有n輛車(chē)輛，每輛車(chē)每公里的運(yùn)輸費(fèi)用為ci（i=1,2,…,n），運(yùn)輸費(fèi)用包括燃油費(fèi)、人工費(fèi)及其他相關(guān)費(fèi)用。在某個(gè)時(shí)間段t內(nèi)，共有m項(xiàng)運(yùn)輸調(diào)度的請(qǐng)求任務(wù)，任務(wù)地點(diǎn)的坐標(biāo)分別為（xi,yi），i=1,2,…,m。此時(shí)，共有l(wèi)輛可供調(diào)度的車(chē)輛，其中l(wèi)≥m。根據(jù)GPS定位系統(tǒng)可知，每輛可供調(diào)度車(chē)輛的地理位置為（Xi,Yi），i=1,2,…,l。可采用大中小三種車(chē)型進(jìn)行調(diào)度，若可以派遣任意一種沒(méi)有任務(wù)的車(chē)型時(shí)，可采用小車(chē)進(jìn)行調(diào)度，若無(wú)小車(chē)，則中型、大型車(chē)按順序依次替補(bǔ)；若申請(qǐng)調(diào)度中型車(chē)時(shí)，則可派遣中型車(chē)，當(dāng)無(wú)中型車(chē)時(shí)，則采用大型車(chē)來(lái)替補(bǔ)；若申請(qǐng)調(diào)度大型車(chē)時(shí)，則只能派遣大型車(chē)。

根據(jù)上述假定，可知在t時(shí)間段內(nèi)，物流運(yùn)輸調(diào)度模型的調(diào)度總成本z表達(dá)式如下：

其中cj表示第j輛車(chē)每公里的運(yùn)輸費(fèi)用；dij表示第j個(gè)車(chē)輛到第i個(gè)客戶的距離；xij為車(chē)輛的調(diào)度情況，其值可表示如下：

由于每輛調(diào)度車(chē)輛僅能完成一項(xiàng)請(qǐng)求，則該運(yùn)輸調(diào)度約束條件可表示為：

由于每項(xiàng)請(qǐng)求有且僅有一輛車(chē)輛完成，則該運(yùn)輸調(diào)度約束條件可表示為：

根據(jù)式（4）、（5）、（6），可將物流調(diào)度問(wèn)題改寫(xiě)為：

其中x為解矩陣，c為效率矩陣，A為約束矩陣，具體可表示如下：

匈牙利算法的基本思想是設(shè)法調(diào)整矩陣c的元素，使得新的效率矩陣c′的每一行和每一列至少含有一個(gè)零元素，但是不能存在負(fù)數(shù)。當(dāng)然，在線性變化的過(guò)程中，要求新效率矩陣與原效率矩陣是等效的，即所表達(dá)的調(diào)度問(wèn)題存在相同的可行解。若存在這樣的新效率矩陣，則對(duì)應(yīng)的c'的不同行不同列的零元素，在解矩陣中的相應(yīng)位置的元素為1，其余的元素全部為零，那么就得到了調(diào)度的最優(yōu)解，也就是總運(yùn)輸成本最低下的調(diào)度方案。新的效率矩陣與原效率矩陣所表達(dá)的目標(biāo)函數(shù)值，只相差一個(gè)常數(shù)，表明新問(wèn)題與原問(wèn)題具有相同的解。

當(dāng)請(qǐng)求數(shù)量與調(diào)度車(chē)輛不相等時(shí)，可采用虛擬調(diào)度請(qǐng)求，將其完成的成本設(shè)為0，即在效率矩陣下面添上k行，其中k為請(qǐng)求數(shù)量與調(diào)度車(chē)輛兩者之間的差值，再用匈牙利算法來(lái)求解調(diào)度問(wèn)題。

4 案例分析

某物流企業(yè)在t時(shí)刻共有6個(gè)調(diào)度請(qǐng)求，此時(shí)共有12輛可供調(diào)度的汽車(chē)，假定它們均能在任務(wù)要求的時(shí)間內(nèi)到達(dá)任務(wù)的指定地點(diǎn)。在這12輛汽車(chē)中，大中小三類車(chē)輛均有，其中大、中、小型車(chē)輛每公里的運(yùn)行成本分別為4元、3元和2元。

表1 物流運(yùn)輸調(diào)度車(chē)輛與任務(wù)地點(diǎn)的運(yùn)輸距離

根據(jù)GPS、GIS和GSM技術(shù)，可以準(zhǔn)確的測(cè)定車(chē)輛與任務(wù)地點(diǎn)的距離，具體的調(diào)度車(chē)輛與任務(wù)地點(diǎn)之間的距離見(jiàn)表1。

根據(jù)調(diào)度車(chē)輛的運(yùn)輸距離以及各個(gè)車(chē)輛的運(yùn)輸費(fèi)用和任務(wù)要求的車(chē)輛，可得物流運(yùn)輸調(diào)度成本，見(jiàn)表2。

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

根據(jù)表2可知，效率矩陣可表示如下：由于可供調(diào)度的車(chē)輛與任務(wù)請(qǐng)求的數(shù)量不等，為了滿足車(chē)輛調(diào)度與請(qǐng)求數(shù)量相等這一條件，本文將虛構(gòu)六個(gè)請(qǐng)求，則可得到新的效率矩陣，具體如下：

首先，調(diào)整效率矩陣，使其每一行和每一列都至少含有一個(gè)零元素，具體的做法可仿照線性規(guī)劃中的線性變化方法，從c的每一行減去該行的最小元素，可得如下的新效率矩陣：

在矩陣c'中，選出不同行不同列的12個(gè)零元素，具體的做法是從0元素最少的行開(kāi)始標(biāo)記，直到標(biāo)出所有的零元素。依照上述的算法，可得該物流運(yùn)輸調(diào)度問(wèn)題的最優(yōu)解矩陣為：

根據(jù)最優(yōu)解矩陣可知：調(diào)度車(chē)輛8完成請(qǐng)求任務(wù)1，調(diào)度車(chē)輛3完成請(qǐng)求任務(wù)2，調(diào)度車(chē)輛10完成請(qǐng)求任務(wù)3，調(diào)度車(chē)輛6完成請(qǐng)求任務(wù)4，調(diào)度車(chē)輛11完成請(qǐng)求任務(wù)5，調(diào)度車(chē)輛9完成請(qǐng)求任務(wù)6。根據(jù)匈牙利算法可知，最優(yōu)的調(diào)度成本為：

將匈牙利算法得出的結(jié)果與表2對(duì)比可知，該調(diào)度方案是最佳方法，是所有調(diào)度中成本最低的，通過(guò)這一處理可以非常迅速地獲得最優(yōu)方案，避免了復(fù)雜的矩陣乘法運(yùn)算，提高了物流運(yùn)輸調(diào)度方案的決策效率，非常適合高階的矩陣運(yùn)算。

5 結(jié)語(yǔ)

線性規(guī)劃理論在運(yùn)輸問(wèn)題中有著廣泛的用途，本文建立了物流運(yùn)輸?shù)恼{(diào)度系統(tǒng)模型，該系統(tǒng)實(shí)時(shí)監(jiān)控物流企業(yè)的車(chē)輛，并與車(chē)輛進(jìn)行實(shí)時(shí)通訊，及時(shí)響應(yīng)任意時(shí)間每一個(gè)客戶的需求，及時(shí)處理物流運(yùn)輸中的突發(fā)事件和臨時(shí)性請(qǐng)求，完善物流企業(yè)的運(yùn)輸調(diào)度管理。

[1]覃運(yùn)梅.多源點(diǎn)物流配送車(chē)輛調(diào)度模型探討[J].物流科技,2010,(9):32-35.

[2]李惠珠,宋海清.基于GIS的物流配送車(chē)輛調(diào)度實(shí)現(xiàn)與應(yīng)用[J].長(zhǎng)春師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2011,30(2):20-24.

[3]曹克官,陳峰.多車(chē)輛直運(yùn)越庫(kù)調(diào)度的建模與啟發(fā)式算法[J].上海交通大學(xué)學(xué)報(bào),2009,43(9):1403-1406,1416.

[4]裴志松.一種新型物流調(diào)度算法的優(yōu)化研究[J].長(zhǎng)春工程學(xué)院學(xué)報(bào)(自然科學(xué)版),2011,12(2):117-119.

[5]張建中,許紹吉.線性規(guī)劃[M].北京:科學(xué)技術(shù)出版社,1997.

[6]張潛.物流配送路徑優(yōu)化調(diào)度建模與實(shí)務(wù)[M].北京:中國(guó)物資出版社,2006.