AlphaTransit: 도시 규모의 대중교통 노선 설계를 위한 학습 방법

대중교통 네트워크를 설계하려면 많은 순차적인 노선 확장 결정이 필요하지만, 그 품질은 전체 네트워크가 조립된 후에야 비로소 확인할 수 있는 경우가 많습니다. 이러한 지연된 피드백(delayed-feedback) 문제는 대중교통 노선 네트워크 설계 문제 (Transit Route Network Design Problem, TRNDP)의 핵심입니다. 이 문제에서는 노선 간의 상호작용이 기만적일 수 있습니다. 즉, 국지적으로는 유용해 보이는 확장이 환승 병목 현상을 일으키거나, 중복된 겹침을 발생시키거나, 전체 처리량(throughput)을 감소시킬 수 있습니다. 지연된 시뮬레이터 피드백 하에서 노선 구축을 안내하기 위해, 우리는 도시 규모의 버스 네트워크 설계를 위한 탐색 기반 계획 프레임워크인 AlphaTransit를 소개합니다. AlphaTransit는 몬테카를로 트리 탐색 (Monte Carlo Tree Search, MCTS)을 신경망 정책-가치 네트워크 (neural policy-value network)와 결합합니다. 정책(policy)은 노선 확장을 제안하고, 가치(value)는 향후 설계 품질을 추정하며, 탐색(search)은 이러한 예측을 사용하여 각 결정을 개선합니다. 이를 통해 탐색 트리 내부에서 시뮬레이터 롤아웃 (simulator rollouts)을 실행하지 않고도 노선 구축 과정 중에 의사결정 시점의 앞서보기 (decision-time lookahead)를 제공합니다. 우리는 현실적인 도로 위상 (road topology)과 인구 조사 기반 수요 (census-derived demand)를 갖춘 새로운 Bloomington TRNDP 벤치마크에서 혼합 및 전체 대중교통 수요 설정 하에 AlphaTransit를 평가합니다. Bloomington 네트워크에서 AlphaTransit는 두 수요 설정 모두에서 각각 54.6%와 82.1%에 도달하며 가장 높은 서비스율 (service rate)을 달성했습니다. 탐색이 없는 강화학습 (reinforcement learning)과 비교했을 때, 이는 각각 9.9%와 11.4%의 서비스율 이득에 해당하며, 학습된 가이드가 없는 MCTS와 비교했을 때는 각각 2.5%와 11.2%의 이득에 해당합니다. 이러한 결과는 학습된 가이드와 MCTS를 결합하는 것이 대중교통 네트워크 설계를 위해 어느 한 가지 접근 방식만을 사용하는 것보다 더 효과적임을 시사합니다. 우리의 코드와 데이터는 https://github.com/poudel-bibek/AlphaTransit 에서 공개적으로 사용할 수 있습니다.