鄰域搜索類啟發(fā)式算法有很多種，比如禁忌搜索啦，模擬退火啦，變鄰域搜索啦等等。這次帶來的自適應(yīng)大鄰域搜索代碼，相對(duì)上述幾種會(huì)更復(fù)雜，內(nèi)容相對(duì)全面。

小編在編寫代碼時(shí)，主要采用git-hub上一位作者de.markusziller的代碼，參考他的ALNS框架下寫出了解決帶時(shí)間窗的車輛路徑規(guī)劃問題的代碼，今天文章的主要內(nèi)容將圍繞代碼實(shí)現(xiàn)展開。下面就開始今天的內(nèi)容吧！

算法介紹

有關(guān)ALNS概念的介紹，公眾號(hào)內(nèi)已經(jīng)有相關(guān)內(nèi)容了，這里稍提一下，有疑惑的同學(xué)可以參考往期內(nèi)容：

干貨 | 自適應(yīng)大鄰域搜索(Adaptive Large Neighborhood Search)入門到精通超詳細(xì)解析-概念篇

干貨|自適應(yīng)大規(guī)模鄰域搜索算法求解帶時(shí)間窗的車輛路徑規(guī)劃問題（上）

簡單的講，ALNS主要有兩個(gè)特點(diǎn)：1.先用destroy方法破壞當(dāng)前解，再用repair方法組合成新解。2.設(shè)計(jì)一組destroy，repair方法，動(dòng)態(tài)評(píng)估每種方法的效果，在搜索中選用效果較好的方法。

ALNS算法是脫胎于大鄰域搜索算法（Large Neighborhood Serach，LNS）的，第一個(gè)特點(diǎn)就是LNS的關(guān)鍵。通過帶有隨機(jī)性的destroy、repair方法構(gòu)造新解，從而對(duì)解空間進(jìn)行啟發(fā)式搜索。

第二個(gè)特點(diǎn)是ALNS的自適應(yīng)部分。類似于蟻群算法中的信息素，或禁忌搜索算法重點(diǎn)的禁忌表，由于ALNS算法的解空間是有destroy和repair方法定義的，因此這里記憶的主要是算子的使用情況。

下面針對(duì)這次的VRPTW代碼進(jìn)行一些講解。當(dāng)然，這里只是挑選部分重點(diǎn)內(nèi)容進(jìn)行講解，代碼總量有2000多行，想要認(rèn)真研究還需要下載代碼親自查閱哦！

初始解：Greedy方法

初始解的構(gòu)造一般采用簡單的greedy方法，這里小編編寫了一個(gè)簡單的greedy算法在滿足時(shí)間窗約束和容量約束的情況下，往路徑中不斷加入距離最后一個(gè)客戶距離最近的客戶，若不滿足約束，則使用下一輛車。

Greedy構(gòu)造初始解(by.zll)： solution = 空集； new route = 空集； add depot to new route； while unserved customers > 0: c = find the closest customer（）； if satisfy load constraint and time windows constraint: add c to new route； else: add new route to solution； new route = 空集； end while return solution

不過在實(shí)際測試中，小編也發(fā)現(xiàn)這種方法的一些缺陷。車輛數(shù)量約束較小、客戶較少的Solomon算例，這種算法沒有太大問題，而且構(gòu)成的解效果不錯(cuò)；但對(duì)車輛約束較大、客戶較多的Homberger算例，初始解可能無法在車輛約束內(nèi)裝滿客戶。因此構(gòu)造方法還是視算例情況而定。

一種解決策略是放寬車輛上限，在后續(xù)優(yōu)化中減少到約束條件內(nèi)。對(duì)這次小編編寫的代碼，還可以采取另一種方式：構(gòu)造違背約束條件的不可行解。因?yàn)樵诤罄m(xù)ALNS優(yōu)化部分，我們?cè)试S不可行解的存在，因此可以將多余的客戶隨機(jī)插入greedy后的路徑中，保證被服務(wù)到。

框架：ALNSProgress

先給出ALNS框架的偽代碼：

ALNSProgress(by.zll): global_solution = initial_solution； local_solution = global_solution； for i = 0 to MaxIteration: // 產(chǎn)生新解 current_solution = local_solution; destroy_opt = Chose_destroy(); destroy_solution = Destroy(destroy_opt, current_solution); repair_opt = Chose_repair(); new_solution = Repair(repair_opt, destroy_solution); // 更新滿意解 if new_solution better than global_solution: Update_global_solution(new_solution, local_solution, destroy_opt, repair_opt); else if new_solution better than local_solution: Update_local_solution(local_solution, destroy_opt, repair_opt); else Update_worse_solution(local_solution, destroy_opt, repair_opt); // 更新算子選擇策略 Update_OptChose_strategies(); end while return global_solution

