最小支撐樹混合貪婪算法求解車輛路徑問題

張 恒，冉 雨，于卓岑，俸 衛*

(1.內江師范學院數學與信息科學學院，四川內江641100； 2.內江師范學院四川省高等學校數值仿真重點實驗室，四川內江641100)

物資配送［1］是物資流通企業按照用戶的訂貨需求及其標準，以最經濟的方式對貨物進行采購、儲存、加工、分揀、配裝、運輸，直到把貨物交到用戶手中的物資流通活動.由于物流對國民經濟的重大影響，物流系統化、合理化能創造巨大經濟利益，因此物流與商流、信息流并稱為現代經濟的三大支柱，被稱為繼勞動力、資源之后的“第三大利潤源泉”［2］.而如今，物流企業面臨的現狀是服務效率較低，服務成本較高.

現階段，國內外對物資配送的研究主要涉及車輛調度，路徑優化方面的研究，并針對不同問題采用各種算法進行求解［3-4］.C.Clarke 等［5］在 1964年針對車輛調度問題首先提出C-W節約啟發式算法，其算法具有較強的局部搜索能力.王剛［6］利用遺傳算法全局搜索能力的特點研究車輛調度問題.最近，喻偉等［7］將遺傳算法的全局搜索能力與節約算法的局部搜索能力相結合，設計了遺傳節約綜合算法.而現代物流不僅要降低成本，更要滿足客戶的需求，因此如何在滿足用戶需要的前提下，進一步降低物流成本已成為國內外許多理論與應用學者研究的焦點.

文章將針對一定客戶規模的物資配送進行研究，建立區域劃分——路徑優化模型，設計最小支撐樹混合貪婪算法求解.最終達到物流企業物資配送低成本，高效率的目的.

1 問題描述

物資配送問題的一般描述為:某配送中心擁有一支貨運車隊，為若干個客戶配送物資，配送中心與客戶以及客戶與客戶之間的公路里程為已知.配送中心如何制定每天的配送方案?配送方案包括:當天出動的車輛數，出行時間，行駛路徑等，由此形成當天的總運行里程.一個合格的配送方案要求配送中心按照客戶需求，高效率為客戶服務；而一個好的配送方案還應該給出使配送費用最小或總運行里程最短的車輛調度方案，降低配送中心的服務成本.

2 車輛路線問題的數學模型

車輛路線問題假設如下:

1)有相同載重量Q的車m輛；

2)只有一個配送中心，并以配送中心為路線的起止點；

3)有l個客戶且每個客戶在不同的地理位置；

4)每個客戶都有一個確定的需求量di，且每個客戶有且只有被其中一輛車滿足；

5)每個客戶有且只被服務一次；

6)每輛車必須服務若干客戶，且始于配送中心，終于配送中心；

7)對被一輛車所服務的客戶集的總需求量不超過車輛的載重量.

目標為每輛車設計一條路線，使得總運輸里程最小，并且確保全部客戶的需求得到滿足.定義0-1決策變量:

假設z為k個客戶集的總運輸里程，車輛路線問題的模型［8］如下:

模型中各式含義如下:(1)式為目標函數，表示k個客戶集總的最小運輸成本，l為客戶數，m為最大車輛估計數(通過文獻［4］可確定)，sij代表客戶i到客戶j的距離.(2)式為載重約束，表示第k個客戶集里的客戶總需求量不超過一輛車的載重量.(3)式表示客戶集中每個客戶都只被車輛k服務一次.(4)～(5)式表示所有車輛起于點i，終于點i.(6)式保證巡回路線不出現子圈.(7)～(8)式為變量約束.

在配送中心和客戶之間的車輛調度問題的客戶規模和約束條件較少時，可精確求解.但經考察發現，現實中物流公司物資配送服務的客戶數量較大(客戶數量級≥102).在這種大規模條件下，直接求解難度較大，難以運用到實際生活中［9］.因此，本文思路利用最小支撐樹算法對客戶先進行區域劃分，縮小問題規模，再用貪婪算法對每個分區求解最優路線.

3 最小支撐樹混合貪婪算法

3.1 區域劃分問題描述以及數學模型區域劃分假設如下:區域中有一個配送中心；每個客戶都要被服務；一輛車服務于一個分區，且一個分區僅有一輛車服務.目標是將客戶分成若干個客戶集，使得配送中心到客戶集，客戶集中客戶與客戶的距離總和最小，且保證每個分區內的總需求量不超過一輛車的最大載重量.區域劃分的目的是分解規模，方便優化和計算，而且也是管理本身的需要.定義0-1決策變量:

建立區域劃分的數學模型［10］如下所示:

根據后文案例，該模型通過Lingo軟件也可以實現.模型中各式含義如下:(9)式為目標函數，使得運輸成本最小化.li表示第i分區中，距離配送中心最近的客戶點到配送中心的運輸里程，sij表示節點j到本分區距離配送中心最近的客戶點的運輸成本.(10)式表示每一客戶點都被選中.(11)式表示每一分區內的需求總量不超過單輛車的載重量，dj為第j個客戶所需物資的重量，Q為單輛貨車載重量.(12)式表示分區i與客戶點j的關系.(13)～(14)式為變量約束.

3.2 基于最小支撐樹的區域劃分算法設G=(V，E，w)是一個連通賦權圖，頂點個數為n，T是G的一棵生成樹，T的每條邊所賦權之和稱為T的權，記為W(T).G中具有最小權的生成樹稱為G的最小支撐樹［11］.求最小支撐樹的Prim算法(反圈法)如下所述:

Step 1在連通賦權圖G中取一頂點v1相關聯的且權值最小的邊，設為e(v1v2)；

