確定性成本擾動法求解旅行售貨員問題之研究

Abstract

本研究的目的主要是在求解旅行售貨員問題(Traveling Salesman Problem, TSP)，利用傳統鄰域搜尋方法(Local Research)為主要核心，例如2-Opt和Or-Opt等發展成熟的方法，結合確定性成本擾動法(Deterministic Noising Method)擾動成本的方法，能在搜尋的過程中陷入區域最佳解時，提供一個跳脫的機制；確定性成本擾動法主要是引用成本擾動法(Noising Method)擾動成本的觀念加以修正和測試，將原本隨機性擾動成本的方式修正為確定性擾動成本的方式；確定性成本擾動法保留成本擾動法在擾動節線成本的觀念，並在擾動上提出具有靈活性且可重現最終結果的方法，希望藉由此研究提供一套穩定、精確且有效的方法。 研究中所提出的確定性成本擾動法針對成本擾動比率值、增加成本比率值、成本擾動比率值長度、增加成本比率值長度等參數，以及起始解解法、核心交換法及擾動公式等執行架構組件的設計與測試。在所建議的組件組合方式與數值範圍下得到的之解題績效為：16個測試例題在總擾動次數30的總平均誤差為1.01%、標準差為1.22%；總擾動次數45的總平均誤差為0.88%、標準差為1.11%；總擾動次數60的總平均誤差為0.80%、標準差為1.16%。若從整個測試過程中所能找到16個例題的最佳個案來看：DNM法共找到13題的已知最佳解，而平均個案誤差為0.19%。

Traveling salesman problem is a well-known NP-hard combinatorial optimization problem. It has been one of the problems in some academic fields such as mathematics, computer science and management science want to resolve. Due to the NP-hard complexity of TSP, it seems to be no way to find out an algorithm which can provide an optimal solution for the TSP without suffering from exponentially growing complexity. If we can find out a more efficient methods to solve the problem, it will help many industries to improve their operational costs. This research presents an implementation of the Deterministic Noising Method, a combinational optimization meta-heuristics, for solving traveling salesman problem. The DNM revises the Noising Method form a stochastic method to a deterministic method. In this paper, we provide a new formula to disturb the cost matrix in order to escape from a local solution. We also consider different parameter settings to test the performance of the DNM. Sixteen problems from TSPLIB library are used to test the quality of the DNM. The average accuracy of the best solutions of the sixteen problems computed by the DNM is 0.19 % above the performance of the current best known solution. Overall, the heuristics should be a tool for real-world application of TSP.