지하철 일간승무계획문제의 정수계획해법 = An Integer Programming Approach to the Subway Daily Crew Scheduling Problem

다국어 초록 (Multilingual Abstract)

This paper considers subway crew scheduling problem. Crew scheduling is concerned with finding a minimum number of assignments of crew to a given timetable satisfying various restrictions. Traditionally, crew scheduling problem has been formulated as a set covering or set partitioning problem possessing exponentially many variables, but even the LP relaxation of the problem is hard to solve due to the exponential number of variables. In this paper, we propose the solution is not guaranteed. We develop an algorithm that solves the column-generation problem in polynomial time. In addition, the integrality of the solution is accomplished by variable-fixing technique. Computational result for a real instance is reported.