철도 노선 계획 부문제의 다면체적 접근

Abstract

역과 역간 선로로 이루어진 철도 네트워크에서 승객들의 출발, 도착지점별 수요에 따라 통행이 배정되었을 때, 이를 모두 만족시키면서 비용을 최소화하도록 각 노선별 정차패턴과 빈도를 결정하는 문제를 철도 노선 계획 문제라고 한다. 이 문제는 NP-hard이며, 혼합정수계획문제 모형에 기반하여 열생성 기법을 적용한 접근 방법이 제시되었다. 열생성 기법을 적용했을 때 가장 큰 수정비용을 갖는 정차패턴을 결정하는 부문제를 정의할 수 있고 본 연구에서는 이 부문제를 최적화 모형의 하나인 혼합정수계획문제로 모형화하고 다면체적 접근을 통한 해법을 제안한다. 문제의 혼합정수계획문제 모형에 적용되는 두 유형의 절단평면과 각각의 다항시간 알고리듬을 개발하였고 실험적 결과를 제시하였다.

Railway line planning problem is about deciding stopping pattern of trains on each line and frequency of each pattern to satisfy the origin/destination demands while minimizing cost. The problem is NP-hard and column generation method based on mixed integer programming model was suggested. This study investigates on solution method based on polyhedral approach to the mixed integer programming model of the pricing subproblem which is about finding the stopping pattern that has the maximum reduced cost. Two types of cutting plane and polynomial time algorithm of each cutting plane is introduced and computational results is presented.