【文章內(nèi)容簡介】 年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法（savings methods）來建立車隊(duì)配送路線。簡單啟發(fā)式方法簡單易懂、求解速度快，但只適合求解小型、簡單的VRP問題。 兩階段方法包括先分組后定路線（clusterfirstroute second）和先定路線后分組（routefirstcluster second）兩種啟發(fā)式策略。前者是先將所有需求點(diǎn)大略分為幾個(gè)組，然后再對各個(gè)組分別進(jìn)行路線排序；后者則是先將所有的需求點(diǎn)建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨(dú)路線。 1990年以來，人工智能方法在解決組合優(yōu)化問題上顯示出強(qiáng)大功能，在各個(gè)領(lǐng)域得到充分應(yīng)用，很多學(xué)者也將人工智能引入車輛路線問題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算法。禁忌搜索法（TS）基本上是屬于一種人工智能型（AI）的局部搜尋方法，Willard首先將此算法用來求解VRP ，隨后亦有許多位學(xué)者也發(fā)表了求解VRP的TS 算法。西南交通大學(xué)的袁慶達(dá)等設(shè)計(jì)了考慮時(shí)間窗口和不同車輛類型的禁忌算法，這種算法主要采用GENIUS方法產(chǎn)生初始解，然后禁忌算法對初始解優(yōu)化。模擬退火方法具有收斂速度快，全局搜索的特點(diǎn)，Osman對VRP的模擬退火算法進(jìn)行了研究，他提出的模擬退火方法主要適合于解決路線分組。遺傳算法具有求解組合優(yōu)化問題的良好特性，Holland首先采用遺傳算法（GA）編碼解決VRPTW 問題?，F(xiàn)在多數(shù)學(xué)者采用混合策略，分別采用兩種人工智能方法進(jìn)行路線分組和路線優(yōu)化。Ombuk提出了用遺傳算法進(jìn)行路線分組，然后用禁忌搜索方法進(jìn)行路線優(yōu)化的混合算法。Bent和Van Hentenryck則首先用模擬退火算法將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（largneighborhood search）將運(yùn)輸費(fèi)用降到最低。 總結(jié)幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運(yùn)算時(shí)間也最長，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能較好的逼近最優(yōu)解，同時(shí)使運(yùn)算時(shí)間大大縮短，所以GA算法能兼顧運(yùn)算時(shí)間和效率兩方面，是具有較好的發(fā)展前途的方法；SA算法求解速度非?？?，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問題上具有較好效果。 4 遺傳算法介紹遺傳算法簡稱 GA(Genetic Algorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。它是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的概念最早是由Bagley 在1967 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是1975 年，這一開創(chuàng)性工作是由Michigan . Holland 所實(shí)行。當(dāng)時(shí)，其主要目的是說明自然和人工系統(tǒng)的自適應(yīng)過程。遺傳算法是受生物進(jìn)化學(xué)說和遺傳學(xué)說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。具有如下特點(diǎn)：(1) 遺傳算法運(yùn)算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解；(3) 遺傳算法只使用報(bào)酬信息（適值函數(shù)），不使用導(dǎo)數(shù)或其他輔助知識(shí)；(4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性的問題，可廣泛用于組合優(yōu)化、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。作為一種隨機(jī)優(yōu)化技術(shù)在解優(yōu)化問題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能，遺傳算法的一個(gè)顯著優(yōu)勢是不需要目標(biāo)函數(shù)明確的數(shù)學(xué)方程和導(dǎo)數(shù)表達(dá)式，同時(shí)又是一種全局尋優(yōu)算法，不會(huì)象某些傳統(tǒng)算法易于陷入局部最優(yōu)解。 遺傳算法是具有“生成+檢測”(generateandtest)的迭代過程的搜索算法。遺傳算法中包含了如下5個(gè)基本要素：1)參數(shù)編碼；2)初始群體的設(shè)定；3)適應(yīng)度函數(shù)的設(shè)計(jì)；4)遺傳操作設(shè)計(jì)；5）控制參數(shù)設(shè)定(主要是指群體大小和使用遺傳操作的概率等)。這5個(gè)要素構(gòu)成了遺傳算法的核心內(nèi)容。 遺傳算法的基本思想遺傳算法是受生物進(jìn)化學(xué)說和遺傳學(xué)說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。具有如下特點(diǎn)：(1) 遺傳算法運(yùn)算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解；(3) 遺傳算法只使用報(bào)酬信息（適值函數(shù)），不使用導(dǎo)數(shù)或其他輔助知識(shí)；(4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 遺傳算法流程圖圖2 遺傳算法流程圖5 模型建立求解及實(shí)例應(yīng)用根據(jù)上述對問題的描述，可以采用混合整數(shù)規(guī)劃方法對車輛調(diào)度進(jìn)行建模設(shè)N為最小成本，則目標(biāo)函數(shù)為滿足約束條件1：式中：K為所有車輛的集合， ；G為所有客戶的集合， ， ，其中{0}代表配送中心； 為由車輛k服務(wù)的客戶的集合； 為車輛到達(dá)客戶i的時(shí)間；為懲罰函數(shù)，車輛在時(shí)間 到達(dá)客戶i時(shí)所對應(yīng)的懲罰成本；為車輛從客戶i到客戶j的所有運(yùn)輸成本；為車輛從客戶i到客戶j的行車時(shí)間；為客戶i的需求量；Q為車輛k的最大裝載量；為車輛在客戶i處的停留的時(shí)間。另外，變量和的值為0或1。若車輛k為客戶i服務(wù)，則1，否則為0，即：此變量表示車輛分配方案，可用布爾矩陣表示；若車輛k經(jīng)由客戶i到客戶j，則為1，否則為0，即：，表示車輛路線安排。約束條件2：保證每個(gè)客戶均被服務(wù)，而且每輛車都從配送中心出發(fā)；約束條件3：表示每輛車負(fù)責(zé)的客戶點(diǎn)的貨物需求量總和不超過該車輛的最大裝載量；約束條件5：表示對任一由k服務(wù)的客戶點(diǎn)j必定有另一(而且只有一個(gè))由k服務(wù)的客戶點(diǎn)(包括配送中心)I,車輛k從客戶點(diǎn)i到達(dá)客戶點(diǎn)j,而對由k服務(wù)的客戶點(diǎn)i同樣存在由k服務(wù)的另一客戶點(diǎn),車輛k是從該客戶點(diǎn)到達(dá)客戶點(diǎn)i的,依次類推；約束條件6：保證每輛車的行車路線的總耗時(shí)不超過一個(gè)事先定下的數(shù)值；約束條件7：對某個(gè)客戶點(diǎn)，車輛到達(dá)時(shí)間限制在某一時(shí)間段內(nèi)。根據(jù)實(shí)際情況，本文采用軟限制時(shí)間窗，其懲罰函數(shù)如圖2所示。其中，為客戶所要求的送貨時(shí)區(qū)，為時(shí)間窗，超過該范圍客戶將拒絕收貨，因此設(shè)定一個(gè)極大的懲罰成本以避免此情況的發(fā)生。圖3 懲罰函數(shù) 帶時(shí)間窗的物流配送問題優(yōu)化問題帶時(shí)間窗 VRP（VRP with Time Windows，VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP，CVRP)的擴(kuò)展。在該類問題中，有車輛裝載能力約束，且每個(gè)客戶i 都有一個(gè)與之相聯(lián)系的時(shí)間區(qū)間[ai ,bi]，稱為時(shí)間窗?？蛻舻姆?wù)必須在相應(yīng)的時(shí)間窗內(nèi)開始，車輛必須在客戶點(diǎn)停留的時(shí)間長度為si。按客戶對物流中心違反