Solving the Line-Based Dial-a-Ride Problem by Generating Stopping Patterns

Each language version is independently generated for its own context, not a direct translation.

1. 배경: "기존 버스 vs. 완전한 택시"의 중간 지점 찾기

기존 버스 (Fixed Bus): 정해진 시간표에 따라 모든 정류장에 멈춥니다. 승객이 없어도 정류장에 서야 하므로 비효율적일 수 있습니다.
완전 주문형 택시 (Dial-a-Ride): 승객이 원하는 곳이면 어디든 갈 수 있지만, 차가 길을 잃거나 비효율적인 경로를 돌 수 있어 비용이 많이 듭니다.
이 논문이 제안하는 시스템 (liDARP):
- 비유: 마치 **"기존 버스 노선 (줄) 을 따라 달리는 택시"**입니다.
- 차는 정해진 버스 노선을 따라 달리지만, 승객이 없으면 정류장을 지나쳐가고 (스킵), 승객이 있으면 멈춥니다.
- 중요한 규칙은 **"차 안에 승객이 타고 있을 때는 방향을 틀 수 없다"**는 것입니다. (예: 서울로 가는 차에 승객이 탔다면, 부산으로 가는 승객을 태우기 위해 뒤로 돌아갈 수 없습니다. 차가 비워져야만 방향을 틀 수 있습니다.)

2. 문제: "시간 제한"이라는 족쇄를 떼다

기존 연구들은 "승객은 15 분 안에 도착해야 한다"는 엄격한 시간 제한을 두었습니다. 하지만 현실에서는 승객들이 조금만 기다려도 된다면 (예: 30 분), 훨씬 더 많은 승객을 한 번에 태울 수 있습니다.

이 논문은 **"시간 제한을 아예 없애버린다면?"**이라고 가정했습니다.

핵심 아이디어: "승객이 언제 도착하든 상관없으니, 차가 가장 효율적으로 돌아다니며 최대한 많은 사람을 태우고, 불필요한 주행 거리를 줄이는 최적의 정차 패턴을 찾아보자!"

3. 해결책: "레고 블록"처럼 정차 패턴을 쌓아올리다

이 문제를 해결하기 위해 저자들은 두 가지 핵심 전략을 썼습니다.

A. '정차 패턴 (Stopping Patterns)'이라는 레고 블록

차량이 노선을 따라 달릴 때, "어떤 정류장에 멈출지"를 미리 정한 블록을 정차 패턴이라고 부릅니다.

예: A 정류장 → C 정류장 → F 정류장 (B, D, E 는 스킵)
이 논문은 차의 전체 여정을 이 '레고 블록'들을 이어붙여서 만드는 방식으로 접근했습니다.

B. "가장 이득이 되는 블록 찾기" (Branch-and-Price)

정류장이 100 개라면, 가능한 정차 패턴의 수는 2 의 100 제곱으로 어마어마하게 많습니다. 모든 경우를 다 계산할 수 없죠.

전략: 처음에는 몇 가지 간단한 블록만 가지고 시작합니다.
가격 책정 (Pricing): "지금 가지고 있는 블록들만으로는 부족해. 더 이득이 되는 새로운 블록 (정차 패턴) 을 찾아봐!"라고 컴퓨터에게 시킵니다.
컴퓨터는 **"어떤 정류장을 멈추면 승객 수익은 최대가 되고, 주행 거리는 최소가 되는가?"**를 계산해 새로운 블록을 찾아냅니다.
이 과정을 반복하며 최적의 답을 찾습니다.

4. 실험 결과: "빠른 것이 최고의 효율"

저자들은 이 방법을 실제로 테스트해 보았습니다.

기존 방법 (ALAEB): 작은 문제 (승객 40 명 미만) 는 잘 풀지만, 문제가 커지면 (승객 60 명 이상) 답을 찾지 못하거나 1 시간 이상 걸려도 "해결 불가"라고 뜹니다.
이 논문의 방법 (Branch-and-Price):
- 빠른 수: 15 분~1 시간 안에 승객 100 명까지의 큰 문제도 해결했습니다.
- 정확도: 완벽한 정답 (최적해) 을 찾는 데는 시간이 걸릴 수 있지만, 95% 이상 정확한 답을 매우 빠르게 찾아냅니다.
- 실용성: 현실 세계에서는 "완벽한 정답"보다 "빠르고 괜찮은 답"이 더 중요합니다. 이 방법은 그 점에서 매우 뛰어납니다.

5. 한 줄 요약

