[논문]철도 승무교번 배치를 위한 유전알고리즘 적용방안

박상미; 김현승; 강인석

doi:10.5762/kais.2019.20.9.133

철도 승무교번 배치를 위한 유전알고리즘 적용방안
Application of Genetic Algorithm for Railway Crew Rostering 원문보기

한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society, v.20 no.9, 2019년, pp.133 - 141

박상미 (경상대학교 토목공학과) , 김현승 ((주)서영엔지니어링) , 강인석 (경상대학교 건축도시토목공학부)

초록
AI-Helper

철도 승무원 교번표 작성은 보통 한 달을 주기로 승무원에게 기 작성된 승무다이아를 근무 기준에 맞게 배치하는 작업으로 균등한 사업 시간을 갖도록 작성해야 한다. 본 연구는 기존 철도 운영시에 승무 교번작성과 관련된 문제점을 파악하고, 승무 운영의 합리적 계획 시에 적용할 수 있는 최적화된 승무 교번표 작성 방안을 제시하고 있다. 이를 위해 실제 철도운영기관의 근무 기준을 파악하였으며, 실제 근무패턴을 고려한 교번표 작성 및 유전알고리즘을 통한 최적화 과정을 통해 균등한 사업 시간을 갖는 교번표를 도출하고자 하였다. 교번표 최적화 과정은 입력데이터 분석, 근무패턴생성, 해생성, 최적화 단계로 구성하였으며, 최적화 단계에서는 유전알고리즘을 적용하여 교번표를 도출하는 방안을 제시하였다. 또한 연구에서 제시한 과정을 통해 도출한 교번표와 수작업으로 작성된 교번표의 차이를 비교하여 연구에서 제시한 방안을 검증하고 있다. 연구에서 제시한 승무교번 배치 방안은 사업시간의 표준편차 최소화를 목적함수로 하였으므로 교번 작성시 사업시간 편차를 감소시키는 방법론으로 활용성이 기대된다.

Abstract ▼ AI-Helper

Crew rostering in railway operations is usually done by arranging a crew diagram in accordance with working standards every month. This study was done to identify the problems related to the creation of crew rosters in railway operations and to suggest an optimum crew rostering method that can be applied in railway operations planning. To do this, the work standards of a railway company were identified, and a genetic algorithm was used to develop an optimal roster with equal working time while considering actual working patterns. The optimization process is composed of analysis of the input data, creation of work patterns, creation of a solution, and optimization steps. To verify the method, the roster derived from the proposed process was compared with a manually created roster. The results of the study could be used to reduce the deviation of business hours when generating a roster because the standard deviation of working time is the objective function.

주제어

표/그림 (11)

그림 Fig. 1. Process model of rail crew rostering
표 Table 1. Process of rostering optimization in railway
그림 Fig. 2. Creation of work patterns
그림 Fig. 3. Creation of initial value
그림 Fig. 4. Flowchart of genetic algorithm
그림 Fig. 5. Roulette wheel for selection operation
그림 Fig. 6. Crossover operation by one-point
표 Table 2. Result of selection operation
표 Table 3. Crossover results with a probability of 0.8
그림 Fig. 7. Manually written roster
표 Table 4. Crossover results with a probability of 0.2

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

