城市物流配送車(chē)輛調(diào)度模型及優(yōu)化

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

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

0 引言

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

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

1 模型構(gòu)建

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

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

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

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

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

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

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

（2）對(duì)每一輛配送車(chē)輛，都要求配送的量小于或者等于車(chē)輛的最大載重量，而且對(duì)每一輛車(chē)都有運(yùn)輸路程約束。

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

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

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

w：每輛車(chē)的最大載重量；

K：車(chē)輛總數(shù)；

qi：每個(gè)配送點(diǎn)的需求量；

s：每輛車(chē)的最大運(yùn)行路程；

wk：每輛車(chē)的運(yùn)載量；

nk：車(chē)輛k配送的配送點(diǎn)數(shù)目；

pk：車(chē)輛k所配送的需求量；

gkij：車(chē)輛k從配送點(diǎn)i到配送點(diǎn)j的配送總路程；

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

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

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

約束條件：

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

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

2 算法簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

2.2 Logware軟件概述

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

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

3 案例分析

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

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

表2 C-W配送路線(xiàn)

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

可以看到共有4條配送路線(xiàn)：

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

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

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

④0-4運(yùn)輸量為179t，運(yùn)輸里程為8.5。

（2） 配送路線(xiàn)如圖2（a） 所示：Logware配送路線(xiàn)

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

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

②0-1-8-3-7-0運(yùn)輸量為289t，運(yùn)輸里程為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運(yùn)輸量為369t，運(yùn)輸里程為33.2+21.6+17.0+8.5=80.3，節(jié)約里程為33.5+13.4=46.9。

圖2 配送路線(xiàn)圖

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

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

4 結(jié)論

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

[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] 劉浩，錢(qián)小燕，王榮.隨機(jī)需求VRP的一個(gè)算法[J].南京工業(yè)大學(xué)學(xué)報(bào)，2004,26(5):9-11.

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

[7] 張健同，馮子炎.求解車(chē)輛路徑問(wèn)題的改進(jìn)C-W節(jié)約算法[C]//第十屆中國(guó)不確定系統(tǒng)年會(huì)、第十四屆中國(guó)青年信息與管理學(xué)者大會(huì)論文集，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.