[ Research Paper ]

Journal of the Society of Naval Architects of Korea - Vol. 62, No. 4, pp.271-279

ISSN: 1225-1143 (Print) 2287-7355 (Online)

Print publication date 20 Aug 2025

Received 08 Apr 2025 Revised 26 May 2025 Accepted 27 Jun 2025

DOI: https://doi.org/10.3744/SNAK.2025.62.4.271

Hybrid SA 알고리즘을 적용한 로로선 항차 및 적재 통합계획 의사결정 모델 개발

김종해¹ ; 윤희창¹ ; 배성유¹ ; 오현진¹ ; 우종훈¹^{, 2}^{, †}

1서울대학교 조선해양공학과
2서울대학교 해양시스템공학연구소

Development of an Integrated Decision-Making Model for Voyage and Stowage Planning of RoRo Ships Using a Hybrid SA Algorithm

Jonghae Kim¹ ; Heechang Yoon¹ ; Seongyou Bae¹ ; Hyunjin Oh¹ ; Jonghun Woo¹^{, 2}^{, †}

1Department of Naval Architecture and Ocean Engineering, Seoul National University
2Research Institute of Marine Systems Engineering, Seoul National University

Correspondence to: ^†Jong Hun Woo, j.woo@snu.ac.kr

This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

The integrated planning of voyage scheduling and stowage for Roll-on/Roll-off (RoRo) vessels requires determining the order of ports within each continent and simultaneously handling loading and unloading operations at each port. While previous studies on the RoRo Ship Routing and Stowage Problem (RSRSP) focused on simplified port routing scenarios, this paper extends the problem to a more realistic version by incorporating 3D spatial constraints and inter-continental routes. This study addresses practical considerations that were not covered in earlier research, such as the simultaneous loading and unloading at a single port and adjusting dedicated deck heights for high & heavy (H/H) cargo. To cope with the complexity of the model, we develop the Rule-based Stowage Planner (RSP) heuristic algorithm, which prioritizes stowage positions, maximizes the profit from optional cargo, and enhances space efficiency for mandatory cargo. Furthermore, we introduce a hybrid algorithm that combines a Simulated Annealing approach, which hierarchically explores high-quality initial solutions, with the RSP algorithm applied in the stowage generation phase. Through extensive experiments, we validate the effectiveness and robustness of the proposed algorithms by comparing them with existing methods in previous research.

Keywords:

Stowage Plan, Voyage Plan, Roll-on/Roll-off(RoRo), Simulated Annealing, Hybrid Algorithm

키워드:

적재계획, 항차계획, 로로선, 모의 담금질 기법, 하이브리드 알고리즘

1. 서 론

해운 산업에서의 계획 수립은 전략적, 전술적, 운영적 계획으로 구분된다. 전략적 계획은 선대 구성 및 장기 투자와 같은 수년 단위의 계획을 다루고, 전술적 계획은 수개월 단위로 특정 항로 및 선박 배치를 결정하는 문제를 포함한다. 반면 운영적 계획은 특정 항차에 대한 구체적이고 단기적인 결정을 다루며, 항해 속도 결정, 기상 경로 선택, 화물의 적재 및 양하 등을 포함하는 세부적이고 실무적인 문제를 대상으로 한다 (Øvstebø et al., 2011a).

본 연구는 이러한 계획 체계 중 전술 계획에 해당하는 항차계획과 운영 계획에 해당하는 적재계획을 계층적으로 통합함으로써, 현실 적용 가능한 해상 물류 운송계획을 제안한다. 항차계획은 항구 방문 순서를 결정하는 전술적 문제로, 항로의 효율성과 거리 최소화를 중심으로 수행된다. 반면 적재계획은 각 항차의 실행 과정에서 차량의 적재 순서와 위치를 결정하는 운영적 문제로, 후입선출 제약, 선박 안정성, 화물의 물리적 특성 등 복합적인 제한을 수반한다. 이와 같은 전술–운영 계획의 통합적 접근은 화물 운송 수익의 극대화, 항해 비용의 최소화, 제약조건 위반 페널티 비용 감소라는 다중 목표를 동시에 고려하는 통합적 운항계획을 가능하게 하며, 기존의 단일 수준 최적화 방식 대비 실무적 현실성과 효과성이 강화된다는 점에서 의의가 있다.

Fig. 1

A diagram for inter-continental voyage planning

기존 연구들은 주로 적재계획 관련 연구를 진행했다. Øvstebø et al. (2011a)는 다양한 차량 종류와 갑판 및 차선별 물리적 제약을 고려하였으며, 3D 형태의 선내 공간 화물 배치를 수리적으로 모델링했고, Puisa (2018)는 적재 문제를 MILP로 표현하고 로로선의 공간 배치 효율성과 안전 요소를 동시에 만족시키는 적재 최적화 문제를 다루었다. 또한, Zhang and Tian (2020)은 여객-화물 겸용 로로선을 대상으로, 2차원 배치 문제를 활용한 2단계 적재계획 알고리즘을 제안하였고, Sun et al. (2022)은 로로선의 적재계획 문제에서, 사람의 의사결정을 보조하는 반 자동화 접근법을 제안하였다. 상기 연구를 통해 로로선 적재 문제는 적재 효율만 고려하던 초기 모델에서 안전성, 위험물 규정, 다중 선박 간의 항차 조정 등 실무 제약이 추가되면서, 문제 복잡도가 증가한다는 것을 확인할 수 있다. 그러나 이러한 연구들은 대부분 적재계획에 국한되어 있어, 선박의 항로와 적재 문제를 복합적으로 반영하는데 한계가 있다.

