采用不同算法求解車輛路徑問題的對(duì)比分析

李 寧 馨

(合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009)

進(jìn)入21世紀(jì)以來(lái)，物流產(chǎn)業(yè)作為一個(gè)新興產(chǎn)業(yè)迅猛發(fā)展，被認(rèn)為“降低資源消耗”和“提高勞動(dòng)生產(chǎn)率”兩大企業(yè)利潤(rùn)來(lái)源之后的“第三利潤(rùn)源泉”[1]?！笆濉币?guī)劃指出要構(gòu)建綜合交通運(yùn)輸體系，大力發(fā)展現(xiàn)代物流業(yè)，大力推進(jìn)節(jié)能降耗、實(shí)施區(qū)域物流總體發(fā)展戰(zhàn)略、大力發(fā)展新一代信息技術(shù)等重點(diǎn)任務(wù)[2]。車輛路徑問題作為物流管理領(lǐng)域關(guān)注的熱點(diǎn)和重點(diǎn)問題之一，從提出開始就引起運(yùn)籌學(xué)、管理學(xué)、計(jì)算機(jī)應(yīng)用、組合數(shù)學(xué)、圖論等學(xué)科的專家和學(xué)者的高度重視[3]。研究車輛路徑問題不僅可以幫助企業(yè)提高服務(wù)水平，為顧客提供快捷、準(zhǔn)時(shí)的服務(wù)，而且有助于企業(yè)降低運(yùn)輸成本，提高車輛利用效率，縮短生產(chǎn)周期，加速資金周轉(zhuǎn)，實(shí)現(xiàn)資源的合理配置，對(duì)資源節(jié)約和環(huán)境保護(hù)都有重要意義[4]。

1 標(biāo)準(zhǔn)車輛路徑問題的模型

標(biāo)準(zhǔn)車輛路徑問題是最基本的車輛路徑問題，其他不同類型的車輛路徑問題都是在標(biāo)準(zhǔn)車輛路徑問題的基礎(chǔ)上擴(kuò)展而來(lái)的。通常的標(biāo)準(zhǔn)車輛問題是指帶裝載能力車輛路徑問題(Capacitated Vehicle Routing Problem，簡(jiǎn)稱CVRP)，即每個(gè)車輛都有最大容量的限制。標(biāo)準(zhǔn)車輛路徑問題表示為一個(gè)完備圖G=(V，A)，V是頂點(diǎn)集，A是弧集。其中V={0，1，…，n}，0是倉(cāng)庫(kù)點(diǎn)；1，…，n是待服務(wù)的客戶點(diǎn)；A={(i，j)|i，j∈V，i≠j}。

此外，為了說明問題，定義以下符號(hào)：cij，對(duì)A中的任意一條弧(i，j)賦予一個(gè)非負(fù)值cij作為它的權(quán)(weight)，它根據(jù)實(shí)際需要代表不同的含義，如距離，時(shí)間，費(fèi)用等等。Q為車輛最大容量；qi為客戶點(diǎn)i的貨物需求。?i∈V，i≠0，都有qi≤Q。R為車輛集，R={0，1，…，m}。

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

(1)

約束條件：

(2)

(3)

(4)

(5)

模型式(1)是目標(biāo)函數(shù)，意義是實(shí)現(xiàn)總路程最小化；式(2)表示每個(gè)顧客點(diǎn)都被服務(wù)，且僅被服務(wù)一次；式(3)表示車輛k是否訪問j是由其他點(diǎn)到j(luò)的總和；式(4)表示車輛是否k訪問j是由j到其他點(diǎn)的總和；式(5)表示每輛車的貨物重量不超過其載重。

車輛路徑問題的解法大體分為兩種：精確解法和啟發(fā)式解法。Lenstra JK和Rinnooy Kan[5]證明了車輛路徑問題是組合優(yōu)化領(lǐng)域中的強(qiáng)NP-hard問題，精確算法只能有效求解的需求點(diǎn)數(shù)量和路段數(shù)較少的車輛路徑問題[6]。Bruce L. Golden等指出[7]，對(duì)于客戶點(diǎn)超過50個(gè)的車輛路徑問題，無(wú)法利用精確解法得到一致最優(yōu)解，因此采用啟發(fā)式算法來(lái)尋求車輛路徑問題的滿意解就成為車輛路徑問題研究的重點(diǎn)?，F(xiàn)把常見的車輛路徑問題的解法歸納如圖1所示[8]。

