기술 요약: 이종(Heterogeneous) 철도 시스템을 위한 장애 인지형 동적 경로 최적화를 위한 시계열 계획 프레임워크

1. 문제 정의

이종(heterogeneous) 및 다중 궤간(multi-gauge) 네트워크를 가진 철도 운영은 안전과 정시성을 보장하는 데 있어 상당한 어려움에 직면해 있다. 균일한 메트로 시스템과 달리, 이러한 네트워크는 다양한 속도, 정차 패턴, 그리고 결정적인 인프라 제약 조건(예: 미터 궤간과 광궤 열차는 호환되지 않는 선로에서 주행할 수 없음)을 가진 열차들을 포함한다. 이러한 제약은 경로 옵션을 심각하게 제한하며 조정의 복잡성을 증가시킨다.

이 문제는 선로 차단, 열차 고립, 엔진 고장, 속도 저하와 같은 **확률적 장애(stochastic disruptions)**에 의해 더욱 악화된다. 기존 연구는 주로 상위 수준의 시간표 작성에 집중하여 선로 전환(turnout)과 같은 저수준의 운영 세부 사항을 생략하는 경향이 있다. 결과적으로 중요한 결정들이 인간 운영자에게 맡겨지게 되어 안전 사고의 위험을 높인다. 또한, 기존의 많은 최적화 모델(예: MaxSAT, MILP, 메타휴리스틱)은 열차 특성이 균일하다고 가정하거나 실행 가능한 타임스탬프 기반 액션 시퀀스를 생성하지 못하여, 실시간 장애 관리에서의 유용성이 제한된다.

2. 방법론

저자들은 PDDL 2.1(Planning Domain Definition Language)을 사용하여 철도 운영을 시계열 계획 문제로 모델링하는 DART(Disruption Aware Railway Temporal Planning) 프레임워크를 제안한다.

2.1 도메인 모델링

본 프레임워크는 다음을 사용하여 철도 환경을 인코딩한다:

• 객체 유형(Object Types): track-point(선로 지점), station(역), train(열차), engine(기관차), gauge-type(궤간 유형).
• 서술어(Predicates): 공간적 구성(예: train-at), 인프라 연결성(connected, track-accessible), 궤간 호환성(train-gauge, track-gauge), 그리고 장애 상태(track-blocked, engine-damaged)를 포착한다.
• 수치 함수(Numeric Functions): distance(거리), train-speed(열차 속도), slowdown(감속) 계수, boarding-time(승차 시간)과 같은 동적 파라미터를 모델링하는 데 사용된다.
• 지속적 액션(Durative Actions): 모델의 핵심은 다음 10가지 지속적 액션으로 구성된다:
  • 이동: drive-train(열차 주행) 및 drive-engine(기관차 주행) (궤간 호환성 및 선로 확보 처리).
  • 서비스: board-passengers(승객 승차).
  • 장애 복구: attach-engine(손상된 열차에 보조 기관차 결합), drive-assisted-train(보조 엔진 주행), resolve-train-blockage(열차 차단 해결), clear-blocked-track(차단된 선로 제거).
  • 인프라: turnout(선로 전환/분기기 작동).

2.2 장애 분류(Disruption Taxonomy)

프레임워크는 구체적인 복구 전략과 함께 네 가지 장애 유형을 명시적으로 모델링한다:

1. 차단된 선로(Blocked Track): 대기하거나 호환 가능한 궤간 경로로 우회함으로써 해결된다.
2. 차단된 열차(Blocked Train): 열차는 해결될 때까지 움직이지 못하며, 다른 열차들은 우회 경로를 찾는다.
3. 속도 저하(Slowdown): 감속 계수($\alpha$)를 바탕으로 이동 시간을 재계산하거나 열차를 우회시킨다.
4. 엔진 고장(Engine Failure): 보조 기관차를 파견, 부착하여 운행을 재개한다.

2.3 벤치마크 생성

프레임워크를 평가하기 위해 저자들은 다음과 같이 구분된 200개의 인스턴스 벤치마크를 구축하였다:

