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

2、又回到某個地點的時候總會有意識地避開先前選擇的方向而選擇其他的可能性，這地避開先前選擇的方向而選擇其他的可能性，這樣就可以確定性的樣就可以確定性的避開迂回搜索避開迂回搜索。禁忌搜索算法禁忌搜索算法只進不退的原則只進不退的原則用用TabuTabu表鎖住退路，將表鎖住退路，將近期歷史搜索過程存放在禁忌表中，防止算近期歷史搜索過程存放在禁忌表中，防止算法迂回搜索。法迂回搜索。不以局部最優(yōu)作為停止準則，算法接受劣解，不以局部最優(yōu)作為停止準則，算法接受劣解，只要不在禁忌表的較好解都可作為下一次迭只要不在禁忌表的較好解都可作為下一次迭代的初始解。代的初始解。鄰域選優(yōu)的規(guī)則模擬了人類的記憶功能，找鄰域選優(yōu)的

3、規(guī)則模擬了人類的記憶功能，找過的地方都記下來，不再找第二次。一定迭過的地方都記下來，不再找第二次。一定迭代次數(shù)后，早期進入禁忌表解被解禁退出代次數(shù)后，早期進入禁忌表解被解禁退出核心思想禁忌搜索算法禁忌搜索算法步驟第一步 選定一個初始解xnow;令禁忌表 ;第二步 若滿足終止準則,轉(zhuǎn)第四步; 否則,在xnow的鄰域N(xnow)中選出滿足禁忌要求的候選集C-N(xnow) ,轉(zhuǎn)第三步;第三步 在C-N(xnow)中選一個評價值最好的解xbest,令xnow=xbest,更新禁忌表H,轉(zhuǎn)第二步;第四步 輸出計算結(jié)果,停止.概念禁忌表：為避免迂回搜索，記錄之前搜索過的解或狀態(tài)的表禁忌對象：禁忌表中被

4、禁的那些變化元素禁忌長度：禁忌的步數(shù)特赦原則：對一些顯著提高解質(zhì)量而處于禁忌的操作解禁H 禁忌搜索算法禁忌搜索算法Xx T0k TxS1 kkNGk |kSxO p tsxsxSxTkxSx xsAxSCL, TxLS xSxL xCxCxxxcx,禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題四城市非對稱四城市非對稱TSP問題問題 初始初始解解x0=(ABCD)，f(x0)=4，鄰域映射為兩個城市順序?qū)?，鄰域映射為兩個城市順序?qū)Q的換的2opt，始、終點都是，始、終點都是A城市。城市。1禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題ABCDBCDABC對換評價值CD4.5BC7.5BD8

5、第第1步步解的形式解的形式 禁忌對象及長度禁忌對象及長度 候選解候選解f(x0)=4第第2步步A B D CBCDABC3對換評價值CD4.5BC3.5BD4.5 f(x1)=4.5禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題第第3步步解的形式解的形式 禁忌對象及長度禁忌對象及長度 候選解候選解f(x0)=3.5第第4步步 f(x1)=7.5A C D BBCDAB3C2對換評價值CD8BC4.5BD7.5A C B DBCDAB23C1對換評價值CD4.5BC4.5BD3.5禁忌搜索舉例：禁忌搜索舉例：TSPTSP問題問題第第5步步解的形式解的形式 禁忌對象及長度禁忌對象及長度 候選解候

6、選解f(x0)=4.5第第6步步 f(x1)=8A D B CBCDAB01C2對換評價值CD7.5BC8BD4.5A D C BBCDAB30C1對換評價值CD3.5BC4.5BD4禁忌對象禁忌對象解的簡單變化解的簡單變化 解向量分量的變化解向量分量的變化目標值變化目標值變化 情況情況1：禁忌對象為簡單的解變化：禁忌對象為簡單的解變化xnow=(ABCDE)，f(xnow)=45，H=(ABCDE;45) Can_N(xnow)=(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44) xnext=(ACBDE )情況情況2：禁忌對象為分量

