最優(yōu)化算法案例學(xué)習(xí)(禁忌搜索,混合算法)

1、大作業(yè)匯報(bào) Shanghai Maritime University 禁忌搜索案例學(xué)習(xí)禁忌搜索案例學(xué)習(xí) 目錄目錄 小組分工 禁忌搜索算法 帶軟時(shí)間窗的集貨與送貨 多車輛路徑問題節(jié)約算法 考慮碳排放的開環(huán)取送 貨路徑優(yōu)化問題 數(shù)值實(shí)驗(yàn) 禁忌搜索算法禁忌搜索算法 Fred Glover 禁忌搜索禁忌搜索(Tabu Search)是局部鄰域搜索算法的推是局部鄰域搜索算法的推 廣廣,Fred Glover在在1986年提出這個(gè)概念年提出這個(gè)概念,進(jìn)而形成進(jìn)而形成 一套完整算法一套完整算法. 人類在選擇過程中具有人類在選擇過程中具有記憶功能記憶功能，比如走迷宮時(shí)，比如走迷宮時(shí)， 當(dāng)發(fā)現(xiàn)有可能又回到某個(gè)地

2、點(diǎn)的時(shí)候總會(huì)有意識(shí)當(dāng)發(fā)現(xiàn)有可能又回到某個(gè)地點(diǎn)的時(shí)候總會(huì)有意識(shí) 地避開先前選擇的方向而選擇其他的可能性，這地避開先前選擇的方向而選擇其他的可能性，這 樣就可以確定性的樣就可以確定性的避開迂回搜索避開迂回搜索。 禁忌搜索算法禁忌搜索算法 只進(jìn)不退的原則只進(jìn)不退的原則用用TabuTabu表鎖住退路，將表鎖住退路，將 近期歷史搜索過程存放在禁忌表中，防止算近期歷史搜索過程存放在禁忌表中，防止算 法迂回搜索。法迂回搜索。 不以局部最優(yōu)作為停止準(zhǔn)則，算法接受劣解，不以局部最優(yōu)作為停止準(zhǔn)則，算法接受劣解， 只要不在禁忌表的較好解都可作為下一次迭只要不在禁忌表的較好解都可作為下一次迭 代的初始解。代的初始解。

3、 鄰域選優(yōu)的規(guī)則模擬了人類的記憶功能，找鄰域選優(yōu)的規(guī)則模擬了人類的記憶功能，找 過的地方都記下來，不再找第二次。一定迭過的地方都記下來，不再找第二次。一定迭 代次數(shù)后，早期進(jìn)入禁忌表解被解禁退出代次數(shù)后，早期進(jìn)入禁忌表解被解禁退出 核心思想 禁忌搜索算法禁忌搜索算法 步驟 第一步 選定一個(gè)初始解xnow;令禁忌表 ; 第二步 若滿足終止準(zhǔn)則,轉(zhuǎn)第四步; 否則,在xnow的鄰域 N(xnow)中選出滿足禁忌要求的候選集C-N(xnow) ,轉(zhuǎn)第三步; 第三步 在C-N(xnow)中選一個(gè)評(píng)價(jià)值最好的解xbest,令 xnow=xbest,更新禁忌表H,轉(zhuǎn)第二步; 第四步 輸出計(jì)算結(jié)果,停止. 概

4、念 禁忌表：為避免迂回搜索，記錄之前搜索過的解或狀態(tài)的表 禁忌對(duì)象：禁忌表中被禁的那些變化元素 禁忌長度：禁忌的步數(shù) 特赦原則：對(duì)一些顯著提高解質(zhì)量而處于禁忌的操作解禁 H 禁忌搜索算法禁忌搜索算法 Xx T0k TxS 1 kk NGk | k SxO p tsxsxSxT k xSx xsAxSC L , Tx L S xSx L xCxCxx xcx, 禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題 四城市非對(duì)稱四城市非對(duì)稱TSP問題問題 初始初始解解x0=(ABCD)，f(x0)=4，鄰域映射為兩個(gè)城市順序?qū)?，鄰域映射為兩個(gè)城市順序?qū)?換的換的2opt，始、終點(diǎn)都是，始、終點(diǎn)都是A城