"기존 버스 노선을 따라 달리되, 승객이 없으면 지나쳐가는 '스마트 택시' 시스템을 위해, 시간 제한 없이 가장 효율적인 '정차 조합'을 찾아내는 초고속 알고리즘을 개발했다."

이 연구는 앞으로 공공 교통의 유연성을 높이고, 탄소 배출을 줄이며, 승객의 대기 시간을 줄이는 데 큰 기여를 할 것으로 기대됩니다. 마치 복잡한 도시의 교통 체증을 해결하는 새로운 나침반과 같은 역할을 하는 셈입니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의: 시간 제약이 없는 노선 기반 dial-a-ride 문제 (liDARP without TWs)

배경: 기존 대중교통은 고정된 노선과 시간표를 따르지만, 온디맨드 서비스 (DARP) 는 유연한 경로를 제공합니다. 본 논문은 이 두 가지의 중간 형태인 '반유연 (semi-flexible)' 시스템을 다룹니다.
문제 정의:
- liDARP (Line-based Dial-a-Ride Problem): 차량이 미리 정의된 버스 노선을 따라 이동하되, 승객 요청에 따라 특정 정류장을 건너뛰거나 (skipping), 노선의 끝이 아닌 중간 지점에서 방향을 전환할 수 있는 시스템입니다.
- 핵심 제약 (방향성): 차량은 승객이 탑승한 상태에서는 방향을 전환할 수 없으며, 승객이 모두 하차한 상태 (비어있을 때) 에만 방향을 전환할 수 있습니다. 이는 승객이 원래 이동 방향을 유지하도록 보장합니다.
- liDARP without TWs: 기존 DARP 및 liDARP 연구에서 필수적이었던 '승객의 시간 창 (Time Windows, TW)'과 '최대 대기 시간/이동 시간' 제약을 완전히 제거한 변형 문제입니다.
- 목표: 승객 수락 수와 이동 거리 절감량 (개별 이동 대비) 을 가중치하여 최대화하는 동시에, 차량의 총 이동 거리를 최소화하는 최적의 투어 (경로) 를 찾는 것입니다.
복잡도: 단일 차량, 용량 1 인 경우에도 이 문제는 NP-완전 (NP-complete) 임이 증명되었습니다.

2. 방법론 및 수학적 모델링

저자들은 이 문제를 해결하기 위해 **'정차 패턴 (Stopping Patterns)'**이라는 새로운 개념을 도입하고 이를 기반으로 한 알고리즘을 개발했습니다.

가. 정차 패턴 (Stopping Patterns)

차량의 투어는 '상향 (ascending)' 및 '하향 (descending)' 구간으로 나뉘며, 각 구간은 정류장의 방문 여부를 나타내는 이진 벡터로 표현된 정차 패턴으로 정의됩니다.
정차 패턴은 승객 탑승/하차 지점과 방향 전환 지점을 포함합니다.
가능한 정차 패턴의 수는 정류장 수 $n$ 에 대해 $2^n - 1$개로 기하급수적으로 증가하므로, 모든 패턴을 명시적으로 나열하는 것은 불가능합니다.

나. 혼합 정수 선형 계획법 (MILP) 모델

정차 패턴을 열 (column) 로 간주하는 새로운 MILP 모델을 제안했습니다.
목적 함수: 승객 수락 수와 거리 절감량의 가중 합을 최대화.
제약 조건:
- 각 승객은 최대 1 회만 수락.
- 차량 용량 제한 준수.
- 투어의 연속성 (방향 전환 시 승객 없음).
- 정차 패턴의 시작/종료 지점과 승객의 탑승/하차 지점 일치.

다. Branch-and-Price 알고리즘 (정확 해법)

Column Generation (열 생성): 정차 패턴의 수가 너무 많으므로, 초기에는 소수의 패턴만 포함하는 제한된 마스터 문제 (RMP) 를 풀고, **가격 문제 (Pricing Problem)**를 통해 목적 함수 값을 개선할 수 있는 새로운 정차 패턴을 반복적으로 생성하여 추가합니다.
가격 문제 (Pricing Problem):
- 이는 **가장 수익성이 높은 정차 패턴 (Most Profitable Stopping Pattern)**을 찾는 문제와 동치입니다.
- 이 문제는 **비순환 토너먼트 유방향 그래프 (acyclic tournament digraph)**에서의 경로 찾기 문제로 모델링되며, ILP 로 해결됩니다.
- 이 가격 문제 자체가 NP-난해 (NP-hard) 임이 증명되었습니다.
Branch-and-Price: 분기 한정법 (Branch-and-Bound) 과 열 생성을 결합하여 최적해를 보장합니다. 분기 전략은 승객 할당 변수 ( $x$ ) 와 정차 패턴 할당 변수 ( $y$ ) 에 대해 수행됩니다.

