趙春閣，徐 群

(1.蘭州商學(xué)院 信息工程學(xué)院;2.蘭州商學(xué)院工商管理學(xué)院，甘肅蘭州 730020)

物流配送車輛路徑問題(Vehicle Routing Problem，VRP)最早是由Dantzing和Ramser［1］于1959年首次提出的，是近年來各學(xué)者研究的重點.其基本定義可以描述為下:有客戶若干，他們各自有不同數(shù)量的貨物需求，由配送中心提供貨物，由一個車隊負責(zé)分配貨物，組織適當?shù)男熊嚶肪€，目標是使客戶的需求得到滿足，并能在一定的約束條件下，達到目標(路程最短、使用車輛數(shù)盡量少、費用最少、耗費時間最少等).

VRP屬于NP難題［2］，目前解決VRP的算法主要集中于啟發(fā)式算法.而啟發(fā)式算法包括節(jié)約算法、模擬退火法、確定性退火法、禁忌搜索法、遺傳算法等.每一種算法都存在一定的缺陷，相比其他啟發(fā)式算法，Clarke和Wright［3］提出的節(jié)約算法及其改進算法［4］較為簡單清晰明了，對解決日常生活中的簡單物流配送路徑問題比較適用，國內(nèi)學(xué)者也做了一系列研究，劉誠［5］等研究了具有區(qū)間參數(shù)的VRP及其改進的C-W節(jié)約算法，對費用參數(shù)進行排序，并應(yīng)用了可能度的區(qū)間排序方法;孫焰［6］等提出了一種改進的節(jié)約算法用來解決配送規(guī)劃問題，將AK算法與傳統(tǒng)的C-W節(jié)約算法相結(jié)合，避免了某些情況下C-W算法求解結(jié)果與最優(yōu)解相差較大的問題;張建勇［7］等提出了一種具有模糊費用系數(shù)的VSP的修正C-W節(jié)約算法，在對具有模糊費用系數(shù)的車輛調(diào)度問題進行簡單描述的基礎(chǔ)上，構(gòu)建了模糊車輛調(diào)度的數(shù)學(xué)模型并結(jié)合節(jié)約算法來解決問題;朱曉蘭［8］等提出C-W節(jié)約算法在裝配企業(yè)采購物流中的應(yīng)用，針對裝配企業(yè)采購物流中所運輸產(chǎn)品的特點，在線路規(guī)劃中插入車輛載重量和容積的雙重約束條件，并驗證了C-W節(jié)約算法對此問題的適用性.以上研究多證明節(jié)約算法的優(yōu)勢，未考慮其局限性.本文針對以上研究存在的問題及物流配送領(lǐng)域的現(xiàn)狀，提出一種改良的、簡單適用的C-W節(jié)約算法，建立了數(shù)學(xué)模型，并且通過案例分析來優(yōu)化物流配送路徑.

1 VRP問題概述

1.1 問題描述

VRP問題可以描述如下:有一定數(shù)量的客戶配送中心，負責(zé)向各客戶運輸貨物，假設(shè)配送中心的編號為0，有N個客戶，編號分別為1，2，3，……，N.第i個客戶的貨物需求量為qi，卸貨時間為UTi，客戶允許到達的最早時間、最遲時間分別為ETi、LTi.中心與客戶、客戶與客戶兩兩之間的運輸費用Cij，運輸時間為 Tij(i=1，2，3，…，n).已知每輛車的載重量都有 Q 的限制(Q 〉 qi，i=1，2，3，…，n)，每輛車不允許超載，而且必須在規(guī)定的時間內(nèi)把貨物送到.如果每輛車有工作時限WTk(k=1，2，3，…，k，k表示配送車輛總數(shù)).要求指派車并確定每輛車的配送路線，使總的運輸費用最低或是運輸路徑最短.

1.2 問題假設(shè)

(1)每輛車必須從配送中心出發(fā)，對客戶進行配送服務(wù)最后再返回配送中心;

(2)要求所有的顧客都被服務(wù)，每位顧客一次配送完成;

(3)若在某條配送線路上，i是j前面并且相鄰的節(jié)點，RTi、RTj分別是到達節(jié)點的時間，則它們之間的關(guān)系如下:

2 建立VRP數(shù)學(xué)模型

為了建立模型，需要定義如下決策變量:

帶工作時限和時間窗約束的模型如下:

