Learning-based model predictive control for passenger-oriented train rescheduling with flexible train composition

기술 요약: 유연한 열차 편성(Flexible Train Composition)을 고려한 승객 지향적 열차 재스케줄링을 위한 학습 기반 모델 예측 제어(Learning-based Model Predictive Control)

문제 정의
도시 철도 시스템은 급격히 확장되는 네트워크, 시변적(time-varying) 승객 수요, 그리고 운영 비용과 서비스 품질 사이의 균형 유지 필요성으로 인해 실시간 스케줄링 측면에서 상당한 어려움에 직면해 있다. 기존 연구들은 승객 지향적 스케줄링을 다루고 있으나, 많은 접근 방식이 고정된 열차 편성이나 고정된 운행 빈도에 국한되어 있다. 또한, 유연한 열차 편성(서비스당 열차 단위 수 조정)과 차량 운행(열차 단위를 차고지 간 이동 관리)을 포함하는 것은 방대한 양의 정수 결정 변수를 도입한다. 이는 재스케줄링 문제를 복잡한 혼합 정수 비선형 계획법(MINLP) 또는 혼합 정수 선형 계획법(MILP) 문제로 변환시킨다. 실시간 적용의 주요 병목 현상은 모델 예측 제어(MPC)의 엄격한 시간 제약 내에서 이러한 문제들을 해결하기 위해 요구되는 높은 온라인 계산 부하이다.

방법론
본 논문은 실시간 열차 재스케줄링의 계산 복잡성을 해결하기 위해 딥러닝과 최적화를 결합한 학습 기반 모델 예측 제어(Learning-based MPC) 프레임워크를 제안한다. 이 접근 방식은 다음과 같이 구성된다:

1. 수학적 정식화: 저자들은 시변적 구간별 승객 수요, 유연한 열차 편성, 그리고 차량 운행을 포함하도록 승객 지향적 재스케줄링 모델을 확장하였다. 목적 함수는 총 승객 대기 시간과 운영 비용(에너지 및 편성 변경 비용)을 최소화하는 것이다. 문제는 처음에 MINLP로 정식화되며, 여기서 정수 변수는 열차 편성, 열차 순서, 차량 운행을 나타내고, 연속 변수는 출발 및 도착 시간을 나타낸다.
2. 사전 처리(Presolve) 기법: 최적화 문제의 차원을 줄이기 위해 네 가지 사전 처리 기법이 개발되었다. 이 기법들은 미리 결정된 제약 조건 및 결합된 변수(예: 예정된 시간표에 따른 열차 순서 고정 또는 이미 출발한 열차의 편성 고정)를 바탕으로 정수 결정 변수의 하위 집합을 제거한다.
3. 하이브리드 학습-최적화 접근 방식:
   • 오프라인 학습: 롱 쇼트 터미터 뉴럴 네트워크(LSTM)를 학습시켜 남은 정수 변수의 최적값을 예측한다. 학습 과정에서는 실행 가능성 비율(feasibility rate)을 극대화하기 위해 LSTM 네트워크 앙상블을 사용한다. 네트워크는 전체 MINLP 문제를 풀어 생성된 데이터를 사용하여 학습되며, 손실 함수는 네트워크가 예측한 목적 함수 값과 최적값 사이의 제곱 오차를 최소화한다.
   • 온라인 실행: 실시간 MPC 루프 내에서, 학습된 LSTM 네트워크는 현재 시스템 상태(승객 수, 수요 및 가용 차량)를 바탕으로 정수 변수(열차 편성 및 순서)를 생성한다. 이후 이 변수들은 고정된다.
   • 연속 최적화: 정수 변수가 고정되면, 원래의 MINLP 문제는 연속 비선형 계획법(NLP) 문제(또는 목적 함수가 추가로 근사화될 경우 LP 문제)로 축소된다. 이 축소된 문제는 상세한 시간표(출발 및 도착 시간)를 결정하기 위해 효율적으로 해결된다.
