Bilevel Optimization and Heuristic Algorithms for Integrating Latent Demand into the Design of Large-Scale Transit Systems

이 논문은 잠재 수요를 고려한 대규모 대중교통 시스템 설계를 위해 이분산 최적화 모델 (TN-DA) 을 제안하고, 이를 효율적으로 해결하기 위한 휴리스틱 알고리즘을 개발하여 실제 사례를 통해 높은 품질의 해를 빠르게 도출할 수 있음을 입증했습니다.

핵심

🚌 핵심 비유: "요리사와 손님 사이의 게임"

이 문제를 상상해 보세요. **대중교통 기관 (기관)**은 한 명의 요리사이고, **잠재적인 손님 (잠재 수요)**은 아직 식당에 오지 않은 손님들입니다.

1. 요리사의 고민 (기관):

   • "내가 어떤 메뉴를 만들고, 어떤 테이블을 배치해야 손님이 많이 오고, 내가 돈을 많이 벌까?"
   • 하지만 문제는, 손님이 오기 전에 메뉴를 다 정해야 한다는 점입니다.
   • 만약 손님이 "이 메뉴는 너무 비싸다"거나 "이곳은 너무 멀다"고 생각해서 오지 않는다면, 요리사는 공들여 준비한 음식을 낭비하게 됩니다.

2. 손님의 심리 (잠재 수요):

   • 손님들은 "내가 지금 차를 타고 가는 게 더 편한데, 버스나 지하철을 탈 이유가 있을까?"라고 생각합니다.
   • 만약 새로운 교통수단이 너무 느리거나 비싸면, 그들은 절대 이용하지 않습니다.

이 논문의 핵심:
기존에는 요리사가 "손님이 올 거야"라고 가정하고 메뉴를 정했습니다. 하지만 이 논문은 **"손님이 실제로 오기 전에, 그들의 마음을 미리 읽어보고 메뉴를 설계하자"**고 말합니다. 이를 **이중 최적화 (Bilevel Optimization)**라고 하는데, 쉽게 말해 "요리사가 메뉴를 정하면, 손님이 그 메뉴를 보고 오거나 안 오거나를 결정하고, 그 결과를 다시 요리사가 반영해서 메뉴를 고치는" 과정을 반복하는 것입니다.

---

🚀 해결책: "똑똑한 5 가지 시나리오"

하지만 이 게임은 너무 복잡해서 컴퓨터로도 풀기 어렵습니다. 손님이 수만 명이고, 도시가 너무 크니까요. 그래서 저자들은 **5 가지의 '요리사 시나리오 (휴리스틱 알고리즘)'**를 만들었습니다.

이 시나리오들은 두 가지 방식으로 나뉩니다.

1. "손님 리스트를 조정하는 방식" (Trip-based)

• 비유: 요리사가 처음엔 '기존 단골손님'만 보고 메뉴를 만듭니다. 그리고 "누가 이 메뉴를 좋아할까?"를 계산해서, 좋아할 것 같은 손님 10 명을 더 불러와서 메뉴를 다시 고칩니다.
• 전략:
  • 그리디 어드옵션 (Greedy Adoption): "가장 좋아할 것 같은 손님"부터 하나씩 불러와서 메뉴를 다듬습니다.
  • 그리디 리젝션 (Greedy Rejection): "아무래도 안 올 것 같은 손님"은 리스트에서 빼버리고, 남은 손님들을 위해 메뉴를 최적화합니다.

2. "도시 지도를 점진적으로 확장하는 방식" (Arc-based)

• 비유: 요리사가 처음엔 '기존 버스 노선'만 유지합니다. 그리고 "어디에 새로운 노선을 추가하면 손님이 더 많이 오겠지?"라고 생각하며, 가장 효과가 좋은 노선 하나를 골라 고정합니다.
• 전략:
  • 아크-스1 (Arc-S1): 가장 효과가 좋은 노선을 하나씩 추가하며 네트워크를 넓혀갑니다.
  • 아크-스2 (Arc-S2): 처음엔 천천히, 나중엔 빠르게 노선을 추가하며 최적의 지도를 그립니다.

이 방법들은 완벽한 정답을 찾는 대신, 매우 짧은 시간 안에 "거의 완벽한" 답을 찾아냅니다.

---

📊 실제 사례: 미국 두 도시의 실험

이론만 말하지 않고, 실제 데이터를 가지고 실험했습니다.

1. 미시간 주 (오프디맨드 멀티모달 시스템 - ODMTS):

   • 상황: 기존 버스 + 새로운 '요청형 셔틀'을 결합한 시스템.
   • 결과: 작은 도시에서는 완벽한 답을 찾았고, 큰 도시에서는 기존 방법보다 수천 배 더 빠르게 좋은 답을 찾았습니다.

