TSP 문제 설정

조합 최적화에서, 일반화된 TSP, 그룹 TSP, 원 오브 어 세트 TSP, 다선택 TSP 또는 커버링 세일즈맨 문제라고도 불리는 세트 TSP는 여행 세일즈맨 문제를 일반화한 것으로, 지정된 모든 정점의 그래프에서 최단 투어를 찾아야 합니다.겹치는 부분 집합의 경우 분리된 ^[1]부분 집합의 경우로 축소될 수 있으므로 정점의 부분 집합은 분리되어야 합니다.통상 TSP는 방문하는 모든 서브셋이 싱글톤일 때 설정된 TSP의 특수한 경우입니다.따라서 설정된 TSP도 NP 하드입니다.

설정된 TSP 인스턴스에서 표준 비대칭 TSP ^[2]인스턴스로 변환됩니다.즉, 각 서브셋을 가중치가 0인 에지를 가진 방향성 사이클로 연결하고 이 사이클을 따라 한 꼭지점 뒤로 이동하는 원래 그래프에서 나가는 에지를 상속하는 것입니다.판매원은 일부 부분 집합에서 정점 v를 방문할 때 사이클을 무료로 돌고 원래 그래프에서 v의 나가는 모서리에 해당하는 나가는 모서리만큼 v 앞의 정점에서 v를 빠져나갑니다.

Set TSP에는 몇 가지 패스 플래닝 문제에 관한 대상 어플리케이션이 많이 있습니다.예를 들어, 2대의 차량 공동 라우팅 문제를 세트 TSP로 ^[3]변환하여 Dubins TSP에 대한 엄격한 하한을 설정하고 일반화된 Dubins 경로 문제를 Set TSP를 해결함으로써 ^[4][5]계산할 수 있습니다.

절삭재 문제의 그림

종이/플라스틱 필름 산업에 적용되는 1차원 절삭재 문제는 점보 롤을 더 작은 것으로 절단하는 것입니다.이는 일반적으로 낭비를 최소화하기 위해 절단 패턴을 생성함으로써 이루어집니다.이러한 용액이 생성되면 패턴을 다시 정렬하거나(그림의 위아래로) 롤을 각 패턴 내에서 왼쪽 또는 오른쪽으로 이동하여 칼의 변화를 최소화할 수 있습니다.이러한 움직임은 솔루션의 낭비에는 영향을 주지 않습니다.

위 그림에서 패턴(폭 198 이하)은 열로 되어 있으며, 칼의 변화는 작은 흰색 원으로 나타납니다. 예를 들어 패턴 2-3-4는 왼쪽에 42.5 크기의 롤이 있으므로 해당 칼은 이동할 필요가 없습니다.각 패턴은 TSP 세트를 나타내며, 그 중 하나의 순열을 참조할 필요가 있습니다.예를 들어, 두 개의 반복 크기(각각 크기)를 포함하는 마지막 패턴의 경우 5! / (2! × 2!) = 30개의 순열이 있습니다.위의 예에 대해 가능한 해법의 수는 12! × (5!)⁶ × (6!)⁴ × (7!)² / (2!)⁹ × (3!)² ≈ 5.3 × 10이다³⁵.위의 용액은 39개의 나이프 변화를 포함하고 있으며, 휴리스틱을 통해 얻어진 것으로, 이것이 최적인지는 알려지지 않았다.설명에 따라서, 통상의 TSP 로의 변환에는, 노드수가 5,520 인 TSP 가 포함됩니다.

「 」를 참조해 주세요.

• 삼각형의 세 변을 모두 방문하는 최단 관광을 찾는 파냐노의 문제

레퍼런스