4. 실행 가능성 보장: 재귀적 실행 가능성(recursive feasibility)을 보장하기 위해, 보조 정리 1(Lemma 1)에 기반한 휴리스틱 폴백(fallback) 메커니즘이 사용된다. 만약 LSTM 네트워크가 실행 가능한 정수 변수 집합을 생성하지 못할 경우, 이 휴리스틱이 실행 가능한 해를 구성하여 MPC 루프가 항상 진행될 수 있도록 보장한다.

주요 기여
본 논문은 세 가지 주요 기여를 나열한다:

1. 확장된 모델: 승객 지향적 재스케줄링 모델을 시변적 승객 수요, 유연한 열차 편성 및 차량 운행을 공동으로 최적화하도록 확장하였으며, 수요를 계단형 상수 함수(piecewise constant functions)로 근사하였다.
2. 사전 처리 및 차원 축소: 정수 결정 변수를 제거하여 학습 알고리즘을 위한 탐색 공간을 크게 줄이는 네 가지 사전 처리 기법을 개발하였다.
3. 학습 기반 MPC 프레임워크: 학습된 LSTM 네트워크가 정수 변수를 결정하고 제약 조건이 있는 최적화가 연속 변수를 결정하는 새로운 딥러닝 기반 MPC 접근 방식을 개발하였다. 이는 최적화의 제약 조건 만족 보장 능력과 학습의 계산 속도를 결합한 것이다.

결과
제안된 방식은 베이징 도시 철도 시스템의 3개 노선에서 추출한 실제 데이터를 사용하여 평가되었다. 시뮬레이션에서는 제안된 학습 기반 MPC(NLP 및 LP 변형 모두 포함)를 벤치마크(Warm-start를 사용한 MINLP 및 확장된 시간), 표준 Warm-start MINLP, 그리고 MILP 방식과 비교하였다.

• 계산 효율성: 학습 기반 방식은 솔루션 시간을 획기적으로 단가축시켰다. '학습 + LP' 방식은 폐쇄 루프 테스트에서 평균 0.13초(최대 0.31초)의 솔루션 시간을 달in한 반면, Warm-start MINLP는 96.71초(평균), MILP는 51.36초가 소요되었다.
• 최적성: 학습 기반 방식은 허용 가능한 수준의 트레이드오프를 통해 벤치마크와 유사한 성능을 달성하였다. 폐쇄 루프 테스트에서 '학습 + NLP' 방식은 벤치마크 대비 평균 **4.92%**의 최적성 격차(optimality gap)를 보였으며, '학습 + LP'는 **5.50%**를 기록하였다.
• 실행 가능성: 원시 LSTM 출력의 초기 실행 가능성 비율은 약 98.5~98.9%였다. 그러나 휴리스틱 폴백 메커니즘을 적용한 결과, 모든 학습 기반 방식의 최종 실행 가능성 비율은 폐쇄 루프 시뮬레이션에서 **100%**에 도달하였다.
• 시간표 품질: 생성된 시간표의 시각적 분석 결과, 학습 기반 방식이 승객 흐름에 따라 열차 편성을 성공적으로 조정함(예: 피크 시간대에 더 긴 열차 사용)을 확인하였다. 다만, 벤치마크와 전략상의 미세한 차이로 인해 목적 함수 값에서 약간의 차이가 발생하였다.

의의 및 주장
본 논문은 제안된 프레임워크가 유연한 편성을 포함한 실시간 열차 재스케줄링의 고유한 확장성 및 계산 부하 문제를 효과적으로 해결한다고 주장한다. 정수 의사결정(학습이 처리)과 연속 최적화(솔버가 처리)를 분리함으로써, 이 방법은 운영 관제 센터에 필수적인 실시간 시간표 생성(LP 변형의 경우 1초 미만)을 가능하게 한다. 저자들은 이 접근 방식이 고품질의 제약 조건 만족 해를 얻어야 하는 필요성과 실시간 도시 철도 운영의 엄격한 시간 요구 사항 사이의 균와를 맞추며, 대규모 네트워크를 위한 비용이 많이 드는 정밀 방법론의 실행 가능한 대안을 제공한다고 주장한다. 본 연구는 향-적응성 및 확장성을 더욱 향상시키기 위해 강화 학습 및 멀티 에이전트 시스템을 탐구할 수 있음을 시사한다.