도시철도의 열차 운행계획 문제는 여러 가지 제약조건을 만족시키면서 최적화까지 하여야 하는 복잡한 문제다. 대상 문제에서는 특히 차량기지가 복수로 존재함으로 인해 하루 중 몇 대의 열차가 어느 기지에서 출고하여 어디로 입고해야 하는지가 지정되어 있어 제약이 복잡하다. 본 논문에서는 이러한 입출고 제약을 포함한 여러 제약을 만족시키면서 동시에 1일 운행 비용을 최소화하는 계획의 수립을 위해 유전 알고리즘을 이용하여 2 단계에 걸쳐 탐색하는 방안을 제안한다. 첫 단계에서는 가장 까다로운 제약인 입출고 제약의 만족을 위해 다른 제약을 의도적으로 느슨하게 한 상태에서 제약만족 최적화 탐색을 하고, 후처리 성격의 두 번째 단계에서는 앞 단계에서 위배되었던 제약을 만족시키기 위한 수정 작업과 더불어 최적화 탐색을 다시 수행함으로써 모든 제약을 만족시키면서 최적화된 계획을 도출한다.
The problem of train scheduling for urban subway lines is a constrained optimization problem of a high complexity with multiple constraints. Our target problem is especially complicated because there are multiple train depots and the numbers of trains leaving out of a certain depot and coming into another is predetermined. This paper proposes a two-stage search method based on a genetic algorithm for deriving an optimal schedule with minimum daily operational cost satisfying the depot in-out constraint and the others. The first stage focuses on satisfying the most intricate in-out constraint by performing a constrained optimization search with some other constraints deliberately relaxed. The second stage for post-processing conducts some repair operations to satisfy the formerly relaxed constraints followed by another search to derive an optimized schedule with all the constraints satisfied.
