비대칭 외판원문제에서 최적해에 포함될 가능성이 높은호들을 이용한 비용완화법
Cost Relaxation Using an Arc Set Likely to Construct an Optimal Solution for the Asymmetric Traveling Salesman Problem
권상호(삼성전자(주)); 사공선화(한양대학교); 강맹규(한양대학교)
33권 2호, 17~26쪽
초록
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.
Abstract
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.
- 발행기관:
- 한국경영과학회
- 분류:
- 경영학