Travel_Salesman_Problem(TSP,_旅行推销员问题).pptVIP

旅行推銷員問題Traveling Salesman Problem 漢米爾頓迴圈(Hamiltonian Cycle) 漢米爾頓迴圈(Hamiltonian Cycle) 旅行推銷員問題 一個旅行推銷員必須前往拜訪位於各地的客戶一次，最後再回到原點，則其行走距離(或時間、成本)最短的路線為何? 旅行推銷員問題(TSP)簡介 定義一網路G，節點代表每一顧客，弧線成本表示其距離(或時間) TSP問題即是在網路G上尋找一個經過所有節點恰一次，且總成本最小的迴圈(即成本最小的漢米爾頓迴圈) 通常對應到完全路網(complete graph) 即任意兩點間均存在直接相連之弧線 一般化的旅行推銷員問題 一般化的旅行推銷員問題即是在網路G上尋找一個經過所有節點至少一次，且總成本最小的迴圈 通常對應到實際道路路網 旅行推銷員問題(TSP)簡介 一般化的旅行推銷員問題可以轉換成為標準的TSP問題求解 先求出任意兩點間的最短路徑及其成本。 建構完全路網(complete graph) 旅行推銷員問題之應用 拜訪客戶 自動販賣機補貨、收款 電路板鑽孔 訂單揀貨作業 TSP問題特性 屬於節點服務之網路組合最佳化問題，每個節點恰服務一次 單一車輛 無車輛容量限制 大多先建立一完全網路後再求解 求解複雜度屬於NP-hard，大規模問題難以求得最佳解，實務上多採取「啟發式方法(Heuristics)」求解 TSP問題數學規劃模型 Min s.t. 子迴路 子迴路消除限制式 模型構建練習 TSP問題求解演算法 真正解法(只能處理非常小的問題) 窮舉法、分枝定限法(Branch-and-Bound) 傳統啟發式解法(Heuristics)大致可歸納為以下三種： 路線構建(route construction) 鄰點法、節省法、插入法、掃瞄法…. 路線改善(route improvement) k-Opt交換法、Or-Opt交換法…… 綜合型(composite) 合併執行路線構建及路線改善 最近鄰點法(Nearest-neighbor Heuristic) 任選一節點為起點x 尋找距離節點x最近的節點y作為下一個造訪的節點 尋找距離節點y最近的節點z作為下一個造訪的節點 重覆以上步驟，直到所有節點均已造訪 連接最後一個節點與起點，即形成一個TSP的可行解 最近鄰點法 插入法(Insertion Method) 任選一節點為起點a 尋找距離節點a最近的節點b作為下一個造訪的節點，形成a-b-a的子迴路 尋找距離子迴路最近的節點k作為下一個插入點 尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子迴路。 ?插入成本：Cik+Ckj-Cij 重覆步驟3~4，直到所有節點均已插入迴路之中，即形成一個TSP的可行解 插入法 2-opt 交換法 先構建一個起始可行解 在可行解中任選兩個不相鄰的節線(a?b, c?d)，以及另外兩條對應之替換節線(a?c, b?d)，計算替換後總成本是否降低 (即檢查替換成本是否小於0)。 ?替換成本：Cac+Cbd-Cab-Ccd (對稱型TSP) 若替換後總成本有降低，則予以替換，同時變更中間相關弧線的行走方向 重覆步驟2~3，直到所有可能的替換均無法再降低成本為止 2-opt 交換法 TSP問題求解演算法 傳統啟發式解法(Heuristics)只在目標值有改善時才進行交換，常會陷入局部最佳解，而無法進一步找到更好的解 巨集啟發式方法(Meta-heuristics)則以傳統的啟發式解法為基礎，並根據一些高階的搜尋策略指導下層的啟發式方法，以避免陷入局部最佳解 TSP問題求解演算法 常見之巨集啟發式方法(Meta-heuristics) 禁制搜尋法(Tabu Search, TS) 基因演算法(Genetic Algorithm, GA) 模擬退火法(Simulated Annealing, SA) 門檻接受法(Threshold Accepting, TA) 類神經網路(Neural Network, NN) 蟻群演算法(Ant Colony Optimization, ACO) 其他 TSP延伸性問題 含時窗限制 非對稱性節線成本 多個旅行推銷員 即時性TSP 其他 * * 树葛稽硷慈酮榆诛耿湃睡却獭饭苫潍舜漆拖揖迁滇亥历渣浚兆夹肌导惜革Travel_Salesman_Problem(TSP,_旅行推销员问题)Travel_Salesman_Problem(TSP,_旅行推销员问题) Chapter 7 惮皂箱释盒下济染娃匆膜细晕妨善敖转睦琳硫虏兹妹萨疗襟舅仟洁约目羊Travel_Salesman_Problem(TSP,_旅行推销员问题)Travel_Salesman_Problem(TSP