2. 조지아 주 애틀랜타 (전동 킥보드 연결 시스템 - SCTS):

   • 상황: 버스/기차 + 전동 킥보드를 연결한 시스템.
   • 결과: 킥보드를 타고 역까지 가는 '첫마일/마지막마일' 문제를 해결하는 교통망을 설계했습니다. 역시 빠른 시간 안에 훌륭한 설계도를 뽑아냈습니다.

---

💡 이 연구가 우리에게 주는 교훈

1. 손님의 마음을 읽지 않으면 실패한다: 교통망을 설계할 때 "손님이 올 거야"라고 막연히 생각하면, 실제로는 손님이 오지 않아 예산만 낭비하게 됩니다. 손님의 선택을 미리 예측해야 합니다.
2. 완벽함보다 '빠른 실용성'이 중요하다: 완벽한 답을 찾으려면 몇 달이 걸릴 수 있습니다. 하지만 이 논문이 제안한 방법들은 몇 분 안에 거의 완벽한 답을 줍니다. 급하게 교통 계획을 세워야 할 때 (예: 대형 행사, 재난 상황) 매우 유용합니다.
3. 데이터의 힘: 실제 도시의 데이터 (애틀랜타, 미시간) 를 이용해 검증했기 때문에, 이 방법론은 이론에 그치지 않고 실제 도시 계획에 바로 적용할 수 있습니다.

🌟 한 줄 요약

"이 논문은 복잡한 수학 공식을 써서, 대중교통 기관이 '아직 오지 않은 손님'들의 마음을 미리 읽고, 그들이 실제로 이용할 수 있는 최고의 교통망을 매우 빠르게 설계하는 방법을 알려줍니다."

이처럼 이 연구는 수학적 정교함과 실용적인 속도감을 결합하여, 더 나은 도시 교통 시스템을 만드는 데 큰 도움을 줄 것입니다.

기술 요약

이 논문은 대중교통 네트워크 설계에 **잠재 수요 (Latent Demand)**를 통합하는 문제를 다루며, 이를 해결하기 위한 이중 최적화 (Bilevel Optimization) 모델과 효율적인 휴리스틱 알고리즘을 제안합니다. 주요 내용은 다음과 같습니다.

1. 문제 정의 (Problem Definition)

대중교통 기관은 기존 수요만 고려하여 네트워크를 설계할 경우, 잠재적인 신규 이용자들의 채택 (Adoption) 행동을 놓치게 되어 서비스 품질 저하나 비용 증가로 이어질 수 있습니다.

• 핵심 갈등: 교통 기관 (리더) 은 운영 비용 절감과 잠재 수요 확보를 동시에 추구하는 반면, 잠재 이용자 (팔로워) 는 서비스의 편의성과 비용에 따라 대중교통을 채택할지 여부를 결정합니다.
• 목표: 두 주체의 의사결정 상호작용을 고려하여, 기관의 비용과 이용자의 채택 행동을 균형 있게 최적화하는 네트워크를 설계하는 것입니다.

2. 방법론 (Methodology)

A. 이중 최적화 모델 (TN-DA)

논문은 **채용을 고려한 교통 네트워크 설계 (Transit Network Design with Adoptions, TN-DA)**라는 일반적인 이중 최적화 모델을 제안합니다.

• 리더 문제 (Leader Problem): 교통 기관이 네트워크 아크 (노선) 를 설계하여 투자 비용과 핵심/잠재 이용자의 순비용 (Net-cost) 을 최소화합니다.
• 팔로워 문제 (Follower Problem): 주어진 네트워크 설계 하에서 각 이용자가 최적의 경로를 선택하고, 이를 바탕으로 잠재 이용자가 해당 시스템을 채택할지 여부를 결정합니다.
• 블랙박스 선택 함수: 이용자의 채택 행동을 나타내는 선택 함수 ($C_r$) 를 블랙박스 형태로 정의하여, 로짓 모델부터 머신러닝 기반 모델까지 다양한 선택 모델을 유연하게 적용할 수 있도록 합니다.

B. 휴리스틱 알고리즘 (Heuristic Algorithms)

TN-DA 문제는 NP-hard 성격을 가지며 대규모 인스턴스에서는 계산이 매우 어렵기 때문에, 5 가지 효율적인 휴리스틱 알고리즘을 제안합니다. 이 알고리즘들은 복잡한 이중 최적화 문제를 단순화된 고정 수요 네트워크 설계 (TN-DFD) 문제와 이용자 선택 평가 단계로 나누어 반복적으로 해결합니다.

알고리즘은 크게 두 가지 유형으로 분류됩니다:

