【正文】 好壞對(duì)其搜索質(zhì)量影響不大，能較好跳出局部最優(yōu)，因此易于與其他算法構(gòu)高效的組合算法。但冷卻溫度T難以控制，因?yàn)橹挥蠺的下降與lg(1+ )成比rt例( 為模擬時(shí)間)才能得到最優(yōu)解。在實(shí)際應(yīng)用中，一般只能求得近似解，其計(jì)算rt量相當(dāng)大，十分耗時(shí)，影響了其實(shí)用性 [15]。?禁忌搜索算法(Tabu Search Algorithm) 帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究20禁忌搜索(簡(jiǎn)稱TS)，最早由Glover提出，它是對(duì)局部鄰域搜索的一種擴(kuò)展，是一種全局迭代尋優(yōu)算法，是對(duì)人類智力過(guò)程的一種模擬。禁忌(tabu或者taboo)表示禁止的意思。 禁忌搜索通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)特赦規(guī)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效搜索以最終實(shí)現(xiàn)全局優(yōu)化。禁忌搜索也是人工智能的一種體現(xiàn)，其最重要的思想是標(biāo)記對(duì)應(yīng)已搜索到的局部最優(yōu)解的一些對(duì)象，并在進(jìn)一步的迭代搜索中盡量避開這些對(duì)象，而不是絕對(duì)禁止循環(huán)，從而保證對(duì)解空間中的不同區(qū)域進(jìn)行有效的搜索。這個(gè)算法構(gòu)造一個(gè)解的序列(順序)然后進(jìn)行改進(jìn)步驟，逐次產(chǎn)生的車輛路線可能是不可行的，它們必須用可行的目標(biāo)罰函數(shù)來(lái)測(cè)量并不斷得到改正。Tabu搜索法的特點(diǎn)是:對(duì)目標(biāo)函數(shù)要求較少，理論上可以找到全局最優(yōu)解；搜索速度快，能找到非常好的次優(yōu)解；局部搜索能力強(qiáng)，不易陷入局部最優(yōu)，適于與其他算法組成高效組合算法。搜索過(guò)程是單點(diǎn)操作，大規(guī)模尋優(yōu)特性較弱，易失去系統(tǒng)最優(yōu)解；搜索效率對(duì)初始解的依賴性強(qiáng)；其搜索鄰域結(jié)構(gòu)與禁忌表的結(jié)構(gòu)需要精心構(gòu)造。?蟻群算法(Ants Colony Algorithm)蟻群算法（簡(jiǎn)稱AC）, , 受到對(duì)真實(shí)蟻群行為研究的啟發(fā)而首先提出的。算法通過(guò)模擬蟻群搜索食物的過(guò)程，達(dá)到求解比較困難的組合優(yōu)化問(wèn)題之目的。該方法的主要特點(diǎn)是:正反饋、分布式計(jì)算、易于與其他啟發(fā)式算法相結(jié)合。正反饋過(guò)程使得該方法能很快發(fā)現(xiàn)較好解；分布式計(jì)算使得該方法易于并行實(shí)現(xiàn)；易于與啟發(fā)式算法相結(jié)合使得該方法具有很好的可擴(kuò)展性，但該算法一般需要較長(zhǎng)的搜索時(shí)間，對(duì)于大規(guī)模優(yōu)化問(wèn)題，這是一個(gè)很大的障礙；而且該方法容易出現(xiàn)停滯現(xiàn)象,即搜索進(jìn)行到一定程度后，所有個(gè)體所發(fā)現(xiàn)的解完全一致，不能對(duì)解空間進(jìn)一步進(jìn)行搜索，不利于發(fā)現(xiàn)更好的解。?神經(jīng)網(wǎng)絡(luò)算法(Artificial Neural Networks)神經(jīng)網(wǎng)絡(luò)優(yōu)化算法（簡(jiǎn)稱AN）是利用神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的協(xié)同并行運(yùn)算能力來(lái)構(gòu)造的優(yōu)化算法，它將實(shí)際問(wèn)題的優(yōu)化解與神經(jīng)網(wǎng)絡(luò)的穩(wěn)定狀態(tài)相對(duì)應(yīng)，把對(duì)實(shí)際問(wèn)題的優(yōu)化過(guò)程映射為神經(jīng)網(wǎng)絡(luò)系統(tǒng)的演化過(guò)程。神經(jīng)網(wǎng)絡(luò)算法的特點(diǎn)是:魯棒性好，對(duì)優(yōu)化目標(biāo)函數(shù)要求少，理論上能找到最優(yōu)解；搜索效率高，計(jì)算速度相當(dāng)快，帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究21適合于實(shí)時(shí)處理；易于在并行機(jī)上實(shí)現(xiàn)并行處理。但卻易于陷入學(xué)習(xí)停滯和局部最優(yōu)；對(duì)于一些費(fèi)用和約束的時(shí)變性不易處理；在構(gòu)造能量函數(shù)時(shí)，有關(guān)系數(shù)的選取尚未有理論指導(dǎo) [16]。?遺傳算法(Geic Algorithm)遺傳算法(簡(jiǎn)稱GA)。遺傳算法是基于生物進(jìn)化和隨機(jī)選擇的全局性搜索算法，它模擬生物進(jìn)化的基本過(guò)程，用數(shù)碼串來(lái)類比生物中的染色個(gè)體，通過(guò)選擇，交叉，變異等遺傳算子來(lái)仿真生物的基本進(jìn)化過(guò)程，利用適應(yīng)度函數(shù)來(lái)表示染色個(gè)體所蘊(yùn)涵的問(wèn)題解質(zhì)量的優(yōu)良，通過(guò)種群的不斷“更新?lián)Q代”，從而提高每代種群的平均適應(yīng)度，并在此基礎(chǔ)上，使得最優(yōu)異個(gè)體所代表的問(wèn)題解逼近問(wèn)題的全局最優(yōu)解。綜上所述可以將VRPTW的求解方法歸結(jié)為如下圖型： 圖31 VRPTW求解方法VRPTW 求解方法精確求解方法 啟發(fā)式求解方法精確求解方法K|樹方法割平面法整數(shù)線性規(guī)劃法拉格朗日分解法列生成方法動(dòng)態(tài)規(guī)劃法網(wǎng)絡(luò)流算法帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究22圖32 精確求解方法圖33 啟發(fā)式求解方法啟發(fā)式求解方法方法改進(jìn)啟發(fā)式方法初始啟發(fā)式方法不完全搜索樹節(jié)約法兩階段法插入法掃描法全局優(yōu)化神經(jīng)網(wǎng)絡(luò)模擬退火蟻群算法禁忌搜索遺傳算法局部?jī)?yōu)化路徑間路徑內(nèi)帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究23 遺傳算法《Adaptation in Naturaland Artificial Systems》中正式提出了遺傳算法的基本概念以來(lái)，經(jīng)過(guò)短短二十多年的發(fā)展，作為一種適合大規(guī)模操作的智能算法，遺傳算法不僅在理論上日趨成熟，而且在工程應(yīng)用上也得到豐碩的成果，得到越來(lái)越多研究者的關(guān)注。遺傳算法被證明為很適合用來(lái)優(yōu)化多目標(biāo)，其機(jī)理在于大量個(gè)體可并行搜尋多個(gè)準(zhǔn)則，最終找到問(wèn)題的最佳有效解。 遺傳算法的生物遺傳學(xué)基礎(chǔ)達(dá)爾文的生物進(jìn)化論闡述了這樣一種理念，“適者生存，優(yōu)勝劣汰”。在生物自然環(huán)境中，生物種群的自然繁衍，生存，發(fā)展，最終取決于它對(duì)自然環(huán)境的適應(yīng)能力。當(dāng)一個(gè)種群相對(duì)其他種群，對(duì)周圍的環(huán)境能夠顯示出良好的適應(yīng)能力，它將在生物競(jìng)爭(zhēng)中處于優(yōu)勢(shì)地位，獲取較大的生存機(jī)會(huì)，反之，該種群則趨向于消亡。所以，一個(gè)種群的優(yōu)異的適應(yīng)能力是該種群得以繁衍發(fā)展的根本。從達(dá)爾文的進(jìn)化論可以看出，生物環(huán)境對(duì)生物的進(jìn)化主要通過(guò)三個(gè)途徑來(lái)進(jìn)行:選擇，交叉和變異。 遺傳算法的基本概念遺傳算法是基于生物進(jìn)化和隨機(jī)選擇的全局性搜索算法，它模擬生物進(jìn)化的基本過(guò)程，用數(shù)碼串來(lái)類比生物中的染色個(gè)體，通過(guò)選擇，交叉，變異等遺傳算子來(lái)仿真生物的基本進(jìn)化過(guò)程，利用適應(yīng)度函數(shù)來(lái)表示染色個(gè)體所蘊(yùn)涵的問(wèn)題解的質(zhì)量的優(yōu)良，通過(guò)種群的不斷“更新?lián)Q代”，從而提高每代種群的平均適應(yīng)度，并在此基礎(chǔ)上，使得最優(yōu)異個(gè)體所代表的問(wèn)題解逼近問(wèn)題的全局最優(yōu)解 [17]。 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法(也稱基本遺傳算法或簡(jiǎn)單遺傳算法，Simple Geic Algorithm，簡(jiǎn)稱 SGA)是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì)象，只使用基本遺傳算子——選擇算子、交叉算子和變異算子。其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究24是其他一些遺傳算法的基礎(chǔ)。它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。選擇、交叉和變異是遺傳算法的 3 個(gè)主要操作算子，它們構(gòu)成了遺傳操作，使遺傳算法具有了其他傳統(tǒng)方法沒(méi)有的特點(diǎn)。 遺傳算法的特點(diǎn)? 遺傳算法與傳統(tǒng)優(yōu)化技術(shù)相比，有很大不同。具體體現(xiàn)在：1)遺傳算法運(yùn)算的是解集的編碼，而非解集本身；2)遺傳算法的搜索始于一個(gè)種群，而非單個(gè)解；3)遺傳算法只使用報(bào)酬信息即適應(yīng)值函數(shù)，而非導(dǎo)數(shù)或其他輔助知識(shí)；4)遺傳算法采用概率的，而非確定的狀態(tài)轉(zhuǎn)移規(guī)則。遺傳算法具有隱式并行性和全局搜索性兩大特點(diǎn)。遺傳算法對(duì)問(wèn)題的依賴性小，對(duì)其求解函數(shù)要求簡(jiǎn)單，魯棒性強(qiáng)，實(shí)現(xiàn)簡(jiǎn)單高效，因而，遺傳算法從它被提出以來(lái)，一直受到研究者的普遍關(guān)注，并且在函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、組合優(yōu)化、人工神經(jīng)元網(wǎng)絡(luò)訓(xùn)練、自動(dòng)程序設(shè)計(jì)、專家知識(shí)系統(tǒng)等領(lǐng)域都取得了廣泛的應(yīng)用。? 遺傳算法具體優(yōu)點(diǎn)如下:1)對(duì)可行解表示的廣泛性遺傳算法的處理對(duì)象不是參數(shù)本身，而是針對(duì)那些通過(guò)參數(shù)集進(jìn)行編碼得到的基因個(gè)體。此編碼操作使得遺傳算法可以直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作。所謂結(jié)構(gòu)對(duì)象，泛指集合、序列、矩陣、樹、圖、鏈和表等各種一維或二維甚至多維結(jié)構(gòu)形式的對(duì)象。這一特點(diǎn)使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。 2)群體搜索特性許多傳統(tǒng)的搜索方法都是單點(diǎn)搜索，這種點(diǎn)對(duì)點(diǎn)的搜索方法，對(duì)于多峰分布的搜索空間常常會(huì)陷于局部的某個(gè)單峰的極值點(diǎn)。相反，遺傳算法采用的是同時(shí)處理群體中多個(gè)個(gè)體的方法，即同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估。這一特點(diǎn)使遺傳算法具有較好的全局搜索性能，也使得遺傳算法本身易于并行化。3)不需要輔助信息遺傳算法對(duì)所求解的優(yōu)化問(wèn)題沒(méi)有太多的數(shù)學(xué)要求，魯棒性強(qiáng)。其僅用適應(yīng)度函數(shù)的數(shù)值來(lái)評(píng)估基因個(gè)體，并在此基礎(chǔ)上進(jìn)行遺傳操作。更重要的是，遺傳算法帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究25的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。對(duì)適應(yīng)度函數(shù)的唯一要求是，編碼必須與可行解空間對(duì)應(yīng)，不能有死碼。由于限制條件的縮小，使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。4)內(nèi)在啟發(fā)式隨機(jī)搜索特性遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)它的搜索方向。概率僅僅是作為一種工具來(lái)引導(dǎo)其搜索過(guò)程朝著搜索空間的更優(yōu)化的解區(qū)域移動(dòng)的。它有明確的搜索方向，具有內(nèi)在的并行搜索機(jī)制。5)遺傳算法的各態(tài)遍歷性使得其能夠非常有效地進(jìn)行概率意義下的全局搜索，在問(wèn)題不具有凸性時(shí)也能找到全局最優(yōu)解(或近似最優(yōu)解)。6)遺傳算法采用自然進(jìn)化機(jī)制來(lái)表現(xiàn)復(fù)雜的現(xiàn)象，能夠快速可靠地解決求解非常困難的問(wèn)題。? 遺傳算法的缺陷遺傳算法的進(jìn)化機(jī)制的不完善之處主要表現(xiàn)在以下兩個(gè)方面:1)對(duì)于遺傳算法的收斂性缺少完整的理論。算法的收斂性的研究主要針對(duì)二進(jìn)制編碼。對(duì)于不同的問(wèn)題存在多種不同的編碼方式。二進(jìn)制編碼算法的收斂性是否適用組合優(yōu)化問(wèn)題中的自然數(shù)編碼有待進(jìn)一步研究。遺傳算法的收斂判據(jù)不充分，使得算法的終止準(zhǔn)則過(guò)分依賴研究者的主觀意識(shí)。2)對(duì)于遺傳算法的隨機(jī)搜索機(jī)制缺乏有效性研究。盡管Holland等學(xué)者給出了Shema理論，但該理論不能解釋遺傳算法在實(shí)現(xiàn)過(guò)程中出現(xiàn)的過(guò)早收斂現(xiàn)象即“早熟”現(xiàn)象。在一些文獻(xiàn)中對(duì)此問(wèn)題進(jìn)行了一些研究，提出了一些克服的方法但總的來(lái)說(shuō)，效果并不顯著。 遺傳算法過(guò)程描述遺傳算法模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，從任一初始種群出發(fā)，通過(guò)隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個(gè)體，使群體進(jìn)化到搜索空間中越來(lái)越好的區(qū)城，這樣一代一代地不斷繁衍進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體，求得問(wèn)題的最優(yōu)解。遺傳算法的運(yùn)算流程可以用下圖來(lái)表帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究26示：種群 1?種群 2實(shí)際問(wèn)題參數(shù)集種群 1選擇與遺傳計(jì)算適應(yīng)度值經(jīng)過(guò)優(yōu)化的一個(gè)或多個(gè)參數(shù)集（由解碼得到）統(tǒng)計(jì)結(jié)果改善或解決實(shí)際問(wèn)題種群 2編碼成位串三種基本遺傳算子：選擇算子交叉算子變異算子帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究27圖 34 遺傳算法運(yùn)算流程1）編碼表示個(gè)體或當(dāng)前近似解被編碼為由字母組成的串，即染色體，使基因（染色體值）能在域決策變量上被唯一描述。在遺傳算法中，染色體的表現(xiàn)形式通過(guò)編碼機(jī)制來(lái)實(shí)現(xiàn)的。算法的編碼機(jī)制直接影響著算法的整體性能，并且也決定了種群初始化和各種遺傳算子的設(shè)計(jì)等各種過(guò)程，因此說(shuō)，編碼機(jī)制是遺傳算法的關(guān)鍵步驟。對(duì)于具體問(wèn)題的編碼，目前還沒(méi)有統(tǒng)一的方法。針對(duì)一個(gè)具體問(wèn)題，如何設(shè)計(jì)一個(gè)完美高效的編碼方案是遺傳算法的難點(diǎn)之一。在編碼時(shí)主要的編碼原則有以下兩點(diǎn)：編碼原則一 ——有意義的積木塊編碼原則。應(yīng)使用能夠易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)度模式的編碼方案；這里所提到的模式是指具有某些基因相似性的個(gè)體的集合，而具有短定義長(zhǎng)度、低階且適應(yīng)度高的模式又稱之為構(gòu)造優(yōu)良個(gè)體的積木塊或基因塊。這個(gè)原則事實(shí)上是符合Holland所提出的模式定理的。編碼原則二 ——最小字符串編碼原則。應(yīng)使用能使問(wèn)題得到自然表示或者描述的具有最小編碼字符集的編碼方案。目前，人們常用的編碼方案有二進(jìn)制編碼、實(shí)數(shù)編碼、Gray編碼、自然數(shù)編碼。? 二進(jìn)制編碼二進(jìn)制編碼機(jī)制是遺傳算法中最為常見(jiàn)的編碼機(jī)制。它所用到的字符集是由二進(jìn)制符號(hào)0和1所組成的符號(hào)集{0, 1}，由二進(jìn)制編碼所構(gòu)成的染色體是有一串0, 1符號(hào)所組成的符號(hào)串。二進(jìn)制編碼機(jī)制有著操作簡(jiǎn)單，便于交叉操作和變異操作，符合最小字符集編碼原則等優(yōu)點(diǎn)，但是也有不可彌補(bǔ)的缺陷:海明懸崖(Hamming Clifs)問(wèn)題。海明距離(Hamming Distance)主要用于表示兩個(gè)字符串的對(duì)應(yīng)位之間帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究28相異個(gè)數(shù)的和。 ??iliibabHamp。,1??其中 和 分別表示字符串a(chǎn), b的第i個(gè)分量，l表示字符串a(chǎn),b的位長(zhǎng)。在二iai進(jìn)制編碼表示中，即使是相鄰的兩個(gè)數(shù)之間的海明距離可能很大，例如7和8之間，以四位的二進(jìn)制表示，海明距離達(dá)到了4。這種缺點(diǎn)被稱之為海明懸崖問(wèn)題。海明懸崖問(wèn)題不利于遺傳算法獲得全局最優(yōu)解，因?yàn)?，在算法后期過(guò)程中逼近最優(yōu)解時(shí)，近似最優(yōu)解和全局最優(yōu)解之間由于存在著海明懸崖問(wèn)題，從而會(huì)導(dǎo)致從近似最優(yōu)解到最優(yōu)解之間的逼近過(guò)程緩慢，甚至找不到最優(yōu)解，所以提出了后面的Gray編碼。? Gray編碼Gray編碼是針對(duì)二進(jìn)制編碼中存在著海明懸崖問(wèn)題缺陷而提出的。它有這么一個(gè)特點(diǎn):即任意兩個(gè)整數(shù)之間的差正好是這兩個(gè)整數(shù)所對(duì)應(yīng)的Gray碼之間的海明距離。Gray編碼是對(duì)二進(jìn)制編碼進(jìn)行轉(zhuǎn)換得到的。設(shè)有二進(jìn)制串( )，n?,21??對(duì)應(yīng)的Gray串( )，則從二進(jìn)制編碼到Gray編碼的變換為:n?,21????????kk??1由于Gray編碼的鄰近兩個(gè)數(shù)之間的海明距離短的特點(diǎn)，所以使得算法從近似最優(yōu)解逼近全局最優(yōu)解的代價(jià)減少，有利于提高遺傳算法朝全局最優(yōu)解的逼近能力，便于對(duì)連續(xù)的函數(shù)進(jìn)行局部空間的搜索。本質(zhì)上，Gray編碼仍然是二進(jìn)制編碼的一種變形，所以，Gray編碼仍然可以沿用傳統(tǒng)遺傳算法的選擇、交叉、變異等遺傳算子。? 實(shí)數(shù)編碼對(duì)于一些問(wèn)題的表現(xiàn)形式是實(shí)向量的情形，如果使用二進(jìn)制編碼機(jī)制，會(huì)存在效率低下，無(wú)法控制算法精