Øvstebø et al. (2011b)는 로로선의 항구 라우팅과 스케줄링, 그리고 적재계획을 동시에 고려한 통합 모델을 제시하였고 Zhao et al. (2025)는 여러 척이 동시에 운항하는 선단을 대상으로 통합계획을 수립하는 휴리스틱 알고리즘을 소개하였다. 이들 연구는 항구 라우팅 및 적재계획을 통합하여 문제를 다룬다는 점에서 실무적인 운용 조건을 보다 정확히 반영할 수 있다는 장점을 가지고 있다. 또한, 계획 간 상호작용으로 인한 비효율을 줄이고 전체 운항 효율성을 제고할 수 있는 기반을 마련하였다는 점에서 의의가 있다. 그러나 두 연구 모두 제한된 수의 변수 및 제약조건만 고려하거나, 단순한 운항 환경에 국한된 실험을 수행하였다는 점에서, 다양한 현실적 제약을 포함한 복잡한 운송 시나리오에 적용하는 데에는 한계가 있다.

국내에서는 운항 안전·효율성을 정량화하려는 시도가 병행됐다. Lee et al. (2005)은 파랑·추진 저항을 고려한 ETA·연료소모 기반 최적 항로 평가 시스템을 제시하여 항로 결정 단계에서 안전과 효율을 동시 평가하는 프레임워크를 마련했다. Shin and Hwang (2014)은 3~4개 래싱로드와 2-3 Tier 래싱브리지를 지원하는 컨테이너 고박 최적화 프로그램을 개발해 대형 컨테이너선의 적재-고박 안정성 문제를 정수 최적화로 해결했다. Kim and Yoo (2004)은 Ro/Ro 여객선 차량 갑판 화재를 FDS 기반으로 수치 시뮬레이션하여 워터스프레이 시스템의 화재 억제 효과를 검증, 적재 안전성 평가에 화재 위험 요소를 포함할 필요성을 제기했다. Hong et al. (2005)은 Ro-Pax 선형의 천수역 조파저항 증가량을 레벨-셋 기반 수치해석으로 정량화하여, 수심-프루드수≈1 구간 운항 시 연료비와 ETA 예측 정확도를 높이는 근거를 제공했다. 이러한 국내 연구들은 항차-적재 통합 의사결정에서 항로 안전성 평가·고박 안정성·화재 위험·수심 영향을 함께 고려해야 함을 시사한다.

본 연구는 기존의 항구 라우팅과 적재 계획 통합 문제를 확장하여, 다양한 유형의 화물이 동일 항차 내에서 동시에 적재 및 하역되는 혼합 픽업-딜리버리 형태로 문제를 정의하였다. 제안된 모델은 복수의 항차와 항구 간의 구체적인 연결 관계를 포함함으로써, 실제 로로선 운항 환경을 반영한 현실적이고 복합적인 계획 문제로 구성된다. 또한 현실적인 운용 조건 하에서 화물 적재 실현 가능성을 검증하기 위해 3차원 적재 시뮬레이터를 구현하였다. 시뮬레이션 과정에서는 각 화물의 실제 크기와 선박의 구조적 특성, 항구별 적재 및 양하 순서가 반영된다. Øvstebø et al. (2011a)에서 제안한 3D 적재계획 휴리스틱 알고리즘은 모든 화물을 단일 단계에서 통합적으로 다루기 때문에 문제 복잡도가 증가하고 적재 실현 가능성과 수익성을 동시에 만족시키는 데에 한계가 있다. 이러한 한계를 극복하기 위해 필수화물과 선택 화물을 순차적으로 분리하여 적재 순서를 결정하는 적재 휴리스틱을 개발하였다. 제안 알고리즘은 화물 적재 관점에서 문제를 단순화함으로써 계산 부담을 크게 줄이고, 대규모 문제에서도 신속하게 수렴할 수 있도록 설계한 점이 기존 연구와의 핵심적인 차별점이다.

2. 문제 정의

본 연구는 전통적인 로로선의 경로·적재 문제인 RSRSP를 확장하여, 3차원 적재 제약과 대륙 간 항차계획을 함께 고려하는 문제를 3L-MPD-RSRSP로 정의한다. 여기서 3차원 적재는 차량의 높이·너비·길이를 모두 반영해 갑판과 차선에 배치하는 과정을 의미하며, 대륙 간 항해는 다수의 대륙을 거치는 실제 장거리 운항 상황을 반영한다. 본 연구에서 정의된 모델 구성요소는 Table 1과 같다.

Table 1

Model components

Table 2에 제시된 결정 변수들은 적재계획과 항차계획을 구성하는 주요 의사결정 요소로 분류한다. 적재계획과 관련된 변수들은 화물의 공간 배치, 수량, 선박 구조 조정, 적재 순서, 선택 여부 등의 결정을 포함하며, 이는 화물 적재에 따른 수익 극대화와 작업 효율성 향상을 위한 핵심 정보를 제공한다. 화물의 적재 위치를 정의하는 이진 변수는 갑판과 차선, 항구 및 대륙을 기준으로 공간 배치를 결정하고, 정수형 변수는 특정 위치에 적재된 차량의 수량을 나타낸다. 갑판 높이와 차선 너비는 연속형 변수로, 다양한 화물 특성에 적응할 수 있도록 선박의 공간 활용도를 조정한다. 또한 차량 간 적재 순서와 선택 화물의 채택 여부를 나타내는 이진 변수들은 작업 순서의 충돌을 방지하고 수익성을 고려한 화물 선택을 가능하게 한다.

Table 2

Decision variable

항차계획과 관련된 변수들은 항구 간 이동 여부와 항차 내 방문 순서를 결정하여 전체 항로의 효율성과 항해 비용 최소화를 도모한다. 이동 여부는 항구 간 연결을 이진 변수로 정의하며, 방문 순서는 정수형 변수로 표현되어 최적의 항구 방문 순서를 구성하는 데 활용된다.

