基于線性規劃模型的物流運輸調度問題研究

安立軍，劉 進，郝建林,2

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

1 引言

物流運輸調度問題是指物流企業在一定數量車輛的情況下，通過靜態或動態的方法求解滿足客戶需求的車輛調度問題。在物流產業發展初期，由于物流企業的規模較小、管理方式落后以及經驗缺乏等原因，導致物流運輸的調度成本偏高，從而抑制了物流運輸調度的發展，也導致客戶滿意度普遍偏低?，F代物流產業的發展，采用先進的運輸技術和高效的管理方法，能夠實時根據客戶的需求來制定相應的物流運輸調度方案。因此，物流運輸調度是降低物流企業成本、提高其運行效率的有效方法。

基于此，本文將現代化無線通訊技術和GPS技術相結合，運用動態的線性規劃模型，建立現代化物流運輸調度管理系統，利用匈牙利算法求解物流運輸中的調度問題，并運用實例來分析這種算法的有效性。

2 線性規劃理論

線性規劃問題（LP）是指在一定的人力、物力、財力等的條件下，設計一種運輸方案，以達到某個目標（如成本最小化）。用數學語言描述為：求一個線性函數在一組線性的等式或不等式條件約束情況下的最小值或最大值問題。由于線性規劃問題可采用對偶方法求解，因此可將最小值問題轉化為最大值問題。本文以最大值為例，規定線性規劃問題的標準形式是：

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

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

線性規劃問題解法有很多種，可采用坐標軸畫圖、分析可行域和可行解得到。但由于物流調度的約束條件太多，導致這種方法并不可行。此外，單純形法也不適合求解約束條件過多的調度問題。因此，本文采用匈牙利方法來求解此類問題。

3 物流運輸調度的數學模型

物流運輸調度問題是一種特殊的運輸問題，調度問題的約束條件比一般的物流運輸問題多，且更需要結合實際，導致其復雜程度也遠大于運輸問題。物流調度的對象一般是運輸車輛，且調度問題涉及的行程也較長，因此需要選擇最佳的調度路徑。

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

假定物流運輸中心共有n輛車輛，每輛車每公里的運輸費用為ci（i=1,2,…,n），運輸費用包括燃油費、人工費及其他相關費用。在某個時間段t內，共有m項運輸調度的請求任務，任務地點的坐標分別為（xi,yi），i=1,2,…,m。此時，共有l輛可供調度的車輛，其中l≥m。根據GPS定位系統可知，每輛可供調度車輛的地理位置為（Xi,Yi），i=1,2,…,l?？刹捎么笾行∪N車型進行調度，若可以派遣任意一種沒有任務的車型時，可采用小車進行調度，若無小車，則中型、大型車按順序依次替補；若申請調度中型車時，則可派遣中型車，當無中型車時，則采用大型車來替補；若申請調度大型車時，則只能派遣大型車。

根據上述假定，可知在t時間段內，物流運輸調度模型的調度總成本z表達式如下：

其中cj表示第j輛車每公里的運輸費用；dij表示第j個車輛到第i個客戶的距離；xij為車輛的調度情況，其值可表示如下：

由于每輛調度車輛僅能完成一項請求，則該運輸調度約束條件可表示為：

由于每項請求有且僅有一輛車輛完成，則該運輸調度約束條件可表示為：

根據式（4）、（5）、（6），可將物流調度問題改寫為：

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

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

當請求數量與調度車輛不相等時，可采用虛擬調度請求，將其完成的成本設為0，即在效率矩陣下面添上k行，其中k為請求數量與調度車輛兩者之間的差值，再用匈牙利算法來求解調度問題。

4 案例分析

某物流企業在t時刻共有6個調度請求，此時共有12輛可供調度的汽車，假定它們均能在任務要求的時間內到達任務的指定地點。在這12輛汽車中，大中小三類車輛均有，其中大、中、小型車輛每公里的運行成本分別為4元、3元和2元。

表1 物流運輸調度車輛與任務地點的運輸距離

根據GPS、GIS和GSM技術，可以準確的測定車輛與任務地點的距離，具體的調度車輛與任務地點之間的距離見表1。

根據調度車輛的運輸距離以及各個車輛的運輸費用和任務要求的車輛，可得物流運輸調度成本，見表2。

表2 物流運輸調度的成本

根據表2可知，效率矩陣可表示如下：由于可供調度的車輛與任務請求的數量不等，為了滿足車輛調度與請求數量相等這一條件，本文將虛構六個請求，則可得到新的效率矩陣，具體如下：

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

在矩陣c'中，選出不同行不同列的12個零元素，具體的做法是從0元素最少的行開始標記，直到標出所有的零元素。依照上述的算法，可得該物流運輸調度問題的最優解矩陣為：

根據最優解矩陣可知：調度車輛8完成請求任務1，調度車輛3完成請求任務2，調度車輛10完成請求任務3，調度車輛6完成請求任務4，調度車輛11完成請求任務5，調度車輛9完成請求任務6。根據匈牙利算法可知，最優的調度成本為：

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

5 結語

線性規劃理論在運輸問題中有著廣泛的用途，本文建立了物流運輸的調度系統模型，該系統實時監控物流企業的車輛，并與車輛進行實時通訊，及時響應任意時間每一個客戶的需求，及時處理物流運輸中的突發事件和臨時性請求，完善物流企業的運輸調度管理。

[1]覃運梅.多源點物流配送車輛調度模型探討[J].物流科技,2010,(9):32-35.

[2]李惠珠,宋海清.基于GIS的物流配送車輛調度實現與應用[J].長春師范學院學報(自然科學版),2011,30(2):20-24.

[3]曹克官,陳峰.多車輛直運越庫調度的建模與啟發式算法[J].上海交通大學學報,2009,43(9):1403-1406,1416.

[4]裴志松.一種新型物流調度算法的優化研究[J].長春工程學院學報(自然科學版),2011,12(2):117-119.

[5]張建中,許紹吉.線性規劃[M].北京:科學技術出版社,1997.

[6]張潛.物流配送路徑優化調度建模與實務[M].北京:中國物資出版社,2006.