멀티 에이전트 강화학습을 활용한 버스 노선망 최적화

Abstract

버스 노선망 최적화는 대중교통 효율성 향상에 필수적 요소이다. 버스 노선망 최적화 문제는 조합 최적화 문제로 NP-hard 특성을 가져, 실제 대규모 네트워크에서 최적해를 찾기가 어렵다. 현재까지의 관련 연구 대부분은 휴리스틱(heuristic) 또는 메타 휴리스틱(meta-heuristic) 방법론을 통해 문제를 해결하였다. 본 연구에서는 멀티 에이전트 강화학습을 활용한 버스 노선망 최적화 방법론을 제시한다. 멀티 에이전트 강화학습은 에이전트들끼리 협력 또는 경쟁을 통해 보상을 최대화하는 방법론이다. 버스 노선망 최적화 문제는 각 버스 노선들 간의 협업(환승)을 통해 전체 이용수요를 최대화하며, 최적화된 환승 위치를 통해 이용자들의 환승을 최소화할 수 있어야 한다. 본 연구에서는 이용수요를 이동시간으로 나눈 값을 보상값으로 설정하여 이용수요뿐만이 아닌 이동 효율성을 함께 최대화하는 방향으로 노선을 탐색하였다.