Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)
Journal of Society of Korea Industrial and Systems Engineering Vol.41 No.4 pp.238-247
DOI : https://doi.org/10.11627/jkise.2018.41.4.238

Crane Scheduling Considering Tenant Service Time in a Rail-Road Transshipment Yard : Case of the Uiwang ICD

Kwang-Tae Kim*, Hyo-Jeong Kim**, Dong-Hoon Son***, Jin-Myeong Jang***, Hwa-Joong Kim***†
**School of Industrial Management Engineering, Korea University, Entrue Consulting, LG CNS
****Hi-Tech Business Division, LG CNS
***Graduate School of Logistics, Inha University
Corresponding Author : hwa-joong.kim@inha.ac.kr
12/11/2018 21/12/2018 24/12/2018

Abstract


This paper considers the problem of scheduling loading and unloading operations of a crane in a railway terminal motivated from rail-road container transshipment operations at Uiwang Inland Container Depot (ICD). Unlike previous studies only considering the total handling time of containers, this paper considers a bi-criteria objective of minimizing the weighted sum of the total handling time and tenant service time. The tenant service time is an important criterion in terms of terminal tenants who are private logistics companies in charge of moving containers from/to the terminal using their trucks. In the rail-road container shipment yard, the tenant service time of a tenant can be defined by a time difference between beginning and finishing loading and unloading operations of a crane. Thus, finding a set of sequences and time of the crane operations becomes a crucial decision issue in the problem. The problem is formulated as a nonlinear program which is improved by linearizing a nonlinear constraint in the model. This paper develops a genetic algorithm to solve the problem and performs a case study on the Uiwang ICD terminal. Computational experiment results show that the genetic algorithm shows better performance than commercial optimization solvers. Operational implications in terms of tenants are drawn through sensitivity analyses.



철도-육상트럭 환적지에서의 입주사 작업시간을 고려한 크레인 적하작업 스케줄링 : 의왕ICD 사례

김광태*, 김효정**, 손동훈***, 장진명***, 김화중***†
**고려대학교 산업경영공학부, LG CNS Entrue컨설팅
****LG CNS 하이테크사업부
***인하대학교 물류전문대학원