1. 여행 기반 반복 알고리즘 (Trip-based Iterative Algorithms):
   • $\rho$-GRAD: 잠재 수요 중 채택하는 이용자를 단계적으로 추가하며 설계합니다. (최종 해가 '부정확한 거부 (False Rejection)'가 없음을 보장)
   • $\eta$-GRRE: 거절하는 이용자를 단계적으로 제외하며 설계합니다. (빠른 근사 해 제공)
   • $\rho$-GAGR: 위 두 알고리즘을 결합하여 더 많은 설계 공간을 탐색합니다.
2. 아크 기반 반복 알고리즘 (Arc-based Iterative Algorithms):
   • arc-S1: 기존 네트워크에 최적의 하위 네트워크 (서브-네트워크) 를 단계적으로 추가하여 설계합니다.
   • arc-S2: arc-S1 의 확장 버전으로, 여행 집합 확장 규칙을 두 단계 (느린 확장 $\rightarrow$ 빠른 확장) 로 나누어 계산 효율성과 해의 질을 균형 있게 맞춥니다.

C. 평가 지표

최적 해의 성질을 평가하기 위해 두 가지 새로운 지표를 제안합니다:

• 거짓 거부율 (False Rejection Rate, %Rfalse): 설계 과정에서 제외되었으나 실제로는 시스템을 채택했을 잠재 이용자의 비율.
• 거짓 채택율 (False Adoption Rate, %Afalse): 설계 과정에 포함되었으나 실제로는 시스템을 거부한 잠재 이용자의 비율.
• 이상적인 해: 두 지표가 모두 0 인 상태 (이용자와 기관 간의 균형) 를 의미합니다.

3. 주요 기여 (Key Contributions)

1. TN-DA 프레임워크 도입: 잠재 수요의 채택 행동을 블랙박스 선택 함수로 통합한 범용 이중 최적화 모델을 제시했습니다.
2. 휴리스틱 알고리즘 개발: 대규모 문제에 적용 가능한 5 가지 반복 알고리즘을 제안하여, 최적 해의 성질 (거짓 거부/채택 방지) 을 만족하거나 빠른 근사 해를 제공합니다.
3. 실증 연구: 실제 데이터를 활용한 대규모 사례 연구를 통해 알고리즘의 유효성을 입증했습니다.

4. 실험 결과 (Results)

두 가지 실제 대중교통 시스템에 대한 사례 연구를 수행했습니다:

1. 주문형 멀티모달 교통 시스템 (ODMTS):
   • 미시간 (Ypsilanti/Ann Arbor, 중간 규모): 휴리스틱 알고리즘이 정확한 알고리즘 (Exact Alg.) 과 P-Path 모델이 찾은 최적 해와 동일한 품질의 해를 매우 짧은 시간 (수 분) 내에 찾았습니다.
   • 애틀랜타 (대규모 및 초대규모): 정확한 알고리즘은 24 시간 이상 소요되어도 최적 해를 보장하지 못하거나 메모리 부족으로 실패했습니다. 반면, 휴리스틱 알고리즘 (특히 arc-S2) 은 1 시간 이내로 높은 품질의 해를 찾았으며, 최적 해 대비 1% 미만의 오차 범위를 보였습니다.
2. 전동 킥보드 연결 교통 시스템 (SCTS):
   • 대중교통 (버스/전철) 과 전동 킥보드를 연계하는 시스템 설계에 적용되었습니다.
   • arc-S1 및 arc-S2 알고리즘이 거짓 거부율과 거짓 채택율이 모두 0 인 이상적인 해를 짧은 시간 (약 0.5 시간) 내에 찾아냈습니다.

5. 의의 및 결론 (Significance)

• 계산 효율성: 대규모 교통 네트워크 설계 문제에서 정확한 알고리즘이 수 일의 계산 시간이 걸리는 반면, 제안된 휴리스틱 알고리즘은 수 분~수 시간 내에 고품질 해를 제공합니다.
• 실무 적용성: 교통 기관은 제한된 컴퓨팅 자원이나 긴급한 계획 수립 시 (예: 특별 행사 대응) 휴리스틱 알고리즘을 활용하여 잠재 수요를 효과적으로 포착하는 네트워크를 설계할 수 있습니다.
• 이론적 통찰: 최적 해가 가져야 할 '정확한 거부'와 '정확한 채택'의 성질을 규명하고, 이를 기반으로 알고리즘 설계 가이드라인과 평가 지표를 제공했습니다.

결론적으로, 이 연구는 잠재 수요를 고려한 대중교통 설계의 복잡성을 해결하기 위해 이중 최적화 이론과 휴리스틱 기법을 결합한 강력한 프레임워크를 제시하며, 실제 도시 규모의 교통 계획에 실질적인 도움을 줄 수 있음을 입증했습니다.