[논문]열차 증편방법에 관한 연구

김영훈; 임석철

doi:10.7782/jksr.2014.17.4.313

문제 정의

대부분의 기존 연구들의 목적은 역에서의 경합 해소를 위한 추월 및 교차 역을 결정하는 문제이고 본 논문의 목적과 유사한 경우는 Cacchiani의 논문으로 기존 시각표의 열차 스케줄을 고정한 상태에서 화물열차를 추가하는 것을 목적으로 하였으나 본 논문에서는 열차 속도에 따른 차종별 증편방법과 시간범위내에 모든 슬롯의 운행가능성 있는 해를 제시하였다.
그러나 열차 증편을 고려한 비주기 시각표 작성문제는 기존에 운행되고 있는 대부분의 여객열차들의 정차 및 출발시각 변동을 금지한 상태에서 증편되는 열차의 스케줄을 찾아야 하기 때문에 기존 시각표의 운행밀도와 차종별 운행패턴, 추가열차의 역간 운행시간 영향에 따라 증편 열차의 경합회피를 위한 운행지연이 발생하거나 스케줄을 추가하지 못하는 경우가 발생한다. 따라서 본 논문에서는 열차 증편 문제를 시공간 네트워크를 사용하여 혼합정수계획법 문제로 모형화하고 열 생성 기법으로 해를 구하는 절차를 제안하였다.
본 논문에서는 열차 증편을 위해 시공간 네트워크로 문제를 모형화하고 열생성기법으로 최적화 문제를 해결하였다. 제안한 모형은 증편 열차의 계획 스케줄을 최대한 많이 생성할 수 있는 목적을 가지며 여객열차 2개 차종과 화물열차의 증편 실험을 통해 시공간네트워크 생성과 최적화 프로그램 수행시간이 3분이내에 실행되어 계산시간상 빠른 시간내에 해를 도출함으로써 모형의 실용성을 확인하였다.

가설 설정

기존 시각표는 경부선 구간을 운영하는 실제 열차 스케줄을 사용하였으며 증편 열차종별로 역간운행시간도 기존 스케줄에서 역간 운행시간을 도출하여 사용하였다. 또한 대피 가능 역들은 모든 역들이 대피가 가능하다고 가정하였다. 모든 실험에서 사용되는 제약조건은 출· 도착 역에서의 안전시격을 3분으로 하였으며 추월제약은 역에서만 추월이 가능하도록 하였다.
운영수익(operation profit)은 시·종착형태와 열차 종류별로 다르게 수익을 얻는 것으로 가정하였다.

제안 방법

