乾貨|蟻群演算法求解帶時間窗的車輛路徑規劃問題詳解（附Java程式碼）

• 2020 年 2 月 25 日
• 筆記

學 習 警 告

一眨眼春節又過去了，相信很多同學也和小編一樣，度過了一段時間相對輕鬆的時光。

當然，玩耍過後也不能忘記學習。本著~造福人類~的心態，小編又開始幹活，為大家帶來 有 · 趣 的乾貨演算法內容了！

本期為大家帶來的內容是蟻群演算法，解決大家熟悉的帶時間窗的車輛路徑規劃問題。關於蟻群演算法，公眾號內已經有相關內容介紹TSP：

乾貨 | 十分鐘快速搞懂什麼是蟻群演算法(Ant Colony Algorithm, ACA)（附程式碼）

本文主要分為以下部分：

蟻群演算法簡介

蟻群演算法與VRPTW

程式碼測試

筆記總結

01

蟻群演算法簡介

蟻群系統(Ant System或Ant Colony System)一種群體仿生類演算法，靈感來源於在螞蟻覓食的過程。學者們發現，單個螞蟻的行為比較簡單，但是蟻群整體卻可以體現一些智慧的行為，例如可以在不同的環境下找到到達食物源的最短路徑。

經進一步研究發現，螞蟻會在其經過的路徑上釋放一種可以稱之為「資訊素」（phenomenon）的物質，蟻群內的螞蟻對資訊素具有感知能力，它們會沿著資訊素濃度較高路徑行走，而每隻路過的螞蟻都會在路上留下資訊素。這樣經過一段時間後，整個蟻群就會沿著最短路徑到達食物源了。

蟻群演算法通過模仿螞蟻「每次在經過的較短路徑上留下資訊素」的行為，通過資訊素記錄下較優結果，不斷逼近最優解。

02

蟻群演算法與VRPTW

VRPTW在之前的推文里已經提到過多次了，這裡不再詳細介紹。感興趣的朋友可以看過去的推文：

禁忌搜索演算法求解帶時間窗的車輛路徑規劃問題詳解（附Java程式碼）

通過上面的介紹，大家不難想到，蟻群演算法的關鍵在於資訊素的利用。在蟻群尋找食物時，每次都由一隻螞蟻從頭開始尋找（不同於禁忌搜索或遺傳演算法的鄰域動作）；每次尋找的不同點在於資訊素的改變：不斷靠近資訊素較濃的路徑。

用蟻群演算法解決VRPTW的過程主要分為以下幾步：

1.初始化螞蟻資訊（以下用agents表示）；

2.為每位agents構造完整路徑；

3.更新資訊素；

4.迭代，保存最優解。

演算法的關鍵在第二步：構造解時該如何查找下一個服務的客戶。

我們用以下公式計算客戶j被服務的概率：

03

程式碼測試

這次程式碼是由小編親自編寫的，由於是第一次編寫ACS的VRPTW程式碼，有不周之處還請多包涵。

因為小編太懶了，具體程式碼就不在此展示了，有興趣的朋友可以在公眾號內輸入【ACSVRP】不帶【】即可下載對應Java程式碼。

這裡展示一下程式碼的運行情況。對Solomon Benchmark C101算例的測試效果如下：

25點（迭代次數1000，算例最優解191.3）：

50點（迭代次數1000，算例最優解362.4）：

100點（迭代次數1000，算例最優解827.3）：

從測試數據來看，結果似乎不是很好。。。不過，VRPTW僅是一個載體，目的是為了深入了解蟻群演算法的運行機制。 小編在測試時發現，參數設置地不同對結果還是有一定影響的。演算法偶爾會跑出單個點構成的路徑，小編認為應該加大時間窗對應參數w_2，效果有一些提升。推薦的參數已經默認設置在程式碼中。

同時，蟻群演算法也有其他仿生類演算法的特點，比較容易早熟。這點在測試100點數據是尤為明顯，全局最優解可能與前100次迭代的最優解相同。

04

筆記總結

大致了解了蟻群演算法對VRPTW的求解過程後，我的第一感覺是，和禁忌搜索的思路其實很像：兩者都是利用過去搜索的「記憶」指導下一步走向。禁忌禁止一些方向，資訊素引導一些方向。但兩者又有很大區別：禁忌搜索作為鄰域搜索類演算法，每次都在舊解里變換出新解；蟻群演算法卻需要重新派出螞蟻走完全程。對比之下，每次迭代時蟻群演算法可能需要跟更多花費時間。從測試結果來看，蟻群演算法確實沒有禁忌搜索高效。當然，這可能和小編個人編寫程式碼的能力有關。

但不可否認的是，大自然的智慧確實不同尋常，在每一個領域都閃耀著光輝，如此美妙絕倫。

（小小的螞蟻，也蘊藏著讓人意想不到的智慧呢！）

那麼本期的內容差不多就到此為止了。如果感覺還不夠明白，可以登錄公眾號【程式猿聲】，輸入【ACSVRP】不帶【】，即可獲取相關Java程式碼，再作研究。

#

-The End-

文/舟寒丶

版/舟寒丶

碼/可憐的打工仔舟寒丶

審/工地老闆番茄雞蛋炒飯丶

#