Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

당신이 지도 위에 수많은 경유지를 가진 배달 기사라고 상상해 보세요. 당신은 모든 지점을 정확히 한 번씩만 방문하여 집으로 돌아가고 싶지만, 동시에 가솔린을 가장 적게 쓰고 싶습니다. 이것은 고전적인 "외판원 문제(Traveling Salesperson Problem)"로, 수십 년 동안 수학자와 컴퓨터 과학자들을 괴롭혀 온 난제입니다. 이는 단순히 배달 트럭에 국한된 문제가 아닙니다. 스마트 차량의 경로를 설정하거나 컴퓨터 칩 위의 데이터를 정리하는 것 등 모든 분야에 적용됩니다. 까다로운 점은, 방문해야 할 지점이 늘어날수록 가능한 경로의 수가 너무 빠르게 폭발적으로 증가하여 세계에서 가장 빠른 컴퓨터조차 미로 속에서 길을 잃을 수 있다는 것입니다.

이를 해결하기 위해 컴퓨터는 종종 "제약 프로그래밍(Constraint Programming)"이라는 방법을 사용합니다. 이것은 단순히 무작위로 경로를 추측하는 것이 아니라, 매우 똑똑한 탐정처럼 행동하는 것과 같습니다. 대신 탐정은 불가능하거나 터무니없는 옵션을 즉시 제거하기 위한 일련의 규칙(제약 조건)을 설정합니다. 예를 들어, "같은 도시를 두 번 방문할 수 없다"라거나 "나머지 여정을 건너뛰는 식으로 원을 그리며 주행할 수 없다"와 같은 규칙입니다. 보통, 이 문제가 평면 위의 거리(과학자들이 "유클리드(Euclidean)" 사례라고 부르는 경우)와 관련될 때, 컴퓨터는 지점들이 종이 위의 직선과 각도로 그려져 있다는 사실을 무시한 채 지도를 단순한 숫자 목록으로 취급합니다. 이는 마치 실제 지도를 전혀 보지 않고 오직 거리 이름 목록만을 보고 도시를 항해하려는 것과 같습니다.

이 논문은 간단하지만 강력한 질문을 던집니다. "만약 우리가 지도를 무시하는 것을 멈춘다면 어떻게 될까?" 저자인 알레산드로 베르타뇽(Alessandro Bertagnon)과 마르코 가발리(Marco Gavanelli)는 컴퓨터 탐정이 실제로 기하학을 이해할 수 있는 새로운 "규칙"을 구축하기로 했습니다. 그들은 경로가 하늘에서 "X"자 모양처럼 서로 교차해서는 안 되며, 지점들의 외곽 가장자리는 깔끔하고 원형적인 순서로 방문되어야 한다는 것을 아는 특수한 알고리즘을 만들었습니다. 컴퓨터에게 문제의 형상을 "보게" 함으로써, 그들은 이전보다 훨씬 빠르게 수백만 개의 잘못된 추측을 잘라내는 방법을 찾아냈습니다. 또한 그들은 이러한 기하학적 기술이, 여러 도시 중 하나만 방문해야 하는 경우처럼 문제가 더 복렴해질 때도 작동한다는 것을 보여주었습니다.

논문의 핵심 발견

이 연구의 주요 발견은 유클리드 외판원 문제(TSP)의 구체적인 기하학적 특성, 즉 평면상의 최단 경로는 절대 스스로 교차하지 않으며 형상의 외곽 가장자리를 따라간다는 사실을 이용함으로써 컴퓨터가 이러한 경로 문제를 현저히 빠르게 해결할 수 있다는 것입니다. 저자들은 이 새로운 규칙들을 "제약 논리 프로그래밍(CLP)"이라는 프로그래밍 언어에 구현했습니다.

그들은 자신들의 새로운 "기하학적 필터링"을 기존의 가장 우수한 방법들과 테스트했습니다. 결과는 놀라웠습니다. 최대 100개의 지점이 있는 무작위 지도에 대해, 그들의 새로운 접근 방식은 최적의 해를 찾는 데 걸리는 시간을 평균적으로 약 70% 단축했습니다. 컴퓨터의 "사고 단계(search nodes)" 측면에서 보면, 사용된 전략에 따라 약 59%에서 75%까지 작업량을 줄였습니다. 이는 컴퓨터가 단계당 더 빨리 생각했을 뿐만 아니라, 답을 찾기 위해 고려해야 할 단계 자체를 훨씬 적게 거쳤음을 의미합니다.

무엇을 배제했으며 어떻게 했는가

이 논문은 유클리드 TSP(평면 위의 직선 거리)를 일반적인 TSP와 동일하게 취급하는 표준적인 방식에 명시적으로 반대합니다. 흔히 쓰이는 방식은 모든 지점 쌍 사이의 거리를 계산하여 거대한 숫자 테이블을 만든 다음 일반적인 규칙을 적용하는 것입니다. 저자들은 이러한 "맹목적인" 접근 방식이 이미 존재하는 정보인 지점들의 좌표를 무시한다는 점을 보여줍니다. 그들은 기하학을 무시하는 것이 훨씬 더 큰 탐색 공간과 느린 해결책으로 이어진다는 것을 입증했습니다.

