www.kicem.or.kr (pISSN 2005-6095 / eISSN 2465-9703) http://dx.doi.org/10.6106/KJCEM.2019.20.5.042 KJCEM 20. 5. 042~051
September 30, 2019
1. 서론
1.1 연구의 배경 및 목적
철도운영기관은 효율적인 열차운용을 위해 열차차량과 같은 운영 장비의 수송능력을 확인하고 수송 수요를 예측하 는 계획을 수립해야한다. 이후 열차운행계획을 통해 열차의 운행간격을 조정하여 열차운행시간표(Train Diagram)를 작 성할 수 있으며, 열차운행시간표를 바탕으로 차량을 관리하 고 운영하는 계획 또한 세울 수 있다. 마지막으로 승무일정 계획을 통해 열차다이아에 따른 승무원의 승무다이아(Crew Diagram) 및 근무교번을 작성한다. 즉 승무일정계획은 열 차운행계획 수립결과에 따라 운행되는 열차들이 차질 없이 운용될 수 있도록 필요 승무인력을 판단하여 배치하는 절차
이다. 승무일정계획 중 승무다이아는 승무원 1인이 출근하 여 퇴근할 때까지 운행하는 열차의 순서를, 근무교번은 승 무다이아의 운용순서를 의미한다(Park, 2000). 이렇듯 승 무다이아를 통해 승무원은 자신이 운전해야하는 열차를 파 악하고 열차운행 시 주의사항을 숙지하며, 자신의 전체적인 근무시간을 알 수 있다.
승무일정계획을 수립하는 과정은 관련 근로기준법, 근무 의 형태, 근무 작성기준과 더불어 철도운영기관의 내규 및 노사합의 사항 등 수많은 제약조건이 있으며 이를 고려해야 하기 때문에 복잡하다. 또한 편승행로의 최소화, 주박사업의 최소화, 승무원 사업시간의 균등화 등 다양한 목적에 따라 결과물이 달라 질 수도 있다. 이러한 승무일정계획 최적화 시스템의 부재로, 현재는 전문가들이 직접 경험적 지식에 의 해 승무다이아 및 근무교번을 작성하기 때문에 상당히 많은 시간이 소요되며, 그렇게 생성된 승무다이아와 근무교번이 최적의 해인지 판별하기 어려운 실정이다. 따라서 본 연구에 서는 승무일정계획 문제 중 하나인 승무다이아 작성을 위해 승무원 근무규정 및 여러 제약조건을 준수하고, 최적의 승무
* Corresponding author: Kang, Leenseok, ERI, Department of Civil Engineering, Gyeongsang National University, Korea
E-mail: [email protected] Received May 27, 2019: revised – accepted July 19, 2019
철도 운영관리 효율화를 위한 이웃해 탐색기법을 사용한 승무다이아 생성방안
이재희1·박상미1·강인석*
1
경상대학교 토목공학과
A Study on the Generation of Crew Scheduling Diagram Using Neighborhood Search Method for Improving Railway Operation Management
Lee, Jaehee
1, Park, Sangmi
1, Kang, Leenseok
*1
Department of Civil Engineering, Gyeongsang National University
Abstract :
The train operation institution establishes a transportation plan based on the forecast of transport demand and the ability of train vehicles to transport, and establishes a train operation plan accordingly. The train operation plan adjusts the intervals between trains, creates a timetable (train diagram) for trains, and establishes a plan for the operation of train vehicles used for train operation. The train operation institution shall establish a crew schedule to determine and place the crew members of the trains arranged in the diagram in order to enhance the efficiency of the operation management of the trains. In this study, the authors apply the neighborhood search method that satisfies the constraints at the phase of generating the crew diagram. This suggests a methodology for efficient management of crew schedule plan. The crew diagram generated in this study compared with the existing crew diagram in accordance with the actual operating train timetable, and verified the effectiveness of the suggested method.
Keywords :
Railway Operation, Crew Scheduling, Crew Diagram, Neighborhood Search
다이아를 생성할 수 있는 방안을 제시하고자 한다. 그리고 제시한 방안으로 생성된 승무다이아와 현재 철도운영기관에 서 작성하여 운용하고 있는 승무다이아를 비교하여 본 연구 에서 제시한 방안의 효과를 입증하고자 한다.
1.2 유사연구 동향
Kim et al. (2011)은 지하철 승무일정계획 수립을 위한 후 보다이아 생성방안으로 승무교대가 가능한 역들의 사이를 이용한 레그 결합 휴리스틱과 제약 조건 설정 두 가지 방법 을 제시하여 부산 지하철 2호선에 적용하여 운행가능계획 을 세울 수 있다는 결론을 도출하였다. Hwang et al. (2004) 의 연구에서는 승무일정계획 최적화를 위한 이웃해 탐색 기 법과 정수계획법의 결합 방안을 제시하였는데, 두 가지 기 법을 결합한 알고리즘을 사용한 경우 각 기법을 단독으로 사용할 때 보다 더 나은 수준의 승무계획을 빠른 시간 내에 수립할 수 있음을 증명하였다. Park (2000)은 ‘승무일정계 획 최적화 시스템’의 일부에 사용되는 휴리스틱 교정 기법 을 제시하였다. 해당 연구에서는 휴리스틱 교정 기법을 사 용하여 초기 승무일정계획에 대해 근무표를 양질로 유지하 면서 승무원 수를 줄인 일정계획을 수립하였다. Tormos, P.
et al. (2008)은 열차운행계획문제 해결방안으로 유전알고 리즘(GA, Genetic Algorithm)을 적용하였고, Khmeleva, E. et al. (2014) 역시 화물열차 승무원 일정계획문제 해결 방안으로 유전알고리즘을 제시하였다. Khosravi, A. et al.
(2016)은 철도승무원일정계획 문제를 해결하기 깊이우선탐 색(Depth-first search) 알고리즘, 정수계획법의 하나인 집 합 덮개(Set covering) 모델을 적용하여 최적의 운행조합을 찾아내고, 최적운행조합에 승무원 그룹을 배치하는 수학적 모델을 제시하였다.
승무일정계획 문제를 해결하기 위해 문헌에서 조사된 해 결방안 사례로는 이웃해 탐색기법, 정수계획법, 휴리스틱 교정기법, 레그 결합 휴리스틱, 제약조건 설정, 열 생성 기 법 등이 있다. 정수계획법은 대상 문제의 제약조건 및 목점 함수가 모두 선형적으로 표현되어야 적용가능하며 문제의 규모가 클 경우 과도한 수행시간이 필요하다는 단점이 있 으며(Hwang & Ryu, 2004), 유전알고리즘은 초기데이터 를 유전자 형태로 표현하는 방법과 개체 수, 선택방법·교 차연산·돌연변이 비율 등 다양한 파라미터 값에 따라 결과 차이가 크게 달라질 수 있다. 따라서 본 연구에서는 승무일 정계획 문제 중 교번작성에 큰 영향을 미치는 승무다이아에 초점을 맞추어 승무다이아 작성 시 고려해야하는 제약조건 및 변수 파라미터 값들을 초기에 설정하여 표현여부에 상관 없이 적용할 수 있도록 하였다. 또한 승무다이아 생성 시 여 러 제약조건을 만족하는 운행열차 조합들의 목록을 생성하
고, 그 중에서 최종 승무다이아를 완성시킴으로써 기존 승 무일정계획 문제 해결방안과 차별성을 두고 있다.
1.3 연구수행 방법
승무일정계획의 한 부분인 승무다이아는 하루 동안 운행 하는 열차들의 조합으로 이루어져 있으며 이에 따라 운행열 차들을 조합하고, 이렇게 조합한 승무다이아를 판별하는 과 정이 수차례 반복된다. 본 연구에서는 승무일정계획의 한 부분인 승무다이아 작성방법으로 제약조건을 만족하는 이 웃해 탐색 기법을 적용하였다.
이웃해 탐색은 이웃해를 반복적으로 탐색함으로써 해를 개선시켜 나가는 방법이다(Hwang & Ryu, 2004). 대표적 으로 시뮬레이티드 어닐링(SA, Simulated Annealing), 터 부탐색(TS, Tabu Search)과 같은 메타휴리스틱 방법이다.
하지만 전체의 범위에서 승무다이아 조합 최적해를 탐색하 면 해의 양이 방대해지기 때문에 최적조합을 찾는데 시간이 과도한 시간이 소요될 수 있다. 이를 방지하고자 승무다이 아 생성 초기단계에서 사용자가 변수 값을 설정하고, 고려 해야하는 제약조건들을 추가함으로써 해 탐색 범위를 좁혀 비교적 짧은 시간 안에 최적의 조합을 찾을 수 있도록 한다.
2. 승무 다이아(Diagram) 작성
2.1 기존 승무 다이아 작성 방법 및 문제점
○○열차운영기관에서는 각 철도운영기관의 열차운행담 당자들 간 열차운행 시간 조정을 통해 최종적으로 정해진 열 차 120편성을 운행하고 있다. 120편성의 상세노선은 수서에 서 부산으로 가는 경부선 하행 40편성, 부산에서 수서로 가 는 경부선 상행 40편성, 수서에서 광주송정으로 가는 호남선 하행 11편성과 수서에서 목포로 가는 호남선 하행 9편성, 광 주송정에서 수서로 가는 호남선 상행 11편성과 목포에서 수 서로 가는 호남선 상행 9편성으로 이루어져 있는데, <Fig. 1>
의 상단은 경부선, 하단은 호남선이며 운행열차의 노선 종 류, 열차번호, 정차 역, 출발·도착시간으로 구성되어 있다.
한 개의 승무다이아는 2~3개의 승무사업의 조합 즉, 열차 운행의 조합으로 구성되어있다. 이렇게 작성된 승무다이아를 통해 다이아 명, 운영요일, 출근·퇴근시간, 열차조합, 총 승 무시간, 편승시간, 준비·정리시간, 승계대기시간, 총 근무시 간, 승무거리, 승무율, 구속율 등을 쉽게 알 수 있다<Fig. 2>.
<Fig. 2>의 S1002 다이아는 승무원이 06:30에 출근하여 311열차-336열차를 운행하고 16:26에 사업이 종료되는 다 이아이며, 월~일요일 모두 운행하는 다이아로 운영요일 칸 모두 1로 표기가 되어있고 그 외 편승시간, 휴게시간, 대기 시간, 총 근무시간, 주행거리등의 정보들이 표기되어있다.
일반적으로 승무다이아는 [출근-출무점호-승무사업-정 리-휴게-승계대기-준비-승무사업-정리-퇴근]의 흐름으 로 구성된다. 편승 사업이 포함되어 있을 경우에는 [출근- 출무점호-편승-정리-휴게-승계대기-준비-승무사업-정 리-퇴근] 혹은 [출근-출무점호-승무사업-정리-휴게-승 계대기-편승-정리-퇴근]의 흐름을 가진다. 구체적인 시간 계산은 다음의 방식을 따른다.
출근시간 = 최초승무사업 출발시간 – 1H
퇴근시간 = 최종승무사업 도착시간 + 정리시간 30분 구속시간 = 퇴근시간 - 출근시간
사업시간 = 구속시간 - 휴게시간
정리시간 = 객실장 : 열차승계 20분, 사업종료 30분 기장 : 열차승계 20분, 사업종료 20분 준비시간 = 30분
휴게시간 = 1H
승무시간 = 승무사업 도착시간 – 승무사업 출발시간 총 승무시간 = 승무시간 + 승무시간
승무율 = 총 승무시간 / 근무시간 * 100(%) 구속율 = 구속시간 / 사업시간 * 100(%)
구속시간은 출근시간부터 퇴근시간까지의 시간을 말하 고, 구속시간에 휴게시간을 뺀 시간을 사업시간 혹은 근무 시간 이라고 하며, 기장의 경우 실제로 열차를 운행한 시간, 객실장의 경우 열차에 탑승하여 근무한 시간을 의미하고 이 는 승무원의 임금과 직접적으로 연결되는 부분이다.
승무원은 운행노선에 따라 2~3번의 운행을 하는데 그 동 안의 시간을 모두 합하면 총 승무시간이 된다. 또한 하나의 승무사업이 종료되고 다음 승계열차가 있을 경우 기장과 객 실장 모두 20분의 정리시간을 갖고 1시간의 휴게시간을 부 여 받은 후, 다음 승무사업시간 까지 승계대기를 하며 승무 시작 30분전에 승무준비를 한다. 승무사업 종료 후 승계열 차가 없으면 기장은 20분, 객실장은 30분의 정리시간을 가 진 이후에 퇴근을 한다.
이와 같은 절차에 따라 모든 승무다이아가 완성되면 다이 아 명을 부여하는데, ○○열차운영기관에서 사용하는 다이 아 명은 다음과 같은 방식으로 명명된다.
Fig. 2. Crew schedule diagram
Fig. 1. Train timetable
출·퇴근시간과 총 승무시간, 그리고 승계대기시간 등의 정보를 담고 있는 승무다이아를 길게 사용하는 것보다 정해 진 규칙에 의한 다이아명을 통해 해당 다이아가 어느 승무 센터의 운행다이아인지 혹은 어느 시간대의 근무다이아인 지 쉽게 확인할 수 있으며, 이는 향후 승무원의 근무교번 작 성 시에도 사용된다.
승무다이아 작성이라는 복잡한 절차는 현재 전문가들의 경험적 지식에 의해 수작업으로 이루어지고 있기 때문에 생 성된 승무다이아가 최적의 다이아인지 판별하기 어렵다. 현 재 ○○열차운영기관에서 작성하여 운용하는 승무다이아의 일주일 간 운행다이아 개수는 전체 481개, 주간 347개, 야 간 134개로 조사되었고, 그 중 편승다이아의 개수는 52개 였다. 편승다이아는 승무원이 실제 근무를 하고 있지 않지 만, 근무시간으로 인정해 주기 때문에 열차운영기관입장에 서 인력운용효율을 저해하는 요소이며 이를 최소화할 필요 가 있다. 그리고 사업시간 편차의 경우 수서승무센터 45분, 부산승무센터 35분, 그리고 광주승무센터는 무려 75분으로 나타났다. 또한 승계대기시간 편차는 수서승무센터가 주간 44분·야간 25분으로, 부산승무센터는 주간 36분·야간 18 분, 광주승무센터는 주간 37분·야간 11분으로 확인되었다.
사업시간과 승계대기시간의 편차가 클수록 향후 승무원의 교번생성 시 총 사업시간의 불균등화를 초래하고, 전체사업 시간의 불균등화는 승무원 임금의 불균등화로 직접적으로 이어지게 되므로 사업시간과 승계대기시간은 전체승무원에 게 균등하게 분배되어야 한다.
2.2 제약조건
승무다이아 작성 시에는 여러 제약조건들을 고려해야 한 다. 이러한 제약조건들은 반드시 지켜야하는 강한 제약과, 원칙을 따르되 경우에 따라 달라질 수도 있는 약한 제약으 로 구분할 수 있다. 승무다이아 작성 시 반드시 지켜야하는 강한 제약은 다음과 같다.
출근시간 = 최초승무사업 출발시간 – 1H 휴게시간 = 1H 이상 부여
야간사업 = 22:00 ~ 06:00 내에 2H 이상의 승무사업 승무율 제한 = 73% 이내
구속율 제한 = 115% 이내 연속운행 횟수, 거리, 시간의 제한 정리 및 준비시간의 부여
수서, 부산, 광주역에서 휴게
운행되는 모든 열차에 승무원이 배정되어야 함 기타 강한 제약으로는
요일별 운행열차 모두 승무다이아에 포함되어야 함
열차의 중복이 발생하지 않아야 함
승무원의 사업시작 역과 종료 역은 동일해야 함
위와 같이 승무원 개인근무 및 사업전체에 관련되어 시간 과 비율이 관련된 제약은 시간적, 승무역과 관련된 제약은 공간적, 그 외기타 제약조건으로 구성될 수 있다. 그리고 약 한 제약으로는 주간사업 기준, 승계대기시간, 편승사업 지 정 등으로 구성되며 해 탐색 범위에 영향을 줄 수 있는 사용 자 설정 가능 변수 파라미터 값이다. 승무다이아는 이러한 제약조건들을 만족하는 열차들을 찾아 서로 연결하여 만들 어지는데 이 과정에서 편승사업이 최소가 되기 위해서는 가 능한 모든 운행열차가 짝을 이루어 연결되어야 한다.
3. 승무 다이아의 이웃해 탐색 이론 적용 방안
3.1 승무다이아 생성 모형
제약조건을 만족하는 이웃해 탐색기법을 사용하여 승무 다이아를 생성하는 과정은 <Fig. 3>과 같이 입력 및 분석단 계, 승무다이아 생성단계, 마무리 단계로 구분할 수 있다.
입력 및 분석단계에서는 사용자가 승무다이아 생성 시 고 려해야하는 변수 파라미터 및 제약조건들을 입력하는데, 입 력된 변수 및 제약조건들은 승무다이아 생성의 중요한 구성
Fig. 3. The procedure of generating a diagram using Neighborhood
search
요소가 된다. 그 다음 열차운행정보를 입력 및 분석하여 앞 서 입력된 변수 파라미터 및 제약조건에 따라 운행요일별, 운행노선별, 근무유형별로 재분류한다.
승무다이아 생성단계에서는 운행요일별·노선별·근무 유형별로 재분류된 열차운행정보 데이터를 서로 조합하여 승무다이아 조합가능 목록을 작성한다. 운행요일-노선-근 무유형과 입력된 제약조건에 아침에 운행하는 열차와 야간 운행열차와 서로 조합하여 야간다이아를 생성하게 되며, 주 간운행열차는 제약조건을 만족하는 열차와 조합하여 주간 다이아 생성가능 목록을 만들게 된다.
마무리 단계에서는 다이아생성 가능해 목록에서 최종 승 무다이아 해를 선택하고 이를 정렬한 후 승무센터별·운행 노선별·근무유형별로 다이아명을 부여하는 것으로 승무다 이아 생성을 완료한다.
3.2 승무다이아 생성 모형의 정보 구성
승무다이아 생성 모형의 자세한 입출력 정보 구성은
<Fig. 4>와 같다.
<Fig. 4>의 입력 및 분석단계에서는 열차운영기관의 승무 다이아 작성과 관련된 규정 및 시간적·공간적 제약조건들 과 변수, 그리고 열차운행정보가 입력되어야 한다. 주요 시 간적 제약조건식은 다음과 같다.
식 (1)에 따라 승무다이아는 최소 8H 이상, 최대 16H 이 하의 구속시간을 갖는 제약조건을 만족하며, 식 (2)는 승무 사업 사이 승계대기시간은 1H 이상, 3H이내로 갖도록 하는 변수가 된다. 열차운행정보는 운행노선, 운행요일, 중련편 성여부에 따라 재분류되며, 이후 승무다이아 생성단계로 넘 어간다.
<Fig. 4>의 승무다이아 생성단계에서는 재분류된 열차운 행정보에 출근시간 산정공식을 적용하여 작업유형을 결정
한다. 출근시간 산정공식은 다음과 같다.
사용자가 입력한 출근시간 변수설정 값에 따라 N요일의 아침·주간 근무가 결정되며, 아침근무의 개수만큼 N-1요 일의 야간근무의 개수가 정해진다. 이후 N요일 아침근무와 전날인 N-1요일의 야간근무를 조합하여 야간다이아를 생 성하며, 주간근무는 일반적인 승무다이아 형태인 [출근-출 무점호-승무사업-정리-휴게-승계대기-준비-승무사업- 정리-퇴근]에 운영기관에서 규정한 시간을 입력하고, 공간 적 제약조건과 시간적 제약조건식을 만족하는 조합을 선별 하여 주간다이아 조합가능 목록을 생성한다. 주간다이아 조 합가능 목록은 <Fig. 4>의 마무리단계로 넘어가 최종 승무 다이아형태로 출력된다.
4. 승무다이아 생성 및 검증
4.1 입력 및 분석 단계
객실장은 검표업무를 수행하고 비상시 기장과 협조하여 열차비상조치를 시행, 유사시 승객의 안전을 책임지지만 객 실 내를 총괄하여 책임지는 중간관리자의 직무를 수행하기 도 한다. 이러한 객실장의 승무다이아를 작성하려면 다이아 작성 시 고려해야하는 제약조건들과 ○○열차운영기관에서 운영하는 열차다이아를 토대로 해당기관에서 실제로 운영 하는 열차운행 데이터, 즉 열차번호대장이 입력되어야한다.
입력된 열차번호대장에는 열차번호, 출발역, 도착역, 출발 및 도착시간, 운행요일, 중련편성 여부에 관한 정보가 들어 있다.
중련열차는 수송수요에 따라 두 대의 운행열차를 서로 연 결한 열차편성을 말하는데, 이 경우 2명의 객실장이 근무하 게 된다. <Table 1>에는 ○○열차운영기관에서 운영하는 열 차의 열차번호대장 일부가 제시되어있으며, 339운행열차의 금·토·일요일에 중련열차 편성임을 확인할 수 있다.
Table 1. Train data of each timetable
Train No. Suseo Pusan Mon Tue Wed Thu Fri Sat Sun
301 05:30 08:05 ○ ○ ○ ○ ○ ○ ○
303 06:00 08:25 ○ ○ ○ ○ ○ ○ ○
305 06:30 09:04 ○ ○ ○ ○ ○ ○ ○
... ... ... ... ... ... ... ... ... ...
339 14:00 16:15 ○ ○ ○ ○ ◎ ◎ ◎
... ... ... ... ... ... ... ... ... ...
Fig. 4. Input and output data of Neighborhood search
입력된 열차번호대장 데이터를 차례대로 읽어 노선과 운 영요일별로 다시 재 정렬한다. 또한 중련편성인 열차에 한 해 ＇기호를 붙이고 하나의 운행사업으로 취급하여 하나의 승무사업으로 간주한다<Fig. 5>.
4.2 승무다이아 생성 단계
요일별 운행열차 정렬이 끝난 목록에서 운행열차의 출발 시간 데이터를 차례대로 분석한다. 열차의 출발시간 데이터 가 승무원의 출근시간을 결정하는 역할을 하는데, 승무원의 출근시간은 식 (3)과 같이 최초승무사업 – 1H 으로 하고 있 으며 수서역에서 부산역으로 가는 경부선 하행 313열차는 수서역에서 08:00에 출발한다. 313열차를 배정받은 승무원 의 경우, 열차 출발 1시간 전인 07:00에 출근을 하여 출무점 호를 받고 열차차량 탑승준비를 해야 한다. 하지만 출근시 간이 과도하게 이른 경우 승무원에게 부담이 될 수 있다. 경 부선 하행 301열차는 수서역에서 05:30에 출발한다. 따라서 승무원의 근무환경 개선을 위해 출근시간이 이른 열차운행 에 대해서는 야간운행열차를 탐색하여 연결시킨 후 아침운 행을 끝으로 퇴근하여 휴식토록 한다.
요일별 운행열차 목록에서 출근시간 = 최초승무사업 출 발시간 – 1H 시간이 06:30미만인 운행을 아침근무로 분류
하면 일주일 전체 운행열차의 아침배정근무가 결정 된다.
출근시간의 제약은 철도운영회사와 근로자들 간 노사합의 를 통해 정할 수 있으며, 결정되는 시간에 따라 야간다이아 의 개수가 증감하게 된다. <Fig. 6>는 위 절차에 따라 열차 번호대장에서 열차운행데이터를 읽어 노선별·운영요일별 재 정렬하여 아침운행과 야간운행 열차를 별도로 표시한 그 림이다. 예를 들어 월요일(N) 운행열차 목록에서 5개의 아 침근무가 배정이 되면, 이를 전날인 일요일(N-1)의 야간근 무와 서로 연결시켜 야간다이아로 만든다. 일요일 야간 근 무는 마지막 운행열차부터 차례대로 5개의 열차가 야간근무 로 정해지며, 일반편성 열차를 최우선으로 연결한다. 또한 중련편성으로 인해 야간운행열차의 목록개수가 다음날 아 침근무열차 목록개수보다 많을 경우 조합이 불가능한 야간 운행열차를 아침근무에 편승하여 사업을 종료하도록 한다.
주간사업은 제약조건을 만족하는 운행열차들을 조합하여 생성되며, 조합 시 고려해야하는 주된 제약조건은 시간적 제약과 공간적 제약이다. 승무사업 종료 후 정리시간 20분, 휴게시간 1H, 승계대기, 준비시간 30분의 시간적 제약을 만 족하는 운행열차가 다음 승무사업으로 조합될 수 있다. 또 한 승무원이 승무를 시작한 역에서 승무사업을 종료할 수 있도록 공간적 제약을 만족시켜야 한다. 승무원의 최초승무 사업으로 수서에서 부산으로 가는 경부선 하행열차를 배정 받았을 경우, 다음 사업에는 시간적 제약을 만족하면서 부 산에서 수서로 가는 경부선 상행열차가 배치되어야한다. 이 러한 시간적, 공간적 제약에 따라 승무다이아로 조합될 수 있는 열차의 탐색범위가 줄어들게 된다.
수서-부산 경부선 하행노선을 승무사업 시작으로 하면 공간적 제약에 따라 다음 승무사업은 부산-수서 경부선 상 행노선 승무사업이 선택되어야 하며, 그 다음 시간적 제약
Fig. 5. Reclassified train data
Fig. 6. Reclassified week train data
에 따라 조합 가능한 해 즉, 운행열차가 표시되어 나타난다.
수서-부산 운행의 월요일 다이아의 경우 총 40개의 운행열 차가 있으며, 아침운행 열차 5개를 제외, 화요일 아침근무 와 연결되는 야간근무 5개를 제외하면 30개의 주간사업 가 능운행이 남게 된다.
<Fig. 7>는 경부선 하행 노선 승무다이아 조합가능 해를 탐색하는 과정을 나타낸 것이다. 첫 번째 운행열차가 지정 이 되면 근무규정과 시간적 제약을 만족하는 다음번 운행열 차 목록이 나타난다. 시간적 제약을 만족하지 않는 경우 붉 은색으로 음영처리가 되어 쉽게 구분 가능할 수 있으며. 이 러한 과정은 주간 운행열차 목록에 대하여 모두 수행된다.
조합가능 해 탐색 도중 일정 시간 이후 열차부터는 조합 가능한 운행열차가 나타나지 않는다. 요일별로 특정 열차 이후 조합 가능한 목록이 더 이상 생성되지 않는데, 이러한 경우에는 승무 시작 사업이 아닌 종료사업으로 배치한다.
수서-부산 운행열차를 승무사업시작으로 하는 다이아 후보
를 생성완료 하고 반대의 노선인 부산-수서 운행열차를 승 무사업시작으로 하는 다이아 후보 목록을 생성한다.
<Fig. 8>의 그림은 월요일 경부선의 수서-부산-수서 운 행, 하단그림은 부산-수서-부산 운행 다이아 조합가능 목 록이며, <Fig. 8>의 좌측 1운행열차에 대하여 조합 가능한 2 운행 열차 목록을 우측에서 확인할 수 있다.
4.3 마무리 단계
조합가능 목록이 생성된 후 마무리 단계에서 열차의 중복 없이 해를 선택한다. 열차조합과정에 운행열차의 개수 짝이 맞지 않거나 해 탐색 범위 내에 적절한 조합가능 열차가 없 는 경우에 한하여 편승사업으로 지정한다.
<Fig. 9>과 같이 다이아 조합가능 목록에서 순차적으로 열차를 조합해 나가면 월요일 승무다이아를 생성할 수 있 다. 이와 같은 동일한 방법을 반복하여 일요일까지 승무다 이아를 생성하고 사업시간 순으로 정렬하여 다이아 명 부여
Fig. 7. Daytime crew diagram generation of Gyeongbu line
Fig. 8. Crew diagram candidate group of gyeongbu line
과정을 끝으로 경부선의 모든 승무다이아 생성은 종료된다.
완성된 승무다이아는 승무센터별로 <Fig. 10>와 같은 행태 로 생성되며, 기존 승무다이아와 같이 다이아 명, 조합된 열 차, 운영요일, 주·야간근무, 편승근무 여부, 출·퇴근시간, 사업시간, 총 승무시간, 승계대기시간 등을 확인할 수 있다.
4.4 승무다이아 최적화 검증
상세 승무다이아 개수와 주요시간의 평균값 및 승무율, 구속비율은 <Table 2>에 정리되어 있으며 실제 운영하는 열 차시간표를 대상으로 기존에 작성된 승무다이아와 연구에 서 제시한 방법론을 적용하여 생성된 다이아비교분석 결과 는 다음과 같다.
Table 2. Generated crew diagram results
Suseo
Number of crew diagrams Day 48 Night 18 Avg. Waiting time Day 02:17 Night 04:10 Avg. Restraint time Day 10:31 Night 12:25 Avg. actual working hours Day 09:31 Night 11:25 Trip percentage (%) Day 50.39 Night 42.34 Restraint percentage (%) Day 110.53 Night 108.79
Pusan
Number of crew diagrams Day 39 Night 13 Avg. Waiting time Day 02:17 Night 04:10 Avg. Restraint time Day 10:42 Night 12:38 Avg. actual working hours Day 09:40 Night 11:38 Trip percentage (%) Day 51.68 Night 42.18 Restraint percentage (%) Day 110.67 Night 108.60
Gwangju
Number of crew diagrams Day 8 Night 5 Avg. Waiting time Day 02:17 Night 04:10 Avg. Restraint time Day 09:58 Night 11:25 Avg. actual working hours Day 08:58 Night 10:25 Trip percentage (%) Day 47.25 Night 36.76 Restraint percentage (%) Day 111.29 Night 109.66
Fig. 9. Monday crew diagram of Gyeongbu line
Fig. 10. Generated solution for crew diagram
기존 승무다이아 조합의 개수는 95개이며 야간 29개, 주간 66개로 구성되어있고, 각 승무센터별 다이아 개수는 수서승 무센터 52개, 부산승무센터 30개, 광주승무센터 13개로 분배 되었다. 실험결과 생성된 승무다이아 개수는 야간 35개, 주 간 95개 총 130개이다. 수서승무센터는 66개의 다이아, 부산 승무센터는 52개의 다이아, 광주승무센터는 13개의 다이아가 분배되어 광주승무센터를 제외하고 기존 승무다이아 대비 다 이아 조합방법의 수가 증가했음을 알 수 있다<Table 3>.
Table 3. Comparison of the number of crew diagram combinations
Center Existing Crew Dia Generated Crew Dia Note
Suseo 52 66 Increase
Pusan 30 52 Increase
Gwangju 13 13 Fixed
Day·night D 66 N 29 D 95 N 35 Increase
기존 승무다이아와 제약조건 만족 이웃해 탐색을 통해 생 성된 승무다이아 간의 사업시간 비교결과는 <Table 4>와 같 다. 수서승무센터 다이아의 주간·야간 평균 사업(근무)시 간은 증가했으나 표준편차는 45분에서 28분으로 17분 감소 하였다. 부산승무센터의 경우 주간·야간 평균 사업시간이 증가하였지만 표준편차는 35분으로 변화가 없었다. 광주승 무센터의 주·야간 평균 사업시간은 소폭 감소하였고, 표준 편차역시 75분에서 57분으로 감소하였다.
Table 4. Comparison of business hours between two crew diagram Center Existing Crew Dia Generated Crew Dia Note
Suseo
Day duty 09:29 Day duty 09:31 Increase Night duty 10:59 Night duty 11:25 Increase
Standard
deviation 45 Min Standard
deviation 28 Min Decrease
Pusan
Day duty 09:31 Day duty 09:40 Increase Night duty 11:22 Night duty 11:48 Increase
Standard
deviation 35 Min Standard
deviation 35 Min Fixed
Gwangju
Day duty 09:13 Day duty 08:58 Increase Night duty 10:30 Night duty 10:25 Decrease
Standard
deviation 75 Min Standard
deviation 57 Min Decrease
승계대기시간 비교결과는 <Table 5>와 같다. 우선 수서 승무센터의 승계대기시간은 기존 승무다이아에 대조하였을 때 주간은 1분 감소, 야간은 23분 증가했으나 편차는 9분가 량 줄어들었다. 그리고 부산승무센터의 승계대기시간은 주 간 13분, 야간 9분가량 증가하였고, 편차는 2분 증가하였다.
마지막으로 광주승무센터의 승계대기시간의 경우 주간은 26분 감소, 야간은 26분 증가, 편차는 6분 감소하였다.
Table 5. Comparison of waiting time
Center Existing Crew Dia Generated Crew Dia Note
Suseo
Day duty 02:19 Day duty 02:18 Decrease Night duty 04:06 Night duty 04:29 Increase
Standard
deviation 44min Standard
deviation 35min Decrease
Pusan
Day duty 02:10 Day duty 02:23 Increase Night duty 04:15 Night duty 04:24 Increase
Standard
deviation 36min Standard
deviation 38min Increase
Gwangju
Day duty 02:56 Day duty 02:22 Decrease Night duty 04:09 Night duty 04:37 Increase
Standard
deviation 37min Standard
deviation 31min Decrease
일주일 총 근무의 개수는 전체 481개에서 474개로, 주간 근무(사업) 개수는 347개에서 345로 2개 감소하였고, 야간 근무 개수는 134개에서 129개로 5개 감소하였다. 특히 편승 근무의 개수가 전체 52개에서 39개로 13개 줄어들었으며 이 는 기존 편승근무대비 25% 가량 감소한 수치이다<Table 6>.
Table 6. Comparison of the total number of the week crew diagrams Existing Crew Dia Generated Crew Dia
Total Day Night Total Day Night Note
Suseo 251 181 70 238 174 64 Decrease
Pusan 157 116 41 158 115 43 Increase
Gwangju 73 50 23 78 56 22 Increase
Total 481 347 134 474 345 129 Decrease
Take riding 52 39 Decrease
5. 결론
본 연구에서는 제약조건을 만족하는 이웃해 탐색기법을 실제 운영하고 있는 열차운행계획에 적용하여 ○○열차 운 영기관 객실장의 승무다이아를 작성하였다. 제시한 기법으 로 작성한 승무다이아와 비교해보면, 평균 근무시간은 늘어 났지만 승무다이아 조합의 방법이 더욱 다양해지고 일주일 주·야간 근무의 개수 감소와 승계대기시간 및 평균 근무시 간의 편차는 줄어들었음을 알 수 있다. 뿐만 아니라 일주일 간 52개 발생하는 편승근무가 39개로 줄어들어 철도운영기 관의 인력운용효율 또한 높일 수 있었다.
본 연구에서 제시한 방법에서는 철도운영기관마다 상이 한 승무일정계획 작성방법 및 제약조건에 따라 사용자가 결 정하는 변수 값을 다르게 입력할 수 있으며, 그 결과 조합방 법 및 해 탐색 범위가 변경되기 때문에 사용자의 의도에 맞 는 다양한 결과물을 얻을 수 있다. 이와 같이 제약조건을 만 족하는 만족하는 이웃해 탐색방법은 승무다이아 작성의 문
제 해결을 위한 많은 방법들 중 하나의 방법이 될 수 있다.
향후 입·출고 열차의 제약조건을 추가하여 조합생성가능 해의 범위를 탐색한다면, 본 연구에서 다루었던 객실장의 승 무다이아 뿐 아니라 열차를 운행하는 기장의 승무다이아역 시 쉽게 생성할 수 있을 것으로 판단된다. 또한 생성된 승무 다이아는 향후 승무교번배치 단계에서 활용 할 수 있다.
감사의 글
본 연구는 2018년 국토교통과학기술진흥원 연구비 지원 사업(19RTRP-C148789-02)으로 수행되었음.
References
Ernst, A., Jiang, H., Krishnamoorthy, M., Nott, H., and Sier, D. (2001). “Rail Crew Scheduling and Rostering Optimization Algorithms.” Computer-Aided Scheduling of Public Transport : Part of the Lecture Note in Economics and Mathematical Systems, 505, pp. 53-71.
Heo, N.I. (2000). “A Crew Scheduling Using Set Partitioning.” Dep, of Management Information Systems, Graduate School, Dong-A Univ, Pusan, Korea.
Hwang, J.H., and Ryu, K.R. (2004). “A Hybrid of Neighborhood Search and Integer Programming for Crew Schedule Optimization.” Journal of Korea Information Science Society : Software and Applications, KISS, 31(6), pp. 829-839.
Hwang, J,H., Park, C.H., Lee, Y.H., and Ryu, K.R.
(2002). “Crew Schedule Optimization by Integrating Integer Programming and Heuristic Search.” Journal of Korea Information Science Society : Computing Practices and Letters, KISS, 8(2), pp. 195-205.
Hwang, J.H. (2014). “An Integer Programming-based Local Search for the Set Covering Problem.” Journal
of the Korea Society of Computer and Information, KSCI, 19(10), pp. 13-21.
Khmeleva, E., Hopgood, A.A. Tipi, L., and Shahidan, M.
(2014). “Rail-Freight Crew Scheduling with a Genetic Algorithm.” Research and Development in Intelligent Systems 31, pp. 211-223.
Khosavi, A., Tamannaei, M., and Reisi-Nafchi, M.
(2016). “A Comprehensive Approach for Railway Crew Scheduling Problem (Case Study : Iranian Railway Network.)” International Journal of Transportation Engineering, IJTE, 4(3), pp. 197-210.
Kim, T.S., Park, K.Y., Park, T.J., and Ryu, K.R. (2011).
“Candidate Dia Creation Methods for Subway Crew Scheduling.” Journal of Korea Information Science Society, KISS, 38(1C), pp. 299-302.
Lee, D.H., Yang, T.Y., and Kim, Y.H. (2006). “A Study on Korean Railroad Crew Rostering Problem.” Journal of the Korean Society for Railway, 9(2), pp. 206-211.
Park, C.H. (2000). “Heuristic Repair Methods for Improving Subway Crew Scheduling.” Dep. of Computer Engineering, Graduate School, Pusan National Univ, Pusan, Korea.
Tormos, P., Lova, A., Barber, F., Ingolotti, L., Abril, M., and Salido, M.A. (2008). “A Genetic Algorithm for Railway Scheduling Problems.” Metaheuristics for Scheduling in Industrial and Manufacturing Applications : Part of the Studies in Computational Intelligence, 128, pp. 255-276.
Yang, J.Y., and Jo, G.S. (1998). “Knowledge-Based vs.
Constraints-Based Scheduling : A Case study of Gate Allocation Problem.” Journal of expert systems, 4(2), pp. 45-59.
요약 :
철도운영기관은 수송수요예측과 열차차량의 수송능력을 토대로 수송계획을 세우고 이에 따른 열차운행계획을 수립한다. 열차 운행계획을 통해 열차 운행간격이 조정되어 열차운행시간표(열차다이아)가 작성되고, 열차운행에 사용되는 열차의 차량운영계획이 수립된다. 열차운영기관에서는 열차 운영관리의 효율성을 높이기 위해 다이아에 편성되어진 열차들의 승무인원을 판단하고 배치하 는 승무일정계획을 수립해야 한다. 본 연구에서는 승무일정계획 문제인 승무다이아 작성단계에 제약조건을 만족하는 이웃해 탐색 기법을 적용하여 승무 계획의 효율적 관리가 가능하도록 하는 방법론을 제시한다. 연구에서 제시한 방법론에 의해 생성된 승무 다 이아는 실제 운영하는 열차시간표를 대상으로 기존 승무다이아와 결과 값을 비교하여 제시된 방법론의 효율성을 검증하였다.
키워드 :
