🤖 AI

Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints

이 논문은 복잡한 휴식 시간 제약이 있는 버스 운전사 스케줄링 문제를 해결하기 위해 Branch and Price 와 Large Neighborhood Search 를 통합한 새로운 하이브리드 알고리즘을 제안하며, 이를 통해 다양한 크기의 인스턴스에서 기존 최첨단 방법보다 우수한 성능을 입증했습니다.

원저자: Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

게시일 2026-04-23

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

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

이 논문은 **"버스 기사님들의 근무표를 어떻게 짜야 가장 효율적이고, 기사님들도 행복할까?"**라는 아주 실용적인 문제를 해결하기 위한 새로운 방법을 제안합니다.

이 문제를 해결하는 과정은 마치 거대한 퍼즐을 맞추는 것과 같습니다. 하지만 이 퍼즐 조각들은 단순히 모양만 맞으면 되는 게 아니라, "법적으로 4 시간 운전하면 30 분 쉬어야 한다", "차량 변경은 너무 자주 하면 안 된다" 같은 복잡한 규칙들이 얽혀 있어 매우 어렵습니다.

저자 팀은 이 퍼즐을 해결하기 위해 두 가지 강력한 도구인 **Branch and Price (B&P)**와 **Large Neighborhood Search (LNS)**를 개발하고, 이 둘을 더 잘 섞어 쓰는 방법을 찾아냈습니다.

1. 문제의 핵심: "복잡한 규칙의 미로"

버스 운전 기사들의 근무표는 단순히 "A 차는 9 시에 출발, B 차는 10 시에 출발" 식으로 짜는 게 아닙니다.

규칙: 운전 시간 제한, 휴식 시간 (30 분, 45 분 등), 차량 변경 횟수, 야간 근무 등 수많은 법적/노동 규정이 있습니다.
목표: 회사의 비용은 줄이면서 (최소화), 기사님들의 스트레스 (휴식 부족, 차량 변경 등) 는 줄여야 합니다.

이 문제는 컴퓨터가 계산할 수 있는 것보다 규칙이 너무 많고 복잡해서, 기존 방법으로는 큰 규모의 문제를 해결하기 힘들었습니다.

2. 해결책 1: "정밀한 건축가" (Branch and Price, B&P)

이 방법은 작은 퍼즐을 완벽하게 맞추는 데 특화되어 있습니다.

비유: 마치 건축가가 작은 건물을 설계할 때, 모든 자재와 구조를 계산해 가장 완벽한 설계도를 뽑아내는 방식입니다.
작동 원리:
1. 먼저 몇 가지 가능한 근무표 (열) 을 만들어 봅니다.
2. 컴퓨터가 "아직 더 좋은 근무표가 있을까?"라고 계속 찾아냅니다 (Column Generation).
3. 찾은 근무표들을 조합해서 최적의 답을 찾습니다.
한계: 작은 도시 (작은 문제) 에서는 완벽하게 최적의 답을 찾지만, 도시가 너무 커지면 (대규모 문제) 모든 경우의 수를 계산하는 데 시간이 너무 오래 걸려서 포기해야 합니다.

3. 해결책 2: "대담한 개조 전문가" (Large Neighborhood Search, LNS)

이 방법은 큰 퍼즐을 빠르게 개선하는 데 특화되어 있습니다.

비유: 이미 지어진 아파트 단지를 개조하는 작업입니다. 처음부터 다 다시 짓는 게 아니라, "이동 구역 (Destroy)"을 정해서 몇 동을 헐어내고, 그 자리에 더 좋은 설계로 다시 짓는 (Repair) 과정을 반복합니다.
작동 원리:
1. 현재 근무표에서 일부 기사님들의 스케줄을 지웁니다 (파괴).
2. 지워진 부분을 다시 채울 때, 위에서 말한 "건축가 (B&P)"의 기술을 빌려와서 그 부분만 아주 빠르게 최적화합니다 (수리).
3. 이 과정을 반복하며 전체적인 근무표를 점점 더 좋게 만듭니다.

4. 혁신적인 아이디어: "두 방법의 완벽한 결혼" (Integration)

기존에는 '개조 전문가 (LNS)'가 '건축가 (B&P)'를 일회성 도구처럼만 썼습니다. 하지만 이 논문은 두 방법을 더 밀접하게 연결했습니다.

아이디어 1: 지식 공유 (Column Reuse)
- 비유: 개조 전문가가 A 동을 고칠 때 발견한 "멋진 설계 아이디어"를 기록장에 적어둡니다. 그리고 다음에 B 동을 고칠 때, 그 기록장을 보고 "아, 이 아이디어도 쓸 수 있겠네!"라고 바로 적용합니다.
- 효과: 매번 처음부터 다시 계산할 필요가 없어서 속도가 빨라집니다.
아이디어 2: 배경에서 일하는 비서 (Background Solver)
- 비유: 개조 전문가가 현장을 돌며 수리를 하는 동안, **비서 (배경 스레드)**는 기록장에 쌓인 모든 아이디어들을 모아 "전체 아파트 단지의 최종 최적 설계도"를 계속 만들어 봅니다.
- 효과: 현장 수리가 끝날 때마다 비서가 "저기, 제가 만든 전체 설계도가 더 좋네요!"라고 제안하면, 그걸로 바로 갈아입습니다. 이렇게 하면 전체적인 결과가 훨씬 좋아집니다.

