1. 서 론

우리나라의 지역간 철도는 크게 고속철도, 일반철도로 운영 중이고 준고속철도(시속 200 ~ 250 km/h급, 중부내륙선 등)의 건설이 계획되어 있는데 이에 따라 철도 네트워크도 점차 복잡해지고 있으며 철도 노선간 교차점이 점차 늘어나고 있는 추세이다. 지역간 철도의 노선은 하나의 선로에 하나의 노선을 사용하는 것이 일반적이다.

물론 하나의 노선에 운행계통이 다른(같은 노선 내에서 정차패턴, 시·종착역 등을 달리하는) 여러 형태의 운행 조합을 운영 중이지만 서로 다른 방향으로 운행하는 열차 노선이 하나의 선로를 공유하는 일은 드물다. 이에 따라 철도교통은 환승을 통해서 다른 노선으로 열차를 갈아타야하는 불편이 생길 수밖에 없어 여객 이용자의 불편 및 철도 물류 경쟁력 약화를 초래하고 있다.

이러한 한계를 극복하기 위해 여러 가지 대안이 제시되고 있는데, 그 중 하나는 연결선 건설을 통해 여러 노선이 하나의 선로를 공유하도록 하는 방법이다. 최근 국내에서도 고속철도 연결선(수원, 인천) 건설사업 등이 사업 타당성을 확보하고 건설 추진 중에 있다. 그러나 연결선 건설을 단순한 개별 건설사업으로 간주하여 사업별로 타당성조사 등을 실시하고 경제성분석 위주로 사업추진여부를 결정하고 있다는 점은 개선의 여지가 있다.

본 연구는 철도 연결선을 활용하여 철도 네트워크를 효율적으로 활용할 수 있는 전략 수립을 위한 모형을 개발하고 그 적용성을 평가하여 철도 네트워크를 최적화할 수 있는 방법을 제시하고자 한다.

2. 기존 연구 및 현황 분석

2.1 관련 연구 고찰

^{Lim et al.(2008)}은 철도승객의 노선선택을 고려한 철도망 설계모형을 제시하였다. 이 연구에서는 철도건설로 인한 네트워크효과를 고려할 수 있는 최적화모형을 제시하였고 링크의 속도가 변함에 따라 이용자가 경로선택을 바꾸는 현상을 구현하였다. 이 연구는 고속철도 건설효과와 네트워크효과를 분석하기 위한 연구이며 모형화 예제풀이를 통해 적용성을 검증하였다.

^{Bae et al.(2009)}의 연구결과에서는 상호직결운행을 고려한 철도망 확충과 철도노선 개편의 패러다임을 구상하였다. 이 연구는 기존 철도망 인프라의 효율적 운영, 환승 편리성 및 쾌적성 개선을 목표로 수도권 철도망을 대상으로 사업 가능구간과 실 사업비용 등을 도출하고 이에 대한 경제적 타당성을 분석하여 제시하였다. 이 연구는 철도 연결선 건설과 직결운행이 철도 네트워크의 효율성 증대에 효과가 있음을 입증하였으나, 개별 사업단위 단계에서 타당성을 검토한 결과라는 한계가 있다.

^{Jin et al.(2013)}은 철도네트워크 최적화 문제를 열생성기법(column generation method)으로 해결할 수 있는 알고리즘을 제시하였다. 이 연구는 철도네트워크 설계 과정에서 발생하는 철도 경로 생성, 개별 열차의 시·종점 선정, 운행빈도 선정, 열차간 간격 조절 및 추월 등의 제약조건 극복 등을 최적화 문제로 모형화하였고, 이에 대한 풀이 알고리즘을 제시하였다.

^{González et al.(2016)}은 인프라 시스템을 최적화하기 위한 독립적인 철도망의 설계 모형을 제시하였는데, 예산제약, 자원제약, 운행빈도 제약 하에 최적화된 철도망을 설계할 수 있는 알고리즘을 제시하였다. 철도망 설계 모형은 복합정수문제(Mixed Integer Programming, MIP)로 해결할 수 있어 여러 시나리오에서 최적해를 도출할 수 있음을 보여주었다.