max ∑ c ∈ C ∑ p ∈ P v ∑ d ∈ D ∑ l ∈ L ∑ i ∈ I o r i ⋅ z i - ∑ i ∈ I ∑ i ′ ∈ I c ∑ c ∈ C ∑ p ∈ P v ∑ d ∈ D ∑ l ∈ L u d l i i ′ ⋅ q i p - f ⋅ α ⋅ ∑ v ∈ V ∑ p ∈ P v ∑ q ∈ P v m p q v ⋅ d p q

(1)

L i × y i d l p ≤ L d × x i d l p c, i ∈ I, d ∈ D, l ∈ L, p ∈ P c, c ∈ C

(2)

H i × x i d l p c ≤ h d + 1 - h d, i ∈ I, d ∈ D, l ∈ L, p ∈ P c, c ∈ C

(3)

W i × x i d l p c ≤ v d l, i ∈ I, d ∈ D, l ∈ L, c ∈ C, p ∈ P i

(4)

∑ d ∈ D ∑ l ∈ L y i d l p = N i, i ∈ I M, p ∈ P

(5)

∑ d ∈ D ∑ l ∈ L y i d l p = N i × z i, i ∈ I O, p ∈ P

(6)

∑ p ∈ P c + 1 ∑ q ∈ P c m p q v = 0, ∀ c ∈ C ∖ max C, ∀ v ∈ V

(7)

∑ p ∈ P c ∑ q ∈ P c + 1 m p q v ≧ 1, ∀ v ∈ V

(8)

∑ p ∈ P c ∑ q ∈ P c + 1 m p q v = 1, ∀ v ∈ V max V

(9)

o p v - o q v + P ⋅ m p q v ≤ P - 1, ∀ p, q ∈ P v, p ≠ q, v ∈ V

(10)

D d L ≤ h d ≤ D d U, i ∈ D R

(11)

w d l ≥ 0, d ∈ D, l ∈ L

(12)

u d l i i ′ ∈ 0,1, i ∈ I, i ′ ∈ I c, d ∈ D, l ∈ L

(13)

x i d l p c ∈ 0,1, i ∈ I, d ∈ D, l ∈ L, p ∈ P c, c ∈ C

(14)

z i ∈ 0,1, i ∈ I

(15)

y i d l p ≥ 0, i ∈ I, d ∈ D, l ∈ L, p ∈ P c

(16)

m p q v ∈ 0,1, p, q ∈ P v

(17)

목적함수는 식 (1)과 같이 정의되며, 운송하는 선택 화물의 총수익에서 후입선출 규칙 위반으로 인해 발생하는 화물 이동 페널티 비용과 전체 항구 간 이동 거리에 따른 항해 비용을 차감한 순이익을 최대화하는 것을 목표로 한다. 이 목적함수는 화물 적재 과정에서 불필요한 화물 이동을 최소화하고, 선박 운항 비용을 줄이면서도 운송 수익을 극대화하여 전반적인 운송 계획의 효율성을 높이기 위해 설정되었다.

본 연구에서는 로로선의 실제 운용에서 발생하는 다양한 물리적 제약조건 중 일부는 모델 단순화를 위해 가정 또는 추상화된 형태로 반영하였다.

먼저 갑판 간 연결 램프와 차량의 통행 경로 확보 문제는 모든 갑판이 차량 이동이 가능한 구조임을 전제로 하였고, 각 갑판 및 차선 단위의 적재는 독립적으로 이루어지는 것으로 가정하였다.

또한, 차량의 개문 방향에 따른 양하 순서 및 공간 확보 문제는 블로킹 방지를 위한 페널티 요소로 간접적으로 반영하였다.

이러한 가정은 복잡한 통로 이동 시뮬레이션을 생략하는 대신, 공간 배치의 합리성과 후입선출 규칙을 유지함으로써 현실성과 계산 효율성을 모두 고려하였다.

식 (2)-(4)는 3차원 공간 제약으로, 각 화물의 길이, 높이 및 너비가 각 갑판 및 차선의 실제 물리적 크기를 초과하지 않도록 제한하여 현실적인 적재 가능성을 확보한다. 식 (5)-(6)은 필수화물의 적재량을 정확히 준수하고, 선택 화물은 적재 결정되면 해당 화물의 모든 차량을 적재해야 하는 제약을 정의한다.

대륙 간 항차의 이동 순서를 고정하는 식 (7)은 항차가 반드시 정해진 대륙 순서를 따라 이동하도록 강제하여 일정의 연속성과 일관성을 유지하며, 식 (8)은 모든 항차에서 각 대륙을 적어도 한 번 방문하도록 하여 필수 운송 노선을 보장한다. 식 (9)는 항차 간 연결 제약으로 각 항차가 정확히 다음 대륙의 항구로 연결되도록 설정하고, 식 (10)은 MTZ 제약을 통해 각 항차 내에서 항구의 방문 순서를 명확하게 정하여 항구의 중복 방문 및 순환 경로의 발생을 방지한다.

갑판의 높이 설정에 대한 현실적 허용 범위를 나타내는 식 (11)은 갑판의 높이가 반드시 주어진 하한과 상한 사이에 위치하도록 하며, 식 (12)는 차선의 너비가 반드시 0보다 커야 한다는 기본적인 물리적 제약을 정의한다. 마지막으로 식 (13)-(17)은 결정변수의 특성을 나타내며, 본 연구에서 설정된 이진 변수 및 정수 변수의 범위를 명확히 하여 최적화 모델의 타당성을 확보한다.