框架主要將解區(qū)分為global_solution（以下簡稱s_g）、local_solution（以下簡稱s_c）和current_solution（以下簡稱s_t）。s_c與s_g的區(qū)別在于，算法中設(shè)計(jì)了模擬退火的接受worse solution策略，概率更新s_c，避免陷入局部最優(yōu)解中。

每個(gè)算子都有一定的選擇概率，通過輪盤賭的方式隨機(jī)選擇本次迭代使用的算子。

每當(dāng)一組算子被選擇后，根據(jù)算子更新的s_g的優(yōu)劣，動(dòng)態(tài)更新算子的參數(shù)，在一定步長后更新算子被選擇的概率。

算子：destroy&repair

相對(duì)于ALNSProgress框架，算子和所解決的問題相關(guān)度更大。前文的框架適用于任何問題，而算子部分則需要針對(duì)解決的問題進(jìn)行重寫。有關(guān)VRPTW的destroy、repair算子，公眾號(hào)內(nèi)有一篇推文進(jìn)行過詳細(xì)介紹：

干貨|自適應(yīng)大規(guī)模鄰域搜索算法求解帶時(shí)間窗的車輛路徑規(guī)劃問題（上）

這里簡單講一下小編所采用的算子。小編的算子主要參考了原先的代碼，由于解決的問題不同，小編進(jìn)行了修改調(diào)整，有一定原創(chuàng)性，童鞋們?nèi)绻X得效果不好可以自行修改、增刪。

destroy算子

小編編寫了三個(gè)destroy算子：random destroy、shaw destroy、worst cost destroy。

random destroy隨機(jī)remove一定量客戶，沒啥好講的。

shaw destroy定義了關(guān)聯(lián)結(jié)點(diǎn)，每次選擇與上一個(gè)移除的結(jié)點(diǎn)關(guān)聯(lián)度較高的結(jié)點(diǎn)進(jìn)行移除。關(guān)聯(lián)度的計(jì)算公式如下：

int l = (lastRoute.getId() == s.routes.get(j).getId())? -1 : 1; double fitness = l * 2 + 3 * distance[lastRemove.getId()][relatedNode.getId()] + 2 * Math.abs(lastRemove.getTimeWindow()[0] - relatedNode.getTimeWindow()[0]) + 2 * Math.abs(lastRemove.getDemand() - relatedNode.getDemand());

worst cost destroy顧名思義就是選擇所有結(jié)點(diǎn)中對(duì)cost影響最大的。計(jì)算公式如下：

double fitness = (route.getCost().getTimeViolation() + route.getCost().getLoadViolation() + customer.getDemand()) * ( distance[customer.getId()][route.getRoute().get(0).getId()] + distance[route.getRoute().get(0).getId()][customer.getId()] );

變量名應(yīng)該寫的比較清楚，如果還有疑問，可以查看具體代碼。

repair算子

repair也寫了三個(gè)算子，分別是：random repair， greedy repair 和regret repair。

random repair就不講啦。

greedy repair也比較好理解，按照greedy策略評(píng)估每個(gè)結(jié)點(diǎn)的最優(yōu)插入位置，進(jìn)行插入操作。

greedy repair的不足之處在于，總是將那些困難（能使目標(biāo)函數(shù)值提高很多）的顧客放到后面插入。這使得可插入的點(diǎn)變得很少。regret repair對(duì)比了兩個(gè)較優(yōu)插入位置，計(jì)算delta cost，最大化把顧客插入到最好的中和第2好的位置中目標(biāo)函數(shù)的差異。

代碼查閱

下載代碼后在Main函數(shù)中修改算例參數(shù)，代碼文件夾內(nèi)包括部分Solomon算例和Homberger算例。

運(yùn)行結(jié)果展示

各個(gè)算子的使用情況：

后記

關(guān)于ALNS，小編還會(huì)專門做一期測試對(duì)比，展示一下ALNS的效果。同時(shí)，這段代碼里面還有一部分可視化的內(nèi)容，可以實(shí)時(shí)查看算子的使用情況和解的收斂情況，也會(huì)更新相關(guān)內(nèi)容，敬請(qǐng)期待！