TY - GEN
T1 - STSP approximation algorithms based on TCPN model
AU - Zhu, Guohun
AU - Hirota, Kaoru
AU - Wu, Yonghua
PY - 2010
Y1 - 2010
N2 - 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(n 2); nets firing part in O(m) (≤O(n 2)) and selected by minimum change rate with a optimal solution in O(m 2 n 2)(≤O(n 6)), 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(n 2) and the worst approximation performance is 1.5-opt.
AB - 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(n 2); nets firing part in O(m) (≤O(n 2)) and selected by minimum change rate with a optimal solution in O(m 2 n 2)(≤O(n 6)), 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(n 2) and the worst approximation performance is 1.5-opt.
KW - Approximation algorithms
KW - Firing
KW - Symmetric traveling salesman problem
KW - Time Color Petri Net
UR - http://www.scopus.com/inward/record.url?scp=84862915347&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84862915347
SN - 9787121113154
T3 - 4th International Symposium on Computational Intelligence and Industrial Applications, ISCIIA 2010
SP - 305
EP - 309
BT - 4th International Symposium on Computational Intelligence and Industrial Applications, ISCIIA 2010
T2 - 4th International Symposium on Computational Intelligence and Industrial Applications, ISCIIA 2010
Y2 - 2 August 2010 through 8 August 2010
ER -