선석배정문제 (Berth Allocation Problem)
쉽게 풀면
손님이 몰리는 식당에서 매니저는 어느 팀을 어느 테이블에 몇 시에 앉힐지 계속 판단합니다. 큰 팀은 넓은 자리가 필요하고, 예약해 둔 손님을 너무 오래 세워 둘 수도 없습니다. 항만도 같습니다. 배마다 길이가 다르고 하역할 화물량이 달라 필요한 자리 폭과 시간이 제각각인데 안벽은 한정되어 있습니다. 어느 배를 어느 구간에 몇 시부터 붙일지 정하는 것이 선석배정문제이며, 계획을 잘못 짜면 배가 바다에서 대기하며 연료를 태우고 체선료 분쟁으로 이어집니다.
왜 중요한가
선석은 항만에서 가장 비싼 자원이고 배 한 척이 지연되면 노선 전체 일정이 흔들립니다. 선석배정문제는 항만 생산성을 좌우하는 핵심 의사결정이어서, 항만 운영 연구에서 안벽크레인 배정과 함께 가장 많이 다뤄지는 최적화 주제로 자리 잡았습니다.
논문에서는 이렇게 쓰입니다
안벽을 칸으로 나누지 않고 배를 어디든 붙일 수 있다고 보는 모형을 수식으로 세운 뒤, 최적해에 가까운 답을 빠르게 찾는 계산 절차를 함께 내놓았다는 뜻입니다.
자리를 정하는 문제와 크레인을 몇 대 붙일지 정하는 문제를 따로 풀지 않고 함께 풀었더니 배가 항만에 머무는 시간이 줄었다는 결과를 보고한 문장입니다.
배가 예정보다 늦게 올 가능성을 미리 계획에 넣어 여유를 둔 배정이, 한 척의 지연이 뒤따르는 배들로 번지는 것을 줄여 주었다는 의미입니다.
조금 더 깊게 보면
선석배정문제는 안벽을 고정된 구획으로 보는 이산형과 배 길이만큼 임의의 위치에 배정하는 연속형으로 나뉘며, 선박 도착 시각을 모두 알고 있다고 보는 정적 모형과 순차적으로 도착한다고 보는 동적 모형으로도 구분됩니다. 목적함수는 대개 대기시간, 하역 완료 지연, 선호 위치에서 벗어난 거리의 가중합입니다. 문제 자체가 계산적으로 어려워 유전 알고리즘 같은 발견적 해법이 널리 쓰이며, 최근에는 야드관리시스템의 장치장 배정과 통합해 푸는 연구가 늘고 있습니다.
주의할 점
단순한 순번 정하기가 아닙니다. 배의 길이와 흘수, 계약상 선호 선석, 크레인 가용 대수가 함께 걸린 자원 제약 문제여서 선착순 배정이 최선이 되는 경우는 드뭅니다. 또 실무 계획은 도착 지연으로 자주 무너지므로, 정적 최적해를 그대로 쓰기보다 재계획 절차를 함께 설계해야 합니다.