^{Lin et al.(2017)}은 탄소배출량을 최소화하기 위한 철도 네트워크 설계 모형을 제시하였다. 탄소배출량을 최소화하기 위해서는 기존 철도망을 효율적으로 운영하기 위한 노선 및 스케줄 설계와 더불어 철도 물류수송에서 화물차 운행을 철도로 전환시킬 수 있는 새로운 노선의 설계도 포함되는 것을 전제로 하여 모형과 풀이과정을 제시하였다. 이 연구는 기존 철도의 효율성 확보와 신선 건설을 복합적으로 고려하여 최적화 모형을 수립하였다는 데에 의의가 있다.

^{Park et al.(2018)}은 철도 노선간 연계성 강화를 위한 상호직결운행 효과분석 연구를 통해 국내 원주-강릉선과 충북선 고속화 및 직결선 사업을 통해 동서 고속화 연결에 따른 운행시간 단축 효과를 분석하였다. 실제 네트워크에서 분석을 통하여 직결 운행을 통해 운행시간 단축효과가 약 30분~1시간 이상 될 것으로 분석하였고 중장기적 철도망의 연계성 및 효율성을 고려한 사업추진이 필요함을 제안하였다.

2.2 국내 현황 분석

국내에서 철도연결선 건설을 모형화하여 제시한 연구 결과는 없는 것으로 분석된다. 그러나 실제 사업 단계에서는 이미 연결선을 운영 중인 노선이 존재하며, 다수의 노선이 사업 추진 중에 있다.

선로를 공유하는 대표적인 사례는 고속철도 경부선-호남선을 오송분기점에서, 일반철도 중 경부선-장항선을 천안분기점에서 각각 분기하여 수요가 집중되는 수도권과 수요가 분산되는 지방권의 수요량에 각각 대응토록 운영 중인 경우이다. 수도권 광역철도에서도 금정역에서 경부선-안산선이 서로 선로를 공유·교차하여 운행할 수 있도록 인프라를 갖추고 있으며, 2003년까지 출퇴근시간에 안산과 노량진을 왕복운행하는 경부선-안산선 직결 전동열차가 운행한 사례가 있다.

현재 추진 중인 사업 중 대표적인 사업은 인천발 고속철도 및 수원발 고속철도 연결사업이다. 해당 사업은 각각 어천연결선, 지제연결선을 건설하여 일반철도와 고속철도 선로를 공유하는 사업인데 경제성이 높아 타당성을 확보하였고 현재 설계 중이다. 그 밖에 GTX-A 사업 또한 수도권고속철도와 선로를 공유하도록 계획되어 있으며 일부 구간에서는 노선간 선로공유도 계획되어 있다.

이와 같이 국내에서도 선로 공유를 통해 철도망 효율성을 제고하기 위한 다양한 사업들이 진행되고 있음을 알 수 있다.

3. 모형의 구축 및 풀이 알고리즘

3.1 연결선 건설 모형

3.1.1 기본 전제

현실에서 철도 연결선을 건설하는 것은 여러 가지 검토를 필요로 한다. 예를 들면 용지 보상 문제, 기하 구조 등 지형적 제약 극복 문제, 서로 다른 노선간 신호·통신체계 등을 해결하는 문제, 속도의 차이 해결 문제 등이 그것이다. 그래서 실제로 연결선 건설사업을 시행하기 위해서는 타당성 조사, 기본·실시 설계 등의 과정을 거쳐야 한다. 그러나 본 연구는 전체적인 네트워크 차원에서 연결선 건설의 전략을 수립하기 위한 이론적인 모형을 구축하는 것이므로 문제를 최대한 단순화하여 가장 일반적인 내용을 다루기로 한다.

본 연구에서는 위에서 언급한 연결선 건설에 따른 기술적 문제들은 충분히 해결 가능한 것으로 가정하였다. 실제로도 연결선 건설시 해결해야 할 제반 문제들은 비용의 크고 작음의 문제이지 가능·불가능의 문제는 아닐 것이라 예상할 수 있다. 따라서 연결선 건설에 관한 사항은 최대한 단순화하여 연결선 건설비용 항목으로만 고려하였다.

철도의 이용 수요는 연결선의 건설에 따라 충분히 달라질 수 있다. 연결선 건설 후 노선이 다양해지면 기존에 없던 수요가 새로 발생(유발수요)할 수도 있고 역간 기종점통행량(Origin-Destination, OD), 경로 선택 등이 충분히 달라질 수 있다. 그러나 본 연구에서는 이를 예측하는 것은 또 다른 추가 연구 사항으로 전체 수요는 고정된 것으로 가정한다. 만약 수요의 변화가 예상된다면 변화할 것으로 예상되는 역간 OD를 적용하면 될 것이고, 모형에서 민감도분석 등을 통하여 그 불확실성을 감안할 수 있을 것이다.

이러한 전제 조건은 현실에서 수치를 대입하여 산출하기는 제약이 있으나, 현실을 적절히 가정하여 모델링하는 과정에서 충분히 적용 가능한 조건이라 판단된다.

3.1.2 모형 구축

먼저 실제 철도망을 그래프로 표현하기 위해 일반적인 철도 네트워크에서 사용하는 표현들을 본 연구에서도 적용하였다. 노드는 역 또는 철도의 교차점을 나타내고 링크는 선로를 나타낸다. 수요는 노드간 통행량으로 나타내고 링크의 속성으로 통행시간, 거리, 용량을 각각 부여하였다. 하나의 노선은 여러 노드와 그 노드 사이의 링크를 통과하는 노드의 집합으로 표현하고, 노선의 속성으로는 운행빈도를 포함하였다.

연결선 건설을 네트워크에서 표현하는 방식은 연결선을 그 형태에 따라 실제 노드-링크체계로 표현할 수도 있으나, 이 경우 네트워크의 복잡도가 증가하게 되어 계산이 어렵게 된다. 따라서 본 연구에서는 연결선 건설을 노드의 회전제약으로 표현하였다. 이 방법은 일반적인 도로네트워크에서 교차로의 회전제약을 표현하기 위해 사용하는 방식인데, 본 연구에서도 이와 유사하게 철도 연결선 건설시 회전제약이 제거되는 것으로 표현하여 연결선 건설에 따른 네트워크의 변화를 모형화하였다.

전체적인 모형의 구조는 비용을 최소화하는 최적화모형으로 구축하였고, 비용항목으로는 연결선 건설비용과 철도 운영비용, 이용자의 통행시간비용을 각각 수식으로 반영하였다. 연결선 건설시 비용은 증가하지만 이용자의 통행시간은 감소하는 트레이드오프(trade-off)관계가 성립한다. 그리고 동일한 철도망이라면 노선을 무작정 많이 늘리는 것이 이용자 통행시간비용을 최소화하는데 도움이 되겠지만 그럴 경우 운영비용이 증가하게 되므로 운영비용과 이용자 통행시간비용도 또한 트레이드오프 관계가 있다. 따라서 본 연구의 모형은 연결선 건설비용·운영자 운영비용·이용자 통행시간비용의 합을 최소화하는 것으로 구축하였다.

본 모형에서 제약조건은 전체 수요의 합이 일정함을 반영하는 수요제약, 연결선 건설을 무제한으로 늘릴 수 없게 만들기 위한 예산제약, 하나의 선로에서 운영 가능한 노선의 개수와 운행횟수를 감안하기 위한 용량제약으로 각각 설정하여 모형 계산시 반영되도록 하였다.

이상의 내용을 반영하여 본 연구에서 구축한 연결선 건설 최적화 목적함수는 다음과 같다.

$$\begin{array}{l}minmizeZ(p,f)=\\\gamma_c\sum_{{}^\forall i,j,k}^{}(1-p_{ij}^k)+\gamma_o\sum_{{}^\forall r}^{}\lbrack f^r\sum_{{}^\forall a}^{}(l_a\cdot\theta_a^r)\rbrack+\gamma_t\sum_{{}^\forall i,j,r}^{}\lbrack D_{ij}^r\cdot\sum_{{}^\forall a,r}^{}(t_a\cdot\theta_a^r)\rbrack\end{array}$$