Step 2在邊集{e(v1v2)|1≤i≤2，v?{v1，v2}}中選取一條權值最小的邊記為e(viv3)；

Step 3假如已找到p個頂點v1，v2，…，vp，在邊集{e(v1v)|1≤i≤p，v?{v1，v2，…，vp}}中選取一條權值最小的邊記為e(vivp+1)，如果已經選出n-1條邊，則所有選出的邊在圖G中構成的子圖即為G的一棵最小支撐樹.

根據文獻［11］基于最小支撐樹的通用區域劃分算法描述，首先實現配送區域劃分，劃分示意圖如圖1所示.

圖1 區域劃分示意圖Fig.1 Schematic diagram of regional division

物資配送是物流的關鍵環節，其中物流公司如何安排車輛的行駛方案，直接影響到物流公司的運輸成本.因此，在配送區域確定后，需要確定的是各區域中車輛的行駛路徑，進而得到優化的車輛路徑方案.

3.3 貪婪算法求單車輛路徑問題本文設計相對于TSP問題的貪婪算法(TSPGEA)［12］，令K表示頂點集為V(K)、弧度集A(K)的完全圖(如果x和y是K中的頂點，那么xy，yx∈A(K)，|V(K)|=n).對于K中的任意弧度xy被分派為一個實數值C(xy)=CK(xy).用C(K)代表K中弧度值的和，結合遞歸程序TSPGEA(n，K，C(K))計算C(K)，在K中找到一個最小值的哈密爾頓巡回路線.TSPGEA(n，K，C(K))程序步驟:

Step 1如果n=2，得到K回路；

Step 2計算?x∈V(K)，C+(x)和C-(x)，這里

Step 3?b∈A(K)，用(C(K/xy)=C(K)-C+(x)-C-(y)+C(xy)-c(yx))計算C(K/b)；

Step 4在K中尋找a(a=xy)，使得τa(K)=min{τuw:u(K)≠w∈V(K)}；

Step 5計算T=TSPGEA(n-1，K/a，C(K/a))；

Step 6用T代替弧度為a的頂點va；

Step 7返回T.

4 實例分析

為了測試算法的有效性，運用以上算法流程，求解如下問題:現有一批物資配送任務，送貨車輛從配送中心(i=0，坐標為原點)出發，為編號是i=1，2，…，8的8個客戶配送物資.其中貨車載重量為Q=200個單位、平均速度為v=50 km/h，某天，第i個客戶所需物資的重量為qi個單位(qi＜Q)，如表1.

表1 客戶點坐標及需求量Table 1 Customer point coordinates and demand

在內存為4 GB，CPU速度為1.80 GHz的硬件環境下，使用Windows 7操作系統，利用Matlab 7.0編程求解［13］.結合最小支撐樹的區域劃分算法的設計步驟，求解過程耗時0.001 054 s，得到車輛分區方案:客戶集1、2、3 的客戶分別為2，4，5、1，3，7、6，8.

對于區域中路線的確定，結合貪婪算法的設計步驟，求解過程耗時0.014 865 s，最終得到車輛安排方案，見表2.

表2 車輛安排方案Table 2 Vehicle scheme of arrangement

根據上述結果分析，本問題算法求解耗時0.015 919 s，計算復雜度為n3，最優值為242.547 5 km.通過利用 Lingo軟件編程求解［14］耗時8 s，得到分區結果一致，運輸里程最優值為240.098 7 km，結果相差不大.但算法計算速度是Lingo的500多倍，說明本文設計的最小支撐樹與貪婪算法的混合算法求解結果準確，計算速度快.同時通過與文獻［15］中四叉樹混合蟻群算法所得最優值248 km進行比較，結果更加優異，達到了運輸成本更低的目的，說明了本文算法的有效性.

［1］陳會明.再論物資配送［J］.鐵道物資科學管理，1997，4(15):9-10.

［2］林慧丹.第三方物流［M］.上海:上海財經大學出版社，2005:101-107.

［3］Homberger J，Gehring H.A two-phase hybird evolution metaheuristics for the vehicle routing with time windows［J］.European J Oper Research，2005，162(1):220-238.

［4］李軍，郭耀煌.物流配送車輛優化調度理論與方法［M］.北京:中國物資出版社，2001.

［5］Clark G，Wright J.Scheduling of vehicles from a central depot to a number of delivery points［J］.Opens Res，1964，4.

［6］王剛.遺傳算法在VRP中的應用與研究［D］.重慶:重慶交通大學，2011.

［7］喻偉，何其超，張增桀.遺傳節約綜合算法在配送路線優化中的應用［J］.物流科技，2009，3:49-52.

［8］郎茂祥.配送車輛優化調度模型與算法［M］.北京:電子工業出版社，2009.

［9］池潔.物流配送區域劃分模型及優化計算研究［D］.重慶:重慶交通大學，2009.

［10］霍亮，安敏，李欣.一種城市物流分區配送方法的研究［J］.物流技術，2003，3:91-94.

［11］王玲娜，李興明.基于最小支撐樹的通用區域劃分算法［C］//2008年中國西部青年通信學術會議論文集，2008.

［12］Gutin G，Yeo A.Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number［J］.Discrete Appl Math，2002，119:107-116.

［13］孫祥，徐劉美，吳清.Matlab 7.0基礎教程［M］.北京:清華大學出版社，2006.

［14］汪曉銀，鄒庭榮.數學軟件與數學實驗［M］.北京:科學出版社，2008.

［15］許菁，雷定猷，鄧煜陽.基于區位理論的物流配送中心調度優化算法［J］.現代物流，2007，9:1-3.