干貨|自適應(yīng)大鄰域搜索(ALNS)算法求解帶時間窗的車輛路徑規(guī)劃問...

轉(zhuǎn)眼距離開學(xué)又過去一個多月了，不知道大家在家里學(xué)習(xí)的怎么樣？這段時間小編在家里也沒閑著，時隔多日，再次為大家?guī)砀韶泝?nèi)容！

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

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

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

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

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

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

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

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

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

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

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

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

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

先給出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è)計了模擬退火的接受worse solution策略，概率更新s_c，避免陷入局部最優(yōu)解中。

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

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

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

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

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

destroy算子

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

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

shaw destroy定義了關(guān)聯(lián)結(jié)點，每次選擇與上一個移除的結(jié)點關(guān)聯(lián)度較高的結(jié)點進(jìn)行移除。關(guā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顧名思義就是選擇所有結(jié)點中對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()] );

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

repair算子

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

random repair就不講啦。

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

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

下載代碼后在Main函數(shù)中修改算例參數(shù)，代碼文件夾內(nèi)包括部分Solomon算例和Homberger算例。如果需要修改ALNS部分相關(guān)參數(shù)，可以在ALNSConfiguration內(nèi)修改，重要參數(shù)做了注釋（其實不需要管太多啦）。

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

各個算子的使用情況：結(jié)果顯示：對結(jié)果進(jìn)行驗證：

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

在公眾號內(nèi)輸入【ALNSVRPTW】不帶【】即可下載相關(guān)代碼

?贊 賞?

感謝您，

支持學(xué)生們的原創(chuàng)熱情！

鄭重承諾

打賞是對工作的認(rèn)可

所有打賞所得

都將作為酬勞支付給辛勤工作的學(xué)生

指導(dǎo)老師不取一文

精彩文章推薦

運(yùn)籌學(xué)教學(xué)|Benders decomposition （二）應(yīng)用實例及算法實現(xiàn)（附源代碼及詳細(xì)的代碼注釋）

運(yùn)籌學(xué)教學(xué)|分枝定界求解旅行商問題

運(yùn)籌學(xué)教學(xué) | 十分鐘快速掌握最大流算法（附C++代碼及算例）

運(yùn)籌學(xué)教學(xué)|列生成（Column Generation）算法（附代碼及詳細(xì)注釋）

運(yùn)籌學(xué)教學(xué) | 十分鐘教你求解分配問題(assignment problem)

-The End-

文案 && 編輯&&代碼：周航

（華中科技大學(xué)管理學(xué)院本科一年級：[email protected]）

指導(dǎo)老師 / 秦虎 華中科技大學(xué)管理學(xué)院?

掃一掃，獲取數(shù)據(jù)和模型

還有更多算法學(xué)習(xí)課件分享喲