盧軍莉，傅忠寧，李金萍 LU Junli,FU Zhongning,LI Jinping

（蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州 730070）

0 引言

車輛路徑問題（Vehicle Routing Problem，VRP） 最早是由Dantzig和Ramser[1]于1959年首次提出，是指擁有一定量的客戶數(shù)，各自都具有不同數(shù)量、不同品種的貨物需求，物流配送中心向需求客戶提供貨物，由一個配送車隊負(fù)責(zé)配送貨物，選擇最優(yōu)的行車配送線路，使得客戶需求得到滿足，并且在特定的約束條件下，達到一些比如路程最大、費用最低和成本最小以及時間最少等目的。

自VRP問題被提出，國內(nèi)外學(xué)者分別從不同角度，使用不同方法對其進行研究。在國外，1991年，Gendrean等人將禁忌搜索算法應(yīng)用于VRP中[2]。1996年，J.Lawrence將遺傳算法用于VRP研究中，并可有效求解帶時間窗口的VRP問題[3]。Archetti等通過分別對車輛路徑問題（VRP）和交付車輛路徑問題進行實例研究，分別得出在有限車容量情況下和無限制車容量情況下的最優(yōu)配置問題[4]。國內(nèi)VRP研究起步較晚，劉浩等研究了隨機需求VRP問題，在服務(wù)僅能路由失敗一次和不允許部分服務(wù)的情況下，給出了兩階段模擬退火算法[5]。朱孟高等針對現(xiàn)有算法在多約束下車輛調(diào)度優(yōu)化問題求解方面的不足，提出兩階段啟發(fā)式算法，即采用集束式算法進行客戶點的合并，從而降低了全局搜索范圍[6]。張健同等通過具體數(shù)例分析了節(jié)約法得到的配送方案，針對出現(xiàn)的配送路徑交叉的情況，結(jié)合掃描法給出了一種改進節(jié)約算法[7]。最后通過具體的算例用這兩種算法進行了對比計算。本文通過C-W節(jié)約算法與Logware仿真進行計算，進行對比。

1 模型構(gòu)建

研究物流配送模型下的車輛調(diào)度問題一般會有以下幾點假設(shè)：

（1）假設(shè)所有配送的貨物都可以進行混裝。

（2）假設(shè)每個需求點的需求量已知。

（3）假設(shè)從配送中心到各個配送點以及各配送點之間的距離都已知。

（4）假設(shè)配送中心具有足夠的貨物量和車輛數(shù)。

物流配送車輛調(diào)度的目的是使總費用最小，就一般情況而言，也可以說是車輛的總運輸噸公里數(shù)最小。即找到滿足條件的最優(yōu)行駛路線。車輛調(diào)度模型的配送路線，主要滿足以下的約束條件：

（1）必須滿足所有配送點的需求品種數(shù)和需求量。

（2）對每一輛配送車輛，都要求配送的量小于或者等于車輛的最大載重量，而且對每一輛車都有運輸路程約束。

物流配送車輛調(diào)度問題應(yīng)在嚴(yán)格的符合上述約束條件的基礎(chǔ)上求解最優(yōu)配送路線，以及選擇車輛類型和車輛數(shù)。運用這樣的配送方法，要求按量、按時地完成配送點的需求的配送任務(wù)，而且還必須保證運輸總噸公里數(shù)最小。

xi：配送網(wǎng)絡(luò)中的節(jié)點，xi在i≠0表示配送點，在i=0表示配送中心；

n：配送需求點數(shù)；

w：每輛車的最大載重量；

K：車輛總數(shù)；

qi：每個配送點的需求量；

s：每輛車的最大運行路程；

wk：每輛車的運載量；

nk：車輛k配送的配送點數(shù)目；

pk：車輛k所配送的需求量；

gkij：車輛k從配送點i到配送點j的配送總路程；

dij：任意兩個配送節(jié)點之間的距離。

物流車輛調(diào)度模型如下：

目標(biāo)函數(shù)：

約束條件：

在上面的式子中，具體解釋如下：