Brannlund(1998)는 폐색구간이나 노선에서 열차 수를 제한하기 위한 제약조건을 도입하였으며 시공간 네트워크로 열차의 이동을 모형화하여 사용하고 라그랑지안 완화법(Lagrangian relaxation)으로 문제해결을 제안하였다[4]. Caprara(2000)와 Cacchiani(2010)의경우 시공간 네크워크를 이용하여 열차 증편을 위한 스케줄링 모델과 화물열차 증편에 대한 모델을 정수계획법으로 모델링하고 라그랑지안 완화법으로 문제 해결을 제안하였다[5,6]. Kim & Rim(2014)은 시공간 네트워크를 사용하여 열생성 기법으로 화물열차 증편에 대한 모형을 제시하였으며[7], Budett(2009)은 역에서의 타임 윈도우를 사용하여 메타휴리스틱 기법인 시뮬레이티드 어널링 기법으로 열차증편에 대한 방법을 제시하였다[8].
가상출발노드(σ)에서 시발역으로 요청한 출발시각 이외의 출발 지연허용범위를 갖도록 하며, 중간역 B에서 대피지연허용범위를 갖도록 하였다.
첫째 실험은 증편열차의 출발시각을 주어진 요청시각으로 가정하여 해를 도출하고 이를 분석한다. 둘째 실험은 증편열차를 추가하려는 시간범위 내에 1분 단위로 모든 가능한 출발시각에서 기존열차와의 안전시격 제약을 만족하는 열차들의 운행가능성을 실험한다.
모든 실험에서 사용되는 제약조건은 출· 도착 역에서의 안전시격을 3분으로 하였으며 추월제약은 역에서만 추월이 가능하도록 하였다.
본 연구에서는 기존 시각표의 역과 열차뿐만 아니라 증편열차들의 경로를 표현하기 위해 시공간 네트워크(time-space network)를 비순환 네트워크 G=(V, A)형태로 표현하였다. 시공간 네트워크는 가로축은 1분 단위의 시간을 세로축은 역을 의미한다.
본 논문에서는 열차 증편을 위해 시공간 네트워크로 문제를 모형화하고 열생성기법으로 최적화 문제를 해결하였다. 제안한 모형은 증편 열차의 계획 스케줄을 최대한 많이 생성할 수 있는 목적을 가지며 여객열차 2개 차종과 화물열차의 증편 실험을 통해 시공간네트워크 생성과 최적화 프로그램 수행시간이 3분이내에 실행되어 계산시간상 빠른 시간내에 해를 도출함으로써 모형의 실용성을 확인하였다. 증편열차의 운행 가능성 여부는 증편열차와 기존 시각표에 운행되고 있는 열차와의 역간 운행시간 차이, 증편열차의 운행시각 선행열차와 후속열차와의 열차종별 관계, 선로용량과의 관계에 영향을 받는다.
가상출발노드(σ)에서 시발역으로 요청한 출발시각 이외의 출발 지연허용범위를 갖도록 하며, 중간역 B에서 대피지연허용범위를 갖도록 하였다. 제약조건의 경우 역에서의 출발노드와 도착노드에서 안전시격을 유지하도록 하였으며,역과 역 사이를 주행하는 도중에는 추월을 허용하지 않고 정차역에서만 추월이 가능하도록 허용하였다. 따라서 Fig.
따라서 증편 열차의 출발시간 범위내에 모든 슬롯의 운행 가능성 실험을 통해 운행 가능한 슬롯을미리 계획자에게 알려줄 수도 있다. 주어진 시각표를 통해각 차종별 열차의 증편 실험을 통해 모든 가용한 슬롯의 운행가능성을 파악하였다.
증편 열차의 경우 출발역에서의 지연 허용범위는 20분, 역에서의 지연허용범위는 10분으로 하였으며 총 운행지연이 60분을 초과하는 것을 금지하였다.
이러한 절차를 따라 본 연구에서는 두가지 실험을 수행한다. 첫째 실험은 증편열차의 출발시각을 주어진 요청시각으로 가정하여 해를 도출하고 이를 분석한다. 둘째 실험은 증편열차를 추가하려는 시간범위 내에 1분 단위로 모든 가능한 출발시각에서 기존열차와의 안전시격 제약을 만족하는 열차들의 운행가능성을 실험한다.
Step 1. 추가하려는 열차 경로변수로만 구성된 주문제의 선형완화식을 풀고 쌍대 해를 구한다.
화주나 시각표 작성자가 증편하려고 하는 임의의 열차시각을 출발 역에서 도착 역까지 모두 지정할 경우의 증편방법을 실험하였다. 증편 차종은 새마을, 무궁화, 화물열차에 대해서 각 차종 별로 5개와 10개의 열차를 증편하는 것을 실험하였다.

대상 데이터

만일 새마을호와 무궁화호 열차를 증편할 경우 기존 열차 스케줄과 동일하게 주어진 역을 정차하도록 하며 화물열차의 경우 모든 역을 정차 없이 통과하는 것으로 한다. 모든 증편열차는 의왕역에서 부산역 구간을 대상으로 한다.
열차증편 모델을 통해 각각의 슬롯에 차량 종류별로 증편 여부를 실험한 결과 새마을호 열차의 경우 가용한 슬롯의 82%에 해당하는 126개의 슬롯이 운행 가능한 슬롯으로 계산되었으며 이중 117개 열차는 지연없이 운행 가능한 열차이며 9개차는 지연을 포함한 열차 스케줄이 계산되었다. 무궁화호 열차의 경우 가용한 슬롯에서 40%에 해당하는 62개의 슬롯이 운행 가능한 슬롯으로 계산되었고 42개 열차는 지연이 없이 운행 가능한 슬롯이며 20개의 슬롯은 지연을 포함한 경우다. 화물열차의 경우 여객열차보다 현저히 떨어지는 약 8%에 해당하는 11개 슬롯이 운행 가능한 슬롯이며 지연이 없는 슬롯은 5개, 지연을 포함한 슬롯은 6개로 계산되었다.
실험을 위해 사용된 시각표는 의왕역에서 부산역까지 총 35개의 역을 포함하는 경부선 구간이며 총 40개의 새마을열차와 무궁화열차 스케줄이 포함되어 있다. 기존 시각표에서 새마을호 열차의 정차역은 10개역을 정차하며 대전과 동대구만 2분씩 정차하고 나머지 정차역은 1분씩 정차하며, 무궁화 열차는 총 17개역을 정차하며 새마을과 같이 대전과동대구역을 2분씩 정차하고 나머지 정차역은 1분씩 정차한다.
이 실험에서는 주어진 시각표에서 전체 시간범위를 대상으로 실험하였다. Table 4는 가용한 모든 슬롯에 각 차종별열차를 투입하여 증편 가능성 여부를 파악한 결과이다.
화주나 시각표 작성자가 증편하려고 하는 임의의 열차시각을 출발 역에서 도착 역까지 모두 지정할 경우의 증편방법을 실험하였다. 증편 차종은 새마을, 무궁화, 화물열차에 대해서 각 차종 별로 5개와 10개의 열차를 증편하는 것을 실험하였다. 증편 열차의 경우 출발역에서의 지연 허용범위는 20분, 역에서의 지연허용범위는 10분으로 하였으며 총 운행지연이 60분을 초과하는 것을 금지하였다.

