旅行推销员问题课件

按一下以編輯母片標題樣式,*,*,*,按一下以編輯母片,第二層,第三層,第四層,第五層,旅行推銷員問題,Traveling Salesman Problem,Chapter 7,1,旅行推銷員問題Traveling Salesman Pro,漢米爾頓迴圈,(Hamiltonian Cycle),環遊世界問題,:,有個人想環遊世界，他選出全世界的二十個著名城世,然後在地圖上開始他的作業。他打算規畫出一條路線,使他可以依序地玩遍這二十個城市。但問題是並不是任兩個城市皆有飛機直航,而他又不願重覆去同一個城市兩次。這個問題轉化為圖論上便是所謂的漢米爾頓迴圈,(Hamilton Cycle),，於,1857,年愛爾蘭數學家漢米爾頓,(Sir William Hamilton),首次提出。,漢米爾頓迴圈,(Hamilton Cycle),不一定存在,2,漢米爾頓迴圈(Hamiltonian Cycle)環遊世界,推廣問題,:,我們可進一步加入每段航程的距離,(,或是票價,),，然後試圖找出最短的總飛行距離,(,或是最便宜的總票價,),是怎樣的一條路線。,80,50,20,30,100,70,80,50,20,30,100,70,80+70+50+100,=300,80,50,20,30,100,70,80+20+50+30,=180,20,30,100,70,100+20+70+30,=220,漢米爾頓迴圈,(Hamiltonian Cycle),3,推廣問題:80502030100708050203010,旅行推銷員問題,一個旅行推銷員必須前往拜訪位於各地的客戶一次，最後再回到原點，則其行走距離,(,或時間、成本,),最短的路線為何,?,4,旅行推銷員問題一個旅行推銷員必須前往拜訪位於各地的客戶一次，,旅行推銷員問題,(TSP),簡介,定義一網路,G,，節點代表每一顧客，弧線成本表示其距離,(,或時間,),TSP,問題即是在網路,G,上尋找一個經過所有節點,恰一次,，且總成本最小的迴圈,(,即成本最小的漢米爾頓迴圈,),通常對應到完全路網,(complete graph),即任意兩點間均存在直接相連之弧線,5,旅行推銷員問題(TSP)簡介定義一網路G，節點代表每一顧客，,一般化的旅行推銷員問題,一般化,的旅行推銷員問題即是在網路,G,上尋找一個經過所有節點,至少一次,，且總成本最小的迴圈,通常對應到實際道路路網,2,1,3,2,1,10,4,3,6,一般化的旅行推銷員問題一般化的旅行推銷員問題即是在網路G上尋,旅行推銷員問題,(TSP),簡介,一般化的旅行推銷員問題可以轉換成為標準的,TSP,問題求解,先求出任意兩點間的最短路徑及其成本。,建構完全路網,(complete graph),2,1,3,2,1,10,4,3,2,1,3,1,5,3,4,3,2,6,7,旅行推銷員問題(TSP)簡介一般化的旅行推銷員問題可以轉換成,旅行推銷員問題之應用,拜訪客戶,自動販賣機補貨、收款,電路板鑽孔,訂單揀貨作業,8,旅行推銷員問題之應用拜訪客戶8,TSP,問題特性,屬於節點服務之網路組合最佳化問題，每個節點恰服務一次,單一車輛,無車輛容量限制,大多先建立一完全網路後再求解,求解複雜度屬於,NP-hard,，大規模問題難以求得最佳解，實務上多採取啟發式方法,(Heuristics),求解,9,TSP問題特性屬於節點服務之網路組合最佳化問題，每個節點恰服,TSP,問題數學規劃模型,Min,s.t.,10,TSP問題數學規劃模型Min10,子迴路,0,3,1,2,5,4,11,子迴路03125411,子迴路消除限制式,新增節點造訪順序,d,j,之變數,新增離開節點時間,d,j,之變數,12,子迴路消除限制式新增節點造訪順序 dj 之變數12,模型構建練習,0,1,3,1,5,3,2,3,2,6,13,模型構建練習013153232613,TSP,問題求解演算法,真正解法,(,只能處理非常小的問題,),窮舉法、分枝定限法,(Branch-and-Bound),傳統啟發式解法,(Heuristics),大致可歸納為以下三種：,路線構建,(route construction),鄰點法、節省法、插入法、掃瞄法,.,路線改善,(route improvement),k,-Opt,交換法、,Or-Opt,交換法,綜合型,(composite),合併執行路線構建及路線改善,14,TSP問題求解演算法真正解法(只能處理非常小的問題)14,最近鄰,點法,(Nearest-neighbor Heuristic),任選一節點為起點,x,尋找距離節點,x,最近的節點,y,作為下一個造訪的節點,尋找距離節點,y,最近的節點,z,作為下一個造訪的節點,重覆以上步驟，直到所有節點均已造訪,連接最後一個節點與起點，即形成一個,TSP,的可行解,15,最近鄰點法(Nearest-neighbor Heurist,最近鄰,點法,1,4,2,3,5,7,4,3,8,7,5,5,3,4,8,1,4,2,3,5,1,2,3,4,5,1,4,7,3,8,2,4,7,5,5,3,7,7,3,4,4,3,5,3,8,5,8,5,4,8,16,最近鄰點法1423574387553481423512345,插入法,(Insertion Method),任選一節點為起點,a,尋找距離節點,a,最近的節點,b,作為下一個造訪的節點，形成,a,-,b,-,a,的子迴路,尋找距離子迴路最近的節點,k,作為下一個插入點,尋找插入成本最小的位置,(,i,-,j,),，將,k,插入,i,-,j,之間，形成新的子迴路。,插入成本：,C,ik,+C,kj,-C,ij,重覆步驟,34,，直到所有節點均已插入迴路之中，即形成一個,TSP,的可行解,17,插入法(Insertion Method)任選一節點為起點a,插入法,1,4,2,3,5,7,4,3,8,7,5,5,3,4,8,1,4,1,4,1,3,3,3,3,7,3,3,3,7,3,1,7,2,2,4,5,2,5,7,2,7,4,2,1,4,5,5,8,8,5,8,4,5,4,5,5,5,8,2,1,4,5,5,4,18,插入法142357438755348141413333733,2-opt,交換法,先構建一個起始可行解,在可行解中任選兩個不相鄰的節線,(,a,b,c,d,),，以及另外兩條對應之替換節線,(,a,c,b,d,),，計算替換後總成本是否降低，若有降低，則予以替換,(,即檢查替換成本是否小於,0),。,替換成本：,C,ac,+C,bd,-C,ab,-C,cd,(,對稱型,TSP),重覆步驟,2,，直到所有可能的替換均無法再降低成本為止,19,2-opt 交換法先構建一個起始可行解19,2-opt,交換法,1,4,2,3,5,7,4,3,8,7,5,5,3,4,8,20,2-opt 交換法14235743875534820,TSP,問題求解演算法,傳統啟發式解法,(Heuristics),只在目標值有改善時才進行交換，常會陷入局部最佳解，而無法進一步找到更好的解,巨集啟發式方法,(Meta-heuristics),則以傳統的啟發式解法為基礎，並根據一些高階的搜尋策略指導下層的啟發式方法，以避免陷入局部最佳解,21,TSP問題求解演算法傳統啟發式解法(Heuristics)只,TSP,問題求解演算法,常見之巨集啟發式方法,(Meta-heuristics),禁制搜尋法,(Tabu Search,TS),基因演算法,(Genetic Algorithm,GA),模擬退火法,(Simulated Annealing,SA),門檻接受法,(Threshold Accepting,TA),類神經網路,(Neural Network,NN),蟻群演算法,(Ant Colony Optimization,ACO),其他,22,TSP問題求解演算法常見之巨集啟發式方法(Meta-heur,TSP,延伸性問題,含時窗限制,非對稱性節線成本,多個旅行推銷員,即時性,TSP,其他,23,TSP延伸性問題含時窗限制23,