#分享 排程力 Schedule Z:演算法介紹|VIG_VNS for TSPTW

1月30日 15:54
最近因課程做了一個排程APP小專題,如果你正在發想專題,此文可能對你有幫助,因為這專案有可以改進的部分;如果你是業務、旅行者或出差者,想要安排出最短行程,你正好是此專案的客群;如果你想學習TSPTW演算法,我會詳細介紹演算法細節。 ▎好讀版: 1. 排程力 Schedule Z 1:軟體使用說明
2. 排程力 Schedule Z 2:演算法介紹|VIG_VNS for TSPTW
3. 排程力 Schedule Z 3:結果、結論與心得
4. Schedule Z載點
5. Schedule Z程式原始碼
一、想要解決的問題
▎客群:業務(客戶拜訪)、旅行者(景點安排)、出差者(工作規劃) ▎問題:有時間窗的旅行推銷員問題 (Traveling Salesman Problem with Time Windows, TSPTW) ▎情境:有位旅行者想要安排五天四夜的自由行,手邊有10個想要去的景點,但尚未安排明確時間,同時過夜的飯店地點時間已經決定好了。這些景點,旅行者希望景點(1)~(5)要排在第1~3天、景點(6)~(7)要排在第4~5天、景點(8)~(9)要排在第2~4天、景點(10)要排在第5天。因此旅行者希望能規劃出最短路徑的旅行行程,要符合旅行者要求且不能與舊行程牴觸。 三、Schedule Z價值 ▎在實用性上,可應用在客戶拜訪、景點安排、工作規劃,具有娛樂與商業價值。 ▎在新穎性上,Google日曆與地圖並無提供這類的整合性的最佳規劃。 ▎在技術性上,TSPTW問題是屬於NP-Hard,演算法需特別設計,才能有好的品質。 四、專題發想過程 宗宗之前在力利冷氣工作時,發現每天都會有很多的工作要分派給不同組的師傅們,老闆會希望能排出最順路(最短)的工作行程,一方面節省師傅們的交通時間,另一方面能排更多的工作。由於此APP處理的是排程問題,且這是在力利冷氣中發想的,所以名稱為排程力 Schedule Z。 五、有時間窗的旅行推銷員問題 (Traveling Salesman Problem with Time Windows, TSPTW)
TSPTW為TSP的變型,TSPTW有加入時間窗 (time windows)的限制。所以TSPTW想要找到一個排程,在不違反時間窗限制前提下,其排程總距離為最短距離。 時間窗規範此行程地點的抵達時間,但不規範離開時間。例如:有個行程的時間窗為 (2022/01/18 09:00, 2022/01/18 11:00),則代表我必早上9點~11點抵達此行程,不可以8點到(早到),也不能12到(晚到),但可以12點離開此行程。 六、VIG_VNS algorithm for TSPTW
VIG_VNS演算法是混合Variable Iterated Greedy Algorithm (VIG)和Variable Neighborhood Search (VNS),VIG為主架構,V代表摧毀 (destruction)數量是會變動的,I代表會迭代 (iteration)多次,G代表使用貪婪演算法 (greedy algorithm)執行全域搜尋 (global search),即為DestructConstruct()。VNS可以看成區域搜尋 (local search),把全域搜尋的解再用區域搜尋去優化現行解,即為VNS_1_Opt()。最後使用Superiority of Feasible Solutions (SF)去比較哪一個排程比較好。 七、Variable Iterated Greedy Algorithm (VIG)
VIG中的DestructConstruct(π, n)有兩個階段,分別為摧毀 (destruction)與建構 (construction),π為行程的排列,n為摧毀的數量。 1. 摧毀階段 (destruction):首先先從π中隨機選出n個元素,並將π拆成兩個部分。上圖n = 3,橘色為被選中的元素,會拆成沒選中的部分和有選中的部分。 2. 建構階段 (construction):迭代1時,將選中部分的元素1插入所有可能位置,並比較所有可能的排列,選擇最好的排列當成下一次迭代的排列;迭代2時,將選中部分的元素2插入所有可能位置,再從中選擇最好的排列,直到所有被摧毀的元素都插回排列中為止。上圖1有7個可以插入的位置,因此會產生7條新排列,再從中選出最好的排列當下一次迭代的排列。 八、Variable Neighborhood Search (VNS)
VNS和VIG很像,一樣都有摧毀和建構的階段,只不過是一個一個慢慢摧毀與建構,更像是區域搜尋 (local search)。VNS_1_Opt()同時使用backward_1_Opt()和forward_1_Opt(),backward和forward相似,只不過摧毀與建構方向是相反的,最後再從三個排列(原始、backward、forward)中取最好的。以下為backward_1_Opt()解說 1. 摧毀階段 (destruction):從最後一個元素到最前面的元素,一個一個璀毀,如上圖先從最後一個元素(3)開始摧毀。 2. 建構階段 (construction):將被摧毀的元素,插入到前面所有可以插入的位置中,從這些新排列中選出最好的排列當作下一次迭代的排列,直到摧毀到第一個元素為止。如上圖3前面有4個可以插入的位置,並從這4條中選出最好的排列,當作下一次迭代的排列。 九、Superiority of Feasible Solutions (SF)
使用SF原則去比較兩個排列的優劣,以下情境可以說πa優於πb: 1. πa和πb都是合理的 (feasible)且πa的fitness值比πb小 2. πa是合理的且πb是不合理的 (infeasible) 3. πa和πb都是不合理的且πa違反時間窗的數目比πb少 4. πa和πb都是不合理的且πa和πb違反時間窗的數目相同且πa的fitness值比πb小 十、Fitness function : Adaptive Penalty Approach
Fitness = Cost + Penalty,Cost = Traveling time + Service time,Penalty的部分是會隨著迭代次數而有所變化的。NFT 被定義為距可行區域的閾值距離,從而鼓勵在可行區域內和可行區域的 NFT 鄰域內進行搜索,但不鼓勵超過該閾值。常數建議值為NFT0 = 0.001, lambda = 0.04, alpha = 2。 ▎相關文章 1. 排程力 Schedule Z 1:軟體使用說明
2. 排程力 Schedule Z 2:演算法介紹|VIG_VNS for TSPTW
3. 排程力 Schedule Z 3:結果、結論與心得
4. Schedule Z載點
5. Schedule Z程式原始碼
6. 高等作業系統|使用者的代理人|王友群
17
留言 4
文章資訊
85 篇文章302 人追蹤
Logo
每天有 6 則貼文
共 4 則留言
國立臺灣師範大學
試過Meta-heuristic?
b1 我覺得VIG_VNS就是一種meta-heuristic,我會實作它是因為它比較新(2014)且好實做。😆 我有看到更早的論文用GA, SA, ACO解TSPTW,這些就是典型的meta-heuristic。
國立清華大學
滿有趣的😂😂 上課也能做個app 真有動力
國立屏東大學
我也是這樣想的 (看不懂趕快推