이론/모형

열차 증편을 위해 필요한데이터는 기존 시각표와 증편 열차의 정차 시분, 역간 운행시간, 대피 가능 역이다. 기존 시각표는 경부선 구간을 운영하는 실제 열차 스케줄을 사용하였으며 증편 열차종별로 역간운행시간도 기존 스케줄에서 역간 운행시간을 도출하여 사용하였다. 또한 대피 가능 역들은 모든 역들이 대피가 가능하다고 가정하였다.
시공간 네트워크에서 열차의 경로흐름(path flow)을 사용하여 다중상품 흐름문제(multicommodity flow problem)로 모형화하여 증편열차는 열차 경로 f_k(p)를 사용하였으며 열생성(column generation) 기법으로 문제를 해결하였다. 열차증편 모형을 위해 필요한 변수와 파라미터는 아래와 같다.
열차 증편문제를 다루는 비주기 시각표 작성문제는 Szpigel(1973)이 열차 스케줄링 문제를 혼합정수계획법으로 모형화한 것이 시초이며, 단선구간에서 추월과 교행 가능 역을 결정하기 위해 분지한계법 알고리즘을 이용한 해법을 제시하였다[1]. Javanovic & Harker(1991)는 정수계획법으로 단선구간에서 교행역 위치결정을 위해 시뮬레이션 기능을 포함한 SCAN(Schedule Analysis)이라는 소프트웨어를 개발하였다[2].
제시한 모형을 풀기 위해 정수 계획 모형을 선형계획모형으로 완화한 열 생성 기법을 사용한다. 위에서 제시한 모형에서는 이를 주문제라 하고 아래의 모형은 열 생성 기법에서의 부문제를 해결하기 위한 모형이다.

성능/효과

정수계획법을 통해 가장 영향력 있고 성공적인 방법을 제안한 Brannlund(1998)와 Caprara(2002)의 경우 아크 흐름(arc flow)을 기반으로 한 라그랑지안 완화법을사용하였는데 이 경우 문제 크기가 시공간 네트워크의 경로상의 아크 수에 비례하여 증가하는 O(|A|)의 문제 크기를 가지기 때문에 문제 사이즈가 커지면 해를 도출하기 어려워진다. 본 논문에서는 경로흐름(path flow) 변수를 가지는 열생성기법을 사용하기 때문에 시공간 네트워크의 경로 수에 비례하여 증가하기 때문에 O(|P|)의 문제 크기를 가지므로 대형문제에 비교적 빠른 시간에 더욱 효율적인 해를 도출할 수있다. 대부분의 기존 연구들의 목적은 역에서의 경합 해소를 위한 추월 및 교차 역을 결정하는 문제이고 본 논문의 목적과 유사한 경우는 Cacchiani의 논문으로 기존 시각표의 열차 스케줄을 고정한 상태에서 화물열차를 추가하는 것을 목적으로 하였으나 본 논문에서는 열차 속도에 따른 차종별 증편방법과 시간범위내에 모든 슬롯의 운행가능성 있는 해를 제시하였다.
화물열차의 가용 슬롯은 주어진 시각표의 마지막 열차 시간 범위를 초과하지 않는 범위의 슬롯을 정하였기 때문이다. 열차증편 모델을 통해 각각의 슬롯에 차량 종류별로 증편 여부를 실험한 결과 새마을호 열차의 경우 가용한 슬롯의 82%에 해당하는 126개의 슬롯이 운행 가능한 슬롯으로 계산되었으며 이중 117개 열차는 지연없이 운행 가능한 열차이며 9개차는 지연을 포함한 열차 스케줄이 계산되었다. 무궁화호 열차의 경우 가용한 슬롯에서 40%에 해당하는 62개의 슬롯이 운행 가능한 슬롯으로 계산되었고 42개 열차는 지연이 없이 운행 가능한 슬롯이며 20개의 슬롯은 지연을 포함한 경우다.
시간범위를 고려한 증편방법은 증편열차가 출발하는 역에서 운행이 허용되는 시간 범위내에서 제약조건을 만족하는 운행 가능한 스케줄을 모두 찾는 것이다. 즉, 증편하려고 하는 열차가 출발 역에서 연속되는 두 개의 기존열차간 안전시격 제약조건을 지키면서 허용되는 모든 슬롯의 운행 가능성을 판단한다. 증편하려고 하는 모든 열차는 기존 시각표의 열차운행시각 변동을 금지한 상태에서 추가된다.

