최적화 모형을 활용한 열차 운행 횟수 및 정차 패턴 생성 : 고속 열차 노선 계획을 중심으로 Finding Train Frequencies and Halting Patterns Using Optimization Models : a Focus on the Line Plan for High-Speed Trains원문보기
박범환
(Department of Railroad Management and Logistics, Korea National University of Transportation)
,
김장욱
(Management Research Department, KORAIL Research Institute)
승객들에게 보다 빠른 고속 열차 서비스를 제공하기 위해 무정차 열차를 비롯한 고속열차의 정차 패턴 최적화에 대한 관심이 증대하고 있다. 이러한 논의는 이후 정차 패턴을 활용한 차별화된 열차 서비스 및 그에 합당한 가격을 통해 신규 고속 열차 서비스 및 수요를 만들 수 있다는 측면에서 보다 더 큰 관심을 불러오고 있다. 일반적으로 정차 패턴은 효율적인 노선계획 작성에 의해 고려되는데, 효율적인 노선계획이란 모든 수요가 만족되고 전체 여정시간이 최대한으로 감소되는 열차 운행 계획을 말한다. 본 논문에서는 이를 위해 두 개의 최적화 모형을 활용한 2단계 프로세스를 제시한다. 첫 번째 단계는 모든 열차의 all-stop 패턴을 가정한 최소 횟수 혹은 최소 킬로미터 노선 계획을 작성하는 단계이고, 두 번째 단계는 첫 번째 단계로부터 도출된 열차들을 다양한 정차 패턴으로 분해하는 과정이다. 본 연구에서는 이와 같은 프로세스를 최근 고속 열차 실적 수요에 적용해 보았고 기존 열차 운행 횟수 및 정차 패턴과 비교분석하였다.
승객들에게 보다 빠른 고속 열차 서비스를 제공하기 위해 무정차 열차를 비롯한 고속열차의 정차 패턴 최적화에 대한 관심이 증대하고 있다. 이러한 논의는 이후 정차 패턴을 활용한 차별화된 열차 서비스 및 그에 합당한 가격을 통해 신규 고속 열차 서비스 및 수요를 만들 수 있다는 측면에서 보다 더 큰 관심을 불러오고 있다. 일반적으로 정차 패턴은 효율적인 노선계획 작성에 의해 고려되는데, 효율적인 노선계획이란 모든 수요가 만족되고 전체 여정시간이 최대한으로 감소되는 열차 운행 계획을 말한다. 본 논문에서는 이를 위해 두 개의 최적화 모형을 활용한 2단계 프로세스를 제시한다. 첫 번째 단계는 모든 열차의 all-stop 패턴을 가정한 최소 횟수 혹은 최소 킬로미터 노선 계획을 작성하는 단계이고, 두 번째 단계는 첫 번째 단계로부터 도출된 열차들을 다양한 정차 패턴으로 분해하는 과정이다. 본 연구에서는 이와 같은 프로세스를 최근 고속 열차 실적 수요에 적용해 보았고 기존 열차 운행 횟수 및 정차 패턴과 비교분석하였다.
There has been much interest in optimizing the halting patterns of high-speed trains, for example by introducing more non-stop trains to supply faster train service to the passengers, which could later bring about a discussion about introducing new high speed train service with differentiated price ...
There has been much interest in optimizing the halting patterns of high-speed trains, for example by introducing more non-stop trains to supply faster train service to the passengers, which could later bring about a discussion about introducing new high speed train service with differentiated price and service. In general, halting patterns can be considered by constructing an efficient line plan, in which all demand should be covered and the total travel time can be reduced as much as possible. In this study, we present a two-step process based on two optimization models. One is to minimize total kilometers of trains to run on each route ; this will be done using a line planning model under the assumption of all-stop patterns. Then, in the next step, the all-stop patterns are optimally decomposed into several halting patterns in order to minimize the total travel time. We applied the two-step process to the latest demand data in order to develop KTX halting patterns as well as to determine the frequency of each line and compare the current line plan with the optimized one.
There has been much interest in optimizing the halting patterns of high-speed trains, for example by introducing more non-stop trains to supply faster train service to the passengers, which could later bring about a discussion about introducing new high speed train service with differentiated price and service. In general, halting patterns can be considered by constructing an efficient line plan, in which all demand should be covered and the total travel time can be reduced as much as possible. In this study, we present a two-step process based on two optimization models. One is to minimize total kilometers of trains to run on each route ; this will be done using a line planning model under the assumption of all-stop patterns. Then, in the next step, the all-stop patterns are optimally decomposed into several halting patterns in order to minimize the total travel time. We applied the two-step process to the latest demand data in order to develop KTX halting patterns as well as to determine the frequency of each line and compare the current line plan with the optimized one.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
정차 패턴을 어떻게 하는지에 따라 투입되어야 하는 열차 운행 횟수가 달라지므로, 정차 패턴에 따른 고속 열차 서비스의 차별화 가능성 여부는 결국 효율적인 열차 운행계획을 작성할 수 있는가에 달려 있다. 열차 운행 계획은 노선계획, 시각표 작성, 차량 운용 등 다양한 계획의 통합적 작성을 통해 만들어 지는데, 본 연구는 열차 운행 비용(operating cost)이나 승객 여정 시간(travel time)의 최소화를 주요 목적함수[1]로 설정하는 노선 계획에 관한 연구이다.
가설 설정
그러나 현재 두 차량의 투입에 있어 주요한 결정 요인은 가용 편성수이며, 노선계획에서 두 차량의 차이에 따라 노선을 따로 설정할 경우, 각 노선에 최적의 열차 횟수를 선정하더라도 편성 제약으로 인해 실행 불가능한 열차 운행 계획이 된다. 이를 해결하기 위해 본 연구에서는 가중 좌석 용량을 활용하여, 각 노선에는 현재 열차 운행 계획에서 투입 되고 있는 두 차량의 비율만큼씩 투입된다고 가정하였다. 이를 계산하기 위해, 각 노선별 KTX와 KTX-산천 투입 횟수를 분석하였고, 이를 이용하여 Table 3과 같은 가중좌석수를 계산하였다.
ASLP의 식(2)에서 Cr을 실제 좌석용량으로 설정할 경우, 승객이 집중되는 시간대가 아닌 경우, 시간대에 속한 모든 수요의 집적효과를 가정함으로써, 상대적으로 적은 숫자의 열차가 투입되는 문제가 있다. 이를 해결하기 위해 현실에서는 좌석용량의 일정부분만 활용된다고 가정하여 실제 투입되는 좌석용량 대비 특정 비율(load factor) 만큼의 좌석용량을 가정하게 된다. Table 4는
본 연구는 [2]에서 활용된 운행 비용과 여정시간의 가중 목적함수 대신에, 운행 비용을 우선적으로 최소화한 후, 여정시간을 최소화하는 이단계로 구성된 최적화 모형을 고려하였다. 첫 번째 단계 최적화 모형은 모든 노선에 운행되는 열차가 all-stop 패턴을 갖는다고 가정하고, 전체 운행 비용을 최소화하는 노선계획을 찾기 위한 모형이고, 두 번째 단계 최적화 모형은 첫 번째 단계로부터 도출된 all-stop 열차들을 다양한 정차패턴으로 분리하는 모형이다. 두 모형의 경우 [2]의 통합 모형보다 훨씬 적은 변수로 구성이 되어, 별도의 알고리즘 설계 필요 없이 분지한계법(Branch-and-Bound) 만으로도 짧은 시간 안에 최적해를 구할 수 있는 장점이 있다.
첫 번째 단계는 모든 열차가 all-stop 정차 패턴을 갖는다고 가정하고, 각 노선별 최적의 열차 운행 횟수를 선정하는 단계이다. 여기서 노선이란 시발역, 종착역, 경로, 여정시간, 공급 좌석수 등으로 구분할 수 있는 열차들의 집합이다.
제안 방법
본 연구에서는 노선 계획의 시간 단위를 1시간으로 설정하였다. 따라서 시간대별 OD별 수요 도출을 위해 2015년 8월 1일부터 12월 31일까지 5개월간의 고속 열차 수요를 분석하였다. 특히 모든 실적 수요는 해당 열차 정보를 파악할 수 있으므로, 열차의 시발역 출발 시간을 기준으로 한 시간대별 수요로 환원하였다.
본 연구는 [2]에서 활용된 운행 비용과 여정시간의 가중 목적함수 대신에, 운행 비용을 우선적으로 최소화한 후, 여정시간을 최소화하는 이단계로 구성된 최적화 모형을 고려하였다. 첫 번째 단계 최적화 모형은 모든 노선에 운행되는 열차가 all-stop 패턴을 갖는다고 가정하고, 전체 운행 비용을 최소화하는 노선계획을 찾기 위한 모형이고, 두 번째 단계 최적화 모형은 첫 번째 단계로부터 도출된 all-stop 열차들을 다양한 정차패턴으로 분리하는 모형이다.
본 연구에서는 기존의 정차패턴을 고려한 노선 계획 모형이 가지고 있던 알고리즘의 한계를 극복하여, 보다 빠른 시간 안에 해를 구할 수 있는 2단계 해법을 제시하였고, 이를 활용하여 고속 열차 노선 계획에 적용해보았다. 실험 결과 모든 시간대에 대해 약 2분 안에 최적해를 도출할 수 있었으며, 기존의 열차 운행 계획에 비해 정차 횟수가 획기적으로 감소할 수 있음을 확인하였다.
본 연구에서는 노선 계획의 시간 단위를 1시간으로 설정하였다. 따라서 시간대별 OD별 수요 도출을 위해 2015년 8월 1일부터 12월 31일까지 5개월간의 고속 열차 수요를 분석하였다.
Table 3에서는 경부선-호남선-전라선-경전선-동해선 등 주요 노선별(corridor) 가중좌석수를 설정하였는데, 시간대별 혹은 첨두/비첨두 시간대별 가중좌석수을 설정하는 것도 가능하다. 앞에서 서술했듯이 가중좌석수를 이용하는 이유는 이후 계획단계인 KTX와 KTX-산천의 차량운용(routing) 계획의 용이성을 위한 것인데, 시간대별로 가중좌석수를 세분화할 경우, 두 차량의 운용대안의 폭을 좁힐 수도 있어, 본 연구에서는 주요 노선별 가중좌석수만 고려하였다.
위 결과를 좀 더 세밀히 분석하기 위해 중간 정차 횟수별 열차 운행 횟수를 계산해보았다. Table 9에서 보듯이, 현재는 무정차 통과 열차가 하나도 없는 반면, HPGM 모형을 통해 도출된 노선계획의 경우, 주중의 경우 12대, 주말의 경우 31대에 이른다.
이를 해결하기 위해 본 연구에서는 가중 좌석 용량을 활용하여, 각 노선에는 현재 열차 운행 계획에서 투입 되고 있는 두 차량의 비율만큼씩 투입된다고 가정하였다. 이를 계산하기 위해, 각 노선별 KTX와 KTX-산천 투입 횟수를 분석하였고, 이를 이용하여 Table 3과 같은 가중좌석수를 계산하였다.
아래 표에서 보듯이 2015년 11월 주중(주말)의 열차 운행 횟수는 하행/상행이 각각 121회/122회(134회/135회)인데, load factor가 커지면 커질수록 투입 열차의 횟수가 증가함을 볼 수 있다. 추후 HPGM 모형의 실험에서 현행 정차 패턴과의 비교 분석을 위해, 실제 운행횟수와 가장 근접한 85%(주중), 100%(주말)를 적용하였다.
성능/효과
1절의 ASLP보다 변수와 제약식이 훨씬 많으며 다품종 흐름이 두 가지가 중첩되어 있는 복잡한 모형이라 할 수 있다. 다음 절의 실험에서 살펴보겠지만, ASLP로부터 도출되는 전체 운행해야 할 열차 횟수가 많아질 경우(|T|가 커짐), 변수의 개수가 기하급수적으로 커져 모형의 복잡도가 올라가지만, 제한된 개수의 열차들의 정차 패턴을 구할 경우 충분히 빠른 시간 안에 최적해를 구할 수 있었다.
본 연구에서는 기존의 정차패턴을 고려한 노선 계획 모형이 가지고 있던 알고리즘의 한계를 극복하여, 보다 빠른 시간 안에 해를 구할 수 있는 2단계 해법을 제시하였고, 이를 활용하여 고속 열차 노선 계획에 적용해보았다. 실험 결과 모든 시간대에 대해 약 2분 안에 최적해를 도출할 수 있었으며, 기존의 열차 운행 계획에 비해 정차 횟수가 획기적으로 감소할 수 있음을 확인하였다.
열차 운행횟수를 살펴보면 주중 주말 모두 경부선 상행의 열차 수가 기존 운행 횟수보다 감소했으며, 동해선과 경전선의 운행 횟수가 소폭 상승하다. 이는 최적화 모형에서 열차 운행 거리에 따른 우선 순위에 따라, 동대구나 부산으로(부터)의 수요를 처리하는 열차가 동해선 열차, 경전선 열차 순으로 더 유리하기 때문이다.
Table 7과 Table 8은 2015년 11월 화요일, 토요일 기준 열차 스케줄의 루트별 평균 중간 정차 횟수와 HPGM 모형을 통해 도출된 노선 계획에서의 중간 정차 횟수를 비교한 것이다. 전체적으로 하행(상행) 기준 10.9%(6.0%)정도의 정차횟수 감소를 보였으며, 특히 경부선 상하행, 전라선의 상행의 정차 횟수 감소폭이 컸으며, 경전선의 경우 하행 기준으로 기존 정차 횟수 보다 9.6% 소폭 증가하는 현상을 보였다. 주말 노선별 평균 정차 횟수 또한 주중 시간대와 비슷한 양상을 보임.
식(1)은 각 노선에서 운행되는 모든 열차들의 운행 비용의 합과 승객의 여정시간의 합을 최소화하는 식이며, 식(2)는 각 노선에 할당되는 전체 공급 좌석수에 대한 제약식이고, 식(3)은 각 노선에 할당된 수요의 주어진 od수요를 만족함을 의미한다. 추후 실험결과에서도 살펴보겠지만, 위 최적화 모형의 변수 개수는 노선의 개수(|R|)와 od의 개수(|S|)의 곱에 비례하는데, 고속열차 네트워크의 경우 변수가 매우 제한적이라 분지한계법을 적용하는 것만으로도 충분히 빠른 시간 안에 최적해를 구할 수 있었다.
후속연구
그러나 본 연구에서 제시한 최적화 모형은 정차 횟수나 열차 운행 횟수에 따른 수요의 변동성을 고려하지 않은 한계를 가지고 있다. 즉 수요는 열차 운행 계획에 관계없이 고정적이라 가정하였고 그 수요를 수송하기 위한 최소 비용의 열차 운행횟수 및 최적의 정차 패턴을 도출하는 모형이므로 새로운 정차 패턴 및 이에 따른 정차역 감소로 인한 수요 감소 효과를 완전히 배제하기 어렵다.
즉 수요는 열차 운행 계획에 관계없이 고정적이라 가정하였고 그 수요를 수송하기 위한 최소 비용의 열차 운행횟수 및 최적의 정차 패턴을 도출하는 모형이므로 새로운 정차 패턴 및 이에 따른 정차역 감소로 인한 수요 감소 효과를 완전히 배제하기 어렵다. 특히 실적 수요로부터 도출된 최적의 노선 계획에서는 더 이상 그러한 수요가 유지되지 않고 변화하는데, 이러한 수요예측과 노선 계획 간의 불일치 문제를 해소하기 위해서는, 노선계획과 그 계획에 따른 수요의 변동성을 동시에 고려할 수 있는 통합 최적화 모형이나 반복적인 프로세스에 대한 추후 연구가 필요하다.
질의응답
핵심어
질문
논문에서 추출한 답변
열차 운행 계획에 사용되는 방법들은?
정차 패턴을 어떻게 하는지에 따라 투입되어야 하는 열차 운행 횟수가 달라지므로, 정차 패턴에 따른 고속 열차 서비스의 차별화 가능성 여부는 결국 효율적인 열차 운행계획을 작성할 수 있는가에 달려 있다. 열차 운행 계획은 노선계획, 시각표 작성, 차량 운용 등 다양한 계획의 통합적 작성을 통해 만들어 지는데, 본 연구는 열차 운행 비용(operating cost)이나 승객 여정 시간(travel time)의 최소화를 주요 목적함수[1]로 설정하는 노선 계획에 관한 연구이다.
노선계획 모형은 무엇인가?
일반적으로 열차운행횟수를 결정하기 위한 모형을 노선계획(line plan) 모형[1]이라 한다. 노선 계획이란 열차종별 시종착별 열차의 운행 횟수 및 열차별 정차 패턴을 작성하는 계획을 말하는데, 노선 계획은 열차별 시각표의 대략적인 얼개로서 열차 운행 계획의 가장 첫 번째 단계라 할 수 있다.
참고문헌 (9)
M.R. Bussieck (1997) Optimal lines in public rail transport, Ph.D thesis, TU Branunschweig.
B.H. Park, Y. Seo, S.-P. Hong, H.-R. Rho (2013) Column generation approach to line planning with various halting patterns - application to the Korean high-speed railway, Asia-Pacific Journal of Operational Research, 30(4), pp.1-19
M.R. Bussieck, P. Kreuzer, U. Zimmermann (1996) Optimal lines for railway systems. European Journal of Operations Research, 96, pp. 54-63.
M. Claessens, van Dijk, P. Zwaneveld (1998) Cost optimal allocation of rail passenger lines. European Journal of Operations Research, 110, pp. 474-489.
M.R. Bussieck, T. Lindner, M. Lubbecke (2004) A fast algorithm for near optimal line plans. Mathematical Methods of Operations Research, 59, pp. 205-220.
R. Borndorfer, M. Grotschel, M. Pfetsch (2007) A column generation approach to line planning in public transport. Transportation Science, 41(1), pp. 123-132.
J. Goossens, S. Hoesel, L. Kroon (2002) On solving multi-type line planning problems. METEOR Research Memorandum RM/02/ 009. University of Maastricht.
J. Goossens, S. Hoesel, L. Kroon (2004) A branch-and-cut approach for solving railway line-planning problems. Transportation Science, 38(3), pp. 379-393.
Y-H. Chang, C-H. Yeh and C-C. Shen (2000) A multiobjective model for passenger train services planning: Application to Taiwan's high-speed rail line. Transportation Research Part B, 34, pp. 91-106.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.