유전자 알고리즘을 활용한 철도 선로배분 모델링 연구 = Railway capacity allocation modeling using genetic algorithm|RISS 상세보기

다국어 초록 (Multilingual Abstract)

The Korean Ministry of Land, Infrastructure, and Transport (MOLIT) recently established the Railway Capacity Allocation Guideline (RCAG) to provide answers to questions about railway capacity allocation such as who should operate the railway service, who should maintain the railway tracks, when the railway plan should be initiated, and how the railway timetable should be constructed. Korea Railroad (KORAIL) has a monopoly for providing rail transportation, which meant that railway capacity allocation until the first half of 2016 involved having to resolve conflicting interests between KORAIL and KR. This hampered research into Korean railway capacity allocation. Recently, a new railway company, Suseo High-speed Railway Corporation (SHSRC), was established and has started to provide a high-speed railway service. The Korean high-speed rail market is very competitive and hence the profits of the railway service providers depend heavily on the railway capacity allocation. Therefore, there is a pressing need to develop a fair and objective railway capacity allocation procedure.
Train operation planning involves each railway company constructing its own train timetable in order to maximize its revenue. Therefore, it is highly likely that conflicts will arise between the train schedules of the different companies. The railway distributor collates the train timetables submitted by the railway companies and adjusts them so that conflicts are kept to the minimum. The aim of this study is to develop a model that can be applied to the railway capacity allocation process in Korea. The model developed here represents the railway network as a location–time network. Since an administered mechanism is used for railway capacity allocation in Korea, various requirements should be considered. In addition, we propose a genetic algorithm (GA) to solve the train timetable problem.
The railway capacity distributor establishes a railway track operation plan by adjusting the train timetable requested by each railway company. If there is a conflict among the requested train schedules, the distributor attempts to resolve it using the following process. Firstly, the distributor adjusts the departure time at the station of origin for each train in order to minimize the conflict; the allowable adjustment time is typically ±5 min for passenger trains and ±30 min for freight trains. Minimizing the conflict means retaining as many feasible scheduled trains as possible in the train operation plan after adjustment by the capacity distributor. In general, the requested train schedule can only be shifted from left to right (i.e., only parallel movement of the schedule in the train graph is allowed). This rule preserves the total journey time for trains to complete their respective itineraries (known as the transit travel time). However, if an adjustment of a train’s transit travel time is needed in order to increase the feasibility of the train timetable, train overtaking is possible at stations that have sidings. When one train overtakes another, it is the train with the higher priority that does the overtaking. To prevent unrealistically excessive waiting events, we restrict the maximum waiting time during overtaking to 5 min. From the viewpoint of the capacity distributor, it makes sense to pursue the maximization of the railway access charge. In this research, we assume that the access charge for each railway section is the same. Thus, maximizing the railway access charge is equivalent to maximizing the scheduled trains after adjustment for any train conflicts. I propose a mathematical model for the train timetable problem. The optimization problem for railway capacity allocation in this paper is stated formally as follows. Firstly, set the railway network with as a set of nodes that can be stations or junctions, a detailed layout of the track at each node, and the number of tracks and the number of platforms in station . From the train timetables requested by each railway operators, given 1) the total number of trains, 2) a set of trains, 3) a set of journey sequences for train with respect to its starting location , its final destination , and the ithlocation that it passes, 4) a set of journey times for train with respect to its journey time between and , and 5) a set of commercial stops for train with respect to a commercial time at location for train . The commercial time at the starting location (or the station of origin) of train is zero. The proposed model aims to maximize the number of feasible scheduled trains by adjusting the departure time at location for train . The result of the model is the integrated timetable for railway capacity allocation.
The railway capacity allocation model that was developed during this study has three hierarchical objectives. The first is to maximize the number of feasible scheduled trains, where feasibility means that there are no conflicts among the trains. Because the first objective function counts the number of feasible scheduled trains, the model searches for the most feasible optimum solution. The second objective is to minimize the total adjustment that is required for the allocation. The model looks for the solution that requires the least amount of departure-time adjustment at the station of origin. This second objective function comes into play when two or more solutions have the same number of feasible scheduled trains. The third objective is to minimize the total delayed transit time in excessive of the requested itineraries. Clearly, this third objective function is required when two or more solutions cannot be distinguished using the first and second objectives. The model determines a suitable departure time for each train from its first station. However, there are some constraints on this choice that must be considered, such as safety time, headway, and overtaking restrictions. The model searches for the earliest departure time that satisfies each constraint at each passing station for each train.
Meta-heuristic methods such as GA, simulated annealing, and tabu search try to find a better solution by searching randomly; these methods are simple and easy to implement. A model with a nonlinear representation of the objective function and its constraints can also be solved using meta-heuristic. Meta-heuristic can find good solutions in many cases given sufficient computational time. Simulated annealing considers only neighborhood solutions, which may prohibit the diversification of solutions. Tabu search also uses the method of neighborhood searching, which does not guarantee finding good solutions. GA have been applied successfully to the train timetable problem. Therefore, GA was applied to the various objective functions and constraints of Korean railways. GA performance depends on how a solution is represented. In this work, a gene consist of a train and the number of genes in a chromosome equates to the number of trains requested by a railway company. Trains are assigned arrival and departure times at all stations in the order in which they pass through. These assignments are conducted in the order of the gene list.
GA function consists of an initial population generation, selection, crossover, mutation, and evaluation. In initial population generaton, the algorithm randomly generates the predetermined number of chromosomes. The GA attempt to form the train timetable by considering genes sequentially in a chromosome. If a train cannot be scheduled in the current timetable, it is eliminated. The total number of genes inserted after all genes have been considered defines the fitness value of the corresponding chromosome. The selection process determines which chromosomes survive into the next generation. I select two chromosomes at random and the select the fitter one; this is known as the tournament selection method. I set the selection probability of a chromosome to 80%, which is the crossover probability in this paper. The crossover process makes it possible for offspring to inherit superior genetic characteristics from their parents by combining one part of a chromosome from each parent, which is known as one-point crossover. During the mutation process, I alter the location of a randomly selected gene in a selected chromosome to increase the diversity of the population. The selected gene is then inserted at a random position in the chromosome. I set the selection probability of a gene in the mutation process to 5%, which is the mutation probability. In the evaluation process, the algorithm calculates the fitness value of the chromosomes in the newly generated population. These GA functions are executed repeatedly until the algorithm reaches the predetermined maximum number of generations.
A fictitious timetable of 388 trains was made in order to implement and solve the proposed model. I assumed that two railway companies, KORAIL and SHSRC, want to operate 258 and 130 express trains, respectively, on the Korean express railway network (KERN) during the second half of 2016. Of the 388 trains, 201 are downward and 187 are upward. Only 98 trains are feasible; each of the remaining 290 trains has a conflict (i.e., it violates one or more of constraints mentioned previously) in the test data. Author’s view is that the test data under consideration reflect the real-world scenario in which the most profitable time slots are almost the same to all railway operators, who are not motivated to negotiate unless they are forced to do so. It would appear that the most important factor affecting the uptake of railway capacity is safety time, so we chose two test scenarios: a safety time of 2 min (scenario 1) or 3 min (scenario 2). From the 388 requested trains, the GA constructed a feasible integrated train timetable for 341 trains in scenario 1 and for 303 trains in scenario 2. The results suggest that more trains could be inserted into the timetable for a shorter safety gap, which is to be expected. Of the initial 290 conflicts, the GA resolved 243 in scenario 1 and 205 in scenario 2. The two test scenarios converged to a solution within 20 iterations, which took 148 min in scenario 1 and 129 min in scenario 2. The GA converged relatively quickly with this test data. I validated the test results in two ways: a compulsory scheduling attempt, and a headway analysis. Firstly, I tried to schedule infeasible (or non-scheduled) trains compulsively, which proved impossible to do without relaxing one or more constraints in each test scenario. For the headway analysis, I calculated an average headway for feasible scheduled trains by dividing the total service (or operating) time by the number of scheduled trains. The service time was 17 h (1,020 min) per day, which resulted in average headways of 5.8 min for downward trains and 6.2 min for upward ones in scenario 1, and 6.6 min for downward trains and 6.8 min for upward ones in scenario 2. The average headway for real trains operating on the GEL is 7.2 min, which is acceptably close to what I found in analysis. Future research will include other meta-heuristic approaches to the proposed model, such as simulated annealing and tabu searching. By comparing diverse meta-heuristic methods, I expect to find a more efficient approach to the problem of railway capacity allocation. And considering diverse train type or train class might be our future study, too.

번역하기

국문 초록 (Abstract)

우리나라는 2016년 상반기까지는 단독 철도운영사인 Korail만이 철도서비스를 제공하여 왔기 때문에 사실상 선로배분권자의 선로배분업무는 단독 철도운영자와 선로작업시행자간의 상충 해소에 그쳤다. 이러한 이유로 선로배분업무의 복잡성이 비교적 낮았고, 선로배분과 관련한 연구나 합리적이고 공정한 선로배분을 위한 모형 개발 등이 미흡한 실정이었다. 최근 수서 고속철도라는 새로운 철도운영사가 고속철도 서비스를 제공하기 시작함에 따라 국내에도 복수 철도운영사 시대가 도래하였고, 이에 따라 이전에 비하여 공정하고 객관적인 철도 선로배분이 요구되기 시작하였다.
각 철도운영사는 자사의 수익 극대화를 위해 열차운행계획(열차시각표)을 수립한다. 따라서 복수의 철도운영사들이 수립한 열차운행계획에는 상충이 발생할 가능성이 매우 크다. 철도 선로배분자는 철도운영사들이 수립하여 제출한 열차운행계획에서 발생한 열차 간 상충을 해소하여 조정된 열차운행계획을 수립한다. 본 연구는 우리나라의 철도 선로배분절차에 적용할 수 있는 선로배분모형을 개발하는 것을 목적으로 한다.
선로배분절차는 규칙기반 선로배분, 비용기반 선로배분, 입찰에 의한 선로배분방식 3가지가 있다고 알려져있다. 우리나라는 규칙기반 선로배분방식을 사용하고 있는데, 선로배분지침에 의해서 철도운영사간 열차운행계획을 조정하고 있다. 본 연구에서는 선로배분지침에 따라 선로배분권자가 조정 가능한 범위, 철도운영사의 서비스 유지를 위한 요구조건, 안전을 위한 필수 요구조건을 검토하여 이를 모형에 반영하였다.
철도 선로배분을 모형화한 연구들은 크게 철도 네트워크를 표현하는 방식에 따라 Space-Time Network 모형, Space Network 모형, Location-Time Network 모형으로 분류할 수 있다. 본 연구에서는 다양한 목적식과 제약식의 수용 가능성, 모델의 확장성 및 구현 용이성, 결과 해석 등의 의사소통 용이성 등의 측면에서 장점이 많은 Location-Time Network 모형을 사용하였다. 한편, 이들 철도 네트워크 모형은 의사결정변수의 개수가 많아 합리적인 시간 내에 해를 도출해내지 못하는 NP-Hard문제로 알려져있어 대부분의 철도 선로배분 모형 개발 연구들은 Heuristic방법론을 사용한다. 국내 선로배분절차와 철도운영사들의 요구조건과 안전을 위한 필수조건들을 제약식으로 표현한 뒤 최대한 이들 제약식을 많이 반영할 수 있는 방법을 검토한 결과 비선형, 조건부(if~then 형태) 제약식 등을 모두 반영하기에는 Heuristic 알고리즘이 적절하다고 판단하였다. 이에 여러 Heuristic 알고리즘들을 비교 검토하여, 모형의 확장성, 제약식의 추가 및 완화 용이성, 다양한 제약식 수용 가능성의 장점이 있는 유전자 알고리즘을 사용하였다.
Location-Time Network 모형과 유전자 알고리즘을 활용한 철도 선로배분 모형을 국내 고속철도(경부선, 호남선, 전라선)에 적용하여 본 결과 유전자 알고리즘 20번의 Iteration(Computing Running Time 기준 약 300분) 이내 해를 도출할 수 있는 것으로 나타났다. 해의 성능은 최초 388개의 열차 중 290개의 상충 열차가 존재하는 상태에서 최대 243개의 열차(약 83%)가 상충이 해소되었고, 상충이 해소되지 못해 제거된 열차들은 더 이상 제약식을 완화하지 않는 이상 스케줄링이 불가능한 상태로 분석되었다. 또한 현재 운행중인 KTX의 평균 운행시격 7.2분 대비 모형에 의한 열차시각표의 평균 운행시격은 5.8~6.2분으로 나타나 최소한 현재 운행시각표 보다 더 효율적인 해를 도출해내는 것으로 볼 수 있어 간접적으로 본 모형의 적정성을 확인할 수 있었다.

번역하기

우리나라는 2016년 상반기까지는 단독 철도운영사인 Korail만이 철도서비스를 제공하여 왔기 때문에 사실상 선로배분권자의 선로배분업무는 단독 철도운영자와 선로작업시행자간의 상충 해...

목차 (Table of Contents)