후속연구

현재 사용되는 야마기시 선로 용량산정방법은 혼용된 차종군을 가정하기 때문에 생기는 단점을 본 모형을 통해 계산된 가용슬롯의 갯수가 여러 차종을 혼용하여 운행 했을 경우 기존 선로용량 방법과의 비교 분석을 통해 본 모형이 선로용량 분석에 활용될 수 있음을 연구해 볼 필요가 있다. 또한 열차 증편 모형은 열차들의 역간 운행시각을 상수로 가정하여 사용하기 때문에 열차 주행시뮬레이터(Train Performance Simulation)와 함께 활용하면 열차들의 역간 운행 시간을 보다 정확한 값으로 사용하면 보다 세밀한 증편 모형을 활용할 수 있을 것으로 생각된다.
향후 연구 방향은 가용 슬롯의 갯수와 선로용량과의 관계를 분석해 볼 수 있다. 현재 사용되는 야마기시 선로 용량산정방법은 혼용된 차종군을 가정하기 때문에 생기는 단점을 본 모형을 통해 계산된 가용슬롯의 갯수가 여러 차종을 혼용하여 운행 했을 경우 기존 선로용량 방법과의 비교 분석을 통해 본 모형이 선로용량 분석에 활용될 수 있음을 연구해 볼 필요가 있다.
향후 연구 방향은 가용 슬롯의 갯수와 선로용량과의 관계를 분석해 볼 수 있다. 현재 사용되는 야마기시 선로 용량산정방법은 혼용된 차종군을 가정하기 때문에 생기는 단점을 본 모형을 통해 계산된 가용슬롯의 갯수가 여러 차종을 혼용하여 운행 했을 경우 기존 선로용량 방법과의 비교 분석을 통해 본 모형이 선로용량 분석에 활용될 수 있음을 연구해 볼 필요가 있다. 또한 열차 증편 모형은 열차들의 역간 운행시각을 상수로 가정하여 사용하기 때문에 열차 주행시뮬레이터(Train Performance Simulation)와 함께 활용하면 열차들의 역간 운행 시간을 보다 정확한 값으로 사용하면 보다 세밀한 증편 모형을 활용할 수 있을 것으로 생각된다.

핵심어	질문	논문에서 추출한 답변
	열차 증편계획 문제란 무엇인가	열차 증편계획 문제는 기 작성된 시각표에 추가로 운행하고자 하는 열차를 기존 열차와의 경합을 해소하면서 운행 가능한 시각을 결정하는 문제로 정의할 수 있다. 일반적인 열차시각표 작성문제는 주기적 열차운행을 위한 스케줄 생성을 목적으로 최적화나 휴리스틱 기법으로 많은 연구가 진행되어 있는 분야이다.
	스케줄링 문제를 구분하시오	스케줄링 문제는 크게 주기적 시각표 작성 문제(Cyclic Train Timetable Problem)와 비주기 시각표 작성문제(Non-cyclic Train Timetabling Problem)로 구분된다. 주기적 시각표 작성문제의 경우 열차를 운행하기 이전의 운영계획 단계에서 문제를 고려하기 때문에 계획된 열차들이 출·도착 역과 경로가 이미 결정되어 있는 상태에서 운전시격을 고려하기 때문에 각 열차들의 출발시각 변동이 자유롭고 유동적이다.
	스케줄링 문제 중 주기적 시간표 작성 문제의 특징은 무엇인가	스케줄링 문제는 크게 주기적 시각표 작성 문제(Cyclic Train Timetable Problem)와 비주기 시각표 작성문제(Non-cyclic Train Timetabling Problem)로 구분된다. 주기적 시각표 작성문제의 경우 열차를 운행하기 이전의 운영계획 단계에서 문제를 고려하기 때문에 계획된 열차들이 출·도착 역과 경로가 이미 결정되어 있는 상태에서 운전시격을 고려하기 때문에 각 열차들의 출발시각 변동이 자유롭고 유동적이다. 그러나 열차 증편을 고려한 비주기 시각표 작성문제는 기존에 운행되고 있는 대부분의 여객열차들의 정차 및 출발시각 변동을 금지한 상태에서 증편되는 열차의 스케줄을 찾아야 하기 때문에 기존 시각표의 운행밀도와 차종별 운행패턴, 추가열차의 역간 운행시간 영향에 따라 증편 열차의 경합회피를 위한 운행지연이 발생하거나 스케줄을 추가하지 못하는 경우가 발생한다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

열차 증편방법에 관한 연구
A Study on the Additional Train Scheduling Method 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

열차 증편방법에 관한 연구 A Study on the Additional Train Scheduling Method 원문보기

초록 AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

김영훈 (11)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

열차 증편방법에 관한 연구
A Study on the Additional Train Scheduling Method 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper