TSP 연구에 사용할만한 솔버와 예제 문제

TSP란?

TSP 는 np hard 문제이다. 다항 시간 내에 최적해를 찾을 수 없는 문제의 특성때문에 사이즈가 큰 instance 의 경우 아직도 최적해를 찾아나가고 있는 중이며 현재까지 찾은 해중 가장 좋은 해를 best known solution 이라 명명한다

 

TSPLIB

유명한 instance 들은 아래에서 찾아볼 수 있다. 만일 누군가 TSP 문제를 더 효율적으로 풀기 위한 heuristic 을 개발했다고 해보자. 그 성능 (얼마나 빨리 더 좋은 해를 찾나) 을 기존에 제시된 알고리즘과 비교하기위해 특수한 instance 가 아니라 잘 알려진 instance 에 적용해보고 싶을 수 있다. 그럴때 사용할수 있는 것이 TSPLIB 이다.
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

TSPLIB

CVRPLIB

http://vrp.atd-lab.inf.puc-rio.br/index.php/en/

CVRPLIB - All Instances

CVRP 푸는 알고리즘을 개발하고나면 본인 알고리즘이 성능이 어느정도인지를 파악하기 위한 benchmark가 필요하다. 

본 사이트에는 well known 데이터셋과 best known optimal solution 가 나와있다. 연구자들이 많이 사용하는 잘알려진 데이터 셋이므로 연구 목적으로 사용하기 적합해보인다. 

TSP solver Concorde

Concorde 는 TSP 솔버이다. symmetric TSP 문제를 다룬다는 특징이 있다 (A에서 B로 가는 통행 비용이 B에서 A로 가는 통행 비용과 같은 것을 symmetric TSP 라 한다.)
https://www.math.uwaterloo.ca/tsp/concorde.html

Concorde Home

 

솔버를 잘 사용하기 위해서는 기본 원리를 이해해야한다. TSP/VRP 는 discrete optimization 에 기반한다. 다음 강의를 추천한다. 

https://www.coursera.org/learn/discrete-optimization/lecture/QB8JE/vehicle-routing

Vehicle Routing - Advanced Topics: Part I | Coursera