라. 루트 노드 휴리스틱 (Root Node Heuristic)

실제 응용에서는 최적해보다 빠른 해가 더 중요할 수 있으므로, 분기 한정 트리를 구축하지 않고 루트 노드 (Root Node) 에서 생성된 열들만을 사용하여 제한된 마스터 문제를 해결하는 휴리스틱을 제안했습니다.
이는 대규모 인스턴스에 대해 매우 빠르게 근사 최적해를 제공합니다.

3. 주요 기여 (Key Contributions)

새로운 문제 변형 제안: 시간 제약이 없는 liDARP (liDARP without TWs) 를 정의하고, 기존 연구에서 간과되었던 시간적 유연성과 공간적 구조의 결합을 수학적으로 모델링했습니다.
복잡도 증명: '가장 수익성이 높은 정차 패턴' 문제와 그 무용량 버전이 NP-난해임을 증명했습니다.
새로운 MILP 및 Branch-and-Price 알고리즘: 정차 패턴을 기반으로 한 새로운 MILP 형식과 이를 해결하기 위한 Branch-and-Price 알고리즘을 개발했습니다.
실용적 휴리스틱: 대규모 문제 (최대 100 건의 요청) 에 대해 15 분 이내에 5% 미만의 최적성 간격 (optimality gap) 을 달성하는 루트 노드 휴리스틱을 제안했습니다.

4. 실험 결과 (Computational Results)

성능 비교 (Branch-and-Price vs. State-of-the-Art):
- 기존 최첨단 방법 (ALAEB MILP) 은 40 건 이하의 작은 인스턴스에서는 최적해를 찾지만, 55 건 이상에서는 해를 찾지 못하거나 상한값 (bound) 만 구하는 데 그쳤습니다.
- 반면, 제안된 Branch-and-Price 알고리즘은 3600 초 (1 시간) 내에 60 건까지의 인스턴스에서 평균 MIP 갭 2.79% (최대 4.48%) 이내의 해를 찾았습니다.
- 특히, 실현 가능한 해 (incumbent) 를 찾는 속도가 기존 방법보다 훨씬 빨랐습니다.
휴리스틱 성능:
- 규모: 100 건의 요청과 5 대의 차량이 포함된 대규모 인스턴스에서도 900 초 (15 분) 이내에 실행 가능했습니다.
- 정확도: 다양한 설정 (정류장 수, 차량 용량 등) 에서 평균 최적성 간격이 5% 미만을 기록했습니다.
- 용량 영향: 차량 용량이 증가할수록 휴리스틱의 성능이 향상되었습니다 (용량 3 일 때 6.93% 갭 $\rightarrow$ 용량 12 일 때 1.21% 갭).
- 위치 수 (Positions): 이론적으로 필요한 위치 수 ($2m$) 를 줄여도 (예: 10% 수준) 목적 함수 값에는 큰 영향을 주지 않으면서 계산 시간을 크게 단축할 수 있음을 확인했습니다.

5. 의의 및 결론

실용적 가치: 이 연구는 시간 제약을 완화함으로써 승객 풀링 (pooling) 효율을 높일 수 있음을 시사합니다. 특히 실시간 수요 대응이 필요한 온디맨드 교통 서비스에서, 복잡한 시간 창 제약 없이도 효율적인 경로를 빠르게 생성할 수 있는 강력한 도구를 제공합니다.
방법론적 혁신: 정차 패턴을 생성하는 방식은 기존 DARP 연구에서 사용되던 시간 기반 그래프 접근법과 구별되며, 노선 기반 시스템의 고유한 구조를 효과적으로 활용합니다.
미래 전망: 동적 환경 (실시간 요청 도착) 으로의 확장, 시간 창이 있는 경우의 적용, 그리고 기존 시간표 기반 교통 시스템의 지연 복구 (recovery) 에의 활용 가능성 등을 향후 연구 과제로 제시했습니다.

요약하자면, 본 논문은 시간 제약을 제거한 노선 기반 dial-a-ride 문제를 정의하고, 정차 패턴 생성 기법을 통해 대규모 인스턴스를 효율적으로 해결할 수 있는 정밀 알고리즘과 실용적 휴리스틱을 제시함으로써, 차세대 유연 대중교통 시스템의 운영 최적화에 중요한 기여를 했습니다.