3L-MPD-RSRSP의 해결 과정은 항차계획과 적재계획으로 구분된다. 항차계획은 대륙 간 순차적인 운항 흐름을 기반으로 하며, 각 항차는 인접한 두 대륙 간의 적재 및 양하 작업으로 구성된다. 선행 대륙에서 적재된 화물은 반드시 다음 순서의 대륙 내 항구에서만 양하될 수 있으며, 이를 통해 대륙 간 화물 흐름의 방향성과 운송 논리를 명확히 정의할 수 있다. 이때, 첫 번째 대륙에서는 모든 항구에서 적재만 수행되고, 마지막 대륙에서는 양하만 수행되며, 중간 대륙에서는 각 항구가 양하 직후 적재를 수행하는 구조로 되어 있다. Fig. 1은 이러한 항차계획 구조를 시각적으로 나타낸다.

예를 들어 Fig. 1에서 B 대륙은 첫 번째 항차에서는 A 대륙으로부터 적재된 화물을 양하하는 도착지 역할을 수행하고, 두 번째 항차에서는 C 대륙으로 향하는 새로운 화물을 적재하는 출발지 역할을 수행한다. 이와 같이 동일한 대륙이 연속된 항차에 중복 참여하는 구조는, 각 항차의 종착지에서 다음 항차의 출발이 자연스럽게 이어지는 연속적 항차계획을 형성한다. 따라서 본 연구에서는 이러한 대륙 간 연결 구조를 기반으로, 각 항차에서 항구 방문 순서를 결정함과 동시에 적재 및 양하 작업의 순서를 고려하는 통합계획 문제를 정의한다.

적재계획은 선내 다층 갑판과 차선 구조를 고려하여 차량을 배분하는 문제로, 운송 요청에 포함된 화물을 필수화물과 선택 화물로 구분하는 과정이 선행된다.

필수화물은 운송 계약에 따라 반드시 선적 및 운송해야 하는 화물이며, 선택 화물은 전체 운송 수익과 선내 공간, 선박 용량 등의 제약조건을 고려하여 선적 여부가 결정되는 화물이다. 선택 화물의 경우, 경제적 가치와 운항 제약조건을 고려하여 선적할 화물을 결정하게 되며, 이를 통해 전체 수익 극대화를 달성하고자 한다. 특히, H/H 화물처럼 중량이 크거나 높이가 큰 차량은 일반 차량과 달리 갑판 높이 조정 같은 물리적 조치가 필요할 수 있기에 특정 구역에서만 적재가 가능하다는 점도 고려해야 한다.

이러한 두 개의 의사결정 과정은 단순히 별개의 문제로 처리할 수 없는 상호 연관성을 지니고 있다. 운항 경로와 일정은 특정 항구에서 화물의 적·양하 시점을 결정하고, 이에 따라 화물의 하역 및 새로운 화물의 적재가 이루어진다. 따라서 항차계획과 적재계획은 상호 연계된 의사결정 문제로서, 항로 및 일정과 화물 선택 및 적재 공간 배치가 통합적으로 고려될 때 전체 시스템의 비용 절감과 선단 운영 효율성이 극대화될 수 있다.

본 문제는 3차원 배낭 문제와 항차 라우팅 문제를 결합한 형태로, 두 문제 모두 NP-hard로 알려져 있다. 특히 대륙 간 항차 구성 시 기항 항만 수 증가에 따른 조합 수 급증과 복잡한 적재 공간 제약으로 인해 수리적 최적화만으로는 해결이 어렵다. 이에 따라 본 연구는 해 탐색 효율성과 실현 가능성을 고려하여, RSP와 SA-2I를 결합한 Hybrid SA 기반 알고리즘을 제안한다.

3. 방법론

3.1. Hybrid SA 알고리즘

본 연구에서는 로로선의 항차 및 적재계획을 통합적으로 수립하기 위한 Hybrid SA 알고리즘을 제안하였다. 제안된 알고리즘은 Fig. 2와 같이 선박의 항차계획과 적재계획 문제를 동시에 다루기 위한 SA-2I와 RSP 알고리즘으로 구성된다.

Fig. 2

Pseudocode for hybrid simulated annealing

항차계획에 사용된 SA-2I 알고리즘은 기존 SA 알고리즘을 변형하여, 초기 해를 무작위로 생성하는 대신 두 단계의 계층적 접근법을 적용하였다. 첫 번째 단계에서는 대륙 간 연결 항구를 결정해 장거리 이동 구간을 단순화하고, 두 번째 단계에서는 대륙 간 연결 항구를 제외한 나머지 항구의 방문 순서를 최적화하는 방식으로 초기 해를 수립한다. 이러한 2단계 초기 해 생성 과정은 초기 해 품질을 향상시키고, 알고리즘의 수렴 속도를 높이는 효과가 있다.

SA-2I에서 생성된 각 항차계획에 대해 RSP 알고리즘을 적용하여 적재계획을 수립한다. RSP 알고리즘은 각 대륙과 항구에서 선적해야 하는 필수화물과 선택화물을 구분하여, 차량 적재 공간과 안정성 제약을 고려하여 화물 배치를 수행한다. 이렇게 생성된 적재계획과 항차계획은 통합적으로 평가되어 목적함수 값을 산출하며, 목적함수는 화물 운송 수익과 화물 이동 시 발생하는 후입선출 위반 페널티, 그리고 항해 비용을 포함한 항로 비용을 통합적으로 고려하여 계산된다.