圖1車輛路徑問題的解法分類

2 節(jié)約法

2.1 基本概念

節(jié)約法是Clark和Wright于1964年提出來(lái)求解標(biāo)準(zhǔn)車輛路徑問題的，又稱節(jié)約里程法或CW算法，它基于節(jié)約原則逐步構(gòu)造車輛路線，是解決車輛路徑問題的一種經(jīng)典啟發(fā)式算法。節(jié)約法的基本原理很簡(jiǎn)單：三角形任意兩邊之和大于第三邊。節(jié)約法核心思想是依次將車輛路徑問題中的兩條路徑合并為一條路徑，使得合并后的運(yùn)輸距離能夠當(dāng)前最大幅度的節(jié)約，直到不能再進(jìn)行下去，此時(shí)對(duì)剩余的客戶重復(fù)相同的過程，直至所有的邊都被考慮。節(jié)約法原理簡(jiǎn)單，易于實(shí)現(xiàn)，車輛路徑問題很多啟發(fā)式算法利用節(jié)約法來(lái)產(chǎn)生初始解。

2.2 算法流程

算法的初始路線是n條(n是顧客點(diǎn)數(shù)目)僅含倉(cāng)庫(kù)和一個(gè)客戶點(diǎn)的路線集：

Ru={Ri|Ri=(0，j，0)}，j=1，2，…，n，i∈R.

Step 1：計(jì)算各邊節(jié)約值sij=ci0+c0j-cij，i，j=1，2，…，n且i≠j；

Step 2：將Step 1中計(jì)算出來(lái)的節(jié)約值按從大到小的順序降序排列；

Step 3：按照Step 2中排列出來(lái)的順序，從大到小依次檢查各邊，若刪去(i，0) 和(0，j)并以(i，j)代替仍能夠保持解的可行性，則選擇滿足條件的兩條路線進(jìn)行合并。

Step 4：操作Step 3直到?jīng)]有可合并的路線，現(xiàn)在得到的路線就是最終路線。

2.3 評(píng) 價(jià)

節(jié)約法是一種簡(jiǎn)便而且易行的算法，形象體現(xiàn)出了優(yōu)化運(yùn)輸?shù)倪^程而且思路簡(jiǎn)單清晰、便于執(zhí)行，因此在國(guó)內(nèi)外物流配送過程中受到青睞。節(jié)約法也有它的缺點(diǎn)：利用節(jié)約法來(lái)決定配送路線的方法只考慮了運(yùn)輸距離，而完全沒有考慮其他因素。 節(jié)約法適合應(yīng)用于那些客戶需求固定而且對(duì)于送貨時(shí)間不急迫的場(chǎng)合，這顯然與現(xiàn)在有較大不確定性的市場(chǎng)不符，這就限制了節(jié)約法的使用范圍[9]。

3 遺傳算法

3.1 基本概念

1975年，Holland出版了第一本系統(tǒng)論述遺傳算法的學(xué)術(shù)專著“Adaptation in and Artificial Systems”[10]，書中將達(dá)爾文的“優(yōu)勝劣汰，適者生存”的思想應(yīng)用到人工系統(tǒng)的自適應(yīng)行為中，此后Holland將這種算法加以發(fā)展和推廣，并正式命名為遺傳算法。1992年出版的“Genetic algorithms+Data Structures = Evolution Programs”[11]一書推動(dòng)了最優(yōu)化問題中遺傳算法的應(yīng)用。1996年，J.Lawrence最先將遺傳算法應(yīng)用到車輛路徑問題的研究。學(xué)者們通過對(duì)編碼方式、選擇方式、交叉方式、變異方式進(jìn)行深入研究，在簡(jiǎn)單遺傳算法基礎(chǔ)上提出了多種改進(jìn)的遺傳算法，改進(jìn)的遺傳算法提高了遺傳算法的運(yùn)行效率和求解質(zhì)量?，F(xiàn)就遺傳算法中的基本概念[12]介紹如下：

(1) 編碼方法。解的編碼是遺傳算法的基礎(chǔ)工作之一，常見的編碼方式有二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼等[13]。具體在某一問題中選擇何種編碼方式，應(yīng)充分考慮到問題的復(fù)雜度、解的連續(xù)性、空間大小等因素[14]。