目標函數(shù)(1)表示費用最低;約束條件(2)表示每輛車的裝載貨物不能超過車容量;約束條件(3)表示每個客戶點的任務(wù)只能由一輛車來完成;約束條件(4)、(5)表示到達和離開某以客戶的車輛有且僅有一輛;約束條件(6)表示每輛車的工作時間不能超過最大工作時限;約束條件(7)要求所有車輛都必須在規(guī)定的時間內(nèi)到達，同時還需要保證運輸網(wǎng)絡(luò)必須是聯(lián)通的;約束條件(8)是用來表示消除之路，以避免出現(xiàn)孤立圈;約束條件(9)是變量取值約束.

3 VRP模型求解

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

文章將采用C-W節(jié)約算法及其改進的算法來求解模型.C-W節(jié)約算法的基本思想是:假設(shè)首先每輛車從配送中心出發(fā)抵達某一個客戶，車輛卸貨后直接返回配送中心，即構(gòu)成了n條“0-i-0”(i=1，2，3，……，n)的初始配送路線，第i條路線的運輸費用可記為:

然后把客戶 i和客戶 j連接，形成線路“0-i-j-0”(i，j=1，2，3，…，n)，計算線路連接后到達客戶的運輸費用的“節(jié)約值”:

Y(i，j)越大.說明把客戶i和客戶j連接在一起用同一條運輸路線進行送貨時的費用的節(jié)約值就越多，因此應(yīng)該優(yōu)先連接y(i，j)值較大的i和j點.

3.2 改進的C-W節(jié)約算法

由于Clarke-Wright的節(jié)約啟發(fā)式算法簡單、交互特性好.在實際應(yīng)用中非常廣泛，但并不是所有的問題都可以簡單調(diào)用.本文在對C-W算法深入研究的基礎(chǔ)上，對其進行改進［9-10］，并在下文中通過實例具體應(yīng)用了此節(jié)約算法.改進的C-W節(jié)約算法的步驟如下:

(1)計算 y(i，j)，令 M={y(i，j)|y(i，j)〉0，i，j=1，2，3，…，n}，并把集合 M 的元素按從大到小的順序排序，轉(zhuǎn)(2);

(2)選擇集合M的第一個元素y(i，j)，考察點i和j，如果滿足點i和j均在初始化線路上，或者是點i和點j有一個在已構(gòu)成線路上且與配送中心相連，另一個在初始化線路上，或者點i和點j位于不同的已構(gòu)成線路上，但都與配送中心相連，則轉(zhuǎn)(3)，否則轉(zhuǎn)(8);

(3)計算連接點i和j后車輛的貨運量NQ，若NQ≤Q，轉(zhuǎn)(4)，否則轉(zhuǎn)(8);

(4)計算連接點i和j后線路總的工作時間NW，若NWT〈WT，轉(zhuǎn)(5)，否則轉(zhuǎn)(8);

(5)根據(jù)式(1)計算連接i和j后到達m點(m點為連接前包含j的線路上的個點)的時刻RTm，若ETm≤RTm≤LTm，則轉(zhuǎn)(6)，否則轉(zhuǎn)(8);

(6)連接點i和j，計算車輛到達各個客戶的時間，轉(zhuǎn)(7);

(7)如果本線路與其他任何一條線路連接后，若貨運量都大于車的載重量或車的工作時間都大于工作時限，則轉(zhuǎn)(9)，否則轉(zhuǎn)(8);

(8)在集合M中消去這個最大元素y(i，j)，轉(zhuǎn)(10);

(9)在集合M中消去所有包含本線路上任一點的元素，轉(zhuǎn)(10);

(10)如果M=?算法結(jié)束，否則回到(2);

4 實例驗證

為了使模型和算法體現(xiàn)的較為明了，本文給出一個簡單易懂的實例介紹.假設(shè)某配送中心有一定配送任務(wù)，現(xiàn)有5個客戶，各任務(wù)貨運量為Ri(見表1，圖1)，配送中心0有5輛載重量為4t的貨車.最大運輸距離為40km.車輛由配送中心0出發(fā).各客戶之間的距離可由表2給出.

表1 配送中心配送任務(wù)表

表2 各項任務(wù)點之間的距離

(1)計算各個用戶連接之間的費用“節(jié)約值”，y(i，j)=C0j+Cj0-Cij.比如連接用戶1和用戶2，y(1，2)=C01+C20-C12=10+13-5=18.類似的，連接其他各用戶，可以得到相應(yīng)的“節(jié)約值”，按照“節(jié)約值”從大到小的順序排序，見表3.

表3 節(jié)約里程排序表

(2)構(gòu)造線路

