도시철도 자율 간격 조정 문제에 대한 게임 이론적 접근

Abstract

혼잡도가 높은 도시철도 운영에서의 핵심 요소 중 하나는 예상치 못한 외란(e.g., 승객 수요 급증, 도착 지연)에 대응하여 열차 간 간격을 조정함으로써 승객의 지연을 최소화하는 실현 가능한 시각표를 확보하는 것이다. 도시철도의 경우 짧은 역간 간격으로 인해 열차 간 간격 조정 문제는 각 역에서의 출/도착 시각을 결정하는 문제가 된다. 본 논문에서는 열차 간 통신 자원 제한을 고려하기 위해 각 열차를 분산화된 의사 결정권자로 하는 멀티에이전트 협력 문제로 모형화한다. 열차 에이전트들은 각 역에서의 대기 시간의 합과 각 열차 내 탑승객의 지연 시간의 합을 최소화하는 것을 목표로 한다. 각 에이전트는 반복적인 동시 게임(repeated simultaneous game)을 수행하며, 제한된 커뮤니케이션 상황에서 근접한 열차의 행동만 관측 가능하다. 자신의 비용 함수를 최소화하는 결정이 전역 비용 함수를 최소화하는 행동이 되도록 비용 함수를 디자인하고, 이웃 에이전트들의 행동을 학습하여 이에 대응하는 최적 행동(best response)을 실시간으로 결정하는 온라인 알고리즘을 제안한다. 마지막으로, 현실 문제 수준의 시뮬레이션 실험을 수행함으로써 제안한 알고리즘의 수렴성과 효과성을 입증한다.

In the highly congested urban urban railway transit systems, adjusting headway to minimize passengers cost, which is caused by unexcpected disturbance (e.g. demand variation, arrival time delays), is one of the key decisions. Headway can be controlled by rescheduling arrival/departure time at stations because of the short distances between adjacent stations on URT systems. To consider limitation of communication resources, the agent-based distributed algorithm based on game theory is proposed. The goal of train agents is not only to minimize total passenger waiting time at platforms but also total in-transit delays of on-board passengers. Train agents play the simultaneous game and decide their action by using local information. The cost function of each agent is aligned with global cost function, so the selfish decision made by agent can be interpreted as a cooperative decision of systems view. To reach a Nash equilibrium, the game played repeatedly and each agent observe neighbors action and choose best actions at each iteration. The simulations are conducted to verify effectiveness and to show the proposed algorithm converge to one of the Nash equilibria.