또한 그들은 자신들의 방법이 무엇이 아닌지도 명확히 합니다. 그들은 TSP를 완전히 해결했다거나 모든 유형의 경로 문제에 작동하는 마법의 탄환을 만들었다고 주장하는 것이 아닙니다. 예를 들어, 그들은 도로가 반드시 교차해야 하는 경우(예: 일방통행 도로가 있는 실제 도시 격자 구조)나 우회로가 필요한 엄격한 시간 제한이 있는 문제에서는 자신들의 "교차 금지" 규칙이 적용되지 않는다고 언급했습니다. 그들의 작업은 지점들이 평면에 있고 교차가 피할 수 있는 형태인 "완전 유클리드 인스턴스(complete Euclidean instances)"를 대상으로 합니다.

"교차 금지"와 "볼록 껍질"의 마법

컴퓨터를 더 똑똑하게 만들기 위해 저자들은 두 가지 주요 기하학적 개념을 도입했습니다.

1. 교차 금지 규칙: 탁자 위의 점들을 연결하는 실로 루프를 그린다고 상상해 보세요. 만약 실이 스스로 교차한다면, 당신은 항상 실을 더 팽팽하게 당겨서 교차하지 않는 더 짧은 루프를 만들 수 있습니다. 저자들은 최적의(가장 짧은) 경로는 교차하는 선을 갖지 않는다는 것을 수학적으로 증명했습니다. 그들은 어떤 경로 옵션이 교차를 일으키는지 즉시 삭제하는 특수한 "필터"를 컴퓨터 프로그램에 구축했습니다. 이것은 클럽 입구에서 잘못된 문으로 들어오려는 사람을 즉시 쫓아내어, 보안 요원이 나중에 신분증을 확인할 필요가 없도록 만드는 문지기와 같습니다.

2. 볼록 껍질 순서(Convex Hull Order): 판 위의 못 그룹 주변에 고무줄을 씌운다고 상상해 보세요. 고무줄이 만드는 모양을 "볼록 껍질(convex hull)"이라고 합니다. 저자들은 최단 경로에서 이 고무-줄 가장자리에 있는 못들은 특정 순서(시계 방향 또는 반시계 방향)로 방문되어야 함을 보여주었습니다. 그들은 컴퓨터가 가장자리에서 지그재그로 왔다 갔다 하는 경로를 확인하며 시간을 낭비하지 않도록 강제하는 규칙을 만들었습니다.

그룹 문제로의 확장

논문은 더 어려운 버전인 "일반화된 외판원 문제(Generalized Traveling Salesperson Problem, GTSP)"도 다룹니다. 이 버전에서는 모든 도시를 방문하는 대신, "클러스터(그룹)" 세트를 방문해야 하며, 각 그룹에서 단 하나의 도시만 방문하면 됩니다. 이것은 배달 기사가 세 개의 서로 다른 동네에 물건을 배달해야 하지만, 각 동네에서 단 한 집만 방문하면 되는 상황과 같습니다.

저자들은 자신들의 기하학적 규칙이 이 더 어려운 문제에도 적응될 수 있음을 보여주었습니다. 그들은 클러스터의 기하학적 구조를 기반으로 "이웃"을 정의하고 동일한 교차 금지 및 순서 로직을 적용했습니다. 이 그룹 문제들에 대한 테스트에서, 새로운 기하학적 접근 방식은 클러스터형 지도에서는 평균 최대 76%, 격자형 지도에서는 67%까지 해결 시간을 단축했습니다.

결론

저자들은 자신들의 방법이 기존의 제약 프로그래밍 기술보다 크게 개선되었음에도 불구하고, 기본적인 TSP에 대해 세계에서 가장 강력한 특수 솔버(예: Concorde)만큼 빠르지는 않다는 점을 신중하게 밝히고 있습니다. 그러나 그러한 슈퍼 솔버들은 저자들이 성공적으로 다룬 더 복잡한 "일반화된(Generalized)" 버전의 문제를 처리하지 못하는 경우가 많습니다.

논문은 결론적으로, 문제의 형상에 주의를 기울임으로써—즉, 선이 교차하지 않고 가장자리가 곡선을 따른다는 사실을 이용함으로써—컴퓨터가 나쁜 답을 훨씬 더 효율적으로 제거할 수 있다고 설명합니다. 이는 단순히 계산 속도를 높이는 것이 아니라 탐색의 본질을 변화시켜, 컴퓨터가 이전에는 합리적인 시간 내에 해결하기 너무 어려웠던 더 크고 복잡한 경로 문제를 해결할 수 있게 해줍니다. 저자들은 이러한 기하학적 접근 방식이 도로가 피할 수 없이 교차해야 하는 경우가 아니라면, 다른 경로 문제에서도 유사한 개선을 이끌어낼 수 있을 것이라고 제안합니다.