🔢 수학

Centralized Round-Robin Tournament Scheduling with a Flexible Number of Matches per Round

이 논문은 이론적 복잡도 결과와 다항 시간 내에 해결 가능한 사례들을 확립하는 동시에, 대규모 인스턴스에서 혼합 정수 계획법보다 우수한 성능을 보이는 매우 효과적인 반복 지역 탐색 휴리스틱을 제안함으로써, 라운드당 경기 수가 유연한 중앙 집중식 싱글 라운드 로빈 토너먼트에서의 총 이동 거리 최소화라는 NP-난해 문제를 다룬다.

원저자: Hikaru Anai, Yunjian Cao, Wei Wu

게시일 2026-10-15

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Hikaru Anai, Yunjian Cao, Wei Wu

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

스포츠 리그의 물류가 단순히 누가 누구와 경기하느냐를 넘어, 그 여정 자체에 관한 것이라면 어떤 세상이 펼쳐질지 상상해 보십시오. 복잡한 시스템을 효율적으로 운영하기 위해 전념하는 분야인 운영 연구(operations research)의 영역에서, 연구자들은 종종 스케줄링이라는 퍼즐을 다룹니다. 이 퍼즐의 고전적인 버전은 모든 팀이 서로 한 번씩 경기를 치르는 방식인 라운드 로빈 토너먼트입니다. 전통적으로 이러한 토너먼트는 경직되어 있습니다. 즉, 한 라운드는 가능한 최대 수의 경기가 동시에 발생하는 고정된 시간 블록이며, 이는 마치 극장의 모든 좌석이 채워진 만석 상태와 같습니다. 일반적인 과제는 경기의 순서를 결정하거나 비용과 시간을 절약하기 위해 어디서 경기를 열지 결정하는 것입니다. 하지만 실제 세계, 특히 일본의 지역 아마추어 리그나 학교 스포츠에서는 규칙이 더 유동적인 경우가 많습니다. 주최 측은 모든 팀이 동시에 경기를 치를 만큼 충분한 경기장을 확보하지 못할 수도 있고, 특정 날에 특정 팀 그룹의 이동을 제한하고 싶을 수도 있습니다. 이러한 유연성은 그날의 상황에 따라 한 라운드가 단 한 경기만 포함할 수도 있고, 열 경기를 포함할 수도 있음을 의미합니다. 그렇다면 질문은 이것입니다. 하루에 치러지는 경기 수가 변할 수 있고, 매일 하나의 개최 장소가 정해져 있는 상황에서, 모든 팀의 총 이동 거리를 최소화하면서 시즌을 어떻게 조직할 것인가?

이것이 바로 시즈오카 대학교와 세이케이 대학교의 연구팀이 해결하고자 했던 구체적인 문제입니다. 그들은 중앙 주최자가 하루 동안 하나의 경기장을 선정하고, 동일한 날에 한 팀이 두 번 경기하지 않도록 보장하면서 그곳에서 몇 경기를 배치할지 결정하는 시나리오에 집중했습니다. 그들의 목표는 단순하지만 달성하기 어려웠습니다. 모든 팀이 경기에 참여하기 위해 운전하는 총 마일리지를 최소화하는 것이었습니다. 이 난이도를 이해하려면, 게임 그룹을 새로운 날로 나눌 때마다 해당 팀들에게 더 가까운 경기장을 선택할 수는 있지만, 시즌에서 사용 가능한 제한된 날짜 중 하나를 소모하게 된다는 점을 깨달아야 합니다. 이는 일정을 압축적으로 유지하는 것과 이동 거리를 짧게 유지하는 것 사이의 섬세한 균형 잡기입니다.