5、市。城市。1 禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題 ABCD BCD A B C 對(duì)換評(píng)價(jià)值 CD4.5 BC7.5 BD8 第第1步步 解的形式解的形式 禁忌對(duì)象及長度禁忌對(duì)象及長度 候選解候選解 f(x0)=4 第第2步步 A B D C BCD A B C3 對(duì)換評(píng)價(jià)值 CD4.5 BC3.5 BD4.5 f(x1)=4.5 禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題 第第3步步 解的形式解的形式 禁忌對(duì)象及長度禁忌對(duì)象及長度 候選解候選解 f(x0)=3.5 第第4步步 f(x1)=7.5 A C D B BCD A B3 C2 對(duì)換評(píng)價(jià)值 CD8 BC4.5 BD7

6、.5 A C B D BCD A B23 C1 對(duì)換評(píng)價(jià)值 CD4.5 BC4.5 BD3.5 禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題 第第5步步 解的形式解的形式 禁忌對(duì)象及長度禁忌對(duì)象及長度 候選解候選解 f(x0)=4.5 第第6步步 f(x1)=8 A D B C BCD A B01 C2 對(duì)換評(píng)價(jià)值 CD7.5 BC8 BD4.5 A D C B BCD A B30 C1 對(duì)換評(píng)價(jià)值 CD3.5 BC4.5 BD4 禁忌對(duì)象禁忌對(duì)象 解的簡(jiǎn)單變化解的簡(jiǎn)單變化 解向量分量的變化解向量分量的變化 目標(biāo)值變化目標(biāo)值變化 情況情況1：禁忌對(duì)象為簡(jiǎn)單的解變化：禁忌對(duì)象為簡(jiǎn)單的解變化

7、xnow=(ABCDE)，f(xnow)=45，H=(ABCDE;45) Can_N(xnow)=(ACBDE;43)，(ABCDE;45)，(ADCBE;45)， (ABEDC;59)，(ABCED;44) xnext=(ACBDE ) 情況情況2：禁忌對(duì)象為分量變化：禁忌對(duì)象為分量變化 xnow=(ACBDE)，f(xnow)=43，H=(B,C) Can_N(xnow)=(ACBED;43)，(ADBCE;44)，(ABCDE;45)， (ACEDB;58)，(AEBDC;59) xnext=(ACBED) 情況情況3：禁忌對(duì)象為目標(biāo)值變化：禁忌對(duì)象為目標(biāo)值變化 xnow=(ABCDE)

8、，f(xnow)=45，H=45 Can_N(xnow)=(ABCDE;45)，(ACBDE;43)，(ADCBE;45)， (ABEDC;59)，(ABCED;44) xnext=(ACBDE) 特赦原則特赦原則 基于評(píng)價(jià)值的規(guī)則，若出現(xiàn)基于評(píng)價(jià)值的規(guī)則，若出現(xiàn) 一個(gè)解的目標(biāo)值好于前面任一個(gè)解的目標(biāo)值好于前面任 何一個(gè)最佳候選解，可特赦；何一個(gè)最佳候選解，可特赦； 基于最小錯(cuò)誤的規(guī)則，若所基于最小錯(cuò)誤的規(guī)則，若所 有對(duì)象都被禁忌，特赦一個(gè)有對(duì)象都被禁忌，特赦一個(gè) 評(píng)價(jià)值最小的解；評(píng)價(jià)值最小的解； 基于影響力的規(guī)則，可以特基于影響力的規(guī)則，可以特 赦對(duì)目標(biāo)值影響大的對(duì)象。赦對(duì)目標(biāo)值影響大的對(duì)象

