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

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

算法介紹

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

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

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

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

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

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

下面針對這次的VRPTW代碼進行一些講解。當然，這里只是挑選部分重點內容進行講解，代碼總量有2000多行，想要認真研究還需要下載代碼親自查閱哦！

初始解：Greedy方法

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

Greedy構造初始解(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

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

一種解決策略是放寬車輛上限，在后續(xù)優(yōu)化中減少到約束條件內。對這次小編編寫的代碼，還可以采取另一種方式：構造違背約束條件的不可行解。因為在后續(xù)ALNS優(yōu)化部分，我們允許不可行解的存在，因此可以將多余的客戶隨機插入greedy后的路徑中，保證被服務到。

框架：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ū)別在于，算法中設計了模擬退火的接受worse solution策略，概率更新s_c，避免陷入局部最優(yōu)解中。

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

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

算子：destroy&repair

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

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

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

destroy算子

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

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

shaw destroy定義了關聯(lián)結點，每次選擇與上一個移除的結點關聯(lián)度較高的結點進行移除。關聯(lián)度的計算公式如下：

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顧名思義就是選擇所有結點中對cost影響最大的。計算公式如下：

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()] );

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

repair算子

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

random repair就不講啦。

greedy repair也比較好理解，按照greedy策略評估每個結點的最優(yōu)插入位置，進行插入操作。

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

代碼查閱

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

運行結果展示

各個算子的使用情況：

后記

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