(1)

(연결선 건설비용 + 운영비용 + 이용자 통행시간비용)

subject to

$$\sum_r^{}D_{ij}^r=D_{ij}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\mathrm{수요제약})$$

(2)

$$\gamma_c\sum_{{}^\forall i,j,k}^{}(1-p_{ij}^k)<=B\;\;\;\;\;\;\;\;\;\;\;(\mathrm{예산제약})$$

(3)

$$\sum_r^{}f^r\cdot\theta_a^r<=C_a,for^\forall a\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\mathrm{용량제약})$$

(4)

여기서, $N$ 노드(node)의 집합

$D_{ij}$ 노드 $i, j$간 수요(demand), ${}^{\forall }i, j\in N$, $D_{ij}$≧0

$A$ 링크(arc)의 집합

$t_a$ 링크 $a$의 통행시간(travel time), ${}^{\forall }a\in A$, $t_a$>0

$l_a$ 링크 $a$의 거리(length), $l_a$>0

$R$ 노선(route)의 집합

$f^r$ 노선 $r$의 운행빈도(frequency), ${}^{\forall }r\in R$, $f^r$>0

$p_{ij}^k$ 노드 $i-k-j$ 간 회전제약(turn penalty). 회전 가능시 0, 회전 불가시 1, $p_{ij}^k=\{0, 1\}$, ${}^{\forall }i, j, k\in N$

${\gamma }_c$ 연결선 건설비용

${\gamma }_o$ 단위 운영비용

${\gamma }_t$ 이용자 통행시간 비용환산계수

$B$ 건설 예산제약(budget limitation)

$C_a$ 링크 $a$의 용량(회/일)

${\theta }_a^r$ 링크 $a$가 경로 $r$에 포함되면 1, 아니면 0

3.2 풀이 알고리즘

3.2.1 최적화 문제 풀이

Eq. (1)의 최적화 문제는 단순히 보면 연결선 건설여부인 이진 변수와 운행빈도인 정수 변수로 구성된 정수문제(integer problem)로 보이지만 사실은 이용자 통행시간비용을 계산하는 방법에 따라 비선형문제(nonlinear problem)가 포함되어 있으므로 전체적으로는 비선형문제로 보아야 한다. 이에 따라서 유일한 일반해를 구하기는 어렵고, 최적의 유사해를 구할 수 있으므로 명확한 수렴조건을 제시하는데 한계가 있다. 비선형 문제를 풀기 휘한 해법은 branch and bound, column generation, 유전자 알고리즘, 인공신경망 알고리즘 등 이미 개발된 기법들이 다양하며 최근 계산 능력의 발전에 따라 네트워크가 크지 않은 이상 풀이가 어렵지 않으므로 본 연구에서는 이 부분(비선형문제의 해법 알고리즘)은 생략하기로 한다.

본 연구의 최적화문제를 해결하기 위해서는 먼저 경로, 회전제약, 운행빈도 초기치를 정의하고 해당 조건에서 통행배정을 통해 이용자 통행시간비용을 산출한다. 그 후 결과에 따른 목적함수 값을 산출하고 새로운 경로를 생성하여 이 과정을 반복하여 최적의 결과를 찾아 최종적으로 노드별 연결선 건설여부 및 회전 방향, 새로운 노선 경로 및 운행빈도를 산출하는 것으로 하였다.

이상의 내용을 정리하면 다음과 같다.

<Step 1> 초기화

- 모든 $p_{ij}^k=1$ - 경로집합 $R$ 생성, $f^r$ 초기값 부여 - 반복수 $n=0$

<Step 2> 최적전략 통행배정

- step1에서 작성된 경로와 경로별 운행빈도 적용

- 이용자 통행시간비용 산출

<Step 3> 목적함수 값 산출( $Z_0$)

<Step 4> 이전 목적함수 값과 비교,

- 낮으면 새로운 경로 생성, 경로에 따라 $p_{ij}^k$ 조정, <step2>로 반복, $n=n+1$

- 높으면 종료