5. 결과: 새로운 세계 기록 달성

이 새로운 방법 (특히 '지식 공유'와 '비서'를 모두 쓴 버전) 은 다음과 같은 성과를 냈습니다.

작은 문제: 기존에 가장 잘하던 방법 (B&P) 과 비슷하게 완벽하게 해결했습니다.
중간~큰 문제: 기존에 아무도 풀지 못했던 난이도에서, **가장 좋은 결과 (State-of-the-art)**를 기록했습니다.
효율성: 컴퓨터 자원 (메모리) 을 적게 쓰면서도 더 좋은 답을 찾아냈습니다.

요약

이 논문은 "작은 문제는 정밀하게, 큰 문제는 유연하게" 접근하되, 두 방법을 서로의 지식을 공유하게 하고, 배경에서 계속 최적화를 도와주는 시스템을 만들어냈습니다.

이는 버스 기사님들의 근무표를 짜는 문제를 넘어, 복잡한 규칙이 있는 어떤 업무 배정 문제 (병원 간호사, 항공 승무원 등) 에도 적용할 수 있는 강력한 방법이 될 것입니다. 결국, 기술의 발전으로 기사님들은 더 편하게, 회사는 더 효율적으로 일할 수 있게 된 셈입니다.

이 논문은 복잡한 휴식 제약 조건을 가진 버스 운전자 스케줄링 문제 (Bus Driver Scheduling Problem, BDSP) 를 해결하기 위해 Branch and Price (B&P) 와 Large Neighborhood Search (LNS) 를 통합한 새로운 하이브리드 최적화 기법을 제안하고 평가합니다. 오스트리아의 집단 협약 (collective agreement) 에 기반한 엄격한 법적 및 운영 규칙을 반영한 실제 문제를 대상으로 하며, 기존 방법론보다 우수한 성능을 입증했습니다.

다음은 논문의 상세 기술 요약입니다.

1. 문제 정의 (Problem Description)

목표: 사전에 정해진 버스 노선 (Legs) 을 운전자들의 교대 근무 (Shifts) 로 커버하여 총 운영 비용을 최소화하고 동시에 운전자 만족도 (스트레스 감소, 휴식 시간 최적화 등) 를 극대화하는 것입니다.
주요 제약 조건:
- 복잡한 휴식 규칙: 운전 시간 4 시간 이내 휴식 필수, 휴식 시간 분할 가능 (30 분 1 회, 20 분 2 회, 15 분 3 회 등), 유급/무급 휴식의 위치와 길이에 따른 비용 계산.
- 작업 시간: 최대 운전 시간 (9 시간), 최대 작업 시간 (10 시간), 최소 작업 시간 (6.5 시간).
- 교대 근무 분할 (Shift Split): 3 시간 이상의 휴식은 교대 근무 분할로 간주되며, 이는 운전자들에게 불리하게 작용합니다.
- 목적 함수: 총 비용, 총 소요 시간, 무급 휴식 시간, 차량 변경 횟수, 교대 근무 분할 횟수 등을 가중치하여 선형 결합한 다목적 함수를 최소화합니다.

2. 방법론 (Methodology)

A. Branch and Price (B&P) - 정밀 해법

구조: Master Problem(집합 분할 문제) 과 Subproblem(자원 제약 최단 경로 문제, RCSPP) 으로 분해된 Column Generation (CG) 기반의 분기 한정법입니다.
Subproblem (RCSPP) 최적화:
- 복잡한 휴식 규칙으로 인해 라벨 (Label) 의 차원이 매우 높습니다 (11 개의 자원 추적).
- 성능 향상 기법:
  1. 하위 문제 분할 (Subproblem Partitioning): 휴식 유형 (30 분 휴식 유무 및 위치) 에 따라 그래프를 3 개로 분리하여 불확실성을 제거하고 계산 속도를 높입니다.
  2. 비용 바운드 (Cost Bound): 역방향 탐색을 통해 각 노드의 최대 비용 상한을 계산하여 불필요한 라벨을 제거합니다.
  3. 지수적 아크 스로틀링 (Exponential Arc Throttling): 초기 단계에서 비용이 높은 아크를 제한하여 그래프 크기를 줄이고, 점진적으로 아크를 추가하며 수렴합니다.
  4. 비우세 라벨 제거 개선: k-d 트리 (k-d tree) 와 바운딩 박스 (bounding box) 를 활용한 2 단계 지배 (Dominance) 알고리즘을 도입하여 고차원 공간에서의 라벨 비교 속도를 획기적으로 개선했습니다.

B. Large Neighborhood Search (LNS) - 휴리스틱 해법