연구진은 먼저 근본적인 질문을 던졌습니다. 이 문제가 컴퓨터에 의해 합리적인 시간 내에 풀릴 수 있는 문제인가, 아니면 완벽한 답을 찾기에는 너무 혼란스러운 문제인가? 그들은 일반적인 경우에 대해 이 문제가 계산적으로 불가능(computationally intractable)하다는 것을 증证明했습니다. 쉽게 말해, 팀의 수가 늘어남에 따라 최적의 일정을 찾는 데 필요한 시간이 폭발적으로 증가하여, 가장 강력한 컴퓨터로도 대규모 그룹에 대해 완벽한 해답을 찾는 것이 불가능해진다는 뜻입니다. 그들은 이동 비용을 단 세 가지 값으로만 단순화하더라도, 그 기저의 논리가 효율적으로 해결하기에는 여전히 너무 복잡하다는 것을 보여줌으로써 이를 입증했습니다. 이 발견은 매우 중요한데, 이는 토너먼트 주최자들이 대규모 리그를 위한 완벽한 일정을 얻기 위해 단순한 공식에 의존할 수 없으며, 스마트한 지름길이 필요하다는 것을 알려주기 때문입니다.

그러나 연구는 어려움을 증명하는 데서 멈추지 않았습니다. 연구팀은 특정 조건 하에서는 이 문제가 훨씬 쉬워진다는 것을 발견했습니다. 만약 토너먼트에 사용 가능한 날짜가 모든 경기를 소화하는 데 필요한 최소한의 날짜와 정확히 일치한다면, 해결책은 명확하며 빠르게 찾을 수 있습니다. 그들은 또한 단 두 개의 경기장만 존재하는 특수한 경우를 식별했습니다. 이 시나리오에서 그들은 팀들의 선호도라는 수학적 구조를 기반으로 한 방법을 개발하여 최적의 일정을 즉각적으로 결정할 수 있게 했습니다. 이는 작은 규모의 리그나 경기장 옵션이 매우 제한적인 리그를 위한 강력한 도구를 제공하며, 슈퍼컴퓨터 없이도 완벽한 일정을 찾을 수 있게 해줍니다.

많은 팀과 많은 날짜가 포함된 더 흔하고 어려운 상황을 위해, 연구진은 '반복적 지역 탐색(iterated local search)'이라 불리는 정교한 탐색 전략을 설계했습니다. 이것을 광대한 가능한 일정의 풍경을 체계적으로 탐험하는 방법이라고 생각하십시오. 이 과정은 괜찮은 수준의 일정에서 시작하여, 작고 전략적인 변화를 가함으로써 반복적으로 개선을 시도합니다. 이러한 변화에는 두 날의 경기를 하나로 합친 다음 다시 다르게 나누는 것, 또는 갈등을 해결하기 위해 단일 경기를 다른 날로 옮기는 것 등이 포함됩니다. 이 알고리즘은 가끔 더 크고 파괴적인 변화를 주어 분위기를 환기하고 새로운 가능성을 탐색함으로써, 일정은 좋아 보이지만 실제로는 최적에서 멀리 떨어져 있는 '지역적 함정(local traps)'에서 벗어나도록 설계되었습니다.

연구진이 8개 팀부터 64개 팀까지 다양한 64가지 시나리오에 대해 이 방법들을 테스트했을 때, 결과는 놀라웠습니다. 32개 미만의 팀이 참여하는 작은 규모의 토너먼트의 경우, 그들의 수학적 모델은 완벽한 일정을 찾아낼 수 있었고 그것이 최선임을 증명할 수 있었습니다. 더 크고 복잡한 토너먼트의 경우, 정확한 수학적 모델은 메모리가 부족하거나 시간 제한 내에 해를 찾지 못해 어려움을 겪는 경우가 많았습니다. 반면, 새로운 탐색 전략은 일관되게 높은 품질의 일정을 찾아냈습니다. 중간 규모의 문제에서는 이론적 최적값의 1% 미만 오차 범위 내의 솔루션을 만들어냈습니다. 정확한 모델이 실패한 가장 큰 규모의 문제에서도, 이 탐색 전략은 표준적인 수학적 접근 방식이 관리할 수 있는 것보다 훨씬 우수한 실행 가능한 일정을 제공했습니다.