3.2.2 경로생성 알고리즘

본 연구 모형의 풀이는 최적화문제를 푸는 것보다 경로 생성을 어떻게 하는가에 따라 계산 성능이 좌우되고 결과 값의 정확성을 높일 수 있다. 경로생성은 이용자비용을 낮추기 위한 최단경로로 생성하는 것을 원칙으로 하고 운행빈도는 수요를 만족할 수 있도록 정하는 것으로 알고리즘을 수립하였다. 경로의 생성은 최대수요를 최단거리로 수송할 수 있는 경로 순서로 탐색하고, 용량제약을 반영하여 전체 OD가 노선을 이용할 수 있도록 반복하여 수행된다. 경로생성 알고리즘을 정리하면 다음과 같다.

<step 1> 초기화

- 현재 네트워크 선로 구성대로 경로 생성

<step 2> 최대 수요 OD 노드 기준 최단경로 탐색, 경로 생성

- 최대 수요 OD 노드는 리스트에서 삭제

<step 3> 나머지 수요 리스트에서 최대 수요 OD 기준 최단경로 생성

<step 4> 이전 경로 갱신

- 용량 제약시 경로 취소

<step 5> 전체 OD 리스트 경로 생성시 까지 <step 2> 반복

4. 예제 네트워크 풀이

4.1 예제 네트워크 설명

본 연구의 모형을 적용하기 위해 다음과 같은 철도 네트워크를 가정하였다. 예제 네트워크는 노드 9개, 링크 12개로 구성되어 있고, 1-2 링크는 복복선, 1-4, 2-3, 2-5, 4-5, 5-8, 8-9 링크는 복선, 나머지 링크는 단선으로 설정하였으며 링크 위에 표시된 숫자는 링크의 통행비용을 의미한다. OD 통행량은 제시된 수치와 같고 링크의 용량, 예산제약, 환승시 패널티는 주어진 수치와 같다. 현재 네트워크의 상태는 연결선이 건설되지 않은 상태이고 오직 직진방향(180°)로만 환승 없이 진행할 수 있다고 가정하였다.

예제 네트워크의 형상과 주어진 조건을 정리하면 Fig. 1 and Table 1과 같다.

Table 1. Numerical Value for Example Problem

Travel demand		Network specification
OD	OD trips	Description	Value
1→9	100	Capacity-quad track	300
1→8	80	Capacity-double track	200
2→7	60	Capacity-single track	100
4→9	40	Budget limit	40
3→8	20	Inter-connector construction cost	10
-	-	Transfer penalty	3

4.2 예제 네트워크 풀이

n=1일 때 수요가 가장 큰 1→9를 대상으로 최단경로는 1-2- 3-6-9가 되고(연결선 건설은 한 곳만 설치하면 되므로), 2-3-6 방향으로 연결선을 건설하면 통행비용은 44, 누적건설비용은 10이 된다.1-2-5-8-9로 경로를 설정할 경우 링크통행비용만 보면 43으로 더 작지만 연결선을 2개 건설해야하고, 연결선을 건설하지 않으면 환승비용 3이 추가되어 비용이 더 커지게 되므로 연결선을 1개만 건설하는 1-2-3-6-9 경로가 더 유리하다.

n=2일 때 다음으로 수요가 큰 1→8을 대상으로 최단경로는 1-2-5-8이고, 1-2-5 방향으로 연결선 건설시 통행비용은 33, 누적건설비용은 20이 된다. 그런데, 1-2-5방향으로 연결선 건설시 1→9 수요가 5-8-9 방향 연결선 하나만 건설하면 비용이 더 낮아지므로 1→9의 최단경로가 1-2-5-8-9로 수정된다. 따라서 2-3-6 연결선 건설은 취소되고 5-8-9 연결선이 추가되며 누적건설비용은 20으로 유지된다.

n=3일 때 수요 2→7을 대상으로 최단경로는 2-5-8-7이 되는데, 이 경우 2-5, 5-8 링크가 이미 1→9, 1→8 수요에 의해 용량에 도달하여 그 경로는 사용할 수 없고 다른 경로를 탐색해야 한다. 차선의 경로는 2-1-4-7이며 2-1-4 방향으로 연결선 건설이 가능하고 누적예산은 30이 된다.