유전알고리즘은 해의 탐색성능이 우수하여 다양한 분야에 적용가능하며 특히 변수와 제약이 많은 대형 수리문제를 푸는데 적합한 기법이다.[8] 따라서 다양한 제약조건이 존재하는 승무교번표 최적화에 적합하다고 판단되어 유전알고리즘을 적용하고자 한다. 주요 분석 과정은 Table 1과 같다.
또한 교번표 작성 시 근무 패턴을 적용하여 승무원의 규칙적인 근무환경 조성이 가능하다. 따라서 본 연구에서는 실제 국내 철도운영기관 근무기준에 포함되어 있는 6일주기의 근무패턴을 적용하여 교번표를 작성하고 이에 유전알고리즘을 적용하여 최적화된 교번표를 도출하고자 한다.
따라서 본 연구에서는 철도승무계획 단계 중 승무교번 작성 단계에서 다양한 제약조건을 만족하고 승무원 근무시간의 평준화를 고려한 교번표 작성 방법론을 제시하고 있다. 이를 위해 기존 교번표 작성 관련 문헌을 조사하여 문제점을 도출하고, 실제 철도운영기관의 근무기준 및 제약조건 요소를 분석한다.
유전알고리즘을 적용한 최적화의 목적은 근무시간의 평준화, 운전시간의 평준화 등이 될 수 있다. 본 논문에서는 승무원의 근로시간의 평준화를 위해 근무시간의 표준편차의 최소화를 목적함수로 설정하였으며 다음과 같이 나타낼 수 있다.
본 연구에서 제시한 철도 승무교번표 작성방안 및 최적화 과정을 통해 도출한 교번표의 값과 수작업으로 작성하였던 기존 교번표를 비교하고자 한다. 본 연구에서는 2019년도 데이터를 기준으로 교번표를 작성하였으나 수작업으로 작성한 교번표는 2018년도에 작성된 것으로 정확하게 두 교번표를 비교하는 것은 불가능하다.
또한 법적 근로기준의 개정 및 노사 간 협의사항이 추가되거나 변경될 가능성이 있어 모든 조건을 만족하는 알고리즘을 철도운영기관에서 지속적으로 사용하는데 어려움이 있다. 본 연구에서는 실제 철도 운영기관의 근무기준관련 자료를 분석하여 기존 연구에서 고려하지 않은 근무패턴주기를 추가하였으며 근무시간 평준화를 목적으로 유전알고리즘을 활용한 최적해의 도출방안을 제시하였다.
수작업으로 작성된 교번표에서 미할당 다이아가 발생하며 이러한 경우 승무원의 근무시간 표준편차가 커지게 되므로 근무시간을 평준화하는데 적합하지 않다. 본 연구에서는 운행다이아에 맞게 근무패턴을 조정하여 교번표를 작성하여 미할당 다이아가 발생하지 않으므로 기존 수작업으로 작성된 교번표와 비교하여 근무시간의 표준편차를 줄일 수 있을 것으로 사료된다. 본 연구에서 진행한 최적화 과정은 방법론의 검증을 위해 해집단과 세대수 크기를 제한하여 해를 도출하였으므로, 전산화 모듈을 이용하여 해집단의 크기를 크게 하고 많은 세대수를 거쳐 해를 도출해 내는 과정이 추가되면 보다 현실적인 최적해의 도출이 가능할 것이다.
본 연구에서는 철도 승무교번 배치를 위해 기존에 수행된 연구를 조사하고 실제 철도운영기관 근로기준 및 노사협의 사항관련 자료를 분석하여 제약조건을 도출하였다. 또한 기존 연구에서 다루어지지 않은 실제 근무기준에 포함되어 있는 6일주기의 근무패턴을 적용하여 규칙성을 부여하고 있다.
이를 위해 기존 교번표 작성 관련 문헌을 조사하여 문제점을 도출하고, 실제 철도운영기관의 근무기준 및 제약조건 요소를 분석한다. 이를 바탕으로 유전알고리즘 기법을 이용하는 최적화된 승무 교번표의 도출 방안을 제시하며, 근무시간 표준편차의 최소화하는 것을 목적함수로 하여 근무시간 평준화를 고려한다. 또한 연구에서 제시한 과정을 통해 도출한 교번표와 기 작성된 교번표와의 차이를 비교하여 연구에서 제시한 방법론을 검증하고 있다.
제시한 방안에 따라 실제 철도운영기관의 자료를 활용하여 유전알고리즘을 적용하였으며 승무원의 근무시간 평준화를 위해 근무시간 표준편차를 목적함수로 하여 이를 줄이는 것을 목표로 하였다. 유전알고리즘 적용 시 교배확률을 0.
철도 교번표 작성과 관련된 기 논문에서는 다양한 알고리즘을 활용하여 교번표를 작성하고자 하였다. 또한 근무기준 등 다양한 제약조건이 존재하는 교번표 작성의 특징에 맞게 제약조건을 목록화 한 후, 가중치를 두어 최적 해를 도출하는 연구 등이 진행된 바 있다.

제안 방법

