OGC 2025에서는 RoRo 선박에 차량을 싣고 내리는 순서를 최적화하는 문제를 풀었습니다. 저는 제한된 실행 환경 안에서 그래프 기반 상태 표현, blocking-aware 휴리스틱, matching, ALNS 계열 탐색을 실험하며 대회용 알고리즘을 만들었습니다.
문제의 어려움
RoRo 문제는 차량을 많이 싣는 것만의 문제가 아니었습니다. 나중에 먼저 내려야 하는 차량이 안쪽에 들어가면 다시 옮겨야 하고, 이 rehandling이 비용을 만듭니다. 선박 내부 공간, 차량 위치, 목적지 순서, 통로 차단 여부가 함께 얽히기 때문에 단순 정렬로는 해결하기 어려웠습니다.
대회 환경도 빡빡했습니다. 제한된 CPU, 인터넷 없는 실행 환경, 제출 횟수 제한 안에서 알고리즘이 항상 돌아가야 했습니다. 좋은 아이디어가 있어도 실행 시간이 터지거나 특정 케이스에서 멈추면 제출물로는 의미가 없습니다. 이 조건 때문에 저는 처음부터 "항상 유효한 해를 내는 구조"를 우선순위에 두었습니다.
제가 시도한 방법
처음에는 문제를 선박 상태 그래프로 표현하고, 어떤 차량이 어떤 차량을 막고 있는지 계산했습니다. 이후 Hungarian matching으로 배치 후보를 잡고, blocking을 줄이는 휴리스틱을 붙였습니다. 더 나아가 destroy와 repair를 직접 설계한 ALNS/LNS 탐색도 시도했습니다.
하지만 메타휴리스틱 이름을 붙인다고 성능이 자동으로 좋아지지는 않았습니다. destroy가 너무 공격적이면 좋은 구조까지 무너지고, repair가 느리면 시간 제한 안에서 돌아오지 못합니다. 그래서 저는 각 탐색 단계가 실제 입력에서 어떤 실패를 만드는지 로그를 보며 줄여 갔습니다.
실패를 줄이는 설계
대회 문제를 풀면서 제가 가장 많이 배운 것은 fallback의 중요성이었습니다. 더 복잡한 탐색이 항상 더 좋은 답을 주지는 않았습니다. 시간 제한 안에서 실패하거나, 특정 케이스에서 깨지는 알고리즘은 점수가 높아도 믿기 어렵습니다. 그래서 저는 baseline을 통과하는 안정적인 경로를 남기고, 개선 탐색은 그 위에 얹는 방식으로 정리했습니다.
검증도 알고리즘만큼 중요했습니다. 상태 표현이 맞는지, rehandling 계산이 의도대로 되는지, 출력이 제출 형식에 맞는지 계속 확인해야 했습니다. 이 작업을 하면서 저는 최적화 대회에서 성능과 안정성을 분리해서 볼 수 없다는 것을 배웠습니다.
남은 결론
이 프로젝트는 수상으로 끝난 작업은 아니었지만, 최적화 문제를 실전 대회 형식으로 처음 끝까지 다룬 경험이었습니다. 제가 얻은 결론은 단순합니다. 복잡한 알고리즘 이름보다 입력 검증, 상태 표현, fallback, 실행 안정성이 먼저입니다. 이후 데이터 분석이나 시스템 설계를 할 때도 저는 이 경험 때문에 "좋은 아이디어가 실패했을 때 무엇이 남는가"를 더 먼저 생각하게 됐습니다.