구조: 현재 해의 일부를 파괴 (Destroy) 하고 최적화 (Repair) 하는 반복적 알고리즘입니다.
Destroy Operator:
- Tour Remover ( $\omega_{tr}$ ): 특정 노선 (Tour) 을 공유하는 운전자들을 그룹으로 제거합니다. 이는 운전자 간 교대 근무 재배치 가능성을 높여 가장 효과적인 파괴 기법으로 입증되었습니다.
Repair Operator:
- 파괴된 부분 문제를 해결하기 위해 Column Generation (CG) 만을 사용하는 방식 (rcg) 이 전체 B&P 를 사용하는 방식 (rbp) 보다 대규모 인스턴스에서 더 빠르고 효과적이었습니다.

C. B&P 와 LNS 의 긴밀한 통합 (Tight Integration)

Column Storage (+r): LNS 의 하위 문제에서 생성된 열 (Column, 즉 교대 근무) 을 저장하여 이후 다른 하위 문제의 초기 열 집합으로 재사용합니다.
Global Background Solver (+b): LNS 가 실행되는 메인 스레드와 별도로, 저장된 모든 열을 기반으로 정수 계획법 (MIP) 을 백그라운드 스레드에서 지속적으로 실행하여 전역 최적해를 탐색합니다.
최종 제안 모델 (lns+rb(f)):
- 모든 생성된 열을 저장 (Full set) 하고, 백그라운드 솔버를 활성화한 형태입니다.
- 이 방식은 메모리 사용을 줄이면서도 (재사용된 열이 비최적 열 생성을 방지) 해의 품질을 극대화합니다.

3. 주요 기여 (Key Contributions)

고차원 RCSPP 해결: 복잡한 휴식 규칙을 가진 고차원 자원 제약 최단 경로 문제를 효율적으로 해결하기 위한 새로운 지배 알고리즘 (k-d tree 기반) 및 하위 문제 분할 전략 제시.
혁신적인 LNS 설계: 버스 노선 구조를 활용한 새로운 파괴 연산자 ( $\omega_{tr}$ ) 와 CG 기반의 빠른 복구 연산자 도입.
하이브리드 통합 전략: LNS 와 Column Generation 의 상호작용을 강화하여, 하위 문제 간 열 공유 및 백그라운드 전역 최적화 솔버를 도입한 새로운 아키텍처 제안.
새로운 State-of-the-Art (SOTA): 다양한 크기의 인스턴스에 대해 기존 최첨단 방법론 (Construct, Solve, Merge, Adapt 등) 을 능가하는 결과를 달성.

4. 실험 결과 (Results)

데이터셋: 오스트리아 버스 회사 데이터를 기반으로 한 65 개의 벤치마크 인스턴스 (10~250 개의 노선 규모).
작은 규모 인스턴스 (Size < 30): B&P가 최적해를 빠르게 찾거나 매우 낮은 갭 (0.4% 미만) 을 제공합니다.
중간~~대규모 인스턴스 (Size 40~~250):
- lns+rb(f) 모델이 모든 크기에서 가장 좋은 성능을 보였습니다.
- 특히 Size 40 이상부터 기존 메타휴리스틱 (CMSA, Tabu Search 등) 과 B&P 를 모두 압도했습니다.
- 성능 비교: lns+rb(f) 는 평균 GAP 이 가장 낮았으며, 100~250 규모에서도 일관된 성능을 유지했습니다.
통계적 유의성: Friedman 검정 및 Shaffer's post-hoc 검정을 통해 제안된 방법 (lns+rb(f)) 이 다른 모든 방법론과 통계적으로 유의미하게 다른 성능을 보임을 입증했습니다.
효율성: 백그라운드 솔버를 사용하는 lns+rb(f) 는 메모리 사용량이 다소 증가하지만, 계산 자원 대비 얻는 해의 품질 향상 (비용 절감) 이 매우 큽니다.

5. 의의 및 결론 (Significance)

실용적 가치: 복잡한 법적/협약 제약 조건을 가진 실제 버스 운전자 스케줄링 문제에 대해, 소규모에서는 정밀 해법을, 대규모에서는 고품질 휴리스틱을 제공하는 통합 프레임워크를 제시했습니다.
일반화 가능성: 제안된 고차원 RCSPP 해결 기법과 LNS-CG 통합 전략은 버스 운전자 스케줄링뿐만 아니라 다른 인력 스케줄링 문제나 자원 제약 최적화 문제에도 적용 가능합니다.
미래 작업: 초대규모 인스턴스에서의 성능 저하 완화, 백그라운드 스레드의 비최적 열 제거 전략 등 추가적인 통합 기법 연구가 필요함을 제안합니다.

요약하자면, 이 논문은 Branch and Price 의 정밀함과 Large Neighborhood Search 의 확장성을 결합하고, 열 (Column) 재사용과 백그라운드 최적화를 통해 두 방법론의 시너지를 극대화함으로써 버스 운전자 스케줄링 분야에서 새로운 기준 (State-of-the-Art) 을 설정했습니다.