乾貨|自適應大鄰域搜索（ALNS）算法求解帶時間窗的車輛路徑規劃問題（附JAVA代碼）

• 2020 年 3 月 26 日
• 筆記

算法介紹

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

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

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

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

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

第二個特點是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  

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

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

框架：ALNSProgress

先給出ALNS框架的偽代碼：

ALNSProgress(by.zll):      global_solution = initial_solution；    local_solution = global_solution；      for i = 0 to MaxIteration:      // 產生新解    	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  

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

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

每當一組算子被選擇後，根據算子更新的s_g的優劣，動態更新算子的參數，在一定步長後更新算子被選擇的概率。

算子：destroy&repair

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

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

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

destroy算子

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

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

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

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策略評估每個結點的最優插入位置，進行插入操作。

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

代碼查閱

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

如果需要修改ALNS部分相關參數，可以在ALNSConfiguration內修改，重要參數做了注釋（其實不需要管太多啦）。

運行結果展示

各個算子的使用情況：

結果顯示：

對結果進行驗證：

後記

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