(2) 初始群體的生成和群體大小的確定[15]。初始群體通常采取隨機(jī)生成的方式或其他生成方式，通過有效方式產(chǎn)生的初始解可能會(huì)有助于減少進(jìn)化次數(shù)，但也可能會(huì)導(dǎo)致程序過早陷入局部最優(yōu)群體中。群體中個(gè)體的個(gè)數(shù)越多，進(jìn)化到最優(yōu)解的可能性越大，但復(fù)雜度也會(huì)增大。

(3) 適應(yīng)度函數(shù)。對(duì)于無(wú)約束的優(yōu)化問題，可直接選取為目標(biāo)函數(shù)或目標(biāo)函數(shù)的簡(jiǎn)單變形。對(duì)于有約束的優(yōu)化問題，適應(yīng)度函數(shù)要由目標(biāo)函數(shù)和約束條件共同決定。因此，適應(yīng)度函數(shù)是為了在滿足約束條件的解中，使能夠讓目標(biāo)函數(shù)越優(yōu)的解越有可能保留下來(lái)。

(4) 選擇算子。常見的選擇算子主要有賭盤輪轉(zhuǎn)法、波爾茲曼選擇法、排序選擇方法、聯(lián)賽方法、精英選擇方法、穩(wěn)態(tài)選擇方法等。其中最常用的是賭盤輪轉(zhuǎn)法，賭盤輪轉(zhuǎn)法先計(jì)算每個(gè)個(gè)體的適應(yīng)度，再計(jì)算每個(gè)個(gè)體適應(yīng)度的比例，比例越大的個(gè)體越容易被選擇，但不意味著適應(yīng)度高的個(gè)體一定被選擇。

(5) 交叉算子。需要先選擇兩個(gè)個(gè)親體，再進(jìn)行配對(duì)產(chǎn)生新的個(gè)體。一般都是隨機(jī)配對(duì)，交叉規(guī)則有雙親遺傳法、主個(gè)體規(guī)則、單親遺傳規(guī)則等。為了保證產(chǎn)生的個(gè)體是可行解，采用如下方法步驟來(lái)實(shí)現(xiàn)：對(duì)第二個(gè)親體做一個(gè)拷貝；從第一個(gè)親體選擇任一部分；在后代里做最小的變化以完成所選模式。

(6) 變異算子。變異操作是模擬自然界的基因突變，得到新個(gè)體的過程。變異方法也有多種，本文采用的是交叉變異，即隨機(jī)選擇個(gè)體的兩個(gè)基因并將其交換，用新得到的個(gè)體代替舊的個(gè)體。

(7) 終止準(zhǔn)則。終止準(zhǔn)則有設(shè)定最大遺傳次數(shù)，檢測(cè)收斂程度，精英策略保留最佳個(gè)體等方法。

3.2 算法流程[16]

(1) 確定編碼方法、適應(yīng)度函數(shù)、群體大小、選擇算子、交叉算子、變異算子、交叉概率、變異概率等算法參數(shù)；

(2) 隨機(jī)產(chǎn)生解的初始群體；

(3) 計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度；

(4) 選擇，按(1)中確定的選擇算子，從舊群體中選出個(gè)體組成群體1，群體1的規(guī)模與舊群體相同，用群體1代替舊群體，舊群體中的個(gè)體可能在群體1中多次出現(xiàn)，也可能不出現(xiàn)；

(5) 交叉，根據(jù)(1)中確定的交叉算子和交叉概率，在群體1上反復(fù)隨機(jī)選擇兩個(gè)個(gè)體發(fā)生交叉，獲得規(guī)模與群體1相同的群體2，用群體2代替舊群體；

(6) 突變，根據(jù)(1)中確定的變異算子和變異概率，群體2中每個(gè)個(gè)體發(fā)生突變，獲得群體3，用群體3代替舊群體；

(7) 如果滿足終止準(zhǔn)則，則算法停止，輸出群體中適應(yīng)度最高的個(gè)體作為結(jié)果；否則，返回(3)。

3.3 評(píng) 價(jià)

遺傳算法是模擬自然界中優(yōu)勝劣汰和生物個(gè)體中染色體的交叉和變異來(lái)處理現(xiàn)實(shí)中優(yōu)化問題的一類新方法。遺傳算法適應(yīng)性強(qiáng)，且是全局優(yōu)化[17]。另外，遺傳算法能用較少的數(shù)字串來(lái)搜索大量區(qū)域，這是遺傳算法優(yōu)于其他優(yōu)化方法的最主要原因。遺傳算法通用性強(qiáng)，易于移植，魯棒性強(qiáng)，因此在優(yōu)化領(lǐng)域得到廣泛應(yīng)用。另外，若變異概率0