n=4일 때 수요 4→9를 대상으로 최단경로는 4-7-8-9가 되며 4-7-8 방향으로 연결선이 건설되고 누적예산은 40이 된다.

n=5일 때 수요 3→8을 대상으로 최단경로는 3-6-9-8이 되는데, 6-9-8 방향으로 연결선 건설시 누적예산이 50으로 예산제약의 범위를 벗어나게 되므로 연결선 건설이 불가하다. 따라서 3→8 방면의 수요는 9번 노드에서 환승하여 이용하여야 하고, 모든 수요를 만족시켰으므로 알고리즘은 종료된다.

이상의 과정을 거쳐 연결선 건설 전략 수행 결과 1-2-5, 5-8-9, 2-1-4, 4-7-8방향으로 총 4개의 연결선이 건설되고 연결선 건설의 우선순위도 언급한 순서와 같게 된다. 이상의 과정을 정리하면 Fig. 2 and Table 2와 같다(Fig. 2에서 링크 위의 수치는 링크통행량을, 노드의 붉은색 점선은 연결선건설을 의미함).

Table 2. Solving Process and Result

$n$	OD	Shortest route	Travel cost	Note	Inter-connector	Accumulated Const. cost
1	1→9	1-2-3-6-9	44	New	$p_{26}^3=0$	10
2	1→8	1-2-5-8	33	New	$p_{15}^2=0$	20
2'	1→9	1-2-5-8-9	43	Adjust	$p_{26}^3=1$, $p_{59}^8=0$	20
3	2→7	2-5-8-7	33	New. Canceled (capacity limit)	$p_{57}^8=0$	30
3'	2→7	2-1-4-7	35	Adjust	$p_{57}^8=1$, $p_{24}^1=0$	30
4	4→9	4-7-8-9	32	New	$p_{48}^7=0$	40
5	3→8	3-6-9-8	32	New. Canceled (budget limit)	$p_{68}^9=0$	50
5'	3→8	3-6-9, 8	35	Adjust	$p_{68}^9=1$	40
END

5. 결 론

본 연구는 기존 철도망에 연결선을 건설하여 한정된 철도 네트워크를 효율적으로 운영하기 위한 전략 모형을 수립하는 연구이다. 이를 위해 연결선 건설시 소요되는 건설비용, 운영비용, 그리고 이로 인해 절감되는 이용자의 통행비용 등 네트워크 전체에서 발생할 비용의 총합을 최소화하는 최적화 모형을 구축하였고 그에 대한 풀이 알고리즘을 제시하였다. 이를 예제 네트워크에 적용한 결과 현실 네트워크에 적용이 가능할 것으로 판단된다.

서론에서 언급하였다시피 실제 현실에서 철도 연결선을 건설하기 위해서는 본 논문에서 고려하지 못한 여러 가지 문제들을 수반함은 당연하며 실제 소요되는 비용을 일괄적으로 적용할 수 없을 뿐 더러 물리적으로 불가능할 수도 있다. 그러나 본 논문의 모형은 학술적 연구를 목적으로 이를 최대한 단순화하여 모형화하였다는 데에 의의가 있고, 본 연구의 결과는 지역간 철도 뿐만 아니라 광역철도나 도시철도에서도 적용할 수 있을 것이다. 특히, 전체 네트워크 레벨에서 사업 대상지를 선정하거나 사업 대상지가 어느 정도 선별된 단계에서 우선순위를 결정할 때 활용이 가능할 것으로 판단된다.

본 연구의 결과는 철도망 구축의 전략수립 단계에서 사용할 수 있는 수준으로 진행되었지만, 향후 실제 네트워크에 적용하여 정책적 판단의 기초 자료로 활용할 수 있도록 세밀한 부분의 보완(철도 용량 고려, 실제 건설비+운영비 고려, 교통수요 반영 등)이 필요하며 각종 비용 파라미터들을 현실성 있도록 구축하는 것이 필요할 것이다.