목적함수 값이 계산된 후, SA-2I 알고리즘은 새로운 이웃해를 탐색한다. 이웃해 생성 방법으로는 기존의 항차계획에서 무작위로 하나의 대륙을 선택하고 해당 대륙 내 항구의 방문 순서를 임의의 변경 방식을 사용한다. 이웃해에 다시 RSP를 수행하여 새로운 목적함수 값을 산출하고, SA 특유의 확률적 기준에 따라 개선된 해를 채택하거나 기존의 해를 유지한다. 이 반복 과정은 SA 알고리즘과 동일하게 설정된 온도 스케줄에 따라 수행되며, 알고리즘 초기에는 탐색 범위를 넓히고, 점차 수렴하여 최적의 해를 찾아가는 방식을 따른다.

이러한 Hybrid SA 알고리즘의 구조는 기존 SA보다 구조적이고 계층적인 초기 해 생성 방식을 적용하여 효율성과 성능을 높였으며, 로로선 운송의 현실적인 제약조건과 요구 사항을 효과적으로 반영하여 실무에 적합한 항차 및 적재 통합계획을 수립할 수 있다.

3.2 RSP 휴리스틱 알고리즘

본 연구는 로로선 적재계획을 생성하기 위해 RSP 휴리스틱 알고리즘을 제안한다. RSP는 내부적으로 3D 적재 시뮬레이션을 포함하고 있으며, 선박의 구조적 안정성과 경제적 수익성을 동시에 최적화하는 로직에 따라 설계되었다.

RSP는 생성된 항차계획을 입력으로 받아, 항차별로 구분하여 구조화된 로직으로 적재계획을 생성한다. 각 대륙의 역할에 따른 화물 작업 절차가 달라, 선박 내 적재 상태의 변화를 동적으로 반영할 수 있도록 설계되었다. 또한, 선박의 롤링 안정성을 확보하기 위해 기존의 좌현에서 우현으로 순차적으로 적재하는 방식이 아닌, 중심, 좌현, 우현 순서로 적재 위치를 우선 순위화하는 전략을 사용한다.

먼저, 항차의 첫 번째 대륙에서는 적재 작업만 수행되며, 각 항구에서 먼저 필수화물을 적재하고, 필수화물의 적재 순서를 무작위로 100회까지 변경하면서 적재 성공률을 높였다. 그중 적재가 가능한 공간이 가장 많이 남는 해를 선택하여, 선택된 해에 대해 선택 화물 적재를 추가로 시도한다. 선택 화물 역시 무작위 순서를 적용하여 최대 100회까지 적재계획을 생성하며, 최종적으로 선택 화물에 의한 수익이 가장 높은 적재계획을 최종 적재계획으로 선택한다.

중간 대륙에서는 항구별로 다음의 순서를 따른다. 먼저 해당 항구를 도착지로 가진 화물 양하를 진행하고, 후입선출 규칙 위반 여부를 검사하여 블로킹 페널티를 계산한다. 이후 동일 항구를 출발지로 가지는 화물에 대해 첫 번째 대륙과 동일한 방식으로 필수·선택 화물을 순차적으로 적재를 시도한다. 각 항구 작업이 완료될 때마다 해당 항구의 적재계획은 확정되며, 해당 시점에서의 수익과 페널티가 누적된다.

마지막 대륙에서는 모든 항구를 순차적으로 방문하며, 적재 없이 양하만 수행한다. 이때에도 후입선출 위반 여부를 기반으로 블로킹 여부를 확인하고, 페널티 비용을 계량적으로 계산하여 항구별로 기록한다.

전 과정은 내부 시뮬레이션을 통해 3차원 적재 제약, 고중량 화물의 특수 취급, 양하 순서 및 잔여 공간 확인 등 다양한 현실적 제약을 반영하여 정밀하게 수행된다. 이러한 구조화된 절차를 통해 RSP는 단순한 적재 가능성 판단을 넘어, 항차별, 항구별 계획 수립을 정량적이고 경제적으로 평가하고, 수익성과 안정성, 운용 효율성을 모두 통합 고려한 적재계획을 생성한다.

3.3 3D 적재 시뮬레이터

3D 적재 시뮬레이터는 RSP 알고리즘 내부에서 각 항차에 포함된 항구에서의 적재와 양하 작업을 평가하고 결정한다. 시뮬레이터의 입력값으로는 현재 방문한 항구 정보, 이 항구에서 적재할 화물 목록, 현재의 선박 상태 및 적재계획이 있다.

첫 번째 대륙 이후의 항구에서는 먼저 도착지로 지정된 화물의 양하 작업을 수행하고, 이를 실시간으로 적재계획에 반영하여 선내 공간을 갱신한다. 이후, 시뮬레이터는 입력받은 화물들에 대해 식 (2)의 3차원 공간상에서의 제약, 블로킹, 갑판 높이와 같은 복합적인 적재 제약을 만족하는지 평가하며 적재 위치를 결정한다. 특히, H/H 화물의 경우는 조정 가능한 갑판의 높이와 차선 너비를 동적으로 변경하며 화물의 적재 가능성을 최대로 확보한다.

또한, 적재된 화물의 양하 과정에서 후입선출 규칙 위반 여부를 평가하고, 이에 따라 발생하는 추가 작업을 페널티 비용으로 정량화하여 산출한다. 이와 함께 선택 화물의 적재 여부에 따른 화물 수익을 계산하여 최종 순수익을 평가한다. 이렇게 계산된 페널티 비용과 화물 수익은 알고리즘의 반복적 탐색 과정에서 적재 계획의 우열을 판단하는 중요한 기준으로 활용된다.

4. 실 험