• 100개의 정상(Nominal) 인스턴스: 장애가 없는 표준 운영 상황.
• 100개의 장애(Disrupted) 인스턴스: 차단된 선로, 차단된 열차, 속도 저하, 엔진 고장을 도입함.
  인스턴스는 Small, Medium, Large, Very Large의 4개 범주에 걸쳐 단조적으로 규모가 확장되며, 3대에서 120대의 열차 및 최대 1,000개의 선로 지점까지 다룬다.

3. 주요 기여

1. 이종 철도를 위한 시계열 계획 도메인: 궤간 호환성 제약, 다양한 열차 프로필, 그리고 저수준 운영 액션(분기기, 승차 등)을 명시적으로 인코딩한 새로운 PDDL 2.1 도메인을 제공한다.
2. 통합된 장애 관리: 계획 과정 내에서 네 가지 서로 다른 장애 유형을 처리하며, 단순한 조정된 시간표가 아닌 실행 가능한 복구 계획을 생성한다.
3. 확장 가능한 벤치마크 데이터셋: 네트워크 밀도와 장애 심각도 증가에 따른 확장성과 강건성을 테스트하도록 설계된 포괄적인 200개 문제 세트를 제공한다.

4. 실험 결과

프레임워크는 최첨단 시계열 플래너인 POPF와 OPTIC를 사용하여 평가되었으며, VAL 플랜 검증기를 통해 검증되었다.

• 계획 유효성(Plan Validity): 성공적으로 생성된 199개(200개 중)의 모든 계획은 VAL에 의해 의미론적으로 올바른 것으로 검증되었으며, 모든 시간 제약, 전제 조건 및 목표 조건을 충족했다.
• 플래너 성능: 두 플래너는 모든 해결된 인스턴스에서 동일한 makespan(완료 시간), 계획 길이 및 지연 값을 생성했다. 이는 솔루션 공간이 궤간 및 안전 규칙에 의해 엄격하게 제한되어 있어, 두 플래너가 동일한 최적 프로토콜로 수렴했음을 시사한다.
• 확장성(Scalability):
  • 정상 운영: 규모가 커져도 makespan은 안정적(~34분)이었으나, 계획 길이는 네트워크 크기에 비례하여 증가했다.
  • 장애 운영: 지표들이 문제 규모에 따라 단조 증가했다. 단 하나의 실패 사례는 가장 큰 규모의 구성(열차 120대, 선로 1,000개, 동시 장애 108개)에서 발생했으며, 이는 30분의 시간 제한에 도달했기 때문이다.
• 지연 분석:
  • **속도 저하(Slowdowns)**가 전체 지연의 주요 원인(60.1%)이었으며, 엔진 고장(30.4%), 차단(9.5%)이 그 뒤를 이었다.
  • 스피어만 상관계수 분석 결과, 시스템 크기 지표와 계산 시간 사이에는 완벽한 양의 상관관계($\rho = 1.0$)가 있었고, 장애 강도와 총 지연 시간 사이에는 강한 상관관계($\rho \ge 0.976$)가 있음이 확인되었다.

5. 의의 및 주장

본 논문은 DART 프레임워크가 이종 철도 시스템의 안전성과 효율성을 향상시키기 위한 확장 가능하고 검증 가능한 솔루션을 제공한다고 주장한다. 고수준의 시간표 작성을 넘어 저수준의 타임스탬프 기반 운영 계획으로 전환함으로써, 본 프레임워크는 선로 전환과 같은 핵심 작업에 대한 수동 의사결정 의존도를 낮춘다.

저자들은 이 연구를 지능형 철도 관리를 위한 실질적인 토대로 위치시키며, 시계열 계획이 대규모의 장애 발생 환경에서도 실행 가능하고 안전 규정을 준수하는 전략을 생성할 수 있음을 입증한다. 연구는 현재 프레임워크가 결정론적 장애 지속 시간을 가정하고 있으나, 향후 연구를 통해 불확실성 하에서의 계획 수정(plan repair) 및 실시간 데이터 스트림과의 통합을 지원하는 방향으로 확장할 것임을 밝히며 마무리된다.

참고: 본 논문은 일반적인 문제의 NP-hard 특성을 해결한다고 주장하는 것이 아니라, 테스트된 규모 내에서 시계열 플래너가 이종 철도 라우팅의 특정하고 제약된 인스턴스를 효과적으로 처리할 수 있음을 보여준다.