초록


    Jungseok Logistics Foundation

    1. 서 론

    정부는 철도물류산업을 국가발전의 원동력으로 인식 하고 도로 및 해상운송 화물을 철도운송 화물로 전환하 기 위한 전환 물류(modal shift), 물류시설 확충과 재정지 원을 통한 인센티브 제공 등 다양한 정책을 개진하고 있 다. 하지만 정부의 이러한 노력에도 불구하고 국내 철도 화물 물동량 증가의 구체적인 성과가 나타나고 있지 않 으며, 다른 운송 수단과의 화물유치 경쟁에서도 두각을 나타내지 못하고 있다. Moon and Lee[11]에 의하면 철도 화물의 물동량 증대를 위한 근본적 방법 중 하나는 화주 의 철도화물 운송서비스에 대한 선호도를 제고시키는 것 임을 밝히고 있다. 현재 국내 철도화물 물동량의 상당 부 분이 철도화물 터미널 입주사의 철도 운송서비스에 대한 수요에 기인한다. 따라서 철도화물 물동량 증대를 위한 정책이 효과를 거두기 위해서는 터미널 입주사에 대한 철도화물 운송서비스의 이용만족도를 제고시킬 필요가 있다. 하지만 시설투자와 인센티브 정책을 통한 재정지 원은 막대한 공적자금 투입과 정책 시행 기간이 필요하 다[11]. 이러한 이유로 실제 철도화물 터미널 현장에서는 비교적 적은 투자금으로 정책 시행의 효과를 단기간에 유도할 수 있는 터미널 입주사 지향적인 터미널 운영정 책이 고려되고 있다. 하지만 터미널 운영정책의 변화는 터미널 운영효율성의 극대화를 지향하는 터미널 운영사 의 입장과 기업의 이윤 극대화를 지향하는 터미널 입주 사의 이해관계를 포괄적으로 고려해야 한다는 측면에서 정책 시행의 어려움이 있다.

    의왕 내륙컨테이너기지(ICD, inland container depot)는 수도권 지역에 대한 소화물 물류 서비스와 무역화물을 수 출입 항만과 내륙거점으로의 운송서비스를 제공하는 우리 나라 최대 규모의 물류시설 중 하나이다. 터미널 내에는 약 15개의 터미널 입주사가 있으며, 입주사는 개별 화주로 부터 FCL(full container load) 화물 또는 LCL(less than container load) 화물을 인도 받아 컨테이너 단위로 혼재 (consolidation) 작업을 수행한다. 이후 화주의 운송 요청과 운송수단의 운임경쟁력을 고려하여 종합적인 물류서비스 제공을 통해 이윤을 창출한다. 이 과정에서 철도 운송서비 스는 터미널 입주사의 컨테이너를 부산항 및 내륙거점으 로 운송하는 데에 중요한 역할을 담당하고 있다.

    터미널 입주사로부터 도로로 운송된 컨테이너가 철도 운송서비스를 통한 운송으로 연계되기 위해서는 철도화 물 터미널 열차-육상트럭 환적지에서 트랜스퍼 크레인 (이하 철송 크레인으로 통칭)의 컨테이너 환적작업이 필 요하다. 환적작업은 다른 터미널에서 열차에 실려온 컨 테이너를 하역하거나 터미널 입주사로부터 운송 요청을 받은 컨테이너를 적재하는 일련의 작업을 의미한다. 따 라서 철송 크레인의 적재 및 하역(적하) 작업 스케줄은 철도화물 터미널의 운영효율성뿐만 아니라 터미널 입주 사의 컨테이너 처리작업 활동에도 영향을 미친다. 일반 적으로 터미널 운영사는 철도화물 터미널의 운영효율성 을 개선하기 위해 터미널 입주사가 운송을 요청한 컨테 이너를 최대한 빠르게 처리하는 데에 초점을 두고 있다. 반면에 터미널 입주사는 컨테이너 운송과 보관에 필요한 물류비를 절약하기 위해 터미널 운용사로 하여금 자사가 운송을 요청한 컨테이너를 단기간에 처리해주길 원한다. 하지만 철송 크레인의 운영효율성 개선과 터미널 입주사 의 컨테이너 처리시간 단축은 서로 상충관계에 놓여있으 며, 이러한 이해관계를 고려한 철송 크레인 적하작업 스 케줄링은 매우 복잡하다[7]. 따라서 이와 같은 이해관계 를 고려한 철송 크레인 적하작업 스케줄링 방법론 개발 은 현재 의왕ICD를 비롯하여 우리나라 철도화물 터미널 이 직면한 문제에 대한 유력한 해결책이 될 수 있다.

    이러한 배경 하에서 본 연구는 철송 크레인의 운영효 율성 향상과 개별 터미널 입주사의 컨테이너 처리시간 단축을 동시에 달성할 수 있는 철송 크레인 적하작업 스 케줄링 최적화 문제를 다룬다. 구체적으로 기술하면, 본 문제의 목적함수는 철송 크레인의 운영효율성을 추구하 는 철송 크레인 작업소요시간과 개별 터미널 입주사의 컨테이너 처리시간 단축을 추구하는 개별 입주사 작업완 료시간 범위의 가중합의 최소화이다. 본 문제에 대한 비 선형계획모형을 제안하고, 이를 선형화 절차를 통해 혼 합정수계획모형으로의 변경을 제안한다. 또한 본 문제를 효율적으로 해결할 수 있는 유전 알고리즘(GA, genetic algorithm)을 제안하고 민감도분석을 통해 운영 시사점을 도출한다.

    본 연구는 서론을 포함하여 총 7개의 장으로 구성된다. 제 2장에서는 철송 크레인 적하작업 스케줄링 문제에 대 한 선행연구를 조사하고, 본 연구의 차별성을 설명한다. 제 3장은 의왕ICD의 철송 크레인 운영현황을 소개하고 철송 크레인 적하작업 스케줄링 문제를 정의하고 설명한다. 제 4장은 비선형계획모형과 혼합정수계획모형을 제시하 고 제 5장에서는 유전 알고리즘을 제안한다. 제 6장은 의 왕ICD에 입주한 입주사의 컨테이너 적하 기록을 기초로 제안한 휴리스틱 알고리즘의 성능을 평가하고 민감도 분 석의 결과를 논의한다. 마지막으로 제 7장은 본 연구의 의의와 후속 연구에 관해 기술한다.

    2. 선행 연구

    Boysen and Fliedner[3]는 철도화물 터미널에서 크레인 운영 문제를 다섯 가지 유형으로 구분하였다.

    • (a) 열차간 환적을 위한 선로 상의 슬롯 운영문제

    • (b) 화차에 대한 컨테이너 적재위치 결정문제

    • (c) 열차의 선로배분 결정문제

    • (d) 컨테이너 처리작업에 대한 크레인 할당문제

    • (e) 크레인 적하역을 위한 이동순서 결정문제

    본 연구는 기존 연구에서 분류한 유형 (b)와 (e)를 통합 적으로 고려하는 의사결정문제를 다룬다. 철도화물 터미 널의 의사결정문제를 다룬 연구 중에서 본 연구와 유사한 문제를 다룬 연구는 극히 제한적이었다. 그로 인해 문헌 고찰은 연구자가 판단하기에 본 연구와 관련성이 높은 연 구를 중심으로 수행하였다. Souffriau et al.[14]은 열차간 컨테이너 환적작업에 대한 복수의 철송 크레인 일정계획 문제를 다루었으며, 이 문제를 열차의 목적지 결정문제, 컨테이너의 적재위치 결정문제, 그리고 환적작업순서 결 정문제로 나누어 해결하였다. 열차의 목적지 결정문제는 탐욕적 탐색(greedy search)방법을 이용하여 해를 도출하 였으며, 컨테이너의 적재위치 결정문제는 상업용 최적화 소프트웨어를 활용하여 해결하였다. 마지막으로 열차 간 컨테이너의 환적작업순서 결정문제는 가변이웃하강(variable neighborhood decent) 휴리스틱을 활용하여 해결하였다. Heshmati et al.[4]은 환적순서를 결정하기 위해 이산사건 시뮬레이션(discrete-event simulation)을 활용하였다. 이후 작업시간 최소화를 위한 컨테이너 적재위치와 철송 크레 인의 이동 및 적하 작업 순서를 추가로 결정하였다. 앞서 제시한 선행연구들은 크레인의 작업시간 최소화를 목표 로 크레인의 운영에 대한 의사결정 문제를 다루었다. 하 지만 일부 선행연구들 가운데 다소 차별적인 목적함수를 구성하여 크레인 운영에 대한 의사결정문제를 다룬 연구 들도 있다. Kim and Park[6]는 철송 크레인 적하작업의 총 소요시간과 개별 크레인의 총 작업시간의 합을 최소화하 는 목적하에 컨테이너 터미널 내에서의 크레인의 작업순 서와 크레인의 작업 구간 할당문제를 다루었다. 이들은 주어진 의사결정문제에 대한 해법으로 분지한계법(branch and bound algorithm)과 휴리스틱 알고리즘을 제안하였다. Moccia et al.[10]은 Kim and Park[6]이 다룬 문제에 대해 분지절단법(branch & cut algorithm)을 제안하고, 최적해를 도출하였다. Sammarra et al.[12]은 크레인의 총 작업시간과 크레인 완료시간의 가중합을 최소화하는 것을 목적함수 로 하였으며 이에 대한 해법으로써 타부 탐색(tabu search) 방법론을 제안했다. Bostel and Dejax[2]은 철도화물 터미 널에서 적재 및 환적 예정인 컨테이너를 운송 대기 중인 화물열차에 배분하는 의사결정문제를 연구하였다. 이에 대하여 이들은 해당 컨테이너들을 대기 중인 열차에 할 당하는 비용을 최소화하는 목적식을 제안하였다. 이후 해당 문제를 해결하기 위해 휴리스틱 알고리즘을 제안했다. Kozan[8]은 복합운송터미널에서 환적화물에 대해 처리시 간과 크레인의 이동시간을 최소화하는 수리모형을 제안 했다. Bierwirth and Meisel[1]은 터미널에서 철송 크레인 의 컨테이너 적하작업에 대한 스케줄링 문제를 다루었으며, 이에 대한 해법으로 분지한계법을 제안하였다. Kim and Kim[7]은 철도화물 터미널에서 터미널 입주사의 작업완 료시간 범위와 철송 크레인의 총 작업시간의 가중합을 최 소화하는 목적함수를 기반으로 철송 크레인의 하역작업 스케줄링 문제를 다루었다. 아울러 본 문제를 효율적으로 풀어내기 위한 해법으로 메타휴리스틱을 제안하였다. Song [13]은 유연생산시스템에서의 생산작업의 순서를 결정하는 문제를 풀기 위하여 외판원 문제에서 활용되는 휴리스틱 기법을 활용하였다. 이를 통해 서로 다른 작업제품에 대 한 일관적인 작업의 횟수를 최소화하는 생산순서를 결정 하는 해를 도출하였다. Lee[9]는 물류 서비스 향상을 위한 배차계획 시스템의 설계 및 구현을 연구하였다. 본 연구 에서는 경로문제와 배차계획을 동시에 고려함으로써 차량 의 동선을 설계한 후 주어진 경로에 차량을 할당하는 문제 를 고려하는 알고리즘을 개발한 후, 성능을 평가하였다.

    현황 분석과 선행연구조사를 토대로 본 연구는 다음 과 같은 연구의 의의가 있다고 판단된다. 첫째, 본 연구 는 Kim and Kim[7]의 연구를 확장하여 적재와 하역을 동시에 고려하는 철송 크레인 스케줄링 문제를 다룬다. 또한 적재 컨테이너의 화차 할당을 결정하는 문제를 추 가 고려함으로써 선행연구에 대한 차별성을 확보하였다. 둘째, 터미널 운영사와 터미널 입주사의 입장을 동시에 고려한 철송 크레인 스케줄링 문제를 다룬다. 이를 위해 본 연구는 기존 선행연구에서 고려된 바 없었던 새로운 목적함수 기준척도(criterion)를 제시한다. 마지막으로 실 제 의왕ICD 터미널 입주사로부터 획득한 컨테이너 적하 작업 목록을 토대로 연구 결과의 시사점을 논의함으로써 의왕ICD 내에서의 터미널 입주사 지향적인 철송 크레인 운영정책 개발에 대한 대안을 제시한다.

    3. 의왕ICD 터미널 운영과 문제 정의

    <Figure 1>은 의왕ICD의 조감도를 보여주고 있다. 의 왕ICD는 두 개의 터미널로 구성되어 있으며 각 터미널에 는 오봉역과 연결된 선로를 통해 철송 서비스가 이루어질 수 있도록 터미널이 조성되어 있다. 제 1터미널에는 선로 가 총 세 개가 있으며 각 선로는 세 개의 하위 선로로 분 리된다. 이때 하위 선로는 열차-육상트럭의 환적지를 관 통한다. 각 열차-육상트럭의 환적지는 하나의 철송 크레 인이 배치되어 열차와 트럭 간의 컨테이너 적하작업을 지 원한다. 앞서 언급한 바와 같이 이때 처리되는 컨테이너 는 터미널 입주사로부터 운송 요청을 받은 것이다. 일반 적으로 하나의 화물열차에 대해서 2~6개의 터미널 입주 사가 운송을 요청한 컨테이너가 처리되며, 철송 크레인의 적하작업 스케줄은 의왕ICD 터미널 작업자에 의하여 수 립되고 있다. 화주, 터미널 입주사, 터미널 운영사의 관계 에 대해 보다 구체적인 설명은 Kim and Kim[7]에 소개되 어 있다.

    <Figure 2>는 각 열차-육상트럭 환적지를 개념적으로 도식화한 것이다. 해당 그림에는 세 개의 하위 선로에 세 대의 서로 다른 열차가 대기하며, 철송 크레인에 의해 컨테이너의 환적작업이 완료될 때까지 기다리고 있다. 실제 현장에서는 상황에 따라 다수의 열차를 대상으로 철송 크레인의 컨테이너 적하작업이 수행되지만, 일반적 으로는 터미널 운영사가 열차의 출발 약 4~5시간 전에 컨테이너 적하 목록을 확정하고 하나의 열차에 대해 컨 테이너 환적작업을 수행한다. 의왕ICD의 터미널 입주사 는 철송 크레인의 환적작업이 수행될 때, 자사가 보유한 장비를 활용하여 컨테이너 운송과 적재 작업을 수행한 다. 이러한 이유로 <Figure 2>과 같이 컨테이너 적하작업 이 이루어지는 동안 다수의 터미널 입주사 트럭이 환적 지에서 대기하거나 철송 크레인의 작업위치에 따라 이동 하며 컨테이너(해당 그림에서 검은색으로 표시)를 운송 하게 된다. 현재 의왕ICD의 철송 크레인 적하작업 스케 줄은 크레인 작업자의 경험에 의존하고 있으며, 현장 상 황에 따라 근시안적으로 철송 크레인 적하작업 스케줄이 도출되기도 한다. 이러한 환경에서 크레인 운영자의 판 단에 따라 터미널의 운영효율성과 터미널 입주사의 컨테 이너 처리완료시간을 동시에 고려할 수 있는 최적의 철 송 크레인 적하작업 스케줄을 도출하는 것은 어렵다. 그 결과 터미널 입주사의 컨테이너 처리비용이 증가하고 터 미널 운영효율성이 저하되는 문제가 동시에 나타나고 있 다고 판단된다. 이에 본 연구는 터미널의 운영효율성과 터미널 입주사의 컨테이너 처리 시간이 철송 크레인의 작업 스케줄을 매개로 동시에 통제할 수 있다는 점에 착 안하였다. 이를 토대로 본 연구는 터미널 입주사의 작업 완료시간 범위라는 새로운 기준척도을 제시한다. 또한 새롭게 제안하는 기준척도를 활용하여 철송 크레인 스케 줄로부터 터미널의 운영효율성과 터미널 입주사의 컨테 이너 처리 시간의 변화추이를 평가하고 이에 대한 시사 점을 논하고자 한다. 이를 위해 본 연구는 다음의 기본적 인 가정사항을 전제로 수리모형을 제안한다.

    • 화물열차의 화차에는 한 개의 컨테이너만 적재할 수 있다.

    • 컨테이너 적재를 위해 화차는 동일 목적지 기준으로 연속적으로 배치되어 있다.

    • 하역 예정 컨테이너의 적재 위치는 철송 크레인 스케 줄 수립 이전에 이미 알고 있다.

    • 적재 예정 컨테이너는 해당 목적지로 향하는 화차에만 적재가 가능하고, 해당 화차의 하역 컨테이너가 내려 지면 적재할 수 있다.

    4. 수리모형

    수리모형에서 사용되는 집합, 파라미터 및 결정변수를 정의하면 다음과 같다.

    집합

    • IL 적재 컨테이너의 집합

    • IU 하역 컨테이너의 집합

    • I 컨테이너의 전체 집합, I = ILIU

    • Ip 화차 p에 적재 가능한 컨테이너의 집합

    • K 입주사의 집합

    • P 화차의 집합

    • Pi 컨테이너 i를 적재할 수 있는 화차의 집합

    파라미터

    • hi 컨테이너 i의 적하역 단위 소요시간

    • pi 하역 컨테이너 i가 적재된 화차

    • tmn 화차 m에서 화차 n으로 크레인 이동시간

    • t 인접한 화차 간 크레인 이동시간

    • dt 크레인 작업 최대 허용시간

    • M 임의의 큰 수

    결정변수

    • Yi 컨테이너 i의 작업시작시간

    • Xip 만약 컨테이너 i가 화차 p에 적재 또는 하역하면 1, 그렇지 않으면 0

    • Zij 만약 컨테이너 i를 작업하고 컨테이너 j를 작업하면 1, 그렇지 않으면 0

    • Lijmn 만약 컨테이너 i를 화차 m 에서 적하역하고 컨테이너 j를 화차 n에서 적하역하면 1, 그렇지 않으면 0

    • Tij 컨테이너 i의 작업시작부터 컨테이너 j의 작업완료 까지 소요시간

    • Sk 입주사 k의 작업시작시간

    • Fk 입주사 k의 작업완료시간

    • E 철송 크레인의 총 작업소요시간

    앞서 제시한 기호를 바탕으로 철송 크레인 적하작업 스케줄링 문제를 모형화 하면 다음과 같다.(13)(14)

    [ NMIP ] Minimize α k K ( F k S k ) + ( 1 α ) E

    subject to

    p P i X i p = 1 i I L
    (1)

    i I P X i p 1 p P
    (2)

    X i p Z j i i I L , p P i , j I U I p
    (3)

    X i p = 1 i I U , p P i
    (4)

    X i m X j n = L i j m n i , j I , m , n P
    (5)

    Z i j + Z j i = 1 i , j I , i j
    (6)

    Y i + h i + m P i n P j t m n L i j m n Y j + M ( 1 Z i j ) i , j I , i j
    (7)

    Y i + S k k K , i I k
    (8)

    Y i + h i F k k K , i I k
    (9)

    F k E k K
    (10)

    E d t
    (11)

    Y i 0 , T i j 0 i , j I
    (12)

    S k , F k 0 k K
    (13)

    X i p , Z i j { 0 , 1 } i , j I , p P
    (14)

    L i j m n { 0 , 1 } i , j I , m , n P
    (15)

    수리모형의 목적함수는 개별 입주사의 작업완료시간 범위와 작업소요시간의 가중합을 최소화한다. 이때의 가 중치는 터미널 운영사가 결정하는 파라미터(control parameter) 로 컨테이너 총 작업시간과 터미널 입주사의 컨 테이너 처리시간의 중요도를 결정한다. 따라서 가중치 값은 터미널 운영사의 운영목표 및 터미널 운영현황에 따라서 달라질 수 있다. 식 (1)은 모든 적재 컨테이너는 반드시 화차에 적재해야 한다는 것이며, 식 (2)는 각 화 차는 최대 한 개의 컨테이너만 적재 가능한 것을 나타낸 다. 식 (3)은 동일 화차에서 하역 컨테이너가 처리되고 컨테이너를 적재할 수 있다는 것을 의미한다. 식 (4)는 모든 하역 컨테이너는 화차로부터 내려져야 하는 것을 의미한다. 식 (5)와 식 (6)은 컨테이너 작업의 선후관계를 나타내고, 식 (7)은 컨테이너 작업의 선후관계에 따른 각 컨테이너의 작업시간을 계산한다. 식 (8)~식 (9)는 입주 사별 컨테이너 작업 시작시간과 완료시간을 계산하기 위 해 활용된다. 식 (10)은 철송 크레인의 총 작업시간을 계 산한다. 식 (11)은 모든 작업은 열차의 출발시간 이전 혹 은 주어진 작업시간 내에 처리되어야 함을 의미한다. 식 (12)~식 (15)는 결정변수에 대한 제약이다.

    앞에서 제시한 NMIP 모형은 식 (5)로 인해 비선형계획 모형이므로 이를 선형화하고 식의 변경을 통해 새로운 MILP 모형을 제시하고자 한다. MILP 모형에서 기존 식 (5)를 식 (16)~식 (17)로 대체하여 비선형계획모형을 선형 화하였으며, 식 (7)을 식 (18)~식 (20)으로 재정의하였다. 식 (7)의 재정의는 일련의 선행실험을 통해 좋은 해를 도 출하는 것을 경험적으로 확인하였기 때문이다.(19)

    [ MILP ] Minimize α k K ( F k S k ) + ( 1 α ) E

    subject to

    X i m + X j n L i j m n 1 i , j I , m , n P
    (16)

    X i m + X j n 2 L i j m n 0 i , j I , m , n P
    (17)

    t ( n P j n X j n m P i m X i m ) T i j i , j I , i j
    (18)

    t ( m P i m X i m n P j n X j n ) T i j i , j I , i j
    (19)

    Y i + h i + T i j Y j + M ( 1 Z i j ) i , j I , i j
    (20)

    and constraints (1)~(4), (7)~(14)

    5. 유전 알고리즘

    유전 알고리즘은 생물집단의 진화원리를 모방한 탐색 기법으로 Holland[5]가 제안하였다. 유전 알고리즘은 문 제의 해를 표현한 다양한 개체(individuals)로 이루어진 모집단을 (population)을 생성하여 여러 세대에 걸쳐 높 은 적합도(fitness)를 가진 개체(individual)를 반복적으로 재생산하며 최적해 및 근사해를 탐색한다. 각 장에서는 철송 크레인 적하작업 스케줄링 문제를 해결하기 위해 제안한 유전 알고리즘의 연산 과정에 대해 소개한다.

    5.1 초기해 생성 및 적합도 평가

    제안하는 유전 알고리즘의 염색체는 유전자에 해당하 는 컨테이너를 일련의 정수로 표현하였고, 작업 순서와 적재 위치를 동시에 표현하기 위해 전반부는 컨테이너의 작업순서, 후반부는 적재 컨테이너의 위치로 구분하였다. 초기해는 임의생성방법을 통해 모집단을 생성하였다. 예 를 들어 컨테이너 15개의 작업 순서와 적재 컨테이너 5 개의 적재 위치를 결정할 경우 1~15사이 정수와 1~5사 이의 정수를 각각 중복되지 않도록 임의로 나열하여 다 수의 개체를 생성하여 모집단을 구성하였다. 생성된 부 모해가 실행 불가능해이면 제 5.2절에서 소개하는 교정 절차를 적용하여 실행가능해로 교정하였으며, 적합도 평 가는 제 4장에서 제시한 수리모형의 목적함수를 활용하 여 부모해(parent)와 자식해(offspring)의 적합도를 평가하 였다.

    적합도 평가에 대해 구체적으로 설명하면 다음과 같 다. <Figure 4>에서는 컨테이너 1, 4, 5가 하역되어야 하 며 음영으로 표기한 컨테이너 2, 3, 6은 열차에 적재해 야 한다. 이때 하역 컨테이너 1, 4, 5는 각각 화차 A, C, B에 각각 적재되어 있다(이때 A, B, C는 선적 컨테이너 의 목적지를 대표하며, 예시설명의 편의를 위해 화차는 A, B, C순으로 배치되어 있다고 가정함). 적재 컨테이 너 2, 3, 6의 경우 화차 B, A, C에 실려야 한다. 유전 알 고리즘에서 음영으로 표기되지 않은 하역 컨테이너의 배열 순서는 컨테이너 처리 작업 순서를 의미한다. 따 라서 하역 작업 기준으로 컨테이너 1, 5, 4순서로 작업 한다는 것을 의미한다. 유전알고리즘의 적합도 평가 값 을 도출 과정을 설명하면 다음과 같다. 설명의 편의를 위해 인접 화차간의 이동시간을 t초 라고 하고 컨테이 너 단위 적하시간을 p초 라고 가정하자. 화차 A에서 컨 테이너 1을 하역하고, 컨테이너 3을 적재한다. 화차 A 에서 작업한 총 소요시간은 2×p이다. 화차 A 작업 후 인접한 화차 B로 이동하여 컨테이너 5를 하역하고 컨테 이너 2를 적재한다. 화차 A와 B를 기준으로 작업한 총 소요시간은 화차 A의 작업시간, 화차 B의 작업시간, 화 차 A와 B의 이동시간으로 구성되며, 총 시간은 (2×p)+ (2×p)+t이다. 나머지 화차에 대한 작업시간도 이와 같은 방식으로 계산이 가능하다. 개별 입주사의 컨테이너 작 업시간은 입주사 기준으로 컨테이너의 작업시간을 분류 하여 컨테이너 처리 시작시간과 완료시간을 도출하였 다. 이러한 과정을 통해 본 연구는 철송 크레인 총 작업 시간과 입주사별 작업시간을 동시에 도출하고, 이후에 가중치 값을 반영함으로써 목적함수 값을 정확하게 계 산하였다.

    5.2 교차 및 돌연변이

    교차연산은 임의로 선별한 두 개의 부모해를 일점교차 (one-point crossover) 연산으로 자식해를 재생산하였다. 하 지만 일반적인 교차연산의 적용은 실행 불가능해를 생성 하게 된다. 첫 번째는 적재 및 하역 컨테이너의 처리 순 서 제약을 위반한 경우(infeasible case 1)로 동일 화차에서 하역 컨테이너가 처리되기 이전에 적재 예정 컨테이너를 적재하는 작업 순서를 구성한 경우이다. 이런 경우에는 전진수정방법(forward modification method)을 이용하여 실행 가능해로 교정하였다. <Figure 3>은 전진수정방법 의 예시로 음영으로 표시한 컨테이너는 적재 예정 컨테 이너이고 그렇지 않은 것은 하역 예정 컨테이너를 의미 한다. 예제에서 화차 B에 적재 컨테이너 2가 동일 화차 에 적재된 하역 예정 컨테이너 5번 보다 먼저 처리되는 실행 불가능해를 생성하게 된다. 이를 해결하기 위해 적재 컨테이너 2번의 후순위에 위치한 동일 화차의 하역 컨테 이너를 찾아서 순서를 변경하였다. 적재 컨테이너가 할 당된 화차는 적재 위치를 결정하는 유전 정보로 확인이 가능하다. 두 번째 실행 불가능해가 생성되는 경우(infeasible case 2)는 적재 컨테이너를 다른 목적지의 화차로 할당하 면 발생한다. <Figure 4>는 화차와 컨테이너의 목적지 불 일치가 발생하는 예시를 보여준다. 화차 A와 B는 동일 목적지로 향하며 해당 화차에 적재 가능한 컨테이너는 2 와 3이 있고, 다른 목적지로 향하는 화차 C에 적재 가능 한 컨테이너 6이 존재한다. 만약 컨테이너 6을 화차 B에 적재하면, 잘못된 목적지로 할당되어 실행 불가능해가 된다. 이런 경우에도 전진수정방법을 이용하여 실행 가 능해로 교정하였다.

    돌연변이(mutation)는 작업 순서와 화차 위치를 나타내 는 염색체에 대해 각각 임의로 컨테이너 두 개를 서로 교환하는 방법을 적용하였다. 돌연변이 연산에서도 실행 불가능해가 생성되면 전진수정방법을 적용하여 실행 가 능해로 교정하였다.

    6. 실험 설정 및 결과 분석

    이번 장에서는 제안한 유전 알고리즘의 성능 평가와 민감도 분석 결과를 소개한다. 유전 알고리즘의 성능 평 가와 민감도 분석은 의왕ICD 터미널 입주사로부터 획득 한 실제 컨테이너 적하목록을 토대로 수행하였으며, 적 하목록은 운영사가 크레인의 적하작업 스케줄을 수립하 기 위한 기초 자료이다. <Table 1>은 실험을 위해 사용 한 컨테이너 적하목록 데이터 10건이며, 입주사의 수, 하 역 및 적재 컨테이너의 수, 목적지의 수 그리고 입주사별 작업 요청 컨테이너의 수에 대한 정보를 수록하고 있다. 예시적으로 Data 2를 살펴보면 터미널 운영사는 총 22개 컨테이너(하역 컨테이너 12개, 적재 컨테이너 10개)에 대 한 철송 크레인 적하작업 스케줄을 수립해야 하는 것을 의미한다. 철송 크레인에 의해 처리되는 컨테이너는 4개 의 터미널 입주사가 운송을 요청한 컨테이너로 구성되 며, 터미널 입주사의 작업완료시간은 각 터미널 입주사 가 운송을 요청한 컨테이너(터미널 입주사별로 6, 3, 7, 6 개의 컨테이너)의 적하작업 시작 및 종료시각의 차이로 계산된다. 철송 크레인의 화차 간 이동시간과 컨테이너 적하작업 소요시간을 각각 25초와 70초로 설정하였다. 이때 크레인 이동시간과 컨테이너 단위처리시간은 현업 에서 직접 측정한 결과를 바탕으로 설정한 것이다.

    유전 알고리즘 성능은 제 4장에서 제안한 수리모형에 대해 최적화 소프트웨어가 도출한 해와 비교하여 분석 하였다. 유전 알고리즘은 C언어로 구현하였으며, 실험은 Core(TM) i5-7500 CPU @ 3.40GHz PC에서 수행하였다. 유 전 알고리즘에 적용한 파라미터에 대해 살펴보면 모집단 의 크기는 500개로 구성하였고, 각 개체는 임의로 생성하 였다. 일련의 예비실험을 통해 교차 및 돌연변이 연산 수 행의 확률이 높을수록 해 수렴 속도가 빨라지는 것을 확 인하여 교차율과 돌연변이율을 각각 90%로 설정하였으 며, 세대 수는 4,000으로 하였다. NMIP 모형과 MILP 모 형을 풀기 위해 LINGO 13.0과 CPLEX 12.8.0를 각각 활 용하였으며, 최대연산시간은 2시간으로 제한하였다. 실제 현업에서는 철송 크레인 스케줄링 시 30분~1시간 정도의 시간이 소요되지만, 본 연구에서는 짧은 시간 내에서는 최적화 소프트웨어의 해품질 평가 결과가 심각하게 왜곡 될 우려가 있어 연산시간을 2시간으로 설정하였다. 만약 최적화 소프트웨어가 제한된 시간 내에 최적해를 도출하 지 못한 경우에는 종료시점까지 발견한 최선해(incumbent solution)를 유전 알고리즘의 해와 비교하였다. 해의 품질 은 유전 알고리즘이 도출한 해의 목적함수 값(OGA)과 최 적화 소프트웨어가 도출한 해의 목적함수 값(OC)의 차이 (Gap)로 계산하였으며, 이에 대한 산식은 100×(OGA-Oc)/ Oc으로 정의하였다. 계산시간에 대한 성능 평가는 주어 진 문제에 대한 유전 알고리즘의 연산시간과 최적화 소프 트웨어가 해를 도출하는 데에 소요된 연산시간을 단순 비 교하였다. 민감도 분석은 적하목록 10개 데이터에 대해 가중치 α를 0.1부터 0.9까지 0.2만큼 증가시키며, 총 50개 의 실험 데이터를 기준으로 수행하였다.

    <Table 2>는 유전 알고리즘에 대한 성능 평가의 결과 를 보여준다. 실험 결과에서 알 수 있듯이 제안한 유전 알고리즘은 최적화 소프트웨어보다 상대적으로 우수한 해를 도출함을 확인할 수 있다. NMIP 모형에 대해 최적 화 소프트웨어와 유전 알고리즘의 결과를 비교해 보면, 유전알고리즘이 11.62%~57.57%만큼 우수한 해를 도출 하였고, MILP 모형에 대해서는 유전 알고리즘이 약 5%~ 44%만큼 우수한 해를 도출하였다. 또한, 실험 데이터의 크기가 증가하고 입주사의 작업완료시간 범위에 대한 가중치가 증가할수록 유전 알고리즘과 최적화 소프트웨 어의 해 품질에 대한 격차는 더 커지는 경향이 나타났다. 연산시간 측면에서 최적화 소프트웨어는 어떠한 실험 예제에 대해서도 2시간 이내에 최적해를 도출하지 못하 였지만 유전 알고리즘은 모든 실험 예제를 10초 이내에 해결하였다. 이는 대량의 컨테이너를 작업하기 위한 크 레인 스케줄링과 입주사 지향적 철송 크레인 대체할 수 있는 좋은 대안이 될 수 있음을 스케줄링에 유전 알고리 즘이 최적화 소프트웨어를 의미한다고 할 수 있다.

    또한 입주사 지향적인 철송 크레인 스케줄링에 대한 운영 시사점을 도출하기 위해 민감도 분석을 실시하였으 며, 유전 알고리즘에서 도출한 해를 기준으로 가중치에 따라 변화하는 크레인의 총 작업시간과 입주사별 작업완 료시간 범위를 관찰하였다. <Figure 5>는 Data 5와 10에 대해서 가중치의 변화에 따른 크레인의 총 작업시간과 모 든 입주사의 작업완료시간 범위의 합을 보여주고 있다. 가중치가 증가할수록 크레인의 총 작업시간이 대체적으 로 증가하고 입주사의 작업완료시간 범위의 총합이 감소 하는 경향이 나타났다. 하지만 가중치가 다소 높은 0.7과 0.9을 살펴보면 Data 5에서는 입주사의 작업완료시간 범 위의 총합이 꾸준히 감소하는 경향이 나타났지만 Data 10 에서는 오히려 입주사의 작업완료시간 범위의 합이 증가 하는 경향이 나타났다. 이는 실험 데이터의 규모가 커질수 록 유전 알고리즘과 최적해의 목적함수 값의 차이가 커질 수 있음을 의미한다고 할 수 있다. 그럼에도 민감도 분석에 서 두 가지 중요한 시사점을 도출할 수 있었다. 첫째, 입 주사의 작업완료시간 범위에 대한 가중치가 크레인의 총 작업시간보다 큰 경우 크레인의 총 작업시간과 입주사의 작업완료시간 범위의 합의 차이가 줄어드는 경향이 나타 났다는 점이다. 이는 입주사 지향적인 철송 크레인 운영 을 도입하면 크레인의 총 작업시간이 크게 증가할 것이라 는 의왕ICD 현장 관계자들의 의견과는 다소 상반된 결과 이며, 이는 운영사가 입주사 친화적인 철송 크레인 적하 작업 스케줄을 수립하더라도 크레인의 운영 효율성이 급 격히 떨어질 가능성이 낮다는 것을 의미한다고 할 수 있 다. 하지만 가중치가 증가함에도 불구하고 크레인의 총 작업시간과 터미널 입주사의 작업완료시간 범위의 합의 차이가 나타났는데, 이는 입주사 지향적인 운영정책이 크 레인의 공 운전(empty movement) 시간을 증가시킬 수 있 다는 것을 시사한다. 따라서 운영사가 본 연구에서 제안 하는 철송 크레인 운영정책을 도입할 경우 크레인의 공운 전을 감소시킬 수 있는 추가적인 운영정책의 개발을 통 해 입주사에 대한 물류서비스 만족도 제고와 터미널 운영 효율성의 개선을 달성할 수 있을 것으로 판단된다. 둘째, 실험 결과에서 가중치가 0.1에서 0.5로 변화하는 동안 입 주사의 작업완료시간 범위의 합이 급격히 감소하지만 크 레인의 총 작업시간의 증가는 상대적으로 적음을 관찰할 수 있다. 이는 운영사가 입주사 지향적인 철송 크레인 스 케줄을 수립할 경우 크레인의 총 작업시간에 대한 중요도 를 어느 정도 유지하면서 입주사가 열차-육상트럭 환적지 에서 컨테이너 처리 시간을 상당히 단축시킬 수 있음을 의미한다. 따라서 실험결과를 통해 운영사가 전통적으로 중요하게 생각한 크레인의 운영 효율성을 크게 떨어뜨리 지 않고 입주사 지향적인 철송 크레인 운영정책을 효과적 으로 도입할 수 있음을 의미한다.

    입주사 지향적인 철송 크레인 스케줄은 터미널 내의 컨 테이너 흐름과 입주사의 컨테이너 처리활동에 영향을 미친 다. 하지만 선행연구에서 철송 크레인의 적하작업, 입주사 의 작업 행태, 열차-육상트럭 환적지의 물류흐름 변화에 대해 분석은 찾을 수 없었다. 이를 분석하기 위해 철송 크레인 적하작업 수행시 열차-육상트럭 환적지에서 컨테 이너 운송작업을 수행하고 있는 터미널 입주사의 수를 산 출해 보았다. 여기서, 터미널 입주사 수는 산식 k K ( F k S k ) / E 로 정의하였다. <Table 3>은 적하목록과 가중치 변 화에 따라 유전 알고리즘이 도출한 해를 기준으로 열차-육 상트럭 환적지에서 컨테이너 처리작업을 수행하고 있는 평 균 입주사의 수를 나타낸다. 가중치가 0.1에서 0.9로 증가 함에 따라 크레인이 적하작업을 수행하는 동안 환적지에서 컨테이너 처리작업을 하는 평균 입주사의 수는 2.1개에서 0.96개로 감소하는 것으로 나타났다. 이는 입주사의 작업 완료시간 범위에 대한 가중치를 증가시킬수록 열차-육상 트럭 환적지에서 입주사별로 작업시간대가 분산되는 것을 의미하며, 철송 크레인 적하작업 스케줄링 방식의 변화가 입주사의 컨테이너 처리와 철도화물 터미널의 혼잡도에 큰 영향을 미칠 수 있다는 것으로 해석이 가능하다.

    7. 결론 및 향후 연구

    본 연구는 의왕ICD 운영 현황을 토대로 터미널 입주 사 지향적인 철송 크레인 적하작업 스케줄링 방법론을 다루었다. 철송 크레인의 적하작업 순서와 적재 컨테이 너의 화차 위치를 결정하기 위해 수리모형을 제시하였으 며, 해당 문제를 효율적으로 해결하기 위해 유전 알고리 즘을 제안하였다. 본 연구는 유전 알고리즘의 성능 평가 를 위해, 의왕ICD 터미널 입주사로부터 입수한 컨테이너 적하목록에 대하여 철송 크레인의 총 작업시간과 터미널 입주사의 작업완료시간 범위의 중요도를 결정하는 가중 치의 변화에 따라 유전 알고리즘이 도출한 해와 최적화 소프트웨어가 도출한 해를 비교하였으며, 철송 크레인의 총 작업시간과 입주사의 작업완료시간의 가중치 변화에 따른 민감도 분석을 실시하였다.

    운영 시사점을 요약하면 다음과 같다. 첫째, 입주사의 작업완료시간 범위에 대한 가중치가 크레인의 총 작업시 간보다 큰 경우 크레인의 총 작업시간은 대체적으로 크게 증가하지 않았으며, 이는 입주사 작업시간의 최소화 중심 의 크레인 운영이 작업시간을 크게 증가시킬 것이라는 현 장관계자들의 예상과는 다소 차이가 있었다. 따라서 운영 사가 입주사 친화적인 철송 크레인 스케줄을 수립해도 크 레인의 운영 효율성이 급격하게 악화될 가능성에 대해서 는 추가적인 연구가 필요하다고 판단된다. 둘째, 운영사 가 운영 효율성을 크게 포기하지 않더라도 입주사의 작업 완료시간의 범위를 크게 단축시킬 수 있는 대안이 존재할 수 있다는 점이다. 목적함수의 가중치가 0.1에서 0.5로 증 가하면 크레인의 총 작업시간은 소폭 증가하였지만 입주 사의 작업완료시간 범위는 큰 폭으로 감소하는 경향이 나 타났기 때문이다. 즉, 입주사 지향적인 철송 크레인 운영 정책을 도입하고자 하는 운영사는 운영 효율성을 크게 떨어 뜨리지 않고 입주사의 컨테이너 처리비용 감소에 도움을 줄 수 있는 대안을 찾을 수 있다는 것을 의미한다. 마지막 으로 제안하는 목적함수 기준척도는 열차-육상트럭 환적 지에서 터미널 입주사의 컨테이너 운송 작업시간대를 분 리하는 결과를 유도함으로써 환적지에서 혼잡도 감소에 기여할 수 있을 것으로 판단된다.

    향후 연구방향에 대해 소개하면 다음과 같다. 우선, 본 연구는 철송 크레인의 총 작업시간과 터미널 입주사의 작 업완료시간의 범위를 가중합으로 표현한 목적함수를 토 대로 철송 크레인의 운영방법을 분석하였다. 하지만 이러 한 접근 방식은 동일한 목적함수 값을 가지는 다양한 해 를 동시에 분석할 수 없다는 점에서 크레인 스케줄 수립에 대한 유연성을 제한한다. 따라서 이를 다목적 최적화 모 형으로 환원하여 운영사에게 다양한 스케줄을 제공하여 터미널 상황에 따라 적절한 크레인 스케줄을 선택할 수 있도록 지원하는 의사결정문제로 확장할 필요가 있다. 또 한 철도화물 터미널의 혼잡도 측면에서 철송 크레인의 스 케줄링에 관해 추가적으로 연구할 필요가 있다. 마지막으 로 다양한 물리적 및 운영적 제약(화차에 컨테이너 이단 적재, 무게제약, 이종컨테이너 처리 등)을 추가로 고려한 철송 크레인 스케줄링에 대한 연구가 필요하다.

    Acknowledgement

    This work was supported by Jungseok Logistics Foundation Grant.

    Figure

    JKISE-41-238_F1.gif

    Top View of the Ui wang ICD and Rail-Road Transshipment Yards (available at http://www.kihoilbo. co.kr/?mod=news&act=articleView&idxno=670311)

    JKISE-41-238_F2.gif

    Schematic Layout of the Rail-Road Transshipment Yard in the Uiwang ICD

    JKISE-41-238_F4.gif

    Concept of the Solution Modification Procedure for Infeasible Case 2

    JKISE-41-238_F3.gif

    Concept of the Solution Modification Procedure for Infeasible Case 1

    JKISE-41-238_F5.gif

    Tenant Service and Total Handling Times of Containers Obtained from the GA with Data 5 and 10 in Variation of Weight Value α

    Table

    Datasets for the Experiments

    Performance of the GAa

    Average Number of Terminal Tenants During Crane Operations in the Same Period

    Reference

    1. Bierwirth, C. and Meisel, F., A fast heuristic for quay crane scheduling with interference constraints, Journal of Scheduling, 2009, Vol. 12, No. 4, pp. 345-360.
    2. Bostel, N. and Dejax, P., Models and algorithms for container allocation problems on trains in a rapid transshipment shunting yard, Transportation Science, 1998, Vol. 32, No. 4, pp. 370-379.
    3. Boysen, N. and Fliedner, M., Determining crane areas in intermodal transshipment yards : The yard partition problem, European Journal of Operational Research, 2010, Vol. 204, No. 2, pp. 336-342.
    4. Heshmati, S., Kokkinogenis, Z., Rossetti, R., Carravilla, M., and Oliveira, J., An Agent-based Approach to Schedule Crane Operations in Rail-rail Transshipment Terminals, In Computational Management Science, Lecture notes in Economics and Mathematical Systems, 2016,Vol. 682, pp. 91-97.
    5. Holland, J., Adaptation in natural and artificial systems, Ann Arbour : The University of Michigan Press, 1975.
    6. Kim, K.H. and Park, Y.M., A crane scheduling method for port container terminals, European Journal of Operational Research, 2004, Vol. 156, No. 3, pp. 752-768.
    7. Kim, K.T. and Kim, K.M., Metaheuristics of the rail crane scheduling problem, IE Interfaces, 2011, Vol. 24, No. 4, pp. 281-294.
    8. Kozan, E., Optimizing container transfers at multimodal terminals, Mathematical and Computer Modeling, 2000,Vol. 31, No. 10-12, pp. 235-243.
    9. Lee, M.H., Design and implication of vehicle delivery planning system for the improvement logistics services, Journal of the Korea Academia-Industrial cooperation Society, 2006, Vol. 7, No. 4, pp. 587-593.
    10. Moccia, L., Cordeau, J.F., Gaudioso, M. and Laporte, C., A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal, Naval Research Logistics, 2006, Vol. 53, No. 1, pp. 45-59.
    11. Moon, J.S. and Lee, J.M., Development of Support Measure for Increasing Rail Freight, The Korea transportation institute, 2007.
    12. Sammarra, M., Cordeau, J.F., Laporte, G. and Monaco, M.F., A tabu search heuristic for the quay crane scheduling problem, Journal of Scheduling, 2007, Vol. 10, No. 4-5, pp. 327-336.
    13. Song, C.Y., A heuristic for part sequencing on a flexible machine, Journal of Society of Korea Industrial and Systems Engineering, Vol. 22, No. 52, pp, 81-85.
    14. Souffriau, W., Vansteenwegen, P., van den Berghe, G. and van Oudheusden, D., Variable Neighbourhood Descent for Planning Crane Operations in a Train Terminal, S rensen, K., Sevaux, M., Habenicht, W., Geiger, M.J, eds., Metaheuristics in the Service Industry, Lecture Notes in Economics and Mathematical Systems, 2009,Vol. 624, pp. 83-98.