STSP Approximation Algorithms based on TCPN Model

摘要

An approximation algorithms based on Time Color Petri Nets(TCPN) is presented to obtain an optimal solution for a general Symmetric Traveling Salesman Problem(TSP) with a conflict restriction. It is composed of building TCPN model part with complexity O(n2); nets firing part in O(m) (≤O(n2)) and selected by minimum change rate with a optimal solution in O(m2 n2)( ≤ O(n6)), where n and m stand for the number of cities and the number of edges, respectively. Without conflict, an optimal solution is obtained on theory. Experimental (include several TSPLIB) results shows that the best costing is obtained optimal solution in O(n2) and the worst approximation performance is 1.5-opt.