This thesis presents railroad crew rostering problem, which is to determine the railroad plan allocation. This problem is constructed that determine the sequence of duties that railroad crews have to perform. We analyze characteristic of this problem and railroad industry. It’s hard to consider many constraint conditions. We propose Integer Programming model and easy methodology to be considered all given operation rules. This problem is known to be NP-hard. We develop a genetic algorithm, which is proved to be powerful in solving optimization problems. We tested the model and algorithm and showed the effectiveness through comparison of previous research.
본 논문은 철도 승무원들이 수행해야 하는 작업의 순서를 결정하는 이른바 철도 사업 배치 문제에 대해 다루고 있다. 철도 사업 배치 계획은 승무원 사업표가 작성되어 각각의 철도 사업이 모두 정해진 후 이를 전제로 여러 가지 승무원의 운영규칙과 최적화된 근무 조건을 만족하기 위해 이루어진다. 철도 사업 배치 계획은 각각의 철도 승무원 교번표에 반영되어 철도 승무원에게 전달되며, 철도의 공공적인 특성상 승무원이 균등한 사업시간을 갖도록 계획된다. 철도 사업 배치 연구는 우리나라의 독특한 철도 사업 및 운영 규칙을 반영하여야 하며 복잡한 제약 조건을 모두 고려해야 하는 어려움이 있다. 기존의 철도 사업 배치 수리적 모형화 연구는 모든 운영 규칙을 반영하지 못하거나 반영하기 어려워 실제적으로 현장에서 철도 사업 배치 계획을 마련하거나 새로운 현실 규칙을 반영하기에 적합하지 않았다. 본 연구에서는 수리적 모형으로서 모든 제약 조건과 규칙을 고려할 수 있는 정수계획법 모형과 방법론을 제시하였다. 또한 NP - hard 문제로 알려진 이 문제에 적합한 유전 알고리즘을 제안하여 정수계획법 문제와의 효율성을 비교하여 알고리즘의 우수성을 보이고 과거 연구와의 비교를 통해 더 좋은 효율성을 보였다.
