以斐氏網為基礎之演算法求解非對稱旅行銷售員問題

Solving Asymmetric Traveling Salesman Problem by a Petri Net-Based Heuristic Algorithm

彭定國(Ting-Kuo Peng)

《明新學報》 40卷2期 (2014/08) Pp. 45-53

摘要

旅行銷售員問題（TSP）是組合最佳化問題中最基本且具代表性的一種問題型態，此類問題的求解目前已被證實為NP-Complete，而非對稱旅行銷售員問題（ATSP）是傳統對稱型TSP問題的擴展，由於在節點之間的距離放寬了限制，導致問題求解的複雜度較對稱型TSP問題多出一倍。為了使ATSP問題的求解更有效率，各種啟發式演算法相繼產生，如模擬退火法、禁忌搜索法、遺傳演算法、類神經網絡法、蟻群算法和粒子群算法等。本研究首先以斐氏網的觀念，將ATSP兩兩城市的路徑關係轉換成網路模型，並以鄰近搜索法的路徑選擇方式，得到ATSP問題的初始可行解，而後結合複雜度較低的2-Opt演算法，強化區域搜尋的能力，從而提昇整體演算法的效率。

關鍵字

非對稱旅行銷售員問題 ； 斐氏網 ； 鄰近搜索法 ； 2-Opt演算法

並列摘要

Traveling Salesman problem (TSP) is a combinatorial optimization problem that has now been confirmed to be NP-Complete. Asymmetric traveling Salesman problem (ATSP) is an extension of the traditional symmetric TSP problem, the complexity of algorithm for solving ATSP is more than symmetric TSP problems. There have been a variety of heuristic algorithms, such as simulated annealing, Tabu search, genetic algorithms, neural network method, and ant colony algorithm. This paper attempts to combine Petri net and neighborhood search method to obtain a feasible solution of the ATSP problem, and then use the feasible solution as a basis to find the optimal solution by using 2-Opt method. Thereby, the efficiency of the algorithms can be enhanced and the consistence of the solutions can be obtained.

並列關鍵字

Asymmetric traveling salesman problem ； Petri net ； neighborhood search method ； 2-Opt method

參考文獻

楊秉蒼、呂淑鈴(2000)。以自我學習神經網路混合鄰近搜索演算法解TSP問題。運輸計畫季刊。29(2)，281-294。

白杰、朱俊、楊根科、潘常春(2012)。基於反饋校正原理的非對稱旅行商問題的自收斂優化算法。控制理論與應用。29(6)，689-696。

俞文魮(1999)。多旅行商路線的幾個問題。數學的實踐與認識。29(1)，79-86。

駱劍平、李霞、陳泯融(2011)。基於改進混合蛙跳算法的CVRP求解。電子與信息學報。33(2)，429-434。

譚皓、王金岩、何亦征(2005)。一種基於子群雜交機制的粒子群算法求解旅行商問題。系统工程。23(4)，7-10。