4 禁忌搜索算法

4.1 基本概念

Osman、Gendreau、Taillard、Xu和Kelly等人都曾研究過利用禁忌搜索算法來(lái)求解車輛路徑問題。禁忌搜索算法是一種全局搜索算法，禁忌搜索算法從一個(gè)初始可行解作為當(dāng)前解，在它的鄰域范圍內(nèi)進(jìn)行試探，選擇讓目標(biāo)函數(shù)值趨于最優(yōu)的方向移動(dòng)。為了避免陷入局部最優(yōu)，禁忌搜索算法采用建立禁忌表的方法，把近幾次移動(dòng)的反方向移動(dòng)存入禁忌表，以避免迂回搜索。此外，為了盡可能不錯(cuò)過產(chǎn)生最優(yōu)解的移動(dòng)，禁忌搜索算法還采用了破禁策略，因此處在禁忌表中的移動(dòng)并非是絕對(duì)禁止的[18，19]。

4.2 算法流程

(1) 初始化禁忌表為空，初始解為節(jié)約法產(chǎn)生的解，初始化當(dāng)前得到的最優(yōu)目標(biāo)函數(shù)值為初始解對(duì)應(yīng)的目標(biāo)函數(shù)值；

(2) 在當(dāng)前解的鄰域內(nèi)搜索，根據(jù)選擇策略決定移動(dòng)方向，并更新禁忌表和當(dāng)前最優(yōu)目標(biāo)函數(shù)值；

(3) 重復(fù)(2)，直到滿足終止準(zhǔn)則為止；

(4) 現(xiàn)在得到的最優(yōu)解就是最終的最優(yōu)解。

4.3 評(píng) 價(jià)

在啟發(fā)式算法中禁忌搜索算法的求解質(zhì)量最高，是目前最為有效的求解車輛路徑問題的方法，在多個(gè)標(biāo)準(zhǔn)測(cè)試集上取得了令人興奮的結(jié)果。在算法實(shí)施過程中發(fā)現(xiàn)，禁忌搜索算法的搜索速度快，但是禁忌搜索算法對(duì)于初始解具有較強(qiáng)依賴性，較差的初始解會(huì)使得收斂過程放慢。此外禁忌搜索算法的搜索過程是從點(diǎn)到點(diǎn)的，因此全局搜索能力有待提高[20]。

5 結(jié) 論

5.1 實(shí)驗(yàn)結(jié)果

上述4種算法采用matlab語(yǔ)言編寫了相應(yīng)程序，在同一Intel Core i3、2G RAM、計(jì)算機(jī)上進(jìn)行，選取了10個(gè)標(biāo)準(zhǔn)數(shù)據(jù)測(cè)試集合來(lái)進(jìn)行試驗(yàn)。實(shí)驗(yàn)結(jié)果分別如表1、表2、表3所示。

表1 節(jié)約法在標(biāo)準(zhǔn)數(shù)據(jù)測(cè)試集上的實(shí)驗(yàn)結(jié)果

表2 遺傳算法在標(biāo)準(zhǔn)數(shù)據(jù)測(cè)試集上的實(shí)驗(yàn)結(jié)果

表3 禁忌搜索算法在標(biāo)準(zhǔn)數(shù)據(jù)測(cè)試集上的實(shí)驗(yàn)結(jié)果

5.2 實(shí)驗(yàn)分析

圖2 實(shí)驗(yàn)結(jié)果對(duì)比圖

用折線圖表示上述3種算法的實(shí)驗(yàn)結(jié)果對(duì)比如圖2所示。

從圖2可以看出，禁忌搜索算法的結(jié)果大體優(yōu)于遺傳算法。由于本文中把節(jié)約法的解作為遺傳算法和禁忌搜索算法的初始解，因此它的結(jié)果與其他兩種算法的結(jié)果沒有可比性。在實(shí)驗(yàn)中發(fā)現(xiàn)，盡管節(jié)約法與其他兩種算法表示解的數(shù)據(jù)結(jié)構(gòu)不同，在其他算法中節(jié)約法的解可能與原解代表的意義不同，但這樣的初始解仍能明顯改進(jìn)遺傳算法和禁忌搜索算法的解的質(zhì)量和縮短迭代次數(shù)。

