李 寧 馨

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

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

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

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

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

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

(1)

約束條件：

(2)

(3)

(4)

(5)

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

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

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

2 節(jié)約法

2.1 基本概念

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

2.2 算法流程

算法的初始路線是n條(n是顧客點數(shù)目)僅含倉庫和一個客戶點的路線集：

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

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

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

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

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

2.3 評 價

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

3 遺傳算法

3.1 基本概念

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

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

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

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

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

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

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

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

3.2 算法流程[16]

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

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

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

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

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

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

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

3.3 評 價

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

4 禁忌搜索算法

4.1 基本概念

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

4.2 算法流程

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

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

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

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

4.3 評 價

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

5 結(jié) 論

5.1 實驗結(jié)果

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

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

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

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

5.2 實驗分析

圖2 實驗結(jié)果對比圖

用折線圖表示上述3種算法的實驗結(jié)果對比如圖2所示。

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

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

參考文獻：

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

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

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

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

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

[6] 邱月.交叉熵方法在車輛路徑問題中的應(yīng)用研究[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ā)展趨勢[A]. 王建方.中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集[C].香港：Global-Link出版社，2004：997-1002

[9] 陳曉偉，張悟移，耿繼武.節(jié)約法在配送路線選擇中的應(yīng)用[J].昆明理工大學(xué)學(xué)報：自然科學(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].計算機工程與應(yīng)用，2005，41(27)：227-229

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

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

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

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

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

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

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

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