9、。 其它原則其它原則 禁忌長度與評(píng)價(jià)函數(shù)禁忌長度與評(píng)價(jià)函數(shù) （1）t可以為常數(shù)，易于實(shí)現(xiàn)；可以為常數(shù)，易于實(shí)現(xiàn)； （2） ，t是可以變化的數(shù)，是可以變化的數(shù)，tmin和和tmax是確定的。是確定的。 tmin和和tmax根據(jù)問題的規(guī)模確定，根據(jù)問題的規(guī)模確定，t的大小主要依據(jù)實(shí)際問題的大小主要依據(jù)實(shí)際問題 實(shí)驗(yàn)和設(shè)計(jì)者的經(jīng)驗(yàn)。實(shí)驗(yàn)和設(shè)計(jì)者的經(jīng)驗(yàn)。 （3） tmin和和tmax的動(dòng)態(tài)選擇。的動(dòng)態(tài)選擇。 minmax ,ttt 評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù) （1）直接評(píng)價(jià)函數(shù)，通過目標(biāo)函數(shù)的運(yùn)算得到評(píng)價(jià)函數(shù)；）直接評(píng)價(jià)函數(shù)，通過目標(biāo)函數(shù)的運(yùn)算得到評(píng)價(jià)函數(shù)； （2）間接評(píng)價(jià)函數(shù)，構(gòu)造其他評(píng)價(jià)函數(shù)替代目標(biāo)函數(shù)，）

10、間接評(píng)價(jià)函數(shù)，構(gòu)造其他評(píng)價(jià)函數(shù)替代目標(biāo)函數(shù)， 應(yīng)反映目標(biāo)函數(shù)的特性，減少計(jì)算復(fù)雜性。應(yīng)反映目標(biāo)函數(shù)的特性，減少計(jì)算復(fù)雜性。 禁忌長度禁忌長度 記憶頻率信息和終止規(guī)則記憶頻率信息和終止規(guī)則 n記憶頻率信息記憶頻率信息 （1）靜態(tài)頻率信息：解、對(duì)換或目標(biāo)值在計(jì)算中出現(xiàn)的頻率；）靜態(tài)頻率信息：解、對(duì)換或目標(biāo)值在計(jì)算中出現(xiàn)的頻率； （2）動(dòng)態(tài)頻率信息：從一個(gè)解、對(duì)換或目標(biāo)值到另一個(gè)解、對(duì)換）動(dòng)態(tài)頻率信息：從一個(gè)解、對(duì)換或目標(biāo)值到另一個(gè)解、對(duì)換 或目標(biāo)值的變化趨勢(shì)?；蚰繕?biāo)值的變化趨勢(shì)。 n終止規(guī)則終止規(guī)則 （1）確定步數(shù)終止，無法保證解的效果，應(yīng)記錄當(dāng)前最優(yōu)解；）確定步數(shù)終止，無法保證解的效果，應(yīng)記錄當(dāng)

11、前最優(yōu)解； （2）頻率控制原則，當(dāng)某一個(gè)解、目標(biāo)值或元素序列的頻率）頻率控制原則，當(dāng)某一個(gè)解、目標(biāo)值或元素序列的頻率 超過一個(gè)給定值時(shí)，終止計(jì)算；超過一個(gè)給定值時(shí)，終止計(jì)算； （3）目標(biāo)控制原則，如果在一個(gè)給定步數(shù)內(nèi)，當(dāng)前最優(yōu)值沒）目標(biāo)控制原則，如果在一個(gè)給定步數(shù)內(nèi)，當(dāng)前最優(yōu)值沒 有變化，可終止計(jì)算。有變化，可終止計(jì)算。 論文閱讀論文閱讀 帶軟時(shí)間窗的集貨與送貨多帶軟時(shí)間窗的集貨與送貨多 車輛路徑問題節(jié)約算法車輛路徑問題節(jié)約算法 祁文祥祁文祥 陸志強(qiáng)陸志強(qiáng) 孫小明孫小明 交通運(yùn)輸工程學(xué)報(bào)交通運(yùn)輸工程學(xué)報(bào)2010 關(guān)鍵詞關(guān)鍵詞：多車輛路徑問題、集貨與送貨、啟發(fā)式節(jié)約算法、軟時(shí)間窗多車輛路徑問題、

12、集貨與送貨、啟發(fā)式節(jié)約算法、軟時(shí)間窗 背景介紹背景介紹 隨著第三方物流的興起,很多企業(yè)為降低物流成本, 越來越傾向于把原來由自己承擔(dān)的運(yùn)輸任務(wù)外包給 第三方物流企業(yè),而多批次、小批量的送貨模式也成多批次、小批量的送貨模式也成 為各企業(yè)降低庫存風(fēng)險(xiǎn)的重要手段為各企業(yè)降低庫存風(fēng)險(xiǎn)的重要手段。另一方面,第三 方物流企業(yè)出于自身運(yùn)營成本考慮,在滿足客戶運(yùn)輸在滿足客戶運(yùn)輸 要求的前提下需要采取有效的路徑優(yōu)化方案要求的前提下需要采取有效的路徑優(yōu)化方案,才能實(shí)才能實(shí) 現(xiàn)自身利益的最大化現(xiàn)自身利益的最大化 問題描述問題描述 物流配送網(wǎng)絡(luò)物流配送網(wǎng)絡(luò)( ,)GV A 集貨需求點(diǎn)集集貨需求點(diǎn)集P 配貨需求點(diǎn)集配貨

13、需求點(diǎn)集D 所有需求點(diǎn)集所有需求點(diǎn)集NPD 任務(wù)集任務(wù)集1,2,.,Tm 租用貨車的費(fèi)用租用貨車的費(fèi)用 貨車的運(yùn)輸費(fèi)用貨車的運(yùn)輸費(fèi)用 時(shí)間懲罰費(fèi)用時(shí)間懲罰費(fèi)用 變量定義變量定義 客戶客戶j 的集貨需求量的集貨需求量 j M j N 第第m個(gè)任務(wù)要求貨物送到的時(shí)間窗個(gè)任務(wù)要求貨物送到的時(shí)間窗 , mm ijij ab 貨車貨車 k 執(zhí)行第執(zhí)行第 m 個(gè)任務(wù)從客戶個(gè)任務(wù)從客戶 i 的出發(fā)時(shí)間，的出發(fā)時(shí)間， 該任務(wù)配送貨物至該任務(wù)配送貨物至 j 點(diǎn)點(diǎn) m ijk s 貨車貨車 k 執(zhí)行第執(zhí)行第 m 個(gè)任務(wù)到達(dá)客戶個(gè)任務(wù)到達(dá)客戶 j 的時(shí)間，該的時(shí)間，該 任務(wù)從任務(wù)從 i 點(diǎn)點(diǎn) 出發(fā)出發(fā) m ijk

14、r 客戶客戶j 的送貨需求量的送貨需求量 變量定義變量定義 單個(gè)車輛的租賃費(fèi)用單個(gè)車輛的租賃費(fèi)用f mk P 早到晚到時(shí)間懲罰系數(shù)早到晚到時(shí)間懲罰系數(shù) , a b 裝貨時(shí)間裝貨時(shí)間 U 卸貨時(shí)間卸貨時(shí)間 W 貨車貨車k 在執(zhí)行任務(wù)在執(zhí)行任務(wù)m 時(shí)的時(shí)間懲罰值時(shí)的時(shí)間懲罰值 車輛最大裝載量車輛最大裝載量L 車輛最大行駛距離車輛最大行駛距離D 單個(gè)車輛的租賃費(fèi)用單個(gè)車輛的租賃費(fèi)用 g 變量定義變量定義 節(jié)點(diǎn)節(jié)點(diǎn) i 和節(jié)點(diǎn)和節(jié)點(diǎn) j 之間的距離之間的距離 ij d ijk w 0-1變量，貨車變量，貨車k 完成任務(wù)完成任務(wù)m取取1，否則，否則0 mk x mnk y 0-1 變量，貨車變量，貨車k

15、 從客戶從客戶 i 行駛到客戶行駛到客戶 j 則取則取1，否則，否則0 決策變量決策變量 0-1變量，貨車變量，貨車k 完成任務(wù)完成任務(wù)m及任務(wù)及任務(wù) n 取取1，否則，否則0 VRPPDTW數(shù)學(xué)模型數(shù)學(xué)模型 min ijijkmk k Kk K i V j Vk K m T zfkgdwP （1） ijkjhk i V k Kh V k K ww S.T. （2） 00 1 i kjk i Vk K ww （3） jj j Vj V MNJ （4） VRPPDTW數(shù)學(xué)模型數(shù)學(xué)模型 jijkjj i V k K NwNM （5） jjhkjj h V k K MwNM （6） ijkij i

16、V j V w dD （7） jj j Vj V MNJ （8） m ijijk i V k K qLw （9） VRPPDTW數(shù)學(xué)模型數(shù)學(xué)模型 0.5() mnkmknk yxx （9） 0.5()0.5 mknkmnk xxy （10） mm ijkijijk rts （11） / ijij tdv （12） , , ,kK i j hV m nT mn （13） 啟發(fā)式節(jié)約算法啟發(fā)式節(jié)約算法 本研究模型在傳統(tǒng)VRP問題上進(jìn)行了擴(kuò)展,增加 了集貨和送貨任務(wù)的時(shí)間窗要求以及多輛車可 供配置的條件,因此,對(duì)于任意訪問節(jié)點(diǎn),需要將 運(yùn)輸成本的節(jié)省值、時(shí)間懲罰費(fèi)用、租車費(fèi)用 綜合考慮才能構(gòu)造有效可

17、行的啟發(fā)式節(jié)約算法。 ( , ) ixyi s i jcc ( , ) mk s i jP 啟發(fā)式節(jié)約算法啟發(fā)式節(jié)約算法 單車完成 i 到 j 的總?cè)蝿?wù)： mkij Pc 多車完成 i 到 j 的總?cè)蝿?wù)： 0 jijix fccc 0mkjix Pfcc 求解結(jié)果求解結(jié)果 最大載貨量/t10貨車最多可調(diào)用數(shù)量10n 速度/(kmkm-1)40每輛車的固定租車費(fèi)用/元300 最大行駛距離/km240 每公里運(yùn)輸費(fèi)用/(元km-1) 2 固定裝貨時(shí)間/h0.5時(shí)間窗上界懲罰系數(shù)/(元h-1)200 固定卸貨時(shí)間/h0.5時(shí)間窗下界懲罰系數(shù)/(元h-1)300 參數(shù)設(shè)置 求解結(jié)果求解結(jié)果 任務(wù)數(shù)任務(wù)

18、數(shù)租車數(shù)量租車數(shù)量/輛輛總費(fèi)用總費(fèi)用/元元計(jì)算時(shí)間計(jì)算時(shí)間/s貨車平均利用率貨車平均利用率%平局有效運(yùn)輸時(shí)間比平局有效運(yùn)輸時(shí)間比 102147813.293.287.6 208478067.591.482.9 30137872163.288.385.4 401610290266.485.388.5 502213753475.681.684.8 算例結(jié)果 論文改進(jìn)論文改進(jìn) 考慮碳排放的開環(huán)取送貨路考慮碳排放的開環(huán)取送貨路 徑優(yōu)化問題徑優(yōu)化問題 關(guān)鍵詞關(guān)鍵詞：車輛路徑優(yōu)化、集貨與送貨、碳排放、禁忌搜索、蟻群算法車輛路徑優(yōu)化、集貨與送貨、碳排放、禁忌搜索、蟻群算法 論文改進(jìn)論文改進(jìn) 創(chuàng)新點(diǎn)：創(chuàng)新點(diǎn)：

19、 將車輛在集貨配貨中碳排放成本加入到模型中將車輛在集貨配貨中碳排放成本加入到模型中 建立了開環(huán)模式下的路徑優(yōu)化問題建立了開環(huán)模式下的路徑優(yōu)化問題 對(duì)比了禁忌搜索、蟻群算法對(duì)本問題的求解效果對(duì)比了禁忌搜索、蟻群算法對(duì)本問題的求解效果 提出了蟻群緊急搜索混合搜索算法，數(shù)值實(shí)驗(yàn)表明該算提出了蟻群緊急搜索混合搜索算法，數(shù)值實(shí)驗(yàn)表明該算 法求得的解質(zhì)量最高法求得的解質(zhì)量最高 論文改進(jìn)論文改進(jìn) 1 2 3 4 5 6 每個(gè)客戶的需求量較小 違反時(shí)間窗產(chǎn)生懲罰費(fèi)用 假設(shè)路上交通狀況良好 先取貨后配貨 需求確定不可拆分 開環(huán)路徑 考慮碳排放的開環(huán)考慮碳排放的開環(huán) 取送貨路徑優(yōu)化問題取送貨路徑優(yōu)化問題 假設(shè)條件

20、：假設(shè)條件： 論文改進(jìn)論文改進(jìn) 標(biāo)號(hào)含義 客戶集貨點(diǎn)集合， 客戶配送點(diǎn)集合 默認(rèn)由1配送給N+1 網(wǎng)絡(luò)圖節(jié)點(diǎn)集合， 0表示車庫 所有弧的集合， 顧客i 的需求量， （若 則 ，若 ，則 ） 1,2,3,., PN 1,2,.,2 DNNN 0VPD ( , )| ,Ai ji jV ij i q iP0 i qiD 0 i q P D V A 論文改進(jìn)論文改進(jìn) 標(biāo)號(hào)含義 車輛 k 的最大裝載量 車輛 k 的集合 輛 k 車 最大行駛里程 顧客 i 時(shí)間窗起始時(shí)間， 顧客 i 時(shí)間窗起始時(shí)間， i L T K k L i E T k Q iV iV 論文改進(jìn)論文改進(jìn) 標(biāo)號(hào)含義 單位時(shí)間延遲成本

21、單位時(shí)間等待成本 單位超標(biāo)碳排放的懲罰成本 節(jié)點(diǎn) i 的等待時(shí)間 節(jié)點(diǎn) i 延遲時(shí)間 i w p c p i w d p iV iV 論文改進(jìn)論文改進(jìn) 標(biāo)號(hào)含義 車輛 k 經(jīng)過?。╥,j）的碳排放量 ?。╥,j）的運(yùn)輸成本，與運(yùn)輸距離成正比 最大允許碳排放量，若超過此值則按超過量懲罰 燃油轉(zhuǎn)換系數(shù) 車輛k 的的燃油消耗系數(shù) , kk ab i j c W k i j W 論文改進(jìn)論文改進(jìn) 表示節(jié)點(diǎn)之間是否有配送關(guān)系的變量，如有 則該值為1，否則為0； 決策變量含義 0-1變量，當(dāng)車輛 k 經(jīng)過弧（i，j）則為1 ，否則為0 0-1變量，當(dāng)任務(wù)i被指派給k 時(shí)為1，否則為0 k i y k i

22、j x i j MIPMIP模型模型 2222 0 1110111 22 101 min () KNKNNNN kk jijijwidi kjkijii KNN k cij kij Ffxx cpwp pWW 0 11 NK k j jk xK （1）式為目標(biāo)函數(shù)，最小化運(yùn)營成本，其中第一項(xiàng)為車輛的啟用成本， 第二項(xiàng)為車輛的行駛成本，第三項(xiàng)為車輛的等待成本，第四項(xiàng)為車輛的懲 罰成本，第五項(xiàng)為車輛的碳排放成本； （2）式表示車輛數(shù)限制 （1） （2） MIPMIP模型模型 2 1 i,jV,ij, N k ijik j xykK 2 0 i,jV,ij, N k ijjk i xykK （3）表示 與 的函數(shù)關(guān)系 k i j x k i y （4）表示 與 的函數(shù)關(guān)系 k i j x k j y 1 1 /0 K ik k yiV （5）式表示一個(gè)客戶點(diǎn)的配送或集貨需 求只能由一輛車來完成 ,/0,=1, ikjkij yyi jVkK （6）表示每一對(duì)取送貨點(diǎn)須同一車輛完成 （3） （4） （5） （6） MIPMIP模型模型 2 11