①從最大的里程“節(jié)約值”y(i，j)開始考慮各用戶.由表3可知，y(3，4)最大，連接用戶3和用戶4，得到線路0-3-4-0，此時線路上的任務(wù)量為1.9+1.8=3.7〈4.下一個大的里程“節(jié)約值”是y(2，4)，若連入，則任務(wù)量為3.7+2〉4，故不能連接，同理也不能與其他用戶連接，此時得到了第一條線路，里程“節(jié)約值”為23.

②由表3可知，接下來考慮y(1，2)，得到線路0-1-2-0，此時線路上的任務(wù)量為1+1〈4.下一個被配送客戶的里程“節(jié)約值”大的是y(1，5)，線路上的任務(wù)量為2+1.5〈4，則可連入，得到第二條線路，里程“節(jié)約值”為18+1=19.

至此，所有用戶均被包圍在線路中，共兩條線路，分別是0-3-4-0，0-5-1-2-0，共用兩輛車.總的里程為10+7+20+10+5+13+2×6=77km，節(jié)約里程為23+19=42km.可見若采用此種方法，可以大大提高物流效率，大幅度降低業(yè)務(wù)成本.

為了進一步分析此算法的適用性，將客戶規(guī)模增至8，貨車數(shù)量也增至為8輛，其他保持不變，客戶6、7、8 的貨運量依次為0.9、1.5、2.各客戶點分布圖如圖 2.

圖1 各客戶點分布圖

圖2 各客戶點分布圖

根據(jù) C-W 節(jié)約算法計算，最終得0-3-4-0，0-1-2-0，0-6-7-0，0-5-0，0-8-0，共5 條線路，用5輛車，從計算結(jié)果可以看出，此次優(yōu)化結(jié)果并不理想，客戶5、客戶8并沒有被優(yōu)化，而是單獨配送的.此算例表明隨著解的空間的增加，解的精確度也逐漸下降，出現(xiàn)了不理想的情況.從而證明，此改良的C-W算法對解決客戶數(shù)量較少的物流配送問題有較高的適用性.但是隨著客戶規(guī)模的增加，此算法則有一定的局限性.

5 結(jié)語

本文深入研究了基于C-W節(jié)約算法的物流配送車輛路徑問題，通過一種改良的節(jié)約算法得到優(yōu)化配送路線，并通過具體實例驗證了該算法的適用性及局限性.C-W節(jié)約算法求解速度快、通用性強、限制條件易于加入，優(yōu)先考慮一些配送中心較遠的需求點是一種相當實用的啟發(fā)式算法，為該領(lǐng)域的進一步發(fā)展奠定了一定的基礎(chǔ).但是，對于一些客戶規(guī)模大的問題，此算法則沒有優(yōu)越性，需要考慮其他的啟發(fā)式算法.

［1］DANTZIG G，RAMSER J.The truck dispatching problem［J］.Management Science，1959(6):80-91.

［2］Garey M R，Johnson D S.Computers and Intractability:A Guide to Theory of NP-Completeness［M］.San Franciscon:W.H.Freeman and company，1979.

［3］Clarke G，Wright J.Scheduling of vehicles from central depot to a number of delivery points［J］.Operations Research，1964(12):568-581.

［4］林曉寧，李金銘，紀壽文.車輛路徑問題Clarke-Wright算法的改進與實現(xiàn)［J］.交通與計算機，2004，22(6):72-75.

［5］劉誠，顧坤坤.具有區(qū)間參數(shù)的VRP及其改進的C-W節(jié)約算法［J］.武漢理工大學(xué)學(xué)報，2010，32(2):182-185.

［6］孫焰，張喆.一種解決配送規(guī)劃問題的改進節(jié)約算法［J］.物流科技，2009，29(9):29-31.

［7］張建勇，郭耀煌，李軍.一種具有模糊費用系數(shù)的 VSP的修正C-W節(jié)約算法［J］.西南交通大學(xué)學(xué)報，2004，39(3):281-284.

［8］朱曉蘭，趙一飛.C-W節(jié)約算法在裝配企業(yè)采購物流中的應(yīng)用［J］.上海交通大學(xué)學(xué)報，2007，41(9):1420-1424.

［9］Ballou Ronald H.Business logistics Mangement:Planning，Organizing，and Controlling the Supply Chain(4th Edition)［M］.Upper Saddle River，NJ:Prentice-Hall，1999.

［10］劉志強，丁鵬，盛煥燁.物流配送系統(tǒng)設(shè)計［M］.北京:清華大學(xué)出版社，2004.