遺傳演算法求解帶時間窗的車輛路徑規劃問題
1.遺傳演算法
遺傳演算法簡介
遺傳演算法（Genetic Algorithm，簡稱GA）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的基于種群的隨機化搜索方法，它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構物件進行操作，不存在求導和函式連續性的限定；具有內在的隱并行性和更好的全域尋優能力；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則，遺傳演算法的這些性質，已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域，遺傳演算法是現代智能計算中的關鍵技術之一，
遺傳演算法基本思想
在現實生活中，生物的染色體通過基因控制了生物的性狀，而生物的性狀決定了生物在環境中的適應度，適應度高的生物，其基因更容易流傳下來，隨著時間的不斷流逝，整個種群的適應度隨之提高，
遺傳演算法和現實非常類似，首先將問題的解通過一定的方法，編碼到染色體中，通過適應度函式，得到每個個體的適應度，通過選擇，將適應度高的個體保留到下一代中，不斷迭代，即可獲得滿意解，
遺傳演算法流程
2.帶時間窗的車輛路徑規劃問題介紹
車輛路徑規劃問題介紹
車輛路徑規劃問題，經過60年來的研究與發展，研究的目標物件，限制條件等均有所變化，已經從最初的簡單車輛安排調度問題轉變為復雜的系統問題，最初的車輛路徑規劃問題可以描述為：有一個起點和若干個客戶點,已知各點的地理位置和需求,在滿足各種約束的條件下,如何規劃最優的路徑,使其能服務到每個客戶點,最后回傳起點，通過施加不同的約束條件，改變優化的目標，可以衍生出不同種類的車輛路徑規劃問題，同時車輛路徑規劃問題屬于典型的NP-hard問題，其精確演算法能求解的規模很小，故啟發式演算法也就成了研究熱點，
VRPTW簡介
VRPTW(Vehicle routing problem with time windows)即帶時間窗的車輛路徑規劃問題，其對于每一需求點加入了時間窗的約束，即對于每一個需求點，設定服務開始的最早時間和最晚時間，要求車輛在時間窗內開始服務顧客，
需求點的時窗限制可以分為兩種，一種是硬時間窗(Hard Time Window)，即要求車輛必須在時間窗內開始服務顧客，早到必須等待，遲到就拒收，另一種是軟時間窗(Soft Time Window)，不一定要在時間窗內開始服務顧客，但是在時間窗外開始服務必須要懲罰，以懲罰代替等待與拒收是軟時間窗和硬時時間窗的最大的區別，
VRPTW的數學模型如下：
（2.2）保證了每個顧客只被訪問1次
（2.3）保證了裝載的貨物不超過容量
（2.4）（2.5）（2.6）確保了每輛車從depot出發最后回到depot
（2.7）（2.8）確保在時間窗內開始服務
在干貨 | 十分鐘掌握禁忌搜索演算法求解帶時間窗的車輛路徑問題(附C++代碼和詳細代碼注釋)中詳解介紹了如何用禁忌搜索（Tabu Search）演算法求解VRPTW，
3.演算法具體實作
染色體設計
在論文：A simple and effective evolutionary algorithm for the
*vehicle routing problem *中，作者提出了在用GA解決VRP時的幾點注意事項，如下圖所示：
簡單來說染色體的設計可以遵循以下兩點：
-
使用和TSP問題中類似的染色體、編碼，沒有分隔符
- 使用split方法將染色體轉化為問題的解
在使用GA求解VRPTW的程序中，常見的問題就在于交叉后產生的大量不可行解，這里采用分割的思想，一個染色體所存的解是split函式操作后所產生的最優分割，這樣所得到的解都為可行解，大大減少了無效搜索，
在所有分割里，能最小化目標函式的即為最優分割，其實這就是一個編碼和解碼的程序，
下面我們來具體介紹一下這個split方法:
大家可能會覺得獲得最優分割是一個很困難的事情，其實引入圖論的思想，利用Bellman-Ford演算法，在O(n^2)內就能獲得最優分割，
上面兩個圖展示了如何把原問題轉化為一個圖論中的問題：
將每個基因位設為一個點，假如將i到j連接，其路徑滿足容量約束和時間窗約束，則視為從i到j存在一條權值為路徑長度的邊，則最優分割即為從染色體開頭的基因的點到結尾的基因的點的最短路，利用Bellman-Ford演算法，可在O(n^2)中求出最優分割，
流程圖如下：
群體多樣性
遺傳演算法中常見的問題就是早熟，過早收斂，為了避免這種情況的發生，就要保證子代個體中各個個體的不同，
如何判斷個體之間是否相同有很多演算法，小編這里采用通過適應度的不同來判斷的方法：
即兩個個體的適應度相差大于一個值，即視為不同的個體，
crossover
crossover，即交叉操作，這里使用實數編碼中常用的OX（Order Crossover）交叉算子，
OX 交叉算子的程序如圖：
-
隨機選擇兩個點i,j，其中0<=i<=j<=N,N為染色體長度，
-
將親代P1從i到j的基因填入子代相同的位置，
-
將親代P2的基因不重復地依次填入子代中，
交換p1,p2,即可產生兩個子代，
4
mutation
mutation，即突變操作，這里簡單地隨機交換染色體中的兩個基因，程序如下圖：
5
selection
選擇的方法有很多，這里使用二進制錦標賽選擇，每次從親代中選擇兩個個體進行比較，將適應度大的個體保留到親代中即可，
4.代碼
代碼由小編獨立完成，有不周到之處還請多指教！
分為以下幾個類：
Chromosome類為染色體類，提供了和Solution類的相互轉換，即編碼和解碼程序，Customer類儲存了具體的顧客，Conf類是引數的設定，Solution類儲存了解，GA_Stategy中實作了遺傳演算法用的函式，
運行結果如圖：
參考文獻：
[1]Anderson E, Phillips C, Sicker D, et al. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 2004, 31(12):1985-2002.**
[2]Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 1987, 35(2):254-265.**
有問題歡迎交流：郵箱 [email protected]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138114.html
標籤：其他
上一篇：演算法題--整數轉羅馬數字