역간 OD자료를 활용한 급행열차 최적 정차역 결정 방법론
A method for optimal express train stop scheduling using station OD data
권오현† 김명현* 이성모** 전경수** Kwon, O-hyeon Kim, Myeonghyeon Rhee, Sung-Mo Chon, Kyong Soo
ABSTRACT
Although the effectiveness of an express train's service is measured in "Total System Time or Cost" units, many cases had used indirect method what based on the distintion by number of passengers in a station or experiential knowledgements. These methods are not guarantee itself as an optimal strategy. Focusing "Total System Time or Cost" directly, this paper investigates the express train service's stop scheduling based on each OD-volume and trip time which mainly affect system time and cost. To do this, we built an IP model which has a binary set presenting express train's stop scheduling as decision variable and suggest a Genetic Algorithm (GA) to find heuristic optimal solution.
1. 연구의 배경 및 목적
급행열차 운행은 기존 철도노선의 표정속도 향상을 기함으로써 적은 비용으로 여객의 통행시간 절감 편익 을 가져오며, 타 교통수단 대비 철도노선의 경쟁력을 강화하는 유효한 수단으로서 최근 국내에서도 서울9호 선, 경춘선 등 점차 적용 구간이 확대되고 있는 추세이다.
한편, 급행열차의 운행에 의한 효과가 System Time 또는 Cost의 총 절감량에 의해 측정되는 것이 일반적 임에도 불구하고, 현재까지의 급행열차의 정차역 선정 방법은 System Time 또는 Cost에 대한 직접적인 접 근 방법보다는 역별 승하차 승객 수에 의한 판별, 환승역 여부 또는 경험적인 방식 등 간접적인 방법으로 수 립되고 있으며, 이에 따라 도출된 전략의 우수성에 대한 신뢰는 미흡하였다.
본 연구에서는 System Time 및 System Cost에 가장 직접적인 영향을 주는 요소인 각 역간 수송수요 및 소요시간을 직접 근거로 하여 여러 정차역을 가진 철도 노선을 대상으로 최적 급행열차 정차역을 결정하는 객관적인 방법에 대해 분석하고자 하였다. 모든 역을 정차하는 완행과 일부 역을 건너뛰는 급행이 일정 비율 로 운행한다고 가정하고, 역 통과에 따른 OD별 통행시간 절감 또는 대기시간의 증가량을 총 수송량과 곱한 뒤 합산하여 System Time의 총 절감량을 구하게 된다. 문제의 풀이를 위해 각 역별 급행열차의 정차 여부 집합을 결정변수로 하는 IP 모형을 수립하였으며, 이는 곧 2의 n승(n = 전체 정차역 수)의 복잡도를 갖는 NP-Hard 문제이므로 최적해 탐색을 위해서는 유전자 알고리즘 (GA)를 이용한 휴리스틱 방법을 선택하였다. 마지막으로 본 연구의 방법론을 실제 운행 노선인 광역철도 경춘선에 적용하여 현재의 운행 패턴과 비교하였 다. 향후 연구과제로는 열차 간 추월 및 완급결합에 의한 시간절감 편익을 추가 반영하는 등 모형을 정교화하 는 것 이외에도 운행비용을 고려하여 전체 System Cost의 최소화를 목표로 하는 전략 방안의 연구를 제안할 수 있다.
연구명 연구자 정차역 선정 기준 현행 경인선 급행열차 1일 10만 명 이상 역에 정차 급행 지하철의 시간절감 효과분석 연구 (1997) 원제무, 황준환 1일 5만 명 이상 역에 모든 전동차 정차 철도 Skip Stop System 구축에 관한 연구
(2000) 서원호 역별 승하차인원의 평균대비 비율을 사용. 급행열차 도입에 따른 도시철도 운행 최적화에 관한 연구 (2003) 손기민 대피선 설치비용을 고려, 건설비용 최소호 전략을 유전 알고리즘으로 풀이 급행열차 도입을 통한 최적운행방안 수립에 관 경인선 벤치마킹을 통해 도출된 판별식의 표 1. 급행열차 관련 선행연구의 정차역 선정 기준 2. 본론 2.1. 선행 연구 고찰 국내에서의 급행열차 운행 전략에 관한 연구는 1997년 원제무 등의 ‘급행 지하철의 시간절감 효과분석 연 구’을 시작으로 꾸준한 연구가 진행되었다. 초기단계에서는 서울시 도시철도 구간을 대상으로 추가시설 없이 운행방식 병경을 통한 격역정차 방식이 주된 연구의 방법으로 사용되었으며, 2000년대에 들어서는 추월선(대 피선)설치 및 추가노선 설치 등의 방법들이 적용되었으며, 알고리즘 및 시뮬레이터의 개발로 미시적인 분석 이 이루어지기 시작하였다. 최근에 들어서는 서울도시철도 9호선, 중앙선 등 실제 급행열차 적용 사레가 나타 나면서 이들 실제 노선에 대한 실질적인 실행방안에 대한 연구도 등장하고 있다. 한편 원제무 등의 연구 이래 많은 연구가 급행열차 운행대안 성과의 주요 평가 지표로 ‘총 통행시간 (총 통행 인-시간)의 단축’이라는 계량적인 지표를 활용하고 있음에도 불구하고, 급행열차 운행 전략의 중심이 된다고 할 수 있는 정차 역의 선정 기준은 총 통행시간을 직접 목적값으로 하는 수학적 모형에 의하기보다는 상당 부분이 주관적인 방법 또는 경험적인 방법에 의존하고 있었다. 예컨대 역별 승하차 승객 수에 의한 판 별(박경수 등), 환승역 여부 또는 지역대표성(이원순 등)등 간접적인 방법으로 수립되고 있으며, 이에 따라 도출된 정차 전략의 우수성에 대한 신뢰는 다소 미흡하다고 볼 수 있다.
따라서 이상의 선행연구 고찰을 통해 본 연구에서는 System Time 및 System Cost에 가장 직접적인 영향 을 주는 요소인 각 역간 수송수요 및 소요시간을 직접 목적식으로 하는 것을 착안점으로 하여, 여러 정차역 을 가진 철도 노선을 대상으로 최적 급행열차 정차역을 결정하는 객관적인 방법에 대해 분석하고자 함을 연 구의 목표로 설정하였다. 2.2. 분석 방법론 문제의 풀이를 위해 각 역별 급행열차의 정차 여부 집합을 결정변수로 하는 IP 모형을 수립하였으며, 이는 곧 2의 n승(n = 전체 정차역 수)의 복잡도를 갖는 NP-Hard 문제이므로 전역해를 구하기는 어렵다. 따라서 모형의 풀이 방식으로는 유전자 알고리즘 (GA)를 이용한 휴리스틱 방법을 선택하였다. 모든 역을 정차하는 완행과 일부 역을 건너뛰는 급행이 일정 비율로 운행한다고 가정하고, 역 통과에 따른 OD별 통행시간 절감 또는 대기시간의 증가량을 총 수송량과 곱한 뒤 합산하여 System Time(총 통행 인-시 간)의 총 절감량을 구하게 된다.
2.2.1. 이론적 배경
유전자 알고리즘(GA, Genetic Algorithm)은 최적화 문제를 해결하는 휴리스틱 기법의 하나이다. 생물종의 진화 과정 및 적자생존의 원리를 모방한 계산 모델로서 John Holland에 의해서 1975년에 개발되었다. 유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음 이들을 점차적으 로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 유전 알고리즘은 자연과학, 공학 및 인문사회과학 분야에 서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는데 널리 응용되고 있다. 본 연구에서는 역 i의 급행열차 정차 여부를 1 또는 0의 2진 비트로 표현하여 유전자 및 결정변수로 활용 하였다. 이에 따라 유전자의 총 길이는 노선 내 존재하는 모든 정차역의 개수(n)와 같게 된다. 각 개체의 생 존성을 나타내는 적합도 함수로는 목적함수 값인 System Time(총 통행 인-시간)을 사용하였으며, 선택 확 률로는 룰렛 알고리즘을 적용하였다. 초기 모집단의 개수는 100개, 돌연변이가 일어날 확률은 0.01로 설정하 였다. 2.2.2. 모형식 설정 급행열차 운행으로 인한 시간 이득은 기본적으로 중간 정차역을 건너뜀으로서 매 통과역 당 가․감속 및 승 하차에 소요되는 시간(=정차조작시간)을 절감하는 원리이다. 반면 통과역에서는 급행열차가 통과하는 편수 만큼 이용 가능한 열차편이 감소하므로 대기시간이 늘어나는 Trade-off Problem의 성격을 가진다. 이와 같은 특성을 반영하여 본 연구에서는 급행열차 이용이 가능한 통행 패턴과 그렇지 않은 통행 패턴을 나누어, 승객이 일정 확률로 급행열차를 만났을 때 각각의 시간이득 및 시간손실을 반영하는 다음과 같은 정 수계획(IP) 모형식을 수립하였다. ×
× ×
× ×
×
× (1) subject to
(2) ∈ (3) 또한 이 모형에 사용된 변수는 다음과 같다. 급행(Rapid)열차의 운행 횟수 완행(Local)열차의 운행 횟수 노선 내 정차역의 총 개수 대기시간 (평균배차시격의 절반) 역 i에서 역 j까지의 급행열차 소요시간 역 i에서 역 j까지의 완행열차 소요시간 역 i에서 역 j까지의 이용승객 수 (수요) 정차조작시간 역 i의 급행열차 정차여부 결정변수 ( 1 = 정차, 0 = 통과) 목적식(1)과 제약식(2)를 전개하여 나타내면 이 모형식은 다음과 같이 보다 간단히 바꾸어 쓸 수 있다. ×
× ×
× (4) subject to ∈ (3) 목적식(4)을 통해 이 모형은 급행열차가 직접 연결되는 통행 패턴에 대해서는 도중의 1개 통과역 당 정차 조작시간(ST)씩의 시간 이득을 반영하고, 그렇지 않은 패턴에 대해서는 급행열차의 무정차 통과로 인한 대기 에 의해 2W(=headway)만큼의 시간 손실을 반영하는 모형임을 확인할 수 있다. 따라서 급행열차의 정차역을 나타내는 결정변수는 통과역의 개수 및 대기시간(=headway)에 따라 결정되게 될 것이다. 한편 완행-급행 열차의 운행 비율은 급행열차를 만나게 될 확률의 상수로써 사용되었으므로 이 모형의 정차역 선정 결정변수 에는 영향을 미치지 못한다. 2.3. 모형의 적용 설정된 모형을 최근 개통된 경춘선 복선전철 (상봉~춘천, 81.3km) 구간에 적용하여 정차역 대안을 탐색하 였다. 경춘선 구간은 현재 완행과 급행열차가 약 2:1의 비율로 편성되어 운행되고 1일 137회 운행하고 있으 며 급행은 63분, 완행은 79분이 소요되고 있다. 배차시격은 RH 12분, NH 20분을 기본으로 하고 있다. 역간 거리가 길고 배차시격도 길기 때문에 완행과 급행 간 추월은 발생하지 않는 것이 특징이다. 국가교통데이터베이스(KTDB)에 등록된 역간 수송실적 자료를 바탕으로 역간 OD를 생성하였으며, 최신자 료 및 통학수요의 반영을 고려하여 2011년 3월의 수송실적을 기준으로 하였다. 배차시격에 대해서는 0분 ~ 20분까지의 시나리오를 개별 연산한 후 각각의 결과값을 비교하도록 하였다. 3. 결론 모형의 연산 결과는 (표2) 및 (표3)과 같다. 현재의 급행열차 정차 패턴과 비교해본 결과 RH 12분 배차시 격을 기준으로 하여 도출된 최적후보 대안과 현행 패턴이 거의 유사하게 나타남을 확인할 수 있다. 한편 현재의 정차 패턴은 2010년 12월 경춘선 복선전철 개통 이후 지역주민의 지속적인 민원 등에 의해 2 차에 걸친 수정으로 마련된 것임을 주목할 필요가 있다. (2011년 6월 사릉역 추가 정차, 2011년 8월 청평 ․ 강촌역 추가 정차) 따라서 향후 신규 개통 또는 급행열차가 추가 운행되는 노선에 대해서는 사전에 본 연구 및 이와 유사한 방법론을 적용한다면 이와 같은 혼란을 미연에 방지할 수 있음은 물론, 철도운영자 측면에서 도 사후 무리한 추가 정차 요구에 대한 객관적인 반박 근거를 마련할 수 있을 것이 기대된다. 향후 연구 과제로는 급행열차가 완행열차를 추월 및 완급 간 결합이 일어나는 노선에도 적용 가능하도록 모형을 개선 및 역간거리 등 선로조건을 감안하여 통과시간 이득 연산을 보다 정교하게 하는 등의 연구와 더 불어, 운영 측면에서의 Cost를 고려한 전체 System Cost 최소화를 목적식으로 하는 모형의 확장 연구를 제 안할 수 있다.Headway 상봉 망우 갈매 퇴계 원 사 릉 금곡 평내 마석 대 성 리 청 평 상천 가평 굴 봉 산 백 양 리 강 촌 김 유 정 남 춘 천 춘 천 절감값 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 6,976,270 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 5,979,153 2 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 5,205,638 3 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 4,647,597 4 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 4,190,248 5 1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 3,838,722 6 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 3,608,796 7 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 3,422,269 8 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 3,235,742 9 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 3,049,215 10 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 2,862,688 <현행> 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 <현행> 11 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 2,705,557 12* 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 2,574,082 13 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 2,442,607 14 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 2,311,132 15 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 2,179,657 16 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 2,064,486 17 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1,988,181 18 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1,911,876 표 2. 모형식 연산 결과 (정차조작시간 ST = 1.5분) Headway 상봉 망우 갈매 퇴계 원 사 릉 금곡 평내 마석 대 성 리 청 평 상천 가평 굴 봉 산 백 양 리 강 촌 김 유 정 남 춘 천 춘 천 절감값 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 9,301,694 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 8,296,603 2 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 7,323,408 3 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 6,754,837 4 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 6,196,796 5 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 5,722,682 6 1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 5,333,926 7 1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 5,010,482 8 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 4,811,728 9 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 4,625,201 10 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 4,438,674 11 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 4,252,147 12* 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 4,065,620 13 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 3,879,093 <현행> 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 <현행> 14 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 3,695,060 15 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 3,563,585 16 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 3,432,110 17 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 3,300,635 18 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 3,169,160 표 3. 모형식 연산 결과 (정차조작시간 ST = 2.0분)
출발역 상봉 망우 갈매 퇴계원 사릉 금곡 평내 마석 대성리 상봉 185,748 3,895 49,327 44,879 14,475 107,460 60,971 22,951 망우 201,322 237 1,282 2,480 770 3,159 2,340 1,856 갈매 4,019 271 271 300 241 744 538 83 퇴계원 45,871 1,700 419 512 1,495 6,983 4,484 291 사릉 62,013 3,532 633 463 400 2,695 2,235 148 금곡 16,565 960 438 1,625 306 1,422 1,477 131 평내 112,174 4,186 1,347 6,776 2,661 1,208 3,624 528 마석 60,962 3,055 608 4,595 1,915 1,369 3,705 335 대성리 23,283 537 139 325 182 161 551 337 청평 26,793 895 144 900 475 547 2,288 1,777 270 상천 7,518 352 78 194 122 274 503 564 34 가평 43,640 1,101 109 1,315 472 602 2,798 2,239 229 굴봉산 3,098 103 17 81 40 50 118 68 28 백양리 3,356 103 8 70 10 38 60 118 15 강촌 24,988 1,141 165 983 680 532 1,265 1,306 134 김유정 4,144 194 28 105 56 95 228 268 29 남춘천 126,858 3,069 385 7,472 2,494 2,560 10,272 7,558 588 춘천 133,757 3,076 380 5,816 1,910 1,789 7,410 4,954 431 출발역 청평 상천 가평 굴봉산 백양리 강촌 김유정 남춘천 춘천 상봉 30,007 5,358 46,740 3,422 2,929 26,803 5,430 145,097 119,986 망우 1,242 176 1,251 159 205 1,175 99 2,374 2,157 갈매 153 11 106 42 14 136 31 399 358 퇴계원 906 155 1,245 71 81 884 127 7,114 5,142 사릉 651 61 559 55 20 817 60 3,267 2,207 금곡 556 163 687 57 14 478 109 3,012 2,043 평내 2,689 485 2,965 89 77 1,088 233 9,335 6,420 마석 2,165 489 2,337 71 92 1,188 487 7,611 4,548 대성리 355 24 322 21 17 118 36 811 470 청평 719 1,652 35 28 256 134 3,160 1,539 상천 1,263 622 9 4 56 52 515 271 가평 2,370 478 159 117 904 202 6,918 3,700 굴봉산 81 12 142 9 102 75 925 292 백양리 34 9 120 27 161 57 1,085 315 표 4. 2011년 3월 경춘선 운송실적 (자료 : KTDB) 참고문헌 1. 국토해양부, 수도권 광역교통망 개선계획 및 지침, 2008 2. 원제무 황준환, 급행 지하철의 시간절감 효과분석 연구, 1997 3. 이원순 국광호, 수도권 광역철도 급행열차 운행방안 연구, 2007 4. 박정수 이훈희 원제무, 급행열차 도입을 통한 최적운행방안 수립에 관한 연구, 2006 5. 손기민, 급행열차 도입에 따른 도시철도 운행 최적화에 관한 연구, 2003
6. 서원호, 철도 Skip Stop System 구축에 관한 연구, 2000
7. 오석문 홍순흠 김형진, 광역철도의 Skip-Stop 운영에서 최적 열차패턴 및 차량소요 산정을 위한 정 량분석 연구, 2002
