MDMTSP(814-3) 정리

https://gubshig.tistory.com/49을 읽고 오면 좋다.

MDMTSP(Multi Depot Multiple TSP)

https://www.acmicpc.net/problem/20185 (814-3) 이 문제의 정확한 명칭을 모르겠으나 가장 유사한 문제론 MDMTSP(https://www.uv.es/~benavent/MDMTSP/report_MDMTSP.pdf)가 있는 것 같다.

 

이 문제를 요악하자면,
$N$개의 도시를 $K$명의 외판원에게 분배하자. 각 외판원은 분배받은 도시를 순회할 순서를 정하여 모든 도시를 방문하고 다시 시작 도시로 돌아온다. 이때 각 외판원이 이동하는 시간의 최댓값을 최소화하라.

$K = 1$이면 이 문제는 TSP와 동일하기에, NP-hard이다.

현실 세계에서도 다양한 application이 있을 것 같다. $K$개의 버스 노선을 정하는 방법, $K$명의 배달원에게 물건을 배달하는 방법을 정하는 상황 등등...

이 문제에서 주목해볼만한 부분들에 대해 적어보자면,

1. 2D Euclidean TSP이다.

2. 도시들의 분포가 uniformly random이다.

3. 시간과 메모리의 제약이 있다.

4. 가중치의 총합을 최소화 하는 것이 아닌 최댓값을 최소화하여야 한다.

5. $N = 8000, K = 140$으로 고정되어있다.

 

내가 고안한 알고리즘은 크게 다음과 같은 과정을 거친다.

1. 도시를 $K$개의 클러스터로 분할한다.

2. 각 클러스터에서 TSP를 해결한다.

3. 가중치가 가장 큰 해를 개선시킨다.

4. 클러스터끼리 도시를 주고 받는다.

5. 3번, 4번 과정을 반복한다.

 

1. 도시를 분할하기

각 클러스터의 TSP 값이 작아지도록 하는 분할을 찾아내야 한다. 유클리드 거리이니 2차원 좌표평면 내에서 가까운 도시들끼리 묶어주는 것이 좋을거라 생각했다. 

 

k-means나 k-medoids 등의 클러스터링 알고리즘을 적용시켜보았지만, 별로 효율적이지 못하였다. $[0, 814000] \times [0, 814000]$ 공간을 $10 \times 14$개의 격자로 분할시키는 것이 시간과 성능 면에서 파레토 최적이었다.

 

2. 각 클러스터에서 TSP를 해결

이 문제에서 시간의 제약은 결코 널널하지 않다. 때문에 적은 시간에 적당히 괜찮은 해를 구해야 한다. SA, DLAS, LKH, 2, 3-opt 등을 사용해 보았지만 2-opt를 사용한 SA가 이 문제에서 가장 적합하였다.

 

SA는 하이퍼파리미터에 굉장히 민감하다는 단점이 있다. 의도적으로 실수오차를 발생시키면 해가 더 좋아진다던가 하는 이상한 일들이 발생한다. 수많은 시행착오와 지인의 도움 끝에 적절한 하이퍼파라미터를 찾을 수 있었지만 개선의 여지가 있을 것 같다.

 

3. 가중치가 가장 큰 해 개선

클러스터에서 TSP를 해결하는 부분은 크게 두 부분으로 나뉘는데, 클러스터 초기화 후 TSP를 해결하는 것과 초기화 후 가중치가 가장 큰 해에서 TSP를 해결하는 부분이다. 초기화 때는 SA를 짧게만 돌렸고, 가중치가 가장 큰 해를 해결하는 부분에선 SA를 오래 돌렸다.

 

4. 클러스터끼리 도시를 주고 받기

만약 가중치가 가장 큰 클러스터에서 SA를 오래 돌려도 해가 더 좋아지지 않는다면 어떡할까?

 

우선 몇몇 랜덤 데이터에서 각 클러스터의 도시 개수 분포를 확인하였는데, 별로 균등하지 않음을 알 수 있었다. 해를 개선시키는 가장 자연스러운 접근은 도시를 다른 클러스터로 옮기는 것이다.

 

유클리드 거리는 metric을 만족하기에, 어떤 도시를 제거하였을 때 바로 가중치의 개선을 볼 수 있다. $\{ 1 \rightarrow 2 \rightarrow 3\}$에서 $\{ 1 \rightarrow 3\}$이 된다면 metric의 정의에 의해 $d(1, 3) \leq d(1, 2) + d(2, 3)$을 만족하기 때문이다.

 

각 클러스터를 격자처럼 분할시켰으니 인접한 클러스터를 정의하기 편하다. 최대 8개의 인접한 클러스터에 도시 이동을 시도하였고 그중 가장 좋은 클러스터에 도시를 옮겨주었다.

 

이때 가장 좋은 클러스터를 찾는 방법에 대해서는 크게 2가지를 시도해보았다.

현재 가중치가 가장 큰 클러스터를 $p$, 인접한 클러스터들의 집합을 $adj(p)$라 하자.

$j \in adj(p)$에 대해 $j$의 무게중심과 $p$의 도시 중 가장 가까운 도시까지의 거리를 구하고 이를 $j$의 가중치와 더한 값을 기준으로 비교를 한 방법과,

$j$의 도시들과 $p$의 도시들 중 가장 가까운 거리를 구하고, 이 값에 2배를 한 후 $j$의 가중치에 더한 값을 기준으로 비교하는 방법이다.

 

이 중 후자가 더 좋은 성능을 보였다.

 

이제 이 과정을 충분히 반복하면 된다. 

 

여기까지 구현하였을 때 로컬에서 정답에 가까운 해를 구할 수 있었으나, 너무 많은 시간이 필요했다. 맞았습니다!!를 받으려면 상수 최적화 등이 필요해 보인다. 

 

지인의 도움을 받아 상수 최적화와 격자 알고리즘의 수정 등을 거치고 나니 로컬 기준 30~50초 정도에 정답에 가까운 해를 구할 수 있게 되었다.

 

추후 더 강하고 빠른 tsp-solver를 가져오거나 하는 등의 개선이 필요해 보인다.