張利城，吳金卓，何 榮

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

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

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

1 數(shù)學模型的建立

1.1 模型描述

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

1.2 模型的目標函數(shù)

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

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

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

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

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

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

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

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

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

1.3 約束條件

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

（1）時間約束。

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

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

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

2 數(shù)學模型的求解

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

2.1 構造初始解

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

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

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

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

2.2 蟻群算法求解優(yōu)化路徑

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

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

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

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

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

式中:Q為常數(shù);lk為第k只螞蟻在本次迭代中走過的路徑;Lk為路徑長度。程序?qū)崿F(xiàn)框架如下。

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

（2）迭代過程。

3 實例驗證

3.1 算例背景

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

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

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

3.2 算例求解

根據(jù)該公司所在地車輛統(tǒng)一化標準，物流運輸車輛主要采用12 m長東風貨車，其最大容積為61 m3。首先，依據(jù)系統(tǒng)聚類算法對供應商進行分組，所有供應商的零部件供應總量為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

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

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

3.3 循環(huán)取貨路徑優(yōu)化

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

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

圖3 旅行商問題優(yōu)化結果Fig.3 Optimization results for TSP

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

表4 路徑優(yōu)化結果Tab.4 Route optimization results

4 結束語

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

】

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

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

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

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

［5］張 坤，江海容.汽車零部件循環(huán)取貨車輛路徑優(yōu)化研究［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.