교배확률(P_C)을 0.2, 0.8로 나누어 수행하였으며 교배 여부가 판단된 후 교배점은 한 달을 기준으로 1일에서 31일 사이에 난수를 발생시켜 교배위치를 결정하였다. 예를 들어, 난수가 0.
(3)을 이용하여 선택확률을 구할 수 있다. 구한 선택확률을 바탕으로 누적확률을 계산하여 해가 선택될 수 있는 범위를 지정하였다.
적합도에 따라 산출된 선택연산을 통해 해집단 내 k세대 개체를 선택하게 된다. 난수 r을 발생시켜 k세대 해집단 내 해들의 교배유무를 판별하여 교배연산을 진행한 후 다시 해집단의 적합도를 평가한다. 각 세대별 해집단 내 적합도가 가장 높은 개체를 저장하고 해집단의 목적함수가 정지조건에 도달하지 않았을 경우 위의 과정을 반복하고, 도달하였을 경우 저장된 개체 내 가장 좋은 해를 도출하는 것으로 알고리즘을 종료한다.
또한 승무센터별 운영다이아와 승무인원에 맞게 패턴을 변형하여 운행다이아에 적합한 근무 패턴을 생성하였다. 도출된 제약조건과 근무패턴을 만족하는 철도 승무 교번표를 작성한 후 근무시간의 평준화를 목적함수로 한 유전알고리즘을 적용하여 교번표의 최적해 도출방안을 제시한다. 이러한 과정을 OO 철도운영사의 열차 정보를 바탕으로 유전알고리즘을 적용하였으며, 적용 시 조사된 정보를 바탕으로 강한 제약조건에 해당하는 항목만을 한정하여 반영하는 방법론을 도입하고 있다.
또한 근무패턴 생성을 위해 승무다이아 정보를 활용하여 요일별 운행다이아 및 주간·야간다이아를 분류하고 운행다이아 수를 계산한다.
또한 기존 연구에서 다루어지지 않은 실제 근무기준에 포함되어 있는 6일주기의 근무패턴을 적용하여 규칙성을 부여하고 있다. 또한 승무센터별 운영다이아와 승무인원에 맞게 패턴을 변형하여 운행다이아에 적합한 근무 패턴을 생성하였다. 도출된 제약조건과 근무패턴을 만족하는 철도 승무 교번표를 작성한 후 근무시간의 평준화를 목적함수로 한 유전알고리즘을 적용하여 교번표의 최적해 도출방안을 제시한다.
‘주-주-야-비-휴-휴’ 패턴으로 21명의 기장 근무표 작성 시 주간다이아는 250개, 야간다이아는 125개로 구성된다. 또한 요일별 운행다이아가 다르게 계획되어있으므로 요일별 운행 다이아와 승무원에 맞게 근무패턴을 수정하였다. Fig.
4와 같은 순서로 유전알고리즘을 적용하여 최적화 해를 도출한다. 먼저 n개의 개체수를 가지는 초기 해집단을 생성한 후 해집단의 적합도를 평가한다. 적합도에 따라 산출된 선택연산을 통해 해집단 내 k세대 개체를 선택하게 된다.
본 연구에서 승무 교번표 작성 프로세스는 다음 Fig. 1과 같이 입력데이터 분석단계, 근무패턴 생성단계, 해 생성단계, 최적화 단계로 나누었다. 최적단계에서는 유전 알고리즘을 사용하여 최적화된 해를 도출하고자 하였다.
본 연구에서는 앞서 제시한 철도 승무교번표 최적화 방안을 OO 철도운영사에서 제공한 OO 승무센터의 기장 근무표를 사용하여 분석한다.
본 연구에서는 초기해의 해집단의 개체수(n)를 10으로 설정하였으며 앞서 생성된 초기해로 집단을 구성하였다. 초기 해집단이 구성된 후에는 해 집단별 적합도를 평가한다.
해집단의 수만큼 0과 1사이의 난수를 발생시켜 난수가 포함되는 범위의 해집단이 선택된다. 선택된 해집단을 바탕으로 교배연산을 실시하였다. 교배연산은 순차적으로 2개의 해집단을 선택하여 해집단의 교배 수행여부를 난수를 발생하여 판단하였다.
제시한 방안에 따라 실제 철도운영기관의 자료를 활용하여 유전알고리즘을 적용하였으며 승무원의 근무시간 평준화를 위해 근무시간 표준편차를 목적함수로 하여 이를 줄이는 것을 목표로 하였다. 유전알고리즘 적용 시 교배확률을 0.2와 0.8로 나누어 교배연산을 진행하였다. 연구 결과 초기 해집단과 비교하여 승무원의 근무시간 표준편차가 최소 20분에서 최대 31분으로 줄어든 결과를 확인할 수 있었다.
따라서 본 연구에서는 철도승무계획 단계 중 승무교번 작성 단계에서 다양한 제약조건을 만족하고 승무원 근무시간의 평준화를 고려한 교번표 작성 방법론을 제시하고 있다. 이를 위해 기존 교번표 작성 관련 문헌을 조사하여 문제점을 도출하고, 실제 철도운영기관의 근무기준 및 제약조건 요소를 분석한다. 이를 바탕으로 유전알고리즘 기법을 이용하는 최적화된 승무 교번표의 도출 방안을 제시하며, 근무시간 표준편차의 최소화하는 것을 목적함수로 하여 근무시간 평준화를 고려한다.
1과 같이 입력데이터에는 승무다이아, 출/퇴근역, 출/퇴근시간, 근무시간, 승무시간, 승무원 정보, 열차번호 등의 자료가 입력된다. 입력된 데이터를 활용하여 첫 번째로 승무센터 (승무사업소)별로 교번을 작성할 수 있도록 출퇴근역 정보를 활용하여 센터 별 다이아를 분류한다. 또한 근무패턴 생성을 위해 승무다이아 정보를 활용하여 요일별 운행다이아 및 주간·야간다이아를 분류하고 운행다이아 수를 계산한다.
적합도 분석을 완료한 후에는 선택연산을 수행한다. 본 연구에서는 룰렛 휠 방식을 사용하였다.
1의 ‘최적화단계’ 와 같은 순서의 과정이 요구된다. 첫 번째로 n개의 개체수를 가지는 해집단을 생성한 뒤 해집단 별 적합도를 분석한다. Fig.

