基于循環取貨模式的車輛路徑優化研究

張利城，吳金卓，何 榮

（東北林業大學工程技術學院，哈爾濱 150040）

循環取貨（Milk－run）是一個優化的物流系統網絡，用于單個產品或零部件供應商的供應量不能滿足指定運輸車輛的額定容積并且在該供應商附近還有其他供應商存在的情形。這種取貨模式的顯著優點是能夠滿足小批量多頻次的要貨，并且能夠確保運輸車輛達到一定的裝載率。以整車制造廠零部件入庫為例，循環取貨的運作方式是車輛根據預先設定好的路線，從整車廠出發，按次序到多家供應商處提貨，最后返回整車廠的區域分發中心（RDC）。這樣既提高了運輸車輛的裝載率，又能使物料得到及時供給，同時供給量較少的供貨商也不必等到零部件積滿一卡車再發運，在最大程度上實現JIT供給。在Milk－run中，車輛路徑設計是運輸效率的決定性因素，因此，取貨車輛的路徑優化至關重要，屬于車輛路線問題（VRP）。

車輛路線問題（VRP）最早是由Dantzig和Ramser于1959年首次提出［1］，其目標就是在客觀條件的約束下，既能滿足客戶的需求，又能實現總成本最低、時間最短等目的。研究車輛路線問題具有很高的社會和經濟價值，因此，該問題自提出以來一直備受人們的關注，并不斷發展。學術界對于該問題的研究也取得了大量的成果［2］。在國外，對VRP的研究已經比較深入了，并在企業的Milkrun中得到了很好的應用。國內雖然以上海通用為代表的汽車企業已經從Milk－run中獲益，但對于Milk－run車輛路徑優化的理論研究還有待進一步完善。本文以國內一家著名的汽車物流企業實際情況為背景，對其零部件循環取貨的車輛路線進行優化設計。針對其Milk－run模式建立相應的數學模型，并運用蟻群算法進行優化求解。

1 數學模型的建立

1.1 模型描述

基于循環取貨的車輛路徑優化的數學模型可以描述如下:物流公司C負責將汽車制造商F的需求零部件用m輛汽車，從RDC出發依次經過Milk－run路線中的n個供應商，最終把貨物取回送到RDC。對取貨車輛的約束包括:必須在T時間內把貨物取回，并且滿足車輛最大容積限制。要求車輛在盡可能滿載、實現上述約束條件的前提下，尋求物流模式總成本最小的取貨路線。這里的總成本包括運輸成本、庫存成本以及缺貨成本。

1.2 模型的目標函數

基于循環取式的車輛路徑優化以總成本最小為目標，這里的總成本包括運輸成本Z1、庫存成本Z2以及缺貨成本Z3。很明顯，三者在企業實際運營中所占的權重是不一樣的。通過引入各個成本的權重w1、w2、w3，可將多目標函數轉化為單目標函數得:

（1）運輸成本。假設單位貨物運輸費用與距離成線性關系，即cij=a·dij+b，其中a，b為相關的參數。則運輸成本可以表示如下:

式中:nk表示第k條路線的供應商數;dij表示供應商與j的距離;kf表示該供應商在k線路中順序為f。

（2）庫存成本。所有線路上供應商的零部件庫存總成本可以表示如下［3］:

式中:βi為供應商i的零部件單位庫存成本;ukf表示路線k上供應商f的零部件的供應量;總路徑為m條。

（3）缺貨成本。如圖1所示，一旦供應商J供貨不足，損失函數dj（t）快速上升，當運輸車輛在時刻tj［1］到達，斷貨停止，損失開始下降。在 （0，tj［1］）時間，缺貨損失成本僅為損失函數dj（t）=kjt2j;kj為缺貨損失函數參數;在 （tj［1］，t）時間段內，缺貨損失成本為損失函數和補貨函數的差值，即為dj（t） －Rj（t），其中補貨函數可以表示如下［4］:

式中:Oj為補貨函數參數，這兩個參數根據歷史數據確定。

圖1 缺貨損失函數與補貨函數示意圖Fig.1 Out of stock function and supplement function

則目標函數為以上3項成本的總和，即:

1.3 約束條件

由于現實情況中的約束條件十分繁雜，這里簡化起見，只選擇其中最重要的兩個約束條件，即時間約束和容積約束。

（1）時間約束。

式中:V為n個供應商點與RDC的集合，i=0代表RDC;ti為供應商i的裝卸貨時間;tij為供應商i到j的行駛時間;T為每次取貨總的時間限制;xijk和yik表示如下:

（2）容積約束。假設各種零部件由同一種標準箱包裝，零部件的載重量不應超過汽車載重限制，則容積約束如下:

式中:ukf表示用體積表示供應量;Qk為每輛汽車的容積裝載上限。

2 數學模型的求解

擬采用“先分組再排路線”的二階段求解方法，進行取貨路線的安排，也就是先將所有的零部件供應商進行分組，然后再對每一組集中的供應商做最優化路線的處理，換句話說，是將車輛路徑問題（VRP）轉換成多個旅行商問題（TSP），然后運用蟻群算法優化求解。

2.1 構造初始解

先采用系統聚類法按照供應商的地理位置、零部件特性對供應商進行聚類。然后以“車輛裝載體積限制”為約束條件，對供應商供應量之和大于車輛裝載體積的組進行調整［5－6］。具體調整步驟如下:

（1）以第一組中離RDC最近的供應商為起點進行掃描，然后找到離其最近的供應商，依次進行，直到該組達到了車輛的裝載上限，則返回RDC，完成了一條Milk－run線路的構造。

（2）將第一組中剩余的供應商歸入第二組，然后按照步驟1對第二組的供應商進行線路構造。