7、變化：禁忌對象為分量變化xnow=(ACBDE)，f(xnow)=43，H=(B,C) Can_N(xnow)=(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59) xnext=(ACBED) 情況情況3：禁忌對象為目標值變化：禁忌對象為目標值變化xnow=(ABCDE)，f(xnow)=45，H=45 Can_N(xnow)=(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44) xnext=(ACBDE)特赦原則特赦原則基于評價值的規(guī)則，若出現(xiàn)基于評價值的規(guī)則，若出現(xiàn)一個解的目標值

8、好于前面任一個解的目標值好于前面任何一個最佳候選解，可特赦；何一個最佳候選解，可特赦；基于最小錯誤的規(guī)則，若所基于最小錯誤的規(guī)則，若所有對象都被禁忌，特赦一個有對象都被禁忌，特赦一個評價值最小的解；評價值最小的解；基于影響力的規(guī)則，可以特基于影響力的規(guī)則，可以特赦對目標值影響大的對象。赦對目標值影響大的對象。其它原則其它原則禁忌長度與評價函數(shù)禁忌長度與評價函數(shù)（1）t可以為常數(shù)，易于實現(xiàn)；可以為常數(shù)，易于實現(xiàn)；（2） ，t是可以變化的數(shù)，是可以變化的數(shù)，tmin和和tmax是確定的。是確定的。 tmin和和tmax根據(jù)問題的規(guī)模確定，根據(jù)問題的規(guī)模確定，t的大小主要依據(jù)實際問題的大小主要依據(jù)實

9、際問題實驗和設計者的經(jīng)驗。實驗和設計者的經(jīng)驗。（3） tmin和和tmax的動態(tài)選擇。的動態(tài)選擇。minmax,ttt評價函數(shù)評價函數(shù) （1）直接評價函數(shù)，通過目標函數(shù)的運算得到評價函數(shù)；）直接評價函數(shù)，通過目標函數(shù)的運算得到評價函數(shù)； （2）間接評價函數(shù)，構(gòu)造其他評價函數(shù)替代目標函數(shù)，）間接評價函數(shù)，構(gòu)造其他評價函數(shù)替代目標函數(shù)，應反映目標函數(shù)的特性，減少計算復雜性。應反映目標函數(shù)的特性，減少計算復雜性。禁忌長度禁忌長度記憶頻率信息和終止規(guī)則記憶頻率信息和終止規(guī)則n記憶頻率信息記憶頻率信息（1）靜態(tài)頻率信息：解、對換或目標值在計算中出現(xiàn)的頻率；）靜態(tài)頻率信息：解、對換或目標值在計算中出現(xiàn)的頻

10、率；（2）動態(tài)頻率信息：從一個解、對換或目標值到另一個解、對換）動態(tài)頻率信息：從一個解、對換或目標值到另一個解、對換或目標值的變化趨勢?；蚰繕酥档淖兓厔?。n終止規(guī)則終止規(guī)則 （1）確定步數(shù)終止，無法保證解的效果，應記錄當前最優(yōu)解；）確定步數(shù)終止，無法保證解的效果，應記錄當前最優(yōu)解； （2）頻率控制原則，當某一個解、目標值或元素序列的頻率）頻率控制原則，當某一個解、目標值或元素序列的頻率超過一個給定值時，終止計算；超過一個給定值時，終止計算； （3）目標控制原則，如果在一個給定步數(shù)內(nèi)，當前最優(yōu)值沒）目標控制原則，如果在一個給定步數(shù)內(nèi)，當前最優(yōu)值沒有變化，可終止計算。有變化，可終止計算。論文閱讀

11、論文閱讀帶軟時間窗的集貨與送貨多帶軟時間窗的集貨與送貨多車輛路徑問題節(jié)約算法車輛路徑問題節(jié)約算法祁文祥祁文祥 陸志強陸志強 孫小明孫小明交通運輸工程學報交通運輸工程學報2010關(guān)鍵詞關(guān)鍵詞：多車輛路徑問題、集貨與送貨、啟發(fā)式節(jié)約算法、軟時間窗多車輛路徑問題、集貨與送貨、啟發(fā)式節(jié)約算法、軟時間窗背景介紹背景介紹隨著第三方物流的興起,很多企業(yè)為降低物流成本,越來越傾向于把原來由自己承擔的運輸任務外包給第三方物流企業(yè),而多批次、小批量的送貨模式也成多批次、小批量的送貨模式也成為各企業(yè)降低庫存風險的重要手段為各企業(yè)降低庫存風險的重要手段。另一方面,第三方物流企業(yè)出于自身運營成本考慮,在滿足客戶運輸在滿

12、足客戶運輸要求的前提下需要采取有效的路徑優(yōu)化方案要求的前提下需要采取有效的路徑優(yōu)化方案,才能實才能實現(xiàn)自身利益的最大化現(xiàn)自身利益的最大化問題描述問題描述物流配送網(wǎng)絡物流配送網(wǎng)絡( ,)GV A集貨需求點集集貨需求點集P配貨需求點集配貨需求點集D所有需求點集所有需求點集NPD任務集任務集1,2,.,Tm租用貨車的費用租用貨車的費用貨車的運輸費用貨車的運輸費用時間懲罰費用時間懲罰費用變量定義變量定義客戶客戶j 的集貨需求量的集貨需求量jMjN第第m個任務要求貨物送到的時間窗個任務要求貨物送到的時間窗,mmijijab貨車貨車 k 執(zhí)行第執(zhí)行第 m 個任務從客戶個任務從客戶 i 的出發(fā)時間，的出發(fā)時

13、間，該任務配送貨物至該任務配送貨物至 j 點點mijks貨車貨車 k 執(zhí)行第執(zhí)行第 m 個任務到達客戶個任務到達客戶 j 的時間，該的時間，該任務從任務從 i 點點 出發(fā)出發(fā)mijkr客戶客戶j 的送貨需求量的送貨需求量變量定義變量定義單個車輛的租賃費用單個車輛的租賃費用fmkP早到晚到時間懲罰系數(shù)早到晚到時間懲罰系數(shù), a b裝貨時間裝貨時間U卸貨時間卸貨時間W貨車貨車k 在執(zhí)行任務在執(zhí)行任務m 時的時間懲罰值時的時間懲罰值車輛最大裝載量車輛最大裝載量L車輛最大行駛距離車輛最大行駛距離D單個車輛的租賃費用單個車輛的租賃費用g變量定義變量定義節(jié)點節(jié)點 i 和節(jié)點和節(jié)點 j 之間的距離之間的距離

14、ijdijkw0-1變量，貨車變量，貨車k 完成任務完成任務m取取1，否則，否則0mkxmnky0-1 變量，貨車變量，貨車k 從客戶從客戶 i 行駛到客戶行駛到客戶 j 則取則取1，否則，否則0決策變量決策變量0-1變量，貨車變量，貨車k 完成任務完成任務m及任務及任務 n 取取1，否則，否則0VRPPDTW數(shù)學模型數(shù)學模型minijijkmkk Kk K i V j Vk K m TzfkgdwP（1）ijkjhki V k Kh V k KwwS.T.（2）001i kjki Vk Kww（3）jjj Vj VMNJ（4）VRPPDTW數(shù)學模型數(shù)學模型jijkjji V k KNwNM（

15、5）jjhkjjh V k KMwNM（6）ijkiji V j Vw dD（7）jjj Vj VMNJ（8）mijijki V k KqLw（9）VRPPDTW數(shù)學模型數(shù)學模型0.5()mnkmknkyxx（9）0.5()0.5mknkmnkxxy（10）mmijkijijkrts（11）/ijijtdv（12）, , ,kK i j hV m nT mn（13）啟發(fā)式節(jié)約算法啟發(fā)式節(jié)約算法本研究模型在傳統(tǒng)VRP問題上進行了擴展,增加了集貨和送貨任務的時間窗要求以及多輛車可供配置的條件,因此,對于任意訪問節(jié)點,需要將運輸成本的節(jié)省值、時間懲罰費用、租車費用綜合考慮才能構(gòu)造有效可行的啟發(fā)式節(jié)約

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