式（1）是目標(biāo)函數(shù)，表示在車輛可以從i點到j(luò)點的情況下，總的運輸距離最小。是配送車輛從配送中心到配送點及配送點之間的距離之和。式（2）表示任意每個配送點的需求量小于或者等于每輛車的最大載重量。式（3）表示任意每輛車的載重量大于0，但是要小于或者等于每輛車的最大載重量。式（4）表示任意一輛車配送的配送點的數(shù)目都要大于0。式（5）表示任意每輛車配送的需求點需求量要小于車輛的最大載重量。式（6）表示任意兩個點之間的配送路線情況，即xij=0表示i點和j點沒有配送路線，xij=1表示i點和j點有配送路線。車輛從一個配送點到另一個配送點之間的情況，即xkij=0表示車輛k不可以從配送需求點i到配送需求點j，xkij=1表示車輛k可以從配送需求的i到配送需求點j。車輛對配送點的服務(wù)情況，即yki=0表示車輛k不對配送需求的i服務(wù)，yki=1表示車輛k對配送需求點i服務(wù)。式（7）表示每條路徑最多只能走一次。式（8）表示只有在某一配送車輛經(jīng)過某一配送需求點，該輛車才能對該配送需求點進行服務(wù)。式（9）表示中間頂點的平衡，即對于某一配送需求點，其進入的配送路線與出去的配送線路相等。式（10）表示配送車輛數(shù)大于或等于配送的路徑數(shù)。式（11）表示配送中心到任意一個配送需求點或者任意兩個配送需求點之間的距離大于0。式（12）表示一條路徑上的配送需求點的需求量要小于或者等于車輛的最大載重量。式（13）表示配送中心的貨物總量要滿足客戶需求量。式（14）表示每一個配送點最多只能服務(wù)一次。

2 算法簡介

2.1 C-W節(jié)約算法

節(jié)約法（the Clarke-Wright algorithm）是啟發(fā)式算法中最常用的一種算法，是1964年由Clarke和Wright提出的，是根據(jù)配送中心的配送能力和物流配送中心到各配送需求點以及各配送需求點之間的距離，制定使總的車輛運輸噸公里數(shù)（或者時間或者費用）最小的方案。

C-W節(jié)約算法的計算步驟如下[7]：

Step1：根據(jù)配送中心以及各配送需求點的坐標(biāo)，運用歐式距離公式計算出配送中心至各配送需求點以及各配送需求點之間的距離，得到距離矩陣dist。

其中，v［i］,v［j］表示配送需求的i和j。v［i］·x和v［j］·y表示x和y點的橫坐標(biāo)。v［i］·x和v［j］·y表示x和y的縱坐標(biāo)。dist［i］［j］表示i和j點的距離。i=0表示配送中心。

Step2：由距離矩陣計算出任意兩個配送需求點的節(jié)約值，得出節(jié)約值矩陣savingvalue。

此時，設(shè)lij=lji，lij表示i到j(luò)的距離，i=0表示配送中心。

Step3：為了按照節(jié)約值的大小對配送需求點進行由大到小的排序,需要將節(jié)約值矩陣savingvalue轉(zhuǎn)換為節(jié)約值表savingvaluetable。

Step4：從排好序的節(jié)約值表中取出第一項，而且判斷是否要將其加入到當(dāng)前的路徑中。具體如圖1所示：

圖1 節(jié)約法流程圖

2.2 Logware軟件概述

Logware是一組選定的軟件程序，用于分析各種物流/供應(yīng)鏈問題和案例研究。它包含以下模塊：FORECAST：通過指數(shù)平滑法預(yù)測時間序列數(shù)據(jù)和時間序列分解方法；ROUTE：找到路網(wǎng)的最短路徑；ROUTESEQ：找到線路上訪問點的最佳順序；ROUTER：多車型訪問多個客戶的路線選擇；INPOL：基于EOQ的庫存訂購決策；COG：根據(jù)精確中心法找到單個設(shè)施的位置；MULTICOG：根據(jù)精確重心法找到選擇設(shè)施的數(shù)量；PMED：根據(jù)P-median方法找到設(shè)施的數(shù)量；WARELOCA：根據(jù)分析研究倉庫位置；LAYOUT：商品在倉庫和其他設(shè)施的位置；MILES：使用經(jīng)度或linear-grid坐標(biāo)點計算兩點之間的近似距離；TRANLP：解決交通的線性規(guī)劃方法；LNPROG：解決一般線性規(guī)劃問題的單純形法；MIPROG：解決混合整數(shù)線性規(guī)劃問題的分支界限法；MULREG：通過逐步回歸和相關(guān)分析發(fā)現(xiàn)線性回歸方程的程序；SCSIM：通過五階層的供應(yīng)渠道模擬產(chǎn)品的流動。

其中本文運用ROUTER模塊；ROUTER模塊是一個由私人控制車隊來確定最佳路線和時間表的軟件程序。主要有以下輸入：坐標(biāo)點、放縮比例因子、站點時間限制、道路限制、速度地帶、距離、打斷時間、時間窗口、取貨交貨、取貨政策、車輛、路線費用、線路中的障礙物等。

3 案例分析

