大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 祝大家元宵節快樂
本文引用
Shaw P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[M]// Principles and Practice of Constraint Programming — CP98. 1998.
劉小蘭, 郝志峰, 汪國強, et al. 有時間窗的車輛路徑問題的近似算法研究[J]. 計算機內建制造系統, 2004, 10(7):825-831.
Shaw P的這篇論文首次提出大規模鄰域搜尋算法（後文統一稱為LNS），之前小編寫的推文感覺有點簡單，這次再一次精度了這篇經典論文後，決定用MATLAB編寫文中的提出的LNS求解帶時間窗的車輛路徑問題（後文統一稱為VRPTW問題）的代碼。
小編會帶大家詳細梳理LNS的基本流程，其實說白了LNS隻包括兩個步驟：Remove和Re-inserting，先别急後文會詳細介紹針對VRPTW問題，如何Remove和如何Re-inserting；然後用MATLAB編寫LNS代碼求解VRPTW問題。
1.LNS流程
Remove過程是如何選擇出移走的客戶，Re-inserting過程是如何快速地将客戶插到能産生更好解地位置。
1.1 Remove過程
用符号
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示目前解，
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示将要被移走的客戶，
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示被移走的客戶組成的集合，
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示移走的客戶數目，
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示從
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中移走
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 個客戶後剩餘的部分解。則Remove過程如下：
首先，從
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中随機移走一個客戶到
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中，作為集合
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 的第一個元素。剩下的
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 個元素按照如下方法來標明：每次從集合
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中随機選一個客戶
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ，将
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中剩餘的客戶按照與
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 的相關性由小到大的順序排列。從
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中選出與
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 的相關性最大的客戶
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ，從
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中移走
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ，并把它加入到
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中去。重複該過程
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 次，直到剩下的
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 個元素都選好。相關性的定義為：
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 其中
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示将
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 标準化後的值，在[0,1]之間，
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 與
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 之間的歐式距離。
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 與
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 是否在同一條路徑上，即是否由同一輛車服務。如何在同一條路徑上時為0，否則為1。
也就是說地理位置相距很近的兩個客戶的相關性比相距很遠的要大；在同一條路徑上的兩個客戶的相關性比不在同一條路徑上的要大。
實際情況中，不存在完美的相關性函數，如果過度依賴相關性函數選擇被移出的客戶可能會出現“鼠目寸光”的情況。為避免這種情況的出現，Shaw在算法中加入了随機元素，即
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ，它的結果是相關性大小序列中的一個客戶，即假設
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 然後将
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中剩餘的客戶按照與
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 的相關性由大到小的順序排列，得到排序後的序列為lst，是以上述過程的結果為lst[index]。可以看出當D為1時，被移出的客戶是完全随機選擇的；當D等于正無窮時，即接近選擇相關性最大的客戶。也就是說D的值越大，越有利于相關性大的客戶。
Remove過程的僞代碼如下所示：
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 1.2 Re-inserting過程
Re-inserting過程是将移走的客戶集
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 重新插回部分解
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ，以産生更好的解。首先計算
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中每一個客戶的最佳插入位置，将
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中的客戶
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 插回部分解
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ，在多個插入位置中，找出使目标值增加最少的那個位置即為最佳插入位置（該插入位置即為cheapest insertion point），并記下對應的目标值。那麼如何從
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 選擇客戶
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 插回到
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中，以産生更好的解呢？
計算
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中每一個客戶插入到各自的最佳插入位置後所帶來的目标值增量，選擇目标值增量最大的客戶作為第一個插回客戶,該方法被稱farthest insertion heuristic。将此方法重複執行直到
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中的所有客戶都被重新插回部分解
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 。
Shaw 在Re-inserting過程中還使用了有限偏差搜尋(Limited Discrepancy Search，LDS)以提高搜尋效率。但說句實在話，小編沒有看明白如何用LDS提高搜尋效率。
此處可以省略不看
不過在這裡還是有必要介紹一下LDS：它是建立在“手頭上已經有求解某個問題的 一種較好的啟發式算法”的基礎上的，其基本思想是：假設按照事先設計的啟發式算法不能找到目标，則很有可能是算法在幾個關鍵點上“出差錯了”—— 本該朝東走的，卻在朝西走了。如果允許算法在這些關鍵點上“犯錯誤”——背離算法在這些點的走向，轉向其他方向，然後繼續按照算法搜尋下去，則極有可能找到目标。運用到VRPTW，D=0表示全部的客戶都插入到最佳位置，記為
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ，其中
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 表示第i個插回客戶的插入位置，0表示插入到最佳位置，可以看出滿足
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） ；D=1表示
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中隻有一個客戶插入到其第二好的位置，其餘的都插入到最佳位置，即滿足
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 的位置，如（1,0,......,0）;D=2表示
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中一個客戶插入到其第三好的位置，或者
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 中兩個客戶插入到其第二好的位置，即滿足
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 的位置，如（2,0,......,0）,(1,1,......,0)，其餘依此類推，其中D的上限d為一事先給定的值。
2.MATLAB代碼（背景回複“LNS”提取代碼）
代碼說明：直接運作LNS.m即可（小編是按照自己的了解編寫代碼的，可能與論文中講的不太一緻，在這裡還是希望大家多和小編交流，大家共同進步）
連結：https://pan.baidu.com/s/1w1kvuNx3ESi_d2uNSrKZ6A
提取碼：x10h
用CW法構造VRPTW初始解（資料集采用solomon中的c101），共需要12輛車，總距離是916.8716；
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 用LNS優化初始解後，共需要11輛車，總距離是884.1077（這裡各位小夥伴運作的解可能與我的不一樣，沒關系，因為我在程式設計式的時候，設定隻要優化後的總距離一旦小于初始總距離就立馬跳出循環）
大規模鄰域搜尋（LNS）求解帶時間窗的車輛路徑問題（VRPTW）（附MATLAB代碼） 
