基于循環(huán)取貨模式的車輛路徑優(yōu)化研究

張利城，吳金卓，何 榮

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

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

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

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

1.1 模型描述

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

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

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

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

式中:nk表示第k條路線的供應(yīng)商數(shù);dij表示供應(yīng)商與j的距離;kf表示該供應(yīng)商在k線路中順序?yàn)閒。

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

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

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

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

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

則目標(biāo)函數(shù)為以上3項(xiàng)成本的總和，即:

1.3 約束條件

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

（1）時間約束。

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

（2）容積約束。假設(shè)各種零部件由同一種標(biāo)準(zhǔn)箱包裝，零部件的載重量不應(yīng)超過汽車載重限制，則容積約束如下:

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

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

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

2.1 構(gòu)造初始解

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

（1）以第一組中離RDC最近的供應(yīng)商為起點(diǎn)進(jìn)行掃描，然后找到離其最近的供應(yīng)商，依次進(jìn)行，直到該組達(dá)到了車輛的裝載上限，則返回RDC，完成了一條Milk－run線路的構(gòu)造。

（2）將第一組中剩余的供應(yīng)商歸入第二組，然后按照步驟1對第二組的供應(yīng)商進(jìn)行線路構(gòu)造。

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

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

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

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

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

當(dāng)所有螞蟻完成周游后，按公式 （11）、（12）進(jìn)行信息素更新。

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

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

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

（2）迭代過程。

3 實(shí)例驗(yàn)證

3.1 算例背景

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

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

圖2 供應(yīng)商空間分布Fig.2 Spatial distribution of suppliers

3.2 算例求解

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

表2 初步分組結(jié)果Tab.2 Initial grouping results

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

表3 供應(yīng)商分類結(jié)果Tab.3 Classification of suppliers

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

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

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

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

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

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

4 結(jié)束語

本文在分析了循環(huán)取貨的特點(diǎn)后，建立了其車輛路徑的數(shù)學(xué)模型，構(gòu)造了先將規(guī)模較大的VRP轉(zhuǎn)換為多個相對小規(guī)模的TSP，然后再用蟻群算法優(yōu)化求解的的算法，在一定程度上降低了循環(huán)取貨車輛路徑問題的復(fù)雜程度。最后，給出了一個實(shí)際算例驗(yàn)證了優(yōu)化算法的可行性和準(zhǔn)確性，為企業(yè)進(jìn)行循環(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］.計(jì)算機(jī)應(yīng)用，2011，4（31）:1125 －1128.

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

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

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

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

［7］段海濱.蟻群算法原理及其應(yīng)用［M］.北京:科學(xué)出版社，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.