最小支撐樹混合貪婪算法求解車輛路徑問(wèn)題

張 恒，冉 雨，于卓岑，俸 衛(wèi)*

(1.內(nèi)江師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，四川內(nèi)江641100； 2.內(nèi)江師范學(xué)院四川省高等學(xué)校數(shù)值仿真重點(diǎn)實(shí)驗(yàn)室，四川內(nèi)江641100)

物資配送［1］是物資流通企業(yè)按照用戶的訂貨需求及其標(biāo)準(zhǔn)，以最經(jīng)濟(jì)的方式對(duì)貨物進(jìn)行采購(gòu)、儲(chǔ)存、加工、分揀、配裝、運(yùn)輸，直到把貨物交到用戶手中的物資流通活動(dòng).由于物流對(duì)國(guó)民經(jīng)濟(jì)的重大影響，物流系統(tǒng)化、合理化能創(chuàng)造巨大經(jīng)濟(jì)利益，因此物流與商流、信息流并稱為現(xiàn)代經(jīng)濟(jì)的三大支柱，被稱為繼勞動(dòng)力、資源之后的“第三大利潤(rùn)源泉”［2］.而如今，物流企業(yè)面臨的現(xiàn)狀是服務(wù)效率較低，服務(wù)成本較高.

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

文章將針對(duì)一定客戶規(guī)模的物資配送進(jìn)行研究，建立區(qū)域劃分——路徑優(yōu)化模型，設(shè)計(jì)最小支撐樹混合貪婪算法求解.最終達(dá)到物流企業(yè)物資配送低成本，高效率的目的.

1 問(wèn)題描述

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

2 車輛路線問(wèn)題的數(shù)學(xué)模型

車輛路線問(wèn)題假設(shè)如下:

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

2)只有一個(gè)配送中心，并以配送中心為路線的起止點(diǎn)；

3)有l(wèi)個(gè)客戶且每個(gè)客戶在不同的地理位置；

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

5)每個(gè)客戶有且只被服務(wù)一次；

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

7)對(duì)被一輛車所服務(wù)的客戶集的總需求量不超過(guò)車輛的載重量.

目標(biāo)為每輛車設(shè)計(jì)一條路線，使得總運(yùn)輸里程最小，并且確保全部客戶的需求得到滿足.定義0-1決策變量:

假設(shè)z為k個(gè)客戶集的總運(yùn)輸里程，車輛路線問(wèn)題的模型［8］如下:

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

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

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

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

建立區(qū)域劃分的數(shù)學(xué)模型［10］如下所示:

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

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

Step 1在連通賦權(quán)圖G中取一頂點(diǎn)v1相關(guān)聯(lián)的且權(quán)值最小的邊，設(shè)為e(v1v2)；

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

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

根據(jù)文獻(xiàn)［11］基于最小支撐樹的通用區(qū)域劃分算法描述，首先實(shí)現(xiàn)配送區(qū)域劃分，劃分示意圖如圖1所示.

圖1 區(qū)域劃分示意圖Fig.1 Schematic diagram of regional division

物資配送是物流的關(guān)鍵環(huán)節(jié)，其中物流公司如何安排車輛的行駛方案，直接影響到物流公司的運(yùn)輸成本.因此，在配送區(qū)域確定后，需要確定的是各區(qū)域中車輛的行駛路徑，進(jìn)而得到優(yōu)化的車輛路徑方案.

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

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

Step 2計(jì)算?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))計(jì)算C(K/b)；

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

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

Step 6用T代替弧度為a的頂點(diǎn)va；

Step 7返回T.

4 實(shí)例分析

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

表1 客戶點(diǎn)坐標(biāo)及需求量Table 1 Customer point coordinates and demand

在內(nèi)存為4 GB，CPU速度為1.80 GHz的硬件環(huán)境下，使用Windows 7操作系統(tǒng)，利用Matlab 7.0編程求解［13］.結(jié)合最小支撐樹的區(qū)域劃分算法的設(shè)計(jì)步驟，求解過(guò)程耗時(shí)0.001 054 s，得到車輛分區(qū)方案:客戶集1、2、3 的客戶分別為2，4，5、1，3，7、6，8.

對(duì)于區(qū)域中路線的確定，結(jié)合貪婪算法的設(shè)計(jì)步驟，求解過(guò)程耗時(shí)0.014 865 s，最終得到車輛安排方案，見表2.

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

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

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

［2］林慧丹.第三方物流［M］.上海:上海財(cái)經(jīng)大學(xué)出版社，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］李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法［M］.北京:中國(guó)物資出版社，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中的應(yīng)用與研究［D］.重慶:重慶交通大學(xué)，2011.

［7］喻偉，何其超，張?jiān)鲨?遺傳節(jié)約綜合算法在配送路線優(yōu)化中的應(yīng)用［J］.物流科技，2009，3:49-52.

［8］郎茂祥.配送車輛優(yōu)化調(diào)度模型與算法［M］.北京:電子工業(yè)出版社，2009.

［9］池潔.物流配送區(qū)域劃分模型及優(yōu)化計(jì)算研究［D］.重慶:重慶交通大學(xué)，2009.

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

［11］王玲娜，李興明.基于最小支撐樹的通用區(qū)域劃分算法［C］//2008年中國(guó)西部青年通信學(xué)術(shù)會(huì)議論文集，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基礎(chǔ)教程［M］.北京:清華大學(xué)出版社，2006.

［14］汪曉銀，鄒庭榮.數(shù)學(xué)軟件與數(shù)學(xué)實(shí)驗(yàn)［M］.北京:科學(xué)出版社，2008.

［15］許菁，雷定猷，鄧煜陽(yáng).基于區(qū)位理論的物流配送中心調(diào)度優(yōu)化算法［J］.現(xiàn)代物流，2007，9:1-3.