GTSP , TSP ( Traveling Salesman Problem )

외판원 문제 ( TSP , Traveling Salesman Problem )

• 조합 최적화  문제중 하나이며, 그래프 이론과 최적화 이론에서 매우 중요한 역할을 한다.
• 한 외판원이 여러 도시를 한번씩 방문한 뒤 출발지로 돌아오는 최소 비용(최소 거리)의 경로를 찾는 문제
• 문제 개요
  • 외판원 문제는 아래와 같이 정의한다.
    • 1. n개의 도시와 도시간 이동 비용(거리)가 주어진다.
    • 2. 한 도시에서 출발해서 모든 도시를 한번씩 방문하고 다시 출발지로 돌아오는 순회를 찾음.
    • 3. 순회의 총 이동 거리가 최소가 되게 해야한다.
      • ==> 즉, 완전 그래프에서 최소 비용의 해밀턴 순환을 찾는 문제라고 할수있다.

 

 

 

외판원 문제의 수학적 모델링

• 외판원 문제는 그래프 G = ( V, E )로 표현한다.
  • V : 도시(노드)드의 집합
  • E : 도시 간의 도로(엣지)들의 집합
  • c( i , j ) : 도시 i에서 j로 이동하는 비용 
• 최적화를 위한 목적함수
  • 외판원의 경로를 x ij라고하면, 전체 이동 비용을 최소화하는 목표는 아래와 같다.

목적함수

• 최적화의 제약 조건 
  • 1. 각 도시는 한번만 방문해야 함
  • 2. 순환 경로 ( solution )은 하나의 연결된 경로여야 한다.
    • 서브투어subTour를 방지하는 제약이 필요하며, 이를 위해서 miller-tucker-ezmlin제약을 사용하기도 한다.
      • 서브투어: 모든 도시를 포함하지 않고 일부 작은 도시들만 순환하는 작은 사이클 

u i는 도시 i 방문 순서를 나타내며, 서브투어를 방지함.

 

 

 

 

외판원 문제의 해결 방법

• 정확한 해를 찾는 알고리즘
  • 1. brute-force
  • 2. 동적 계획법 ( held karp algorithm )
    • 부분 문제를활용해서 효율적 탐색 
  • 3. branch and bound
    • 불필요한 경로를 조기에 배제한다
  • 4. integer linear programming , ILP
• 근사 해 알고리즘
  • 1. greedy algorithm
  • 2. 최소 신장 트리 기반 방법
  • 3. 유전 알고리즘
  • 4. 개미 알고리즘
  • 5. simulated annealing

 

 

GTSP ( generalized traveling salesman problem , 일반화된 외판원 문제 )

• TSP의 확장된 버전이다.
• 여러개의 clusters or sets으로 나누어진 도시들 중에서, 각 클러스터에서 정확히 하나의 도시를 방문하면서 전체 경로를 최소화 하는 문제이다.
• TSP와 차이점
  • TSP는 모든 도시를 정확히 한번씩 방문한다면, GTSP는 도시들이 여러개의 클러스터로 나누어지며, 각 클러스터에서 정확히 하나의 도시만 선택하면서 최단 경로를 찾아야한다.
• 해결 방법
  • 정확한 해를 구하기
    • 1. branch and bound
      • 분할하여 최적해를 찾지만 계산량이 많다.
    • 2. mixed integer linear programming
      • 정수 선형 계획법을 사용하며 최적해를 찾지만, 계산 시간이 길어질수있다.
  • 근사 해 알고리즘
    • TSP로 변환하기
    • 유전알고리즘 개미 군집 최적화와 같은 메타휴리스틱 방법