데이터처리

본 연구에서는 적합도 함수를 목적함수에 사용된 교번표 내 승무원 근무시간의 표준편차 값을 활용하였으며 다음 Eq. (2)와 같이 정의하였다.

이론/모형

적합도 분석을 완료한 후에는 선택연산을 수행한다. 본 연구에서는 룰렛 휠 방식을 사용하였다. 모든 해의 적합도의 합한 값만큼의 크기를 가진 룰렛 휠 내 각 해의 적합도 만큼 룰렛 휠 상의 범위를 가지게 된다.
연구에서는 Fig. 4와 같은 순서로 유전알고리즘을 적용하여 최적화 해를 도출한다. 먼저 n개의 개체수를 가지는 초기 해집단을 생성한 후 해집단의 적합도를 평가한다.

성능/효과

2보다 높은 적합도 값을 도출해 낼 수 있었다. 교배확률 0.2는 세대를 거칠수록 비교적 목적함수 값이 줄어드는 동시에 각 세대별 적합도도 높아지는 모습을 확인할 수 있었다.
8로 나누어 교배연산을 진행하였다. 연구 결과 초기 해집단과 비교하여 승무원의 근무시간 표준편차가 최소 20분에서 최대 31분으로 줄어든 결과를 확인할 수 있었다.
본 연구에서는 2019년도 데이터를 기준으로 교번표를 작성하였으나 수작업으로 작성한 교번표는 2018년도에 작성된 것으로 정확하게 두 교번표를 비교하는 것은 불가능하다. 이러한 점을 감안하여 수작업으로 진행된 교번표와 본 연구에서 도출한 교번표를 비교해 보았을 때, 수작업으로 작성한 근무표는 본 연구에서 도출한 교번표와는 달리 Fig. 7과 같이 미할당 다이아가 발생한 것을 확인할 수 있다. 이는 근무패턴을 일일이 맞추는 것이 어려운 작업이며 많은 시간이 소요되기 때문이다.
기존 수작업 교번표에서 활용된 승무다이아에서 미할당 다이아가 발생하며, 본 연구에서 활용된 승무다이아가 동일하지 않으므로 근무시간의 표준편차의 정확한 비교는 어렵다. 하지만 5세대에 걸쳐 진행된 최적화 과정을 통해 초기해와 비교하여 근무시간의 표준편차를 최대 31분으로 줄인 결과를 도출하였다. 본 연구에서 제시한 과정을 통해 짧은 시간 내 다양한 해를 도출할 수 있어 수작업으로 교번표를 작성할 경우 많은 시간이 요구되는 단점을 해결할 수 있을 것으로 사료된다.

후속연구