（3）當所有組都構造完路線后，則將最后剩余的供應商依照約束條件再分組，直到所有供應商都被納入到規劃的線路中即完成初始解的構造。

2.2 蟻群算法求解優化路徑

由于上一階段已經將VRP問題轉換為TSP問題，因此，接下來只需對TSP進行求解。TSP的求解是NP－hard問題，本文采用蟻群算法進行求解。蟻群算法的提出是受到螞蟻覓食行為的啟發，屬于啟發式算法。它在求解NP難題中有強大的尋優能力［4］，蟻群算法求解 TSP 的步驟如下［7］:

首先，將m只螞蟻隨機放置在n個城市，位于城市i的第k只螞蟻選擇下一個城市j的概率為:

式中:τ（i，j）為邊 （i，j）上的信息素濃度;η（i，j）=1/d（i，j）是啟發信息;dij為城市i和j之間的距離;α和β為信息素與啟發信息的相對重要性;tabuk為螞蟻k已經訪問過的城市列表。

當所有螞蟻完成周游后，按公式 （11）、（12）進行信息素更新。

式中:ρ為小于1的常數，表示信息的持久性。

式中:Q為常數;lk為第k只螞蟻在本次迭代中走過的路徑;Lk為路徑長度。程序實現框架如下。

（1）初始化。隨機放置螞蟻，為每只螞蟻建立禁忌表，將初始節點置入禁忌表中。

（2）迭代過程。

3 實例驗證

3.1 算例背景

某第三方物流企業專門為汽車制造商提供服務，其零部件物流業務規模非常大，負責制造商的循環取貨代理執行，主要包括路線規劃設計、取貨窗口時間確定，車輛安排調度等。近年來，循環取貨模式在該公司入廠物流業務方面雖然得到了廣泛的應用和發展，但是發現目前物流運作成本仍然偏高。因此，可以采用本文提出的Milk－run路徑優化方法，進一步削減該公司的運營費用。該公司所承擔某訂單的零部件供應商位置坐標、供應商的供應量見表1，供應商分布圖如圖2所示。

表1 供應商的位置和零部件供應量Tab.1 The location of suppliers and quantities of parts supply

圖2 供應商空間分布Fig.2 Spatial distribution of suppliers

3.2 算例求解

根據該公司所在地車輛統一化標準，物流運輸車輛主要采用12 m長東風貨車，其最大容積為61 m3。首先，依據系統聚類算法對供應商進行分組，所有供應商的零部件供應總量為335 m3，因此，先將所有供應商分成5個小組。分組信息如下:供應商4、8為第一組;5、7、13為第二組;6、12、14、15、18 為第三組;1、2、3、9、10、16、17為第四組;11、19、20為第五組。各組別供應總量見表2。

表2 初步分組結果Tab.2 Initial grouping results

第一、二組的供應總量小于給定貨車的容積上限，因此不必調整。其余三組按照設計好的算法進行調整，調整后的分組結果見表3。

表3 供應商分類結果Tab.3 Classification of suppliers

3.3 循環取貨路徑優化

利用蟻群算法求解路徑優化問題時，首先要對啟發式因子α、期望啟發因子β、信息素揮發因子ρ進行賦值。Dorigo［8］在求解TSP問題時，推薦參數的最佳設置為:α=1，β=5，ρ=0.5。

經過計算，得各循環取貨小組運輸路線安排如下，其中第二個循環取貨小組的路徑優化結果如圖3所示。圖中點a（b）的a表示供應商序號，b表示該供應商的零部件供應量。

圖3 旅行商問題優化結果Fig.3 Optimization results for TSP

優化的結果只能確定各供應商間的取貨相對順序，而無法確定起止位置，企業必須結合實際情況加以選擇。各組優化的參考路線見表4。由表4可以看出，優化結果滿足裝載率較高的要求。另外，還可以實現路徑距離的優化。其中線路2的原路線距離為0.815 4，優化后最短路徑為0.745 8，節省了8.5%。由此可見，蟻群算法的結果明顯優于手工排定的線路。

表4 路徑優化結果Tab.4 Route optimization results

4 結束語

本文在分析了循環取貨的特點后，建立了其車輛路徑的數學模型，構造了先將規模較大的VRP轉換為多個相對小規模的TSP，然后再用蟻群算法優化求解的的算法，在一定程度上降低了循環取貨車輛路徑問題的復雜程度。最后，給出了一個實際算例驗證了優化算法的可行性和準確性，為企業進行循環取貨車輛路徑規劃提供了有效參考。

】

［1］Toth P，Vigo D.The Vehicle Routing Problem［M］.Society for Industrial and Applied Mathematics，Philadelphia:SIAM，2002.

［2］王 旭，陳 棟，王振峰.汽車零部件Milk－run車輛調度優化模型和算法［J］.計算機應用，2011，4（31）:1125 －1128.

［3］汪金蓮，蔣祖華.汽車制造廠零部件入廠物流的循環取貨路徑規劃［J］.上海交通大學學報，2009，11（43）:1704 －1708.

［4］曾敏剛，崔增收.基于循環取貨的汽車零部件入廠物流優化研究［D］.廣洲:華南理工大學，2011.

［5］張 坤，江海容.汽車零部件循環取貨車輛路徑優化研究［J］.物流科技，2009（2）:69 －72.

［6］王 蕊，邢艷秋，李 洋.飲料配送中心配送量預測與倉儲空間評價方法［J］.森林工程，2012，28（5）:107 －109.

［7］段海濱.蟻群算法原理及其應用［M］.北京:科學出版社，2005.

［8］Dorigo M，Maniezzo V，Colorni A.The ant system:optimization by a colony of cooperating agents［J］.IEEE Trans.System，Man，AND Cybernetics-Part B:Cybernetics，1996，26（1）:29-42.