추가 제약을 갖는 수송문제를 활용한 공화차 배분 최적화 모형 및 해법 개발 Development of an Optimization Model and Algorithm Based on Transportation Problem with Additional Constraints원문보기
최근 철도 화물 수송은 컨테이너 전세 열차뿐만 아니라 시멘트, 철강 등 일반 화물의 전용열차 수가 증가하고 있고, 이에 따라 영차 수송 계획은 점차 단순해지고 있다. 반면에 공화차 수송의 경우, 수송 계획 최적화 시스템의 부재로, 사령의 경험에 의해 공화차 배분이 이루어지고 있으며, 이의 효율성 여부는 검증된 바 없고, 공화차 배분을 위한 별도의 의사결정지원시스템의 필요성은 여전히 존재한다. 본 연구에서는 연구 문헌상의 공화차 배분 최적화 모형뿐만 아니라 2010년 전후로 개발 되었다가 최근 사용이 중단된 화물수송최적화 시스템(KTOCS)상의 공화차 배분 최적화 모형을 비판적으로 살펴본 후, 수송 문제를 활용한 새로운 공화차 배분 최적화 모형 및 해법을 제시한다. 이 최적화 모형은 기존 모형과 달리, 추가 제약이 있는 수송문제에 포함되는 아크를 동적으로 생성해내는 열생성 기법에 기초하고 있다. 이를 이용한 우리나라 전체 철도 네트워크에 대한 시뮬레이션 결과, 실적 상에 나타난 공화차 km를 상당히 낮출 수 있는 것을 확인할 수 있었다.
최근 철도 화물 수송은 컨테이너 전세 열차뿐만 아니라 시멘트, 철강 등 일반 화물의 전용열차 수가 증가하고 있고, 이에 따라 영차 수송 계획은 점차 단순해지고 있다. 반면에 공화차 수송의 경우, 수송 계획 최적화 시스템의 부재로, 사령의 경험에 의해 공화차 배분이 이루어지고 있으며, 이의 효율성 여부는 검증된 바 없고, 공화차 배분을 위한 별도의 의사결정지원시스템의 필요성은 여전히 존재한다. 본 연구에서는 연구 문헌상의 공화차 배분 최적화 모형뿐만 아니라 2010년 전후로 개발 되었다가 최근 사용이 중단된 화물수송최적화 시스템(KTOCS)상의 공화차 배분 최적화 모형을 비판적으로 살펴본 후, 수송 문제를 활용한 새로운 공화차 배분 최적화 모형 및 해법을 제시한다. 이 최적화 모형은 기존 모형과 달리, 추가 제약이 있는 수송문제에 포함되는 아크를 동적으로 생성해내는 열생성 기법에 기초하고 있다. 이를 이용한 우리나라 전체 철도 네트워크에 대한 시뮬레이션 결과, 실적 상에 나타난 공화차 km를 상당히 낮출 수 있는 것을 확인할 수 있었다.
Recently, in the field of rail freight transportation, the number of trains dedicated for shippers has been increasing. These dedicated trains, which run on the basis of a contract with shippers, had been restricted to the transportation of containers, or so called block trains. Nowadays, such commo...
Recently, in the field of rail freight transportation, the number of trains dedicated for shippers has been increasing. These dedicated trains, which run on the basis of a contract with shippers, had been restricted to the transportation of containers, or so called block trains. Nowadays, such commodities have extended to cement, hard coal, etc. Most full freight cars are transported by dedicated trains. But, for empty car distribution, the efficiency still remains questionable because the distribution plan is manually developed by dispatchers. In this study, we investigated distribution models delineated in the KTOCS system which was developed by KORAIL as well as mathematical models considered in the state-of-the-art. The models are based on optimization models, especially the network flow model. Here we suggest a new optimization model with a framework of the column generation approach. The master problem can be formulated into a transportation problem with additional constraints. The master problem is improved by adding a new edge between the supply node and the demand node; this edge can be found using a simple shorted path in the time-space network. Finally, we applied our algorithm to the Korean freight train network and were able to find the total number of empty car kilometers decreased.
Recently, in the field of rail freight transportation, the number of trains dedicated for shippers has been increasing. These dedicated trains, which run on the basis of a contract with shippers, had been restricted to the transportation of containers, or so called block trains. Nowadays, such commodities have extended to cement, hard coal, etc. Most full freight cars are transported by dedicated trains. But, for empty car distribution, the efficiency still remains questionable because the distribution plan is manually developed by dispatchers. In this study, we investigated distribution models delineated in the KTOCS system which was developed by KORAIL as well as mathematical models considered in the state-of-the-art. The models are based on optimization models, especially the network flow model. Here we suggest a new optimization model with a framework of the column generation approach. The master problem can be formulated into a transportation problem with additional constraints. The master problem is improved by adding a new edge between the supply node and the demand node; this edge can be found using a simple shorted path in the time-space network. Finally, we applied our algorithm to the Korean freight train network and were able to find the total number of empty car kilometers decreased.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구는 기존 연구 문헌 및 KTOCS 시스템에서 구현된 화차배분 모형의 문제점을 극복할 수 있는 새로운 최적화 모형 및 이에 대한 해법을 제시하는데 목적이 있다.
따라서 영차 수송은 화차 배분 최적화 모형에 의한 배분의 필요성이 매우 낮으며, 최적화 모형을 활용하여 영차를 배분하더라도, 영차의 적재시간의 변동, 당일 수요의 변동성 등으로 인해 최적화 모형을 통해 구성된 영차배분은 현실성이 떨어질 개연성이 있다. 본 연구에서는 영차의 열차별 배정은 제외하고 공화차만을 대상으로 역별, 열차별 배분을 시행하여 최적화 모형을 통해 구성된 해의 현실성을 보다 높이고자 한다.
가설 설정
(2008)[5]의 연구는 영차의 배분은 고려하지 않고 공화차의 배분만을 고려하였다. 따라서 이들의 연구에서는 영차의 경로는 더 이상 고려사항이 아니며, 공화차의 수요량과 공급량은 최적화 모형의 입력 값으로 미리 주어졌다고 가정하였다. [4]에서는 네트워크 크기를 줄이기 위해 화차들이 공동으로 사용할 수 밖에 없는 아크의 집합을 하나의 클러스터(cluster)로 구성하여 새로운 축소된 형태의 네트워크를 구성한 후, 타부 탐색(Tabu Search)을 적용하였다.
열차별 여유 용량은 실제 열차별로 수송한 공화차 수송량을 용량으로 간주할 수도 있지만, 소량의 공화차 수송일 경우, 실제 수송량보다 많은 공화차를 수송할 수 있었다고 가정하는 것이 합리적이므로 ① 열차별 실제 공화차 수송량을 여유 용량으로 간주하거나 ② max{10, ①}로 설정하여 10보다 작은 공화차 수송량을 갖는 열차의 경우 10개의 추가적인 공화차 수송 용량을 갖는다고 간주하거나 ③모든 열차의 공화차 여유 용량이 30으로 가정한 세 가지 경우에 대해 실험하였다. 마지막으로 모든 열차의 운행 비용은 열차 주행 거리로 설정하여, 식 (1)의 목적함수값은 공화차·km + 근거리 열차 설정비용이 된다.
초기 주문제에 대해서는 현재 발견된 수요지-공급지간 경로가 없으므로, 가상의 노드로부터 모든 수요를 충족시킨다고 가정하고 가상의 노드를 설정한다. 이 노드로부터 나가는 아크는 무한대의 용량과 무한대의 비용을 갖는다.
제안 방법
근거리 열차의 설정 비용(ft)이 10000일 때와 100일 때로 구분하여 70개의 후보 근거리 열차 중 몇 개의 근거리 열차가 설정되는지를 비교 실험하였다. 실험결과 ft =1000일 경우에는 43대의 근거리 열차가 설정되었고 화차·km의 경우 1,000,452 km가나왔으며, 근거리 열차 설정비용이 훨씬 작아 근거리 열차가 보다 많이 설정될 수 있는 ft =100인 경우에는 51개의 근거리 열차가 설정되었고 그 때의 화차·km는 Table 6의 ②의 결과와 같음을 볼 수 있다.
위 주문제에서 수요지와 공급지가 200개 이상만 되면, 수요지-공급지 쌍에 대해 모든 가능한 열차 경로를 찾아 그것을 아크로 설정할 경우, 매우 많은 변수 및 시간을 필요로 한다. 본 연구에서는 모든 아크를 미리 만들지 않고, 주문제의 목적함수를 개선시킬 수 있는 제한된 개수의 아크만을 생성하는 열생성 알고리듬을 적용하고자 한다. 열생성에 사용되는 부문제를 구성하기 위해 주문제의 식(2), 식(3), 식(4,5)에 대한 쌍대 변수를 πi, πj, #라 하고 yt를 실수로 완화할 경우 주문제의 최적 조건은 아래와 같다.
본 절에서는 KTOCS시스템에 포함된 화차 배분 모형을 비판적으로 검토하고, 해외 연구 문헌에서 제시되어 있는 몇 가지 최적화 모형을 파악하고자 한다.
대상 데이터
또한 이 공화차 수요량을 수송하기 위해, 해당 기간 동안 공화차 수송에 관여한 열차는 총 455개 열차이며, 실험을 위해 455개 열차의 운행 실적을 기초로 열차 스케줄을 작성하였다.
우선 실제 사례와의 비교 분석을 위해 2016년 5월 4일부터 5월 6일까지 3일간의 공화차 운송 내역을 분석하였다. 분석 결과 총 116개 역에서 연결 해방 작업이 이루어졌으며, 총 7733개의 공화차 연결-해방 작업이 이루어졌다. 이러한 공화차 연결-해방 내역으로부터 공급량과 수요량을 도출하기 위해서는 중복되는 연결-해방 차수를 제외해야 되는데, 예를 들어 아래와 같은 연결 해방 내역이 주어져 있을 때, 의왕에서의 6량의 연결-해방 작업은 공급량과 수요량에 영향을 미치지 않아야 한다.
본 절에서는 최적화 모형 및 알고리듬의 성능을 확인해 보기 위해 다음과 같은 과정을 통해 예제를 도출하였다. 우선 실제 사례와의 비교 분석을 위해 2016년 5월 4일부터 5월 6일까지 3일간의 공화차 운송 내역을 분석하였다. 분석 결과 총 116개 역에서 연결 해방 작업이 이루어졌으며, 총 7733개의 공화차 연결-해방 작업이 이루어졌다.
이러한 도중 입환역에서의 연결-해방 작업을 제외한 공화차 종류별 공급량과 12시간 단위로 설정된 향후 3일간의 수요량의 합을 도출하면 Table 4와 같고, 총 수송해야 하는 공화차 수요량은 6,875개이다. 공급시간, 공급역에 따라 최종 공급 노드의 수는 216개이고, 수요지 노드의 수는 405개가 생성되었다.
이론/모형
단계4. 현재까지 만들어진 아크들로 구성된 주문제에 대해 분지한계법(branch-and-bound)을 적용하여 해를 구함.
본 연구에서 고려하는 최적화 모형은[5]에 제시된 수송 모형을 변형한 추가 제약이 있는 수송 모형을 활용한다. 공화차의 공급 노드는(공화차의 종류, 공화차의 위치(역), 공급 가능한 시간, 공급 가능량) 등 네 가지 속성으로 구성되고, 공화차의 수요 노드는(공화차의 종류, 공화차의 위치(역), 납기 시간(due date), 수요량) 등 네 가지 속성으로 구성된다.
성능/효과
결론적으로, 영차의 경우 대부분의 수요량에 대해 열차 경로가 주어지고 있어 최적화 모형을 통한 영차의 열차 배정 필요성은 매우 낮으며, 회귀시간 내의 계획 기간을 고려할 경우, 계획 시점에서 파악한 공화차의 수요량과 공급량은 계획 기간 내에 상태 변환을 일으키지 않으므로, 회귀 시간 내의 계획 기간 동안의 공화차 배분 최적화 모형은 영차의 흐름을 고려할 필요가 없다. 또한 공화차의 수송량의 상당 부분이 현시각 형태의 근거리 열차로 운행되고 있어, 임의적인 근거리 열차 설정을 줄이기 위해서는 공화차의 배분과 근거리 열차 설정을 동시에 다룰 수 있는 최적화 모형이 필요하다.
본 연구에서는 열차별 용량 제약 및 근거리 열차 설정 변수를 가지고 있는 변형된 수송 문제를 이용한 공화차 배분 최적화 모형 및 열생성에 기초한 해법을 제시하였고, 실험을 통해 공화차 운행 거리나 공화차 수송을 위한 근거리 열차 설정 비용 측면에서 보다 효율적인 공화차 배분이 가능함을 보였다.
앞에서 서술했듯이 세 가지 여유용량에 대해 목적함수값의 변화를 살펴보면 여유용량이 증가함에 따라 화차·km가 점차 증가함을 알 수 있다. 이는 본 연구에서 제시하는 알고리즘이 제대로 작동하고 있다는 하나의 증거이며, 여유용량을 ②와 같이 설정할 경우, 최적화 모형의 수행시간은 약 5분, 생성된 아크의 수는 5,579개, 기존 화차·km보다 7.7%정도의 개선된 화차·km를 얻을 수 있었다.
후속연구
그러나 본 연구에서 제시한 실험 결과는 실적 데이터로부터 도출한 최종적인 수요량과 공급량이라는 측면에서, 현실에서 발생하는 부득이한 공화차의 우회 수송이나 중복 수송을 반영하지 않아 최적화 모형을 이용해 도출한 해가 기존 실적 보다는 당연히 좋을 수 밖에 없다는 한계를 가지고 있다. 본 연구에서 제시한 해법의 유용성을 판단하기 위해서는 현실에서 화물 사령에 의해 이루어지고 있는 공화차 배분과 최적화 모형을 통한 공화차 배분과의 직접적인 비교 분석이 필요하다.
그러나 본 연구에서 제시한 실험 결과는 실적 데이터로부터 도출한 최종적인 수요량과 공급량이라는 측면에서, 현실에서 발생하는 부득이한 공화차의 우회 수송이나 중복 수송을 반영하지 않아 최적화 모형을 이용해 도출한 해가 기존 실적 보다는 당연히 좋을 수 밖에 없다는 한계를 가지고 있다. 본 연구에서 제시한 해법의 유용성을 판단하기 위해서는 현실에서 화물 사령에 의해 이루어지고 있는 공화차 배분과 최적화 모형을 통한 공화차 배분과의 직접적인 비교 분석이 필요하다.
질의응답
핵심어
질문
논문에서 추출한 답변
철도 화물 수송 효율은 어떻게 달성되는가?
일반적으로 철도 화물 수송 효율은 화차 수송을 위한 화물 열차의 설정 및 이동 경로에 따른 열차 설정 및 수송 비용을 최소화할 뿐만 아니라, 역에서의 화차 처리에 따른 시간 및 비용을 최소화함으로써 달성된다. 이러한 비용들 중에서도 철도 화물 수송의 여건에 따라 주안점을 두는 부분이 달라지는데, 예를 들어 화물 수송량의 비중이 매우 높은 미국의 경우 흔히 Blocking 계획[2]이라 불리는 도중 입환 비용 최소화에 초점을 둔다.
KTOCS 시스템에 포함된 최적화 모형이 영차와 공화차의 흐름을 최적화하기위해 적용한 방법은?
이를 최적화 모형에 그대로 반영하여 네트워크를 구성할 경우, 영차와 공화차의 흐름을 정의하기 위한 변수의 개수가 너무 많아 통상적인 해법으로는 해를 구할 수 없다. 그래서 KTOCS 시스템은 영차와 공화차의 네트워크를 구분하고 각각의 네트워크를 다시 각 품목별(영차의 경우 품목, 공화차의 경우 화차 종류별) 네트워크로 분해하는 방법을 활용하였다[1]. 먼저 영차의 각 품목별 경로는 분해된 네트워크상에서의 최단경로(shortest path) 모형을 통해 구한다. 영차의 경로가 정해지면 영차의 하화 시점으로부터 일정 시간이 지난 시점이 공화차의 공급지가 되고, 영차의 적재 시점은 공화차의 수요지가 된다는 점을 이용하여, 영차의 모든 품목의 경로가 정해지면 공화차의 수요지 및 공급지가 정해지고, 역시 최단경로 모형에 의해 개별 공화차 품목에 대한 수송 경로를 확정하게 된다.
KTOCS 시스템은 어떻게 구성되어 있는가?
KTOCS 시스템은 Fig. 1과 같이 철도 화물의 중장기 수요 예측을 위한 화물운송계획 모듈(Forecasting), 수요를 처리하기 위한 최적의 화물열차 구성을 위한 화물열차계획 모듈(operating plan), 영차/공차의 열차 별 역별 배분을 위한 화물관제 모듈(car dispatching plan), 마지막으로 철도화물 수송 물량의 예약제 변환을 위한 화물예약관리 모듈(reservation system) 등으로 구성되어 있다[1]. 이 중에서도 철도 화물 수송의 효율성과 직접적으로 연결되는 모듈은 영차/공화차의 열차 별, 역별 배분을 위한 화물관제 모듈로서, 일반적으로 이러한 모형을 화차 배분(freight car distribution)문제라고 한다.
참고문헌 (7)
Korea Railroad (2009) Development of Optimization System for Rail Freight Transportation. Interim report, Korea Railroad.
R. K. Ahuja, K.C. Jha, and Jian Liu (2007) Solving real-life railroad blocking problems, Interfaces, 37(5), pp.404-419
A. Fukasawa, M. Aragao, O. Porto and E. Uchoa (2002) Solving the Freight Car Flow Problem to Optimality, Electronic Notes in Theoretical Science, 66(6), pp. 42-52.
M. Joborn, T. G. Crainic, M. Gendreau, K. Holmberg and J. T. Lundgren (2004) Economies of Scale in Empty Freight Car Distribution in Scheduled Railways, Transportation Science, 38(2), pp. 121-134.
A. K. Narisetty, J. P. Richard, D. Ramcharan, D.M. Murphy, G. Minks and J. Fuller (2008) An Optimization Model for Empty Freight Car Assignment at Union Pacific Railroad. Interfaces, 38(2), pp. 89-102.
B. Lee, D. Won, C. Ahn, B. Park (2016) Status of empty freight car operation, Proceedings of the Korean Railway Association Fall Conference, Jeju, pp. 85-93
O. Ha, K. Kim, H. Kong, S. Choi (2013) Calculation of appropriate return days for securing the objectivity of judgment of wagon quantity required, Proceedings of the Korean Railway Association Fall Conference, Daegu, pp. 108-115.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.