본 연구의 목표는 로로선의 항차 및 적재계획 통합 문제에 대해 제안 알고리즘이 얼마나 효율적인 해를 산출하는지를 다양한 운송 시나리오에서 평가하는 것이다. 실험은 Table 3와 같다. CEU, 대륙 수, 대륙 당 항구 수, 그리고 항구당 화물 종류 수를 조합하여 실험을 설계했다. 기존 연구 및 경험 식을 활용하여 선내 갑판 수와 차선 수, 갑판별 높이 제한 등의 요소를 실제 해운사들이 운영 중인 선박의 구조적 특성으로 구체화했다. 로로선 특유의 제약조건을 세부적으로 반영하기 위해, 최대 8000 CEU 규모 선박을 기준으로 시나리오를 설계하였다. 대륙 수와 항구 수 역시 서로 다른 조합으로 구성하여 알고리즘 성능을 평가했다. 대륙 수가 m개이고 대륙 내 항구 수가 n개일 때, 가능한 조합은 (n!)^m가지 경우의 수다. 또한, 항구당 화물 종류의 수도 최대 12개까지 설정하여 화물 운송량이 많은 경우 제안 알고리즘의 탐색 효율을 중점적으로 살펴볼 수 있도록 하였다.

Table 3

Experimental input data

4.1 실험 환경 및 데이터셋 설정

본 연구의 실험 환경 및 데이터셋 설정은 다음과 같다. 선박용량은 CEU가 2,000에서 8,000 사이인 로로선을 가정하였고, 이를 바탕으로 선내 갑판 수, 각 갑판의 가용 높이 및 차선 수를 산정했다. 선내 갑판별 높이와 차선의 폭은 Øvstebø et al. (2011a)와 같이 각 3.0m, 2.5m로 선정했다. 또한, 특정 갑판 일부 구역이 가변적 높이나 가변 폭을 지원한다고 가정하여 H/H 화물 적재 가능성을 고려하였다. 대륙 및 항만 배치는 대륙 수에 따라 각 대륙에 여러 항만을 할당하며, 항만 간 거리는 해상 운항 실측 자료 및 예측치를 기반으로 임의 생성하였다. 화물 분포는 항만별로 운송 계약이 확정된 필수화물과, 상황에 따라 선별 탑재할 수 있는 선택 화물을 포함한다. 화물의 길이·높이·너비, 중량, 그리고 수익 등은 Øvstebø et al. (2011a)와 마찬가지로 일정 범위 안에서 난수로 생성한다. H/H 화물은 전체 화물의 20%로 배정하여 특수화물 배치 제약을 적용한다. 항구당 화물 종류의 수는 4~12개로 설정하여 총 화물 종류 수는 30~144개까지 생성한다. 선박과 항만 조건에 따라 적재가 불가능할 수도 있도록 실제 변동성을 반영했다.

RSP 내부에서 필수화물과 선택 화물을 단계적으로 적재하며, 이때 각 화물의 순서를 기준으로 여러 조합을 시도하되, 과도한 연산 시간을 방지하기 위해 최대 시도 횟수를 최대 100회로 제한한다. 차선 폭·갑판 높이 조정은 상황에 따라 제한적 범위 내에서만 허용하여, 지나친 구조 변경을 방지한다. 제한적 범위는 갑판 높이는 H/H 전용 갑판의 다음번 순서의 갑판 높이까지, 차선 너비는 다음번 순서의 차선 너비까지 설정한다.

본 연구에서는 시나리오별 동일한 알고리즘 파라미터를 사용하되, 무작위 요소에 의한 편차를 최소화하기 위해 각 다른 무작위 시드를 사용하여 30번 반복 수행한 후 평균값을 결과로 취한다. 모든 알고리즘의 최대 실행시간은 300초로 설정한다.

4.2 비교 알고리즘 설정

본 연구에서는 통합 문제를 평가하기 위해 기존 연구에서 제안된 SWO 하이브리드 알고리즘 (Øvstebø et al, 2011a)을 적재계획의 비교 알고리즘으로 채택하였고, 항차계획의 비교 알고리즘으로는 널리 사용되는 단일 메타 휴리스틱 SA, GA, TS를 선정하였다. 제안한 RSP와 SA-2I 알고리즘을 추가하여 총 8가지 알고리즘 조합을 구성하였으며, 구성된 알고리즘 조합은 Table 4에 제시되어 있다. 각 알고리즘의 성능은 목적함수 값과 이를 구성하는 항해 비용, 화물 수익, 페널티 비용 및 알고리즘의 수렴 시간과 실행시간을 기준으로 평가되었다.

Table 4

Combinations of voyage and stowage algorithms

5. 실험 결과

본 실험은 10th Gen Intel® Core i7- 10700 CPU, RAM 16GB에서 진행되어 제안 알고리즘이 단일 시나리오를 30번 실행하는데 약 1851초 소요된다. Fig. 3에 제시된 전체 평균 목적함수 값을 살펴보면, 제안된 알고리즘인 P1이 모든 경우에서 가장 높은 성능을 보인다. H/H 화물이 많고, 대륙 간 이동 항구가 증가하는 시나리오 3, 4에서 P1과 다른 알고리즘 간 목적함수 값의 차이가 커지는 경향이 관찰되었다.

Fig. 3

Objective value of 10 experiments

Case 1~4에서는 동일한 선박 용량과 항구당 화물 수를 유지한 채 대륙 수와 대륙별 항구 수를 달리하였다. 대륙과 항구 수가 증가할수록 운항 경로가 복잡해지고 항해 비용이 상승하였으며, 이에 따라 항차 탐색 조합의 폭도 확장되었다. 특히 다수 대륙 및 항구를 포함한 Case 4에서는 블로킹 및 H/H 화물 제약이 심화되었고, 그럼에도 P1는 안정적인 경로를 도출하며 가장 우수한 목적함수 값을 기록하였다.