연구는 또한 일정의 유연성이 결과에 어떤 영향을 미치는지에 대한 흥elli로운 통찰을 제공했습니다. 경기를 치를 수 있는 날짜가 많아질수록 일반적으로 여행 비용을 더 많이 절감할 수 있지만, 그 이득은 특정 지점 이후에는 점차 줄어듭니다. 마찬가지로, 선택할 수 있는 경기장이 많아지면 이동 거리를 줄이는 데 도움이 되지만, 스케줄링 퍼즐을 풀기는 더 어렵게 만듭니다. 연구진은 경기를 여러 날로 나눔으로써 서로 가까이 사는 팀들을 그룹화하고 그들에게 인접한 경기장을 보냄으로써 이동 거리를 크게 줄일 수 있다는 것을 발견했습니다. 이는 하루에 치러지는 경기 수를 가변적으로 운영하는 것이 단순한 물류적 편의를 넘어, 비용과 노력을 줄이기 위한 강력한 레버 역할을 한다는 것을 확인시켜 줍니다.

궁극적으로, 이 연구는 이러한 유연한 토너먼트를 조직하기 위한 완전한 도구 상자를 제공합니다. 이 연구는 문제의 난이도에 대한 증명, 특수 사례에 대한 정확한 해법, 그리고 가장 중요한 실제 상황을 위한 강력하고 빠른 휴리스틱을 제공합니다. 깊은 수학적 이론과 실용적인 알고리즘 설계를 결합함으로써, 연구진은 스포츠 주최자들이 시간, 공간, 이동 사이의 복잡한 절충안을 헤쳐 나갈 수 있는 방법을 제시하였으며, 이를 통해 초점이 여정이 아닌 경기에 머물 수 있도록 보장해 주었습니다.

기술 요약: 유연한 라운드당 경기 수를 갖는 중앙 집중식 라운드 로빈 토너먼트 스케줄링

문제 정의

본 논문은 **유연한 라운드당 경기 수를 갖는 중앙 집중식 라운드 로빈 토너먼트 스케줄링 문제(CRRTSP-FMR)**를 다룬다. 이 문제는 일본의 지역 아마추어 스포츠 및 학교 클럽 리그의 맥락에서 발생하며, 운영상의 제약으로 인해 특정 라운드(시간대) 내의 모든 경기가 하나의 공통된 장소에서 개최되어야 하는 경우가 많다.

각 라운드의 경기 수가 팀 수에 의해 결정되는 고정된 최대 매칭을 사용하는 전통적인 라운드 로빈 스케줄링과 달리, CRRTSP-FMR은 라운드당 경기 수를 결정 변수로 허용한다. 스케줄러는 다음을 수행해야 한다:

$n$ 개 팀의 모든 쌍이 정확히 한 번씩 경기를 치르도록 배정한다.
이러한 경기들을 최대 $q$ 개의 라운드(여기서 $q \ge \rho(n)$ , $\rho(n)$ 은 이론적 최소 라운드 수)로 분할한다.
활성화된 각 라운드에 단일 공통 경기장을 배정한다.
각 팀이 한 라운드에 최대 한 번만 경기를 치르도록 보장한다.

목표는 총 이동 거리(total travel distance)를 최소화하는 것이다. 라운드당 경기 수의 유연성은 스케줄링에 트레이드오프를 도입한다: 라운드를 분할하면 특정 팀 집단에 더 가까운 경기장을 선택할 수 있지만, 요구되는 총 라운드 수가 증가하여 상한선 $q$ 와 충돌할 가능성이 있다.

방법론

1. 수학적 정식화

저자들은 두 가지 혼합 정수 계획법(MIP) 모델을 제안한다:

시간 인덱스 정식화(Time-Indexed Formulation): 후보 라운드 $k \in \{1, \dots, q\}$ 를 명시적으로 인덱싱한다. 경기-라운드 할당과 경기장-라운드 할당을 위한 이진 변수를 사용한다. 라운드의 순서가 비용에 영향을 미치지 않는 대칭성을 해결하기 위해, 저자들은 각 라운드의 사전식 순서상 가장 작은 경기 인덱스를 기준으로 정준 순서(canonical ordering)를 강제하는 **대칭성 파괴 제약 조건(symmetry-breaking constraints)**을 도입한다.
할당 기반 정식화(Assignment-Based Formulation): 경기를 작업(job)으로, "경기장 사용 쌍(venue-use pairs)" $(j, k)$ 를 기계(machine)로 취급한다. 이 정식화는 경기를 특정 경기장 사용에 직접 할당한다. 또한, 각 경기장에 할당된 가장 작은 경기 인덱스를 기준으로 경기장 사용 순서를 정하는 대칭성 파괴 제약 조건을 포함한다. 저자들은 이 정식화가 패킹 구조 덕분에 더 강력한 선형 계획법(LP) 완화(relaxation)를 제공한다고 주장한다.

2. 복잡도 분석

NP-완전성(NP-Completeness): CRRTSP-FMR의 결정 버전은 이동 비용이 $\{0, 1, 3\}$ 세트로 제한된 경우에도 **강력한 NP-완전(strongly NP-complete)**임이 증명되었다. 이 증명은 입방 그래프(cubic graphs)의 3-에지 채색(3-edge-coloring) 문제로부터의 환원을 활용한다.
다항 시간 내 해결 가능한 경우:
- 최소 라운드( $q = \rho(n)$ ): 라운드 수가 이론적 최소치와 일치하는 경우, 문제는 다항 시간 내에 해결 가능하다. 최적의 전략은 모든 라운드를 팀의 총 이동 거리를 최소화하는 단일 경기장에 할당하는 것이다.
- 하한 도달 가능성: 저자들은 모든 경기가 가능한 가장 저렴한 경기장에서 치러지는 "독립 경기 하한(independent-match lower bound, $Z_{LB}$ )"을 정의한다. 만약 라운드 제한 $q$ 가 각 경기장에 할당된 경기들로 형성된 그래프들의 크로마틱 인덱스(chromatic indices)의 합보다 크거나 같다면, $Z_{LB}$ 가 달성 가능함을 증명한다.
- 두 개의 경기장 케이스( $m=2$ ): 두 개의 경기장의 경우, 문제는 두 개의 상보적인 **임계 그래프(threshold graphs)**를 분석하는 것으로 귀결된다. 저자들은 이 임계 그래프들의 크로마틱 인덱스를 계산함으로써 하한이 달성 가능한지 여부를 결정하는 정확한 다항 시간 테스트( $O(n \log n)$ )를 개발한다.

3. 휴리스틱 접근법 (반복 지역 탐색, ILS)

정확한 방법(exact methods)이 실패하는 대규모 인스턴스를 위해, 저자들은 반복 지역 탐색(Iterated Local Search, ILS) 휴리스틱을 제안한다:

초기 해(Initial Solution): 두 가지 방법으로 생성된다: (1) 그리디 분할(greedy splitting)을 이용한 1-팩터 분해(1-factorization), (2) 구성적 에지 채색(Misra–Gries 알고리즘) 후 켐페 체인(Kempe-chain) 패킹을 통해 라운드 수를 $q$ 로 줄이는 방식.
지역 탐색 이웃(Local Search Neighborhoods): 알고리즘은 다음 네 가지 이웃을 사용하는 최적 개선(best-improvement) 전략을 채택한다:
1. 병합 및 분할(Merge-and-Split): 두 라운드를 병합하고 경기를 두 개의 새로운 실행 가능한 라운드로 재배분한다(충돌 그래프의 2-채색으로 모델링됨).
2. 단순 퇴출 체인(Simple Ejection Chain): 한 경기를 새로운 라운드로 이동시키고, 충돌하는 경기를 퇴출시킨 뒤, 해당 경기를 제3의 라운드로 이동시킨다.
3. 가변 깊이 퇴출 체인(Variable-Depth Ejection Chain, VEC): 더 긴 변위 시퀀스를 탐색하기 위해 빔 탐색(beam-search)을 사용하여 단순 체인을 확장한다.
4. 퇴출 및 삽입(Eject-and-Inject): 전체 라운드를 제거하고 경기를 재할당한 뒤, 라운드 수를 유지하기 위해 시드(seed) 경기로부터 새로운 라운드를 생성한다.
섭동(Perturbation, Kick Move): 지역 최적해를 탈출하기 위해 하이브리드 적응형 킥 무브(kick move)가 사용된다. 이는 무작위로 라운드 부분 집합을 선택하고, 그 경기들을 모은 뒤 재구성한다. 재구성이 실패할 경우, 할당된 라운드 간에 경기를 순열(permute)하면서 실행 가능성을 유지하는 일반화된 켐페 체인 이동(generalized Kempe chain shift)을 적용한다.

