基于C-W節約算法的物流配送車輛路徑問題的研究

趙春閣，徐 群

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

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

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

1 VRP問題概述

1.1 問題描述

VRP問題可以描述如下:有一定數量的客戶配送中心，負責向各客戶運輸貨物，假設配送中心的編號為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)，每輛車不允許超載，而且必須在規定的時間內把貨物送到.如果每輛車有工作時限WTk(k=1，2，3，…，k，k表示配送車輛總數).要求指派車并確定每輛車的配送路線，使總的運輸費用最低或是運輸路徑最短.

1.2 問題假設

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

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

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

2 建立VRP數學模型

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

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

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

3 VRP模型求解

3.1 C-W節約算法

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

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

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

3.2 改進的C-W節約算法

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

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

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

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

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

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

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

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

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

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

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

4 實例驗證

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

表1 配送中心配送任務表

表2 各項任務點之間的距離

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

表3 節約里程排序表

(2)構造線路

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

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

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

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

圖1 各客戶點分布圖

圖2 各客戶點分布圖

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

5 結語

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

［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算法的改進與實現［J］.交通與計算機，2004，22(6):72-75.

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

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

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

［8］朱曉蘭，趙一飛.C-W節約算法在裝配企業采購物流中的應用［J］.上海交通大學學報，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］劉志強，丁鵬，盛煥燁.物流配送系統設計［M］.北京:清華大學出版社，2004.