節(jié)約法在3種算法中所需要的運(yùn)行時(shí)間最少，求解結(jié)果幾乎也是最差的。但是經(jīng)過對(duì)比可以發(fā)現(xiàn)，節(jié)約法的結(jié)果和其他兩種算法相比，結(jié)果相差不多。因此，在對(duì)解的質(zhì)量要求不是很高的情況下，節(jié)約法是首選。遺傳算法是一種隨機(jī)性算法，想要得到理想的結(jié)果可能要經(jīng)過多次試驗(yàn)才能得到；禁忌搜索算法是一種確定性算法，但在迭代次數(shù)達(dá)到一定程度之后，即使增加迭代次數(shù)，也并不能起到明顯改善結(jié)果的作用。禁忌搜索算法在大部分情況下得到的結(jié)果優(yōu)于遺傳算法，但這是以花費(fèi)更多的計(jì)算時(shí)間為代價(jià)的。禁忌搜索算法適合結(jié)點(diǎn)數(shù)目較少的情況，隨著結(jié)點(diǎn)數(shù)目增長(zhǎng)，計(jì)算時(shí)間大幅增長(zhǎng)，且結(jié)果不甚理想。

參考文獻(xiàn)：

[1] 李永先.車輛路徑問題的仿真模型及優(yōu)化方法研究[D].大連：大連理工大學(xué)管理學(xué)院，2008

[2] 國(guó)家發(fā)展和改革委員會(huì)經(jīng)濟(jì)運(yùn)行調(diào)節(jié)局，南開大學(xué)現(xiàn)代物流研究中心.中國(guó)現(xiàn)代物流發(fā)展報(bào)告[M].北京：中國(guó)物資出版社，2011：87-88

[3] 李相勇.車輛路徑問題模型及算法研究[D].上海：上海交通大學(xué)安泰經(jīng)濟(jì)管理學(xué)院，2007

[4] 鐘石泉.物流配送車輛路徑優(yōu)化方法研究[D].天津：天津大學(xué)經(jīng)濟(jì)與管理學(xué)院，2007

[5] LENSTRA J, RINNOOY K.Complexity ofvehicle routingand schedulingproblem.Networks，1981(11)：221-227

[6] 邱月.交叉熵方法在車輛路徑問題中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(34)：242-248

[7] BRUCE L，EDWARD A，JAMES P.Kelly，I-Ming Chao. Fleet Management and Logistics [M].London：Kluwer Academic Publishers，1998

[8] 符卓，陳斯衛(wèi).車輛路徑問題的研究現(xiàn)狀與發(fā)展趨勢(shì)[A]. 王建方.中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集[C].香港：Global-Link出版社，2004：997-1002

[9] 陳曉偉，張悟移，耿繼武.節(jié)約法在配送路線選擇中的應(yīng)用[J].昆明理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，28(4)：140-143

[10] HOLLAND J. Adaptation in Natural and Artificial Systems [M].Massachusetts：MIT Press，1975

[11] Michalewicz Z. Genetic algorithms+Data Structures = Evolution Programs[M].Berlin：Springer-Verlag，1994

[12] 柳林，朱建榮.基于遺傳算法的物流配送路徑優(yōu)化問題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(27)：227-229

[13] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].2版.北京：清華大學(xué)出版社，2005：52-53，113-130

[14] 王飛朝.遺傳算法編程分析[J].火控雷達(dá)技術(shù)，2005，34(6)：63-66

[15] 張華慶，張喜.改進(jìn)遺傳算法在車輛路徑問題中的應(yīng)用[J].交通信息與安全，2012，30(5)：81-86

[16] 劉峽壁.人工智能導(dǎo)論：方法與系統(tǒng)[M].北京：國(guó)防工業(yè)出版社，2008：233-244，263-266

[17] 金菊良，楊曉華，丁晶.標(biāo)準(zhǔn)遺傳算法的改進(jìn)方案-加速遺傳算法[J].系統(tǒng)工程與實(shí)踐，2001，21(4)：8-13

[18] 張穎，劉艷秋.軟計(jì)算方法[M].北京：科學(xué)出版社，2002：134-139

[19] 郎茂祥，胡思繼. 車輛路徑問題的禁忌搜索算法研究[J].管理工程學(xué)報(bào)，2004，18(1)：81-84

[20] 張德東.物流配送中車輛路徑問題研究[D].天津：天津大學(xué)經(jīng)濟(jì)與管理學(xué)院，2006