設(shè)有10個醫(yī)院，其中0表示醫(yī)藥配送中心。配送中心位于坐標(biāo)原點，車輛最大載重為400t。下面是各門店的坐標(biāo)以及需求量（見表1）。找到最優(yōu)配送路線（見表2）。

表1 門店坐標(biāo)及需求量

表2 C-W配送路線

（1）利用C-W節(jié)約法計算

可以看到共有4條配送路線：

①0-6-2-5-0運輸量282t，運輸里程為29.4+24.1+36.1+53.2=142.8，節(jié)約里程為47.3+59.1=106.6。

②0-1-8-3-0運輸量為194t，運輸里程為46.0+15.7+17.5+20.0=99.2，節(jié)約里程為62.3+34.5=96.8。

③0-9-10-7-0運輸量為25t，運輸里程為33.2+21.6+14.2+20.1=89.1，節(jié)約里程為33.5+27.8=61。

④0-4運輸量為179t，運輸里程為8.5。

（2） 配送路線如圖2（a） 所示：Logware配送路線

可以看到共有3條配送路線，其配送路線圖如圖2（b）所示：

①0-5-2-6-0運輸量為282t，運輸里程為53.2+36.1+24.1+29.4=142.8，節(jié)約里程為47.3+59.1=106.6。

②0-1-8-3-7-0運輸量為289t，運輸里程為46.0+15.7+17.5+10.2+2.1=109.5，節(jié)約里程為62.3+34.5+30.0=126.8。

③0-9-10-4運輸量為369t，運輸里程為33.2+21.6+17.0+8.5=80.3，節(jié)約里程為33.5+13.4=46.9。

圖2 配送路線圖

其中，C-W節(jié)約法的MATLAB程序計算的總運輸里程為339.6，節(jié)約里程為264.4。Logware軟件計算的總的運輸里程為332.6，節(jié)約里程為280.3。運輸里程相差7。

由上面的兩個例子可以看出，Logware軟件比C-W節(jié)約值的MATLAB程序?qū)崿F(xiàn)的路徑更優(yōu)，這是因為運用C-W節(jié)約法過分注重節(jié)約的里程而沒有考慮時間因素，并且沒有考慮運輸過程中花費的費用，而且C-W節(jié)約法不能對客戶的需求進行靈活處理。

4 結(jié)論

本文對VRP問題進行了描述，建立了一般物流配送的VRP模型，然后對物流配送的VRP問題在一定的前提和假設(shè)條件下進行了模型分析與建立。本文的主要假設(shè)有：假設(shè)所有配送的貨物都可以進行混裝，假設(shè)每個需求點的需求量已知，假設(shè)從配送中心到各個配送點以及各配送點之間的距離都已知，假設(shè)配送中心具有足夠的貨物量和車輛數(shù)。根據(jù)假設(shè)條件建立了目標(biāo)函數(shù)和約束條件。通過對兩種方法的比較，發(fā)現(xiàn)Logware軟件更加優(yōu)化一些。這是因為運用C-W節(jié)約法過分注重節(jié)約的里程而沒有考慮時間因素，而且C-W節(jié)約法不能對客戶的需求進行靈活處理，而Logware可以處理這些問題。

[1]Dantzig G B,Ramser J H.The truck dispatching problem[J].Management science,1959,6(1):80-91.

[2] Gendrean M,Hertz A,Laporte G.A tabu search heuristic for the vehicle routing problem[M].Management Sci,1994,40:1276-1290.

[3] Lawrenee S.Mohammad.A Parametric experimentation with a genetic algorithmic configuration for solving the vehicle routing problem[C]//Proceedings-Annual Meeting of the Decision sciences Institute.Decis Scil Inst,1996:488-490.

[4] Archetti C,Feillet D,Gendreau M,et al.Complexity of the VRP and SDVRP[J].Transportation Research Part C:Emerging Technologies,2011,19(5):741-750.

[5] 劉浩，錢小燕，王榮.隨機需求VRP的一個算法[J].南京工業(yè)大學(xué)學(xué)報，2004,26(5):9-11.

[6] 朱孟高，米娜.城市配送車輛路徑優(yōu)化集束式算法的客戶點歸并策略[J].數(shù)學(xué)的實踐與認(rèn)識，2012(11):47-51.

[7] 張健同，馮子炎.求解車輛路徑問題的改進C-W節(jié)約算法[C]//第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學(xué)者大會論文集，2012.

[8] G.Clkare,J.w.wright.Scheduling of Vehieles from a Central Depot to a Number of Delivery Points[J].Oeration Researeh,1963,11:568-581.