하지만 5세대에 걸쳐 진행된 최적화 과정을 통해 초기해와 비교하여 근무시간의 표준편차를 최대 31분으로 줄인 결과를 도출하였다. 본 연구에서 제시한 과정을 통해 짧은 시간 내 다양한 해를 도출할 수 있어 수작업으로 교번표를 작성할 경우 많은 시간이 요구되는 단점을 해결할 수 있을 것으로 사료된다. 또한 미할당 다이아가 발생하지 않는다는 장점이 있다.
본 연구에서는 운행다이아에 맞게 근무패턴을 조정하여 교번표를 작성하여 미할당 다이아가 발생하지 않으므로 기존 수작업으로 작성된 교번표와 비교하여 근무시간의 표준편차를 줄일 수 있을 것으로 사료된다. 본 연구에서 진행한 최적화 과정은 방법론의 검증을 위해 해집단과 세대수 크기를 제한하여 해를 도출하였으므로, 전산화 모듈을 이용하여 해집단의 크기를 크게 하고 많은 세대수를 거쳐 해를 도출해 내는 과정이 추가되면 보다 현실적인 최적해의 도출이 가능할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	승무교번 배치에서 유전알고리즘을 어떻게 사용하고 있는가?	또한 승무센터별 운영다이아와 승무인원에 맞게 패턴을 변형하여 운행다이아에 적합한 근무 패턴을 생성하였다. 도출된 제약조건과 근무패턴을 만족하는 철도 승무 교번표를 작성한 후 근무시간의 평준화를 목적함수로 한 유전알고리즘을 적용하여 교번표의 최적해 도출방안을 제시한다. 이러한 과정을 OO 철도운영사의 열차 정보를 바탕으로 유전알고리즘을 적용하였으며, 적용 시 조사된 정보를 바탕으로 강한 제약조건에 해당하는 항목만을 한정하여 반영하는 방법론을 도입하고 있다.
	현재 승무 교번표 작성의 문제점은 무엇인가?	이와 같이 철도운영에서 승무 교번표의 작성은 매우 다양한 변수요인과 승무원간 평준화된 근로조건을 고려하여 작성되어야 하나, 현재 철도운영기관의 승무 교번표 작성은 관련 경험을 갖고 있는 전문가의 경험적 지식에 의해 수작업으로 작성되고 있는 경우가 대부분이다. 수작업으로 제약조건 및 사업시간 평준화 조건을 만족하는 철도 교번표를 작성 하는 것은 많은 시간이 소요되며 작성된 교번표가 최적화된 결과인지 판별할 수 없다.
	유전알고리즘이란 무엇인가?	최적단계에서는 유전 알고리즘을 사용하여 최적화된 해를 도출하고자 하였다. 유전알고리즘은 해의 탐색성능이 우수하여 다양한 분야에 적용가능하며 특히 변수와 제약이 많은 대형 수리문제를 푸는데 적합한 기법이다.[8] 따라서 다양한 제약조건이 존재하는 승무교번표 최적화에 적합하다고 판단되어 유전알고리즘을 적용하고자 한다.

참고문헌 (9)

N. I. Heo, "A Crew Scheduling Using Set Partitioning", Master's thesis, Donga University, 2001
J. P. Kim, D. H. Kim, T.-O. Ha, "A Study on the Duty Hour Structure for Railway Crews", Journal of the Korean Society for Railway, Vol.7, No.4, pp. 350-355, 2004
Y. H. Kim, J. P. Kim, "A study on the crew roster scheduling", Proceedings of the Korean Society for Railway Conference, pp.86-92, Nov. 2000
M. M. Kang, "A Study on Cabin Crews' satisfaction with their Schedules" Master's thesis, Korea Aerospace University, 2013
J. W. Jeong, "Cabin Crew Pairing Model for Schedule Satisfaction Fairness", Master's thesis, Korea Aerospace University, 2012
D. H. Lee, T. Y. Yang, Y. H. Kim, "A Study on Korean Railroad Crew Rostering Problem", Journal of the Korean Society for Railway, Vol.9, No.2, pp.206-211, 2006
Z. Tian, H. Niu, "Modeling and Algorithms of the Crew Rostering Problem with Given Cycle on High-Speed Railway Lines", Mathematical Problems in Engineering, Vol.2012, Article ID 214607, pp.1-15, 2012. DOI: https://dx.doi.org/10.1155/2012/214607

상세보기
A. Ernst., H. Jiang., M. Krishnamoorthy., H. Nott., D. Sier., "Rail Crew Scheduling and Rostering Optimization Algorithms", Computer-Aided Scheduling of Public Transport, pp.53,71, 2001 DOI: https://doi.org/10.1007/978-3-642-56423-9_4

상세보기
No Woo Hyeob., "A study of workload balancing for nurse schedule using genetic algorithm : based on military hospital", Master's thesis, Yonsei University, 2005

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증