17、平均利用率貨車平均利用率%平局有效運輸時間比平局有效運輸時間比102147813.293.287.6208478067.591.482.930137872163.288.385.4401610290266.485.388.5502213753475.681.684.8算例結(jié)果論文改進論文改進考慮碳排放的開環(huán)取送貨路考慮碳排放的開環(huán)取送貨路徑優(yōu)化問題徑優(yōu)化問題關(guān)鍵詞關(guān)鍵詞：車輛路徑優(yōu)化、集貨與送貨、碳排放、禁忌搜索、蟻群算法車輛路徑優(yōu)化、集貨與送貨、碳排放、禁忌搜索、蟻群算法論文改進論文改進創(chuàng)新點：創(chuàng)新點：將車輛在集貨配貨中碳排放成本加入到模型中將車輛在集貨配貨中碳排放成本加入到模型中建立了開環(huán)

18、模式下的路徑優(yōu)化問題建立了開環(huán)模式下的路徑優(yōu)化問題對比了禁忌搜索、蟻群算法對本問題的求解效果對比了禁忌搜索、蟻群算法對本問題的求解效果提出了蟻群緊急搜索混合搜索算法，數(shù)值實驗表明該算提出了蟻群緊急搜索混合搜索算法，數(shù)值實驗表明該算法求得的解質(zhì)量最高法求得的解質(zhì)量最高論文改進論文改進123456每個客戶的需求量較小違反時間窗產(chǎn)生懲罰費用假設路上交通狀況良好先取貨后配貨需求確定不可拆分開環(huán)路徑考慮碳排放的開環(huán)考慮碳排放的開環(huán)取送貨路徑優(yōu)化問題取送貨路徑優(yōu)化問題假設條件：假設條件：論文改進論文改進標號含義客戶集貨點集合， 客戶配送點集合默認由1配送給N+1網(wǎng)絡圖節(jié)點集合， 0表示車庫所有弧的集合，

19、顧客i 的需求量， （若 則 ，若 ，則 ）1,2,3,., PN1,2,.,2 DNNN0VPD( , )| ,Ai ji jV ijiqiP0iqiD0iqPDVA論文改進論文改進標號含義車輛 k 的最大裝載量車輛 k 的集合輛 k 車 最大行駛里程顧客 i 時間窗起始時間， 顧客 i 時間窗起始時間，iL TKkLiE TkQiViV論文改進論文改進標號含義單位時間延遲成本單位時間等待成本單位超標碳排放的懲罰成本節(jié)點 i 的等待時間 節(jié)點 i 延遲時間iwpcpiwdpiViV論文改進論文改進標號含義車輛 k 經(jīng)過?。╥,j）的碳排放量?。╥,j）的運輸成本，與運輸距離成正比最大允許碳排

20、放量，若超過此值則按超過量懲罰燃油轉(zhuǎn)換系數(shù) 車輛k 的的燃油消耗系數(shù),kkabi jcWki jW論文改進論文改進表示節(jié)點之間是否有配送關(guān)系的變量，如有則該值為1，否則為0；決策變量含義0-1變量，當車輛 k 經(jīng)過?。╥，j）則為1 ，否則為00-1變量，當任務i被指派給k 時為1，否則為0kiyki jxi jMIPMIP模型模型22220111011122101min() KNKNNNNkkjijijwidikjkijiiKNNkcijkijFfxx cpwppWW011 NKkjjkxK（1）式為目標函數(shù)，最小化運營成本，其中第一項為車輛的啟用成本，第二項為車輛的行駛成本，第三項為車輛的等待成本，第四項為車輛的懲罰成本，第五項為車輛的碳排放成本；（2）式表示車輛數(shù)限制（1）（2）MIPMIP模型模型21 i,jV,ij, NkijikjxykK20 i,jV,ij, NkijjkixykK（3）表示 與 的函數(shù)關(guān)系ki jxkiy（4）表示 與 的函數(shù)關(guān)系ki jxkjy11 /0 KikkyiV（5）式表示一個客戶點的配送或集貨需求只能由一輛車來完成 ,/0,=1, ikjkijyyi jVkK（6）表示每一對取送貨點須同一車輛完成（3）（4）（5）（6）MIPM