주어진 TSP의 customer data를 적절한 data structure에 읽어 들이고, 사용자가 선택하는 알고리즘에 따라 TSP 문제의 해를 찾고 각 알고리즘 solution의 quality와 computation 시간을 비교하였습니다.
Data 파일은 각 customer의 위치정보가 아래와 같이 ID, 위도, 경도로 주어집니다.
node_id, lattitude, longitude 11, 37.28131063, 127.5544615 12, 37.61020482, 126.2293698 13, 37.35317849, 126.7162361 14, 37.27952445, 125.047398 15, 37.1860053, 126.283241 16, 37.61608759, 126.3904478 17, 37.67163845, 128.1930648 18, 37.14747215, 124.9156881 19, 37.56721002, 127.1753523 20, 37.39669027, 125.2088654
다음과 같이 4가지 방법의 알고리즘으로 문제를 해결하였습니다.
- Full enumeration (작은 문제): permutations() 함수 사용 가능
- Nearest Neighbor
- Greedy 2-OPT
- Full 2-OPT