Fig. 4에서 확인되듯이, P1과 R4는 단일 SA, GA, TS 기반 알고리즘보다 낮은 항해 비용을 달성하였다. 단일 메타휴리스틱은 운항 경로와 적재 제약을 동시에 탐색하며 스케줄 지연이나 불필요한 경로 변경이 누적되어 평균 10~20% 높은 비용을 초래했다. 반면, P1 구조는 항차 결정에서 비용 절감 방향을 우선 탐색하고 적재 시뮬레이션 피드백을 반복 반영함으로써 불필요한 이동을 줄이고 운항 효율을 향상시켰다.

Fig. 4

voyage cost of case 1-4

Case 5~7은 대륙 수와 항구 수를 고정한 상태에서 항구당 화물 종류를 증가시켜 문제 복잡도를 조절하였다. 화물 종류가 많아질수록 블로킹과 H/H 제약이 중첩되어 배치 실패 및 페널티 증가가 발생하였고, Fig. 5에서 RSP는 고부가가치 화물의 우선 배치와 단일 차선 전략을 통해 SWO 대비 더 높은 화물 수익을 기록하였다.

Fig. 5

cargo profit of case 5-7

Case 8~10은 선박 CEU를 2000, 5000, 8000으로 증가시키는 시나리오로, 적재 가능 화물량은 증가하나 H/H 화물의 비효율적 배치로 인해 공간 제약에 조기 도달하는 사례가 관찰되었다. Fig. 6에 따르면 CEU 증가에 따라 페널티 비용이 크게 상승하였으며, 이 과정에서 RSP는 SWO 대비 블로킹과 충돌을 효과적으로 억제하였다.

Fig. 6

penalty cost of case 8-10

Table 5는 평균 수렴시간과 실행시간을 비교한 결과로, 제안 알고리즘은 기존 SWO나 단일 메타휴리스틱 대비 최대 97% 빠른 수렴 속도와 최대 79% 향상된 실행 성능을 보였다. 여기서 수렴시간은 알고리즘이 더 이상 유의미한 해 개선 없이 안정적인 최적해에 도달하기까지 소요된 평균 탐색 시간을 의미하며, 탐색 효율성과 연산 안정성을 동시에 반영하는 지표로 사용된다. 이는 SA-2I의 효율적 탐색 분할과 RSP의 제약 처리 능력에 기인한다. 특히 RSP는 SWO보다 수익성과 제약 처리에서, SA-2I는 단일 메타휴리스틱보다 유류비용 최소화 측면에서 우수하며, 대규모 사례에서 효과가 두드러졌다. 이러한 결과는 제안 알고리즘의 구조적 강점이 복잡한 RoRo 운항 문제 해결에 효과적임을 보여준다.

Table 5

Average convergence time and execution time

결과적으로 RSP 기반 알고리즘은 복잡도가 높은 환경에서도 배치 실패를 최소화하고 수익을 극대화하는 반면, SWO는 3차원 제약을 고려하나, 선택 화물 활용이 제한되어 고부가가치 화물 배치에 한계가 있었다. RSP는 단일 차선 중심의 탐색과 단계적 배치 전략을 통해 화물 수익성과 안정성을 모두 확보하며 최종 목적함수 향상에 기여한다.

6. 결 론

본 연구는 로로선의 항차 결정과 선내 적재계획을 통합적으로 해결하기 위해 Hybrid SA 알고리즘을 제안하였다. 본 연구의 기여점은 다음과 같다. 첫째, 기존 RSRSP를 확장하여 3차원 공간 제약, 적·양하의 병행 수행, 갑판 높이 조정, 필수·선택·고중량 화물 배치 등을 반영한 3L-MPD-RSRSP 문제를 정의함으로써 실제 운송 환경에 근접한 문제 구조를 제시하였다. 둘째, 항차계획과 적재계획을 분리하되, 항차 해의 변경에 따라 RSP 기반 적재계획을 반복적으로 재구성하여 두 계획 간 상호작용을 반영하고 탐색 효율을 높였다. 셋째, RSP는 단계적 배치, 블로킹 방지, H/H 화물 제약 완화 전략을 통해 기존 SWO 대비 높은 적재 효율성과 탐색 안정성을 확보하였다.

향후 연구에서는 각 항만의 도착·출항 가능 시간 창을 고려한 운항 스케줄링을 통합 모델에 반영함으로써, 기항 지연, 대기료, 항만 운영시간 등의 실무적 제약을 포함하여 정교한 계획 수립이 가능할 것이다. 또한, 항구에서 출항할 때마다 선박 복원력, 무게중심 편차 등을 즉시 계산·검증하는 안정성 평가 모듈을 통합 모델에 연계할 수 있다.

Nomenclature


Abbreviation :	Full meaning
3L-MPD-RSRSP :	3D Loading Constraints Mixed Pickup & Delivery RoRo Ship Routing and Stowage Problem
CEU :	Car Equivalent Unit
GA :	Genetic Algorithm
H/H :	High & Heavy
MILP :	Mixed-Integer Linear Programming
MTZ :	Miller-Tucker-Zemli
NP-hard :	Non-deterministic Polynomial-time hard
RoRo :	Roll-on/Roll-off
RSRSP :	RoRo Ship Routing and Stowage Problem
RSP :	Rule-based Stowage Planner
SA :	Simulated Annealing
SA-2I :	Simulated Annealing with 2-stage Initialization
SWO :	Squeaky Wheel Optimization
TS :	Tabu Search

Acknowledgments

이 논문은 2025년도 정부(산업통상자원부)의 재원으로 한국산업기술진흥원과 해양시스템공학연구소의 지원을 받았으며, 지원에 감사드립니다.(RS-2023-KI002688, 2025년 산업혁신인재성장지원사업)

References

