禁忌搜索算法公式

1、6.2基于均衡原理的LRP算法設(shè)計(jì)6.2.1基于均衡原理的LRP算法整體流程基于均衡原理的LRP算法整體流程如下：stepl：初始化，設(shè)置整體收斂性判斷參數(shù)S；step2：隨機(jī)生成一組LRP選址問題的解D,求出相應(yīng)的目標(biāo)值F ;step3:根據(jù)上層解D ,利用Fraiik-Wolfe算法（見6.2.3節(jié)）求出各客戶的貨物總量。及客戶在各配送中心的貨物均衡分配量X；step4：根據(jù)D及運(yùn)用禁忌算法求解VRP問題（見6.2.4節(jié)），得出各配送中對(duì)各客戶的單位貨物配送費(fèi)用C,廣step5：根據(jù)弟，及公式（6-8）求出下層尤/與次的關(guān)系光,廣怦次+乂疽step6：將LRP模型上層目標(biāo)函數(shù)中用代替，并代

2、入下層求得的。和。；/，運(yùn)用禁忌算法求得新的LRP選址規(guī)劃的解Z及目標(biāo)函數(shù)F（見6.2.2節(jié)）；step7：如果F -FN/NT，則置i點(diǎn)為0,否則置1。重復(fù)以上步驟m次，得到初始解。鄰域的搜索根據(jù)本章選址問題的特點(diǎn)，設(shè)計(jì)了三種鄰域操作，分別為自身取反、2-swap交換和2-opt 交換。1）.自身取反。為單點(diǎn)操作，即選擇解中i點(diǎn)，對(duì)該點(diǎn)的值取反；2）. 2-swap交換。為雙點(diǎn)操作，選擇解中兩點(diǎn)進(jìn)行交換，其它位置的值不變。例如解001101 中的2、6點(diǎn)被選中，則2-swap交換后變?yōu)椋?11100；3）. 2-opt交換。為多點(diǎn)操作，選擇解中兩點(diǎn)進(jìn)行交換，同時(shí)兩點(diǎn)之間的值逆序改變。例 如解

3、001101中的2、6點(diǎn)被選中，則2-swap交換后變?yōu)椋?10110；.自身取反、2-swap交換操作能較快的搜索到局部最優(yōu)解，2-opt交換則能擴(kuò)大搜索空 間。自身取反、2-swap交換是每個(gè)循環(huán)都進(jìn)行的操作，進(jìn)行局部尋優(yōu)。當(dāng)/代最優(yōu)解沒有 變化時(shí)，進(jìn)行一次2-opt交換操作，跳出局部最優(yōu)點(diǎn)。將以上三種鄰域結(jié)合，不僅保持了 TS局部”爬山”能力強(qiáng)的優(yōu)點(diǎn)，同時(shí)也讓它的全局尋 優(yōu)能力大大加強(qiáng)。約束的處理本章LRP模型上層約束包括分廠數(shù)量約束和總投資額約束。對(duì)于分廠數(shù)量限制，本章 在鄰域操作中加以控制：如果當(dāng)前解經(jīng)過某鄰域操作，遷反分廠數(shù)量限制，則取消此鄰域操 作。對(duì)于總投資額約束，本章采用懲罰

4、函數(shù)的方式進(jìn)行處理，把超出約束的量乘以一個(gè)懲罰 系數(shù)，作為一個(gè)懲罰項(xiàng)加入到解的適應(yīng)度中。上層目標(biāo)函數(shù)的適應(yīng)度S可以表示為：S =廠。勺(Z) + P * max(QB 乙 - M)/ jeJjeJ/式中P表示總投資額約束的懲罰系數(shù)。禁忌表和終止準(zhǔn)則根據(jù)本禁忌算法鄰域性質(zhì)的不同，本章設(shè)計(jì)了兩種禁忌表：局部禁忌表和全局禁忌表。 局部禁忌表存儲(chǔ)的是自身取反、2-swap交換鄰域操作的對(duì)象，即如果當(dāng)前解采用了某種鄰 域，那么在接卜.來的個(gè)循環(huán)內(nèi)不允許進(jìn)行該鄰域的逆操作。全局禁忌表存儲(chǔ)的是尋優(yōu)過程 中每個(gè)循環(huán)的解值，此禁忌表只在選用2-opt交換操作時(shí)采用，避免進(jìn)行重復(fù)搜索，加快尋 優(yōu)速度。如果經(jīng)過某鄰

5、域操作得到比當(dāng)前最好解更好的解，那么不管該鄰域是否被禁忌，都采用 該鄰域作為當(dāng)前鄰域。終止條件：如果連續(xù)2代最優(yōu)解沒有改變，則終止循環(huán)，算法結(jié)束。關(guān)鍵步驟stepl：初始化各參數(shù)，搜索循環(huán)次數(shù)，JO：step2：形成初始解，令初始解為當(dāng)前解，其解值為當(dāng)前最優(yōu)解值了 *；step3： /:=/ + !：step4：如果連續(xù)義代最優(yōu)值沒有改變，轉(zhuǎn)step 12,否則繼續(xù)：step5：如果進(jìn)行2-opt鄰域操作后，連續(xù)/花最優(yōu)值沒有改變，繼續(xù)，轉(zhuǎn)step7；step6：搜索當(dāng)前解的2-opt鄰域，轉(zhuǎn)step8；step7：搜索當(dāng)前解的自身取反和2-swap兩種鄰域；steps：按鄰域解值降序排列各鄰

6、域，令j = 0,第/個(gè)鄰域解值為打step9： j：= y + l;steplO：判斷是否大于/*,是則令/*：=/,，令第/個(gè)鄰域解為當(dāng)前解，轉(zhuǎn)step3； 否則繼續(xù)：stepl 1：判斷第，個(gè)鄰域解是否違反禁忌規(guī)則，是則轉(zhuǎn)i：否則令其為當(dāng)前解；轉(zhuǎn)step3； step 12：終 lL6.2.3物流配送均衡模型的Fraiik-Wolfe算法設(shè)計(jì)在得到上層的解。后，本章采用Fraiik-Wolfe算法解下層物流配送均衡模型。該法是用 線性規(guī)劃逐步迭代逼近非線性規(guī)劃的方法，在每步迭代中，先找到一個(gè)目標(biāo)函數(shù)的最速下降 方向，然后再找到一個(gè)最優(yōu)步長(zhǎng)，在最速方向上截取最優(yōu)步長(zhǎng)得到下一步迭代的起點(diǎn)，重復(fù) 迭代直到找到最優(yōu)解。Fiaiik-Wolfe算法解物流配送均衡模型詳細(xì)步驟如卜:stepl：初始化：按照C. = C.實(shí)行一次全有全無(wú)分配，得到客戶分配到各配送中心的貨物量；令 =1；step2：更新各配送中心的單位貨物服務(wù)費(fèi)用：=step3：尋找下一步的迭代方向：按照實(shí)行一次全有全無(wú)分