계산 결과

실험은 $n \in \{8, 16, 32, 64\}$ 팀, $m \in \{2, 4, 8, 16\}$ 경기장, 그리고 다양한 라운드 제한 $q$ 를 가진 64개의 벤치마크 인스턴스를 대상으로 수행되었다.

MIP 성능:
- 할당 기반(AB) 정식화는 중소 규모 인스턴스( $n \le 32$ )에서 시간 인덱스(TI) 정식화보다 성능이 현저히 우수했으며, 종종 최적해를 찾아냈다.
- 그러나 두 정식화 모두 $n=64$ 에서 어려움을 겪었다. AB 모델은 빈번하게 메모리 제한에 부딪히거나 실행 가능한 해를 찾는 데 실패한 반면, TI 모델은 큰 최적성 격차(optimality gap)를 보였다.
- 대칭성 파괴 제약 조건은 $n=32$ 에서 TI 성능을 향상시켰으나, 어려운 인스턴스에서는 AB 성능을 저하시켰다.
ILS 성능:
- ILS 휴리스틱은 64개 인스턴스 모두에서 실행 가능한 해를 성공적으로 찾아냈다.
- $n=8$ 및 $n=16$ 의 경우, ILS는 증명된 최적해와 일치했다(격차 0%).
- $n=32$ 의 경우, 최적의 구성(Merge-and-Split, Simple Ejection Chain, Variable-Depth Ejection Chain 사용)은 평균 **0.15%**의 최적성 격차를 달了했다.
- $n=64$ 의 경우, ILS는 적절한 격차(MIP 모델의 약한 하한 대비 평균 ~10.5%)를 유지하며, 실행 가능한 해를 생성하는 데 자주 실패하는 MIP 접근법보다 실질적으로 우수한 성능을 보였다.
- "Eject-and-Inject" 이웃은 테스트된 매개변수 하에서 역효과를 내는 것으로 나타났으며, 평균 격차를 증가시켰다.

의의 및 주장

본 논문은 네 가지 주요 기여를 주장한다:

문제 정식화: 고전적인 라운드 로bin 문제의 고정된 라운드 구조를 완화하여, 아마추어 스포츠의 실제 제약을 반영하는 새로운 스케줄링 변형(CRRTSP-FMR)을 도입하였다.
복잡도: 단순화된 비용 구조에서도 문제의 본질적인 계산적 난해함(강력한 NP-완전성)을 확립하였다.
구조적 통찰: 다항 시간 내에 해결 가능한 영역을 식별하고, 임계 그래프 이론을 사용하여 두 개의 경기장 케이스에 대한 정확한 최적성 테스트를 제공함으로써 독립 경기 하한이 달성 가능한 조건을 규명하였다.
알고리즘 솔루션: 에지 채색(edge coloring) 및 켐페 체인(Kempe chains)과 같은 그래프 이론적 구조를 활용한 맞춤형 ILS 휴리스틱이 대규모 인스턴스에서 exact MIP 접근법이 실패하는 지점에서 효과적으로 작동함을 입증하였다.

저자들은 라운드 수의 유연성이 라운드 제한 $q$ 가 충분히 높을 때, 특정 팀 집단에 더 가까운 경기장을 선택할 수 있게 함으로써 이동 거리 감소를 크게 가능하게 한다고 결론짓는다. 또한 향-후 연구에서는 경기장 가용성, 심판 배정, 공정성 지표와 같은 추가적인 실무 제약 조건을 포함할 수 있다고 언급하였다.