http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
비대칭 외판원문제에서 최적해에 포함될 가능성이 높은 호들을 이용한 비용완화법
권상호(Sangho Kwon),사공선화(Seonhwa Sagong),강맹규(Maingkyu Kang) 한국경영과학회 2008 韓國經營科學會誌 Vol.33 No.2
The traveling salesman problem is to find tours through all cities at minimum cost;simply visiting the cities only once that a salesman wants to visit. As such, the traveling salesman problem is a NP-complete problem;an heuristic algorithm is preferred to an exact algorithm. In this paper, we suggest an effective cost relaxation using a candidate arc set which is obtained from a regression function for the traveling salesman problem. The proposed method sufficiently consider the characteristics of cost of arcs compared to existing methods that randomly choose the arcs for relaxation. For test beds, we used 31 instances over 100 cities existing from TSPLIB and randomly generated 100 instances from well-known instance generators. For almost every instances, the proposed method has found efficiently better solutions than the existing method.