Hong, C., Shin, S., Kim, J. and Choi, S., 2005. A numerical study to evaluate the resistance performance of a Ro-Pax hull form in shallow water. Journal of the Society of Naval Architects of Korea, 42(4), pp.315–321. [https://doi.org/10.3744/SNAK.2005.42.4.315]
Kim, S. and Yoo, H., 2004. A numerical study of fire development characteristics on a Ro/Ro ferry vehicle deck. Journal of the Society of Naval Architects of Korea, 41(5), pp.48–54. [https://doi.org/10.3744/SNAK.2004.41.5.048]
Lee, J., Choi, K., Park, G., Kim, M. and Bang, C., 2005. Basic research of optimum routing assessment system for safe and efficient voyage. Journal of the Society of Naval Architects of Korea, 42(1), pp.57–63. [https://doi.org/10.3744/SNAK.2005.42.1.057]
Øvstebø, B.O., Hvattum, L.M. and Fagerholt, K., 2011a. Optimization of stowage plans for RoRo ships. Computers & Operations Research, 38(10), pp.1425–1434. [https://doi.org/10.1016/j.cor.2011.01.004]
Øvstebø, B.O., Hvattum, L.M. and Fagerholt, K., 2011b. Routing and scheduling of RoRo ships with stowage constraints.Transportation Research Part C: Emerging Technologies, 19(6), pp.1225–1242. [https://doi.org/10.1016/j.trc.2011.02.001]
Puisa, R., 2018. Optimal stowage on Ro‑Ro decks for efficiency and safety. Journal of Marine Engineering & Technology, 20(1), pp.1–17. [https://doi.org/10.1080/20464177.2018.1516942]
Shin, S. and Hwang, K., 2014. Development of the container securing program for large container carriers. Journal of the Society of Naval Architects of Korea, 51(5), pp.362–368. [https://doi.org/10.3744/SNAK.2014.51.5.362]
Sun, X., Wang, S., Wang, Z., Liu, C. and Yin, Y., 2022. A semi‑automated approach to stowage planning for Ro‑Ro ships. Ocean Engineering, 247, 110648. [https://doi.org/10.1016/j.oceaneng.2022.110648]
Zhang, Y. and Tian, Z., 2020. A two‑phase stowage approach for passenger‑cargo RoRo ship based on 2D‑KP: coping with complex rotation and safe navigation constraints. IEEE Access, 8, pp.95807–95817. [https://doi.org/10.1109/ACCESS.2020.2995639]
Zhao, Y., Peng, P., Zhou, J. and Wang, Y., 2025. Heuristic algorithm for integrated ship scheduling, routing and stowage problem in multi‑vessel roll‑on/roll‑off shipping. Journal of Heuristics, 31(1), pp.15. [https://doi.org/10.1007/s10732-025-09551-8]

김 종 해

윤 희 창

배 성 유

오 현 진

우 종 훈

Indices
i	Cargo
p,q	Port (q is auxilary index for comparison)
d	Deck
l	Lane
c	Continent
v	Voyage Plan
Sets
I	Set of all cargoes
I_M	Set of all mandatory cargoes
I_O	Set of all optional cargoes
I_Q	Set of cargoes i^′ such that $P i ′ L < P i L < P i ′ U < P i U$
P	Set of all ports
P_c	Set of all ports, contained in Continent c
P_v	Set of ports visited on voyage v
D	Set of all decks. Decks are numbered from the bottom in increasing order
L	Set of all potential lanes on each deck. Lanes are numbered from port side to starboard side in increasing order
C	Set of all Continents
V	Set of all voyage
Parameters
L_i	Length of one vehicle in cargo i
W_i	Width of one vehicle in cargo i
H_i	Height of one vehicle in cargo i
r_i	Revenue for transporting optional cargo i
N_i	Number of vehicles in cargo i
q_ip	Cost incurred if cargo i needs to be moved at port p
$P i L$	Loading port of cargo i, $P i L ∈ P c$
$P i U$	Unloading port of cargo i, $P i U ∈ P c + 1$
W_d	Width of deck d
L_d	Length of deck d
$D d L$	Lower bound for where deck d can be placed
$D d U$	Upper bound for where deck d can be placed
d_pq	Distance between port p and q
f	Fuel consumption per distance (ton/km)
α	Unit fuel cost(USD/ton)

x_idlpc	Binary	1 if cargo 𝑖 is loaded on deck 𝑑, in lane 𝑙, at port p within continent c, 0 otherwise
y_idlp	Integer	number of vehicles from cargo 𝑖 on deck 𝑑, in lane 𝑙, when the ship leaves port p
h_d	Continuous	Height of deck 𝑑 from the bottom deck
w_dl	Continuous	width of lane 𝑙 on deck d
u_dlii'	Binary	1 if cargo i'is loaded in front of cargo i on deck 𝑑, in lane 𝑙, at port $P i ′ L$ , 0 otherwise
z_i	Binary	1 if optional cargo 𝑖 is taken, 0 otherwise
m_pqv	Binary	1 if the ship moves from port 𝑝 to port 𝑞 during voyage v, 0 otherwise
o_pv	Integer	Visiting order of port 𝑝 to port 𝑞 during voyage v, 0 otherwise

Case	CEU	Continents	No. of ports per continent	No. of cargo types per port
1	7,000	3	5	4
2	7,000	3	7	4
3	7,000	5	5	4
4	7,000	5	7	4
5	7,000	3	6	4
6	7,000	3	6	8
7	7,000	3	6	12
8	2,000	4	6	4
9	5,000	4	6	4
10	8,000	4	6	4

	RSP				SWO
	SA-2I	SA	GA	TS	SA-2I	SA	GA	TS
Convergence time(s)	2	4	18	32	11	15	20	73
Execution Time(s)	61	60	85	266	95	92	150	300