chap7-旅行推销员问题课件

旅行推銷員問題

TravelingSalesmanProblemChapter71漢米爾頓迴圈(HamiltonianCycle)環遊世界問題:

有個人想環遊世界，他選出全世界的二十個著名城世,然後在地圖上開始他的作業。他打算規畫出一條路線,使他可以依序地玩遍這二十個城市。但問題是並不是任兩個城市皆有飛機直航,而他又不願重覆去同一個城市兩次。這個問題轉化為圖論上便是所謂的漢米爾頓迴圈(HamiltonCycle)，於1857年愛爾蘭數學家漢米爾頓(SirWilliamHamilton)首次提出。漢米爾頓迴圈(HamiltonCycle)不一定存在2推廣問題:

我們可進一步加入每段航程的距離(或是票價)，然後試圖找出最短的總飛行距離(或是最便宜的總票價)是怎樣的一條路線。8050203010070805020301007080+70+50+100=300805020301007080+20+50+30=180203010070100+20+70+30=220漢米爾頓迴圈(HamiltonianCycle)3旅行推銷員問題一個旅行推銷員必須前往拜訪位於各地的客戶一次，最後再回到原點，則其行走距離(或時間、成本)最短的路線為何?4旅行推銷員問題(TSP)簡介定義一網路G，節點代表每一顧客，弧線成本表示其距離(或時間)TSP問題即是在網路G上尋找一個經過所有節點恰一次，且總成本最小的迴圈(即成本最小的漢米爾頓迴圈)通常對應到完全路網(completegraph)即任意兩點間均存在直接相連之弧線5一般化的旅行推銷員問題一般化的旅行推銷員問題即是在網路G上尋找一個經過所有節點至少一次，且總成本最小的迴圈通常對應到實際道路路網2132110436旅行推銷員問題(TSP)簡介一般化的旅行推銷員問題可以轉換成為標準的TSP問題求解先求出任意兩點間的最短路徑及其成本。建構完全路網(completegraph)21321104321315343267旅行推銷員問題之應用拜訪客戶自動販賣機補貨、收款電路板鑽孔訂單揀貨作業8TSP問題特性屬於節點服務之網路組合最佳化問題，每個節點恰服務一次單一車輛無車輛容量限制大多先建立一完全網路後再求解求解複雜度屬於NP-hard，大規模問題難以求得最佳解，實務上多採取「啟發式方法(Heuristics)」求解9TSP問題數學規劃模型Mins.t.10子迴路03125411子迴路消除限制式新增節點造訪順序dj

之變數新增離開節點時間dj

之變數12模型構建練習013153232613TSP問題求解演算法真正解法(只能處理非常小的問題)窮舉法、分枝定限法(Branch-and-Bound)傳統啟發式解法(Heuristics)大致可歸納為以下三種：路線構建(routeconstruction)鄰點法、節省法、插入法、掃瞄法….路線改善(routeimprovement)k-Opt交換法、Or-Opt交換法……綜合型(composite)合併執行路線構建及路線改善14最近鄰點法(Nearest-neighborHeuristic)任選一節點為起點x尋找距離節點x最近的節點y作為下一個造訪的節點尋找距離節點y最近的節點z作為下一個造訪的節點重覆以上步驟，直到所有節點均已造訪連接最後一個節點與起點，即形成一個TSP的可行解15最近鄰點法14235743875534814235123451－473824－755377－344353－858548－16插入法(InsertionMethod)任選一節點為起點a尋找距離節點a最近的節點b作為下一個造訪的節點，形成a-b-a的子迴路尋找距離子迴路最近的節點k作為下一個插入點尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子迴路。‧插入成本：Cik+Ckj-Cij重覆步驟3~4，直到所有節點均已插入迴路之中，即形成一個TSP的可行解17插入法1423574387553481414133337333731722452572742145588584545558214554182-opt交換法先構建一個起始可行解在可行解中任選兩個不相鄰的節線(ab,cd)，以及另外兩條對應之替換節線(ac,bd)，計算替換後總成本是否降低，若有降低，則予以替換(即檢查替換成本是否小於0)。‧替換成本：Cac+Cbd-Cab-Ccd

(對稱型TSP)重覆步驟2，直到所有可能的替換均無法再降低成本為止192-opt交換法14235743875534820TSP問題求解演算法傳統啟發式解法(Heuristics)只在目標值有改善時才進行交換，常會陷入局部最佳解，而無法進一步找到更好的解巨集啟發式方法(Meta-heuristics)則以傳統的啟發式解法為基礎，並根據一些高階的搜尋策略指導下層的啟發式方法，以避免陷入局部最佳解21TSP問題求解演算法常見之巨集啟發式方法(Meta-heuristics)禁制搜尋法(TabuSearch,TS)基因演算法(GeneticAlgorithm,GA)模擬退火法(SimulatedAnnealing,SA)門檻接受法(