화물선용 수학적 최적화 기술

 (research.google)
1P by GN⁺ | ★ favorite | 댓글 1개
  • Google Research의 Operations Research 팀이 정기 컨테이너선의 네트워크 설계·일정·컨테이너 경로를 함께 최적화하는 Shipping Network Design API를 공개함
  • 이 문제는 선박의 항구 방문 순서, 도착·출발 시간, 컨테이너의 출발지-목적지 경로를 동시에 정해야 해 WorldLarge 기준 500척 선박·200개 항구 규모까지 복잡해짐
  • 초기 접근인 이중 컬럼 생성과 CP-SAT는 소·중규모에서 증명 가능한 최적해를 찾았지만, 대규모 문제에는 큰 이웃 탐색과 가변 이웃 탐색을 결합한 휴리스틱이 필요했음
  • LINERLIB 벤치마크에서 WorldSmall, EuropeAsia, Pacific, Mediterranean의 컨테이너 처리량은 각각 35%, 14%, 35%, 32% 늘었고, 사용 선박 수는 7%, 15%, 4%, 23% 줄어듦
  • Google은 이 방법을 WorldLarge 규모의 네트워크 설계와 일정 문제를 풀 수 있는 첫 방법으로 보고, Shipping Network Design API를 향후 Operations Research APIs의 일부로 제공함

컨테이너 해운 네트워크를 동시에 최적화하는 문제

  • 전 세계 상품의 90% 는 바다를 통해 이동하며, 대형 화물선은 길이 0.25마일, 무게 25만 톤, 1만2000개 컨테이너, 총 10억 달러 상당의 화물을 실을 수 있음
  • 화물선은 항공기, 열차, 트럭과 달리 거의 계속 운항하고, 바다 위에서 순환 경로를 따라 움직임
  • 비효율적인 경로와 일정은 컨테이너의 항구 체류, 선박의 해상 대기, 물류 흐름의 지연을 만들고 제품 가격에도 영향을 줌
  • Google의 Shipping Network Design API는 이 문제에 대한 새 해법을 구현함
    • 기존에 알려진 시도보다 더 빠르고 더 잘 확장됨
    • 컨테이너 선사의 이익을 두 배로 만들고, 13% 더 많은 컨테이너를 운송하며, 15% 더 적은 선박으로 운영할 수 있음

LSNDSP가 함께 풀어야 하는 세 결정

  • Liner Shipping Network Design and Scheduling Problem, 즉 LSNDSP는 세 가지 결정을 동시에 다룸
    • 네트워크 설계: 선박이 항구를 어떤 순서로 방문할지 결정함
    • 네트워크 일정: 선박이 언제 도착하고 떠날지 정함
    • 컨테이너 경로 지정: 컨테이너가 출발지에서 목적지까지 어떤 여정을 거칠지 선택함
  • 컨테이너 해운사는 세 문제를 모두 풀어야 하지만, 보통은 순차적으로 처리함
  • 세 문제를 동시에 풀면 난도는 높아지지만 더 나은 해를 찾을 가능성이 커짐
  • 네트워크 설계의 결과는 소수의 선박이 따르는 서비스 라인으로 이어짐
    • 예를 들어 동아시아에서 수에즈 운하를 지나 남유럽으로 가는 경로가 될 수 있음
    • 서비스 라인은 날짜와 함께 공개되어 화주가 언제 어디에 컨테이너를 준비해야 하는지 알 수 있음

항구 접안, 환적, 지연이 만드는 제약

  • 컨테이너선은 원하는 때에 항구에 접안할 수 없고, 사전에 정해진 접안 슬롯을 사용해야 함
  • 선박은 항구에 접근한 뒤 접안 가능 시점까지 해상 정박지에서 닻을 내리고 대기할 수 있음
    • 항구가 혼잡하면 정박지에서 몇 시간 또는 며칠 동안 머물 수 있음
  • 정확한 네트워크 일정은 단순히 어느 날 접안하는지가 아니라 어느 시간에 접안하는지까지 포함함
    • 특정 시간에 맞추기 위해 속도를 높일 수 있음
    • 연료 절감을 위해 속도를 낮추는 선택도 가능함
  • 항구에 접안하면 크레인이 컨테이너를 내리고, 다음 항차에 실을 컨테이너를 다시 선박에 적재함
  • 일정이 밀리면 예정된 컨테이너를 모두 싣기 전에 항구를 떠나는 cut-and-run이 발생할 수 있음
    • 남은 컨테이너는 이후 선박이 싣게 됨
  • 컨테이너가 출발지에서 목적지로 가는 중간 항구에서 시간을 보내는 경우를 환적이라고 부름
    • 환적은 LSNDSP의 가능한 해 수를 더 크게 늘림
    • 컨테이너 경로 생성에 작용하는 여러 제약 중 하나임

최적화 방법: 컬럼 생성에서 이웃 탐색까지

  • 모든 최적화 문제는 변수, 변수에 대한 제약, 최소화 또는 최대화할 목적 함수로 구성됨
    • 예: 선박과 항구는 변수
    • 예: 선박에 실을 수 있는 컨테이너 수는 제약
    • 예: 운송 컨테이너 수 최대화는 목적 함수
  • 변수와 제약은 보통 행렬로 표현되며, 열은 변수, 행은 제약을 나타냄
  • 대규모 문제를 분해하는 일반 기법으로 컬럼 생성을 사용함
    • 처음에는 변수 일부만 고려함
    • 이후 원래 문제를 더 잘 근사하기 위해 새 변수, 즉 새 열을 생성함
  • Google은 문제를 분석해 어떤 열을 생성하는 것이 좋은지 예측하는 소프트웨어 라이브러리를 개발함
    • 이 라이브러리는 수학적 프로그래밍 프레임워크인 MathOpt를 통해 오픈소스로 공개될 예정임

두 가지 기본 접근의 한계

  • 이중 컬럼 생성은 네트워크 설계와 컨테이너 경로 지정을 서로 결합된 두 문제로 봄
    • 각 문제는 가장 좋은 선택지를 고르는 주 선택 문제와 합리적 선택지를 찾는 보조 생성 문제로 구성됨
    • 각 문제 쌍에 최단 경로 알고리듬을 적용해 합리적 선택지를 생성함
    • 이후 선형계획 솔버 Glop을 사용해 각 문제의 최선 선택지를 고름
    • 두 문제에 컬럼 생성을 동시에 적용하고, 한 문제의 중간 결과가 다른 문제의 진행에 영향을 주도록 함
    • 증명 가능한 최적해를 찾을 수 있었지만 중간 규모 문제까지만 잘 확장됨
  • CP-SAT 기반 구현도 시도함
    • Google의 제약 프로그래밍 솔버 CP-SAT를 사용함
    • 중간 규모 네트워크까지는 잘 작동했지만 전 세계 해운 문제 규모로는 확장되지 않음
  • 두 접근 모두 소·중규모 문제에서는 증명 가능한 최적해를 찾았으나, 대규모 확장성이 부족했음

대규모 확장을 위한 휴리스틱

  • 확장성을 높이기 위해 기존 해 주변의 이웃을 살펴 개선 기회를 찾는 로컬 탐색 변형 두 가지를 적용함
  • 큰 이웃 탐색은 해의 일부를 고정한 뒤 앞의 방법들을 적용함
    • 예: “이 선박은 격주 화요일에 Los Angeles를 방문한다” 같은 조건을 고정함
    • 검색 공간을 줄여 확장성을 높임
  • 가변 이웃 탐색은 네트워크와 일정 양쪽의 이웃을 탐색함
    • 탐색을 병렬화하고 여러 머신에 분산해 많은 이웃을 동시에 평가함
    • 검색 공간을 제한하면서 Operations Research와 해운 산업의 지식을 반영할 수 있음
  • 두 접근 모두 유망한 해의 일부를 잠가두고, 이미 좋은 해에서 출발해 더 나은 해로 개선하는 점진적 방식을 사용함
  • 이전 시도들은 문제 해결이 훨씬 어려워진다는 이유로 운송 시간을 고려하지 않았지만, Google은 운송 시간을 포함하면 해의 품질이 크게 개선되는 것을 확인함

LINERLIB 벤치마크 결과

  • 성능 평가는 해운 네트워크 설계 문제를 위한 산업 벤치마크 LINERLIB를 사용함
    • 벤치마크에는 컨테이너 해운 시나리오의 선대, 항구, 컨테이너 수요가 포함됨
  • 테스트 시나리오는 WorldSmall, EuropeAsia, WorldLarge를 포함함
    • WorldLarge는 500척 선박, 200개 항구, 약 14만 개 컨테이너를 포함함
  • 최적화 목적은 단순히 컨테이너 수 최대화나 선박 수 최소화가 아님
    • 컨테이너 수만 최대화하면 더 많은 선박을 투입해 운영비가 커질 수 있음
    • 선박 수만 최소화하면 한 척으로 모든 컨테이너를 운송하는 식의 비현실적으로 긴 배송 시간이 나올 수 있음
  • LINERLIB는 정시 배송 수익에서 항해 비용과 항구 컨테이너 처리 비용을 뺀 추정 이익으로 균형을 맞춤
  • 기준선과 비교해 Google의 방법은 더 적은 선박으로 더 많은 컨테이너를 경로 지정함
    • WorldSmall: 컨테이너 처리량 35% 증가, 선박 수 7% 감소
    • EuropeAsia: 컨테이너 처리량 14% 증가, 선박 수 15% 감소
    • Pacific: 컨테이너 처리량 35% 증가, 선박 수 4% 감소
    • Mediterranean: 컨테이너 처리량 32% 증가, 선박 수 23% 감소
  • LINERLIB의 경제적 가정에 기반하면 예상 이익률도 상당히 개선됨

API와 후속 공개 자료

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이 업계의 터미널 쪽에 있는데, 흥미롭긴 하지만 매우 학술적으로 보임
    실제로 선사와 협업해서 만든 건지 궁금함. 터미널 쪽에서는 지금 컨테이너 최적화에 깊이 들어가 있는데 정말 악몽에 가까움. 같은 회사가 소유한 터미널끼리도 운영 방식이 크게 다르고, 용어조차 회사 내부에서 다를 때가 많음. 한 터미널에 맞춰 최적화해도 다음 터미널에서는 80%를 새로 만들어야 해서 어떤 해법이든 확장하기가 매우 어려움

    • 산업 최적화 문제를 보면 항상 엄청난 돈이 방치된 것처럼 보이지만, 실제로는 문서화되지 않은 사람 중심 제약이 일을 크게 복잡하게 만듦
      예를 들어 독일 엔지니어들은 양산 전 차량의 기능을 잠그는 데 반발했는데, 그러면 여가용으로 쓸 수 없기 때문이었음. 의료 현장에서는 초과근무 비용이 수십억 단위로 나가서 일정 개선이 쉬워 보였지만, 노조 제약이 많고 채용 공급도 부족했음. Google 해법이 얼마나 현실적인지 궁금함. 후티 미사일 같은 제약도 들어가나? 경험상 증명 가능한 최적해보다 예상 밖 변화에 쉽게 조정되는 해법이 더 가치 있는 경우가 많았음
    • 성능 평가에 쓴 벤치마크 데이터는 Maersk에서 나온 것임: https://github.com/blof/LINERLIB
    • 해운은 아니지만 제조업에서 15년 일했고, 주로 테스트 엔지니어링과 자동화, 창고/자재 관리, 운송/물류도 다뤘음. 석사는 제조업 운영 연구였음
      객관적 최적화가 대체로 학술적이라는 데 동의함. 표준화된 프로세스의 가장 효율적인 버전을 그대로 따르기 어렵거나 불가능한 이유는 늘 있음. 때로는 사람 때문에 생기는 “바보 같은” 이유이고, 자주 날씨·다운타임·공급망 중단·계절성에 따른 수요 신호와 예측의 울퉁불퉁함 같은 외부성을 반영한 합리적 이유임. 그래도 알려진 예외를 기준으로 표준 프로세스를 만들기보다, 가장 효율적인 프로세스에서 시작해 예외 처리를 붙이는 편이 거의 항상 낫다고 봄. 예외가 규칙이 되게 두면 최적보다 항상 덜 효율적으로 운영하게 됨
    • 나도 터미널과 내륙 운송 회사 쪽 일을 함. 적재 계획 최적화, 선석 배정, 크레인 분할 같은 “멋져 보이는” 학술 문제를 풀려는 사람은 많지만, 실제 구현되는 건 아주 적음
      이 업계는 어렵고, 항만 노동자 노조가 전통적으로 강해서 정치 지형은 더 어렵다. 깔끔하게 나누고 이름 붙일 수 있는 문제들은 실제로는 서로 얽혀 있고, 알고리즘이 사용자를 위해 “마법처럼” 풀어줄 거라고 기대하면 거의 실패함. “그냥 외판원 문제 / 제약 해결기 / 원하는 접근법만 돌리면 되잖아?”라고 생각하고 뛰어드는 소프트웨어 강자들을 이 업계는 쉽게 집어삼킴. 똑똑한 사람은 분명 필요하지만, 겸손하게 시작하고 실제 사용자와 먼저 이야기해야 함. 프로필에 연락처가 없어 보이는데, 이 업계의 다른 회사와 생각을 나누고 싶다면 메일을 보내줬으면 함. 특히 복합 운송 비중이 높은 연 100만 TEU 미만 터미널 세그먼트에서 흥미로운 일을 하고 있음
    • 이 분야 밖 사람들을 위해 지금 하는 일을 좀 더 자세히 설명해줄 수 있는지 궁금함

  • 컨테이너화 초창기 역사를 다룬 The Box를 읽고 있는데 정말 재미있음
    공학, 설계, 비즈니스, 역사가 섞인 즐거운 읽을거리를 찾는 사람에게 강력 추천함. 내가 겪는 작은 코딩 문제들이 우스워 보이게 만들기도 함

    • 훌륭한 책이고 추천에 동의함
      반박이 많이 나올 것 같지만 진심으로 말하자면, 20피트 해상 컨테이너가 세계에 미친 영향은 대규모 언어 모델이 앞으로 달성할 가능성이 있는 영향보다 더 컸다고 봄. 먼저 그 책을 읽고 왜 내가 틀렸는지 말해보길 바람. 물론 나는 틀리지 않았음
    • “The Box”의 Wikipedia 문서: https://en.m.wikipedia.org/wiki/The_Box_(Levinson_book)
    • Flexport에서는 신입에게 이 책을 나눠줬음. 적어도 몇 년 전에는 그랬음

  • 매우 큰 선단에서는 컨테이너 최적화가 아직 풀리지 않은 문제였던 모양임. 몰랐음
    Google 운영 연구가 기존 해법 대비 활용률을 10~20% 개선했다면 놀라운 수준임

  • 공개한 이 API 엔드포인트를 실제로 쓰는 곳이 있을지 매우 궁금함: https://developers.google.com/optimization/service/shipping/...
    그래도 꽤 멋짐

    • Google Cloud에서 2015~2023년에 일한 전문 경험상 이런 운영 연구 API는 1) 학술적이고, 2) Google Cloud 솔루션 아키텍트와 엔지니어가 GCP 위에서 돌아가는 고객 맞춤형 비즈니스 솔루션을 만들 때 상업적으로 쓰는 성격이 강함
      대표적으로 Route Optimization API도 기업 운영 연구 팀이 이런 식으로 공개했고, 이후 몇몇 알파 고객의 입력을 받아 그 위에 Fleet Engine 솔루션이 만들어졌음. 운영 연구 API가 Google Cloud를 통해 노출되기 전까지는 SLA나 신뢰성 보장이 없으므로 학술적 용도 외에는 쓰지 않는 게 좋다고 봄. 내 2센트임
      https://developers.google.com/maps/documentation/transportat...
    • 시도해보지 않는 게 오히려 무책임할 수도 있음. 이게 계획 담당자들이 마주하는 문제와 제약의 전체 형태인지 궁금함. Flexport는 이 분야에서 SF에 기반을 둔 매출 33억 달러 회사임
    • Google의 무덤[1]이 빠르게 커지고 있어서 새 Google 발표에는 조심스러움. 이런 API는 미래에 대체해야 할 때 특히 문제가 커질 것 같음
      [1]: https://killedbygoogle.com/

  • 체선료가 고려되지 않는다면 정말 시도할 가치가 있는지 모르겠음
    https://developers.google.com/optimization/service/reference...

  • Omega Tau Podcast가 컨테이너 선적에 대해 아주 좋은 에피소드[0]를 냈고, 컨테이너 배치 최적화와 경로 계획도 다룸. 강력 추천함
    [0]: https://omegataupodcast.net/146-container-shipping/

  • “비행기와 달리 화물선은 거의 계속 운항한다”는 표현은 조금 따져볼 여지가 있음
    화물선은 항해 중 유지보수를 많이 하긴 하지만, 그 외에는 차이가 훨씬 작다고 봄. 항구에서는 며칠에 걸쳐 하역과 선적을 하며 회전하고, 선석을 기다리느라 몇 시간 또는 며칠 대기하기도 함. Delta A350 사례를 보면 공항에서 3시간 회전하는 시간을 빼면 사실상 24시간 내내 움직임: https://www.flightradar24.com/data/aircraft/n513dz

    • 하역 중에도 “운항 중”이라고 부를 수 있다고 봄

  • 동네 식당 같은 곳의 점주나 매니저들이 아르바이트 직원 일정 짜느라 골치 아프다고 하고, 그게 급여를 많이 받는 이유라고까지 말하는 걸 떠올리게 함
    알고리즘으로 풀면 되지 않나 싶었음

    • 많은 사람은 근무 시간이 크게 바뀌는 걸 좋아하지 않음
      직원 절반이 Taylor Swift를 보러 간 밤을 메울 수는 있겠지만, 그렇게 사람들을 불러내면 그 사람들의 다음 근무도 다시 누군가가 메워야 하고, 그게 이어지다 보면 한 번도 같이 일해본 적 없는 사람들로 완전히 다른 일정표가 만들어짐. 제약을 더 넣으면 고칠 수는 있지만, 그걸 전부 적어내고 우선순위를 매기는 것만 해도 간단하지 않음. 사람들은 레고 블록이 아님
    • 이게 내가 정확히 풀고 싶은 문제임. 일정을 짜는 거의 모든 사람에게서 같은 이야기를 들음
      운영 연구 배경이 있어서 늘 이상하게 느껴짐. 문제들은 일반적인 해결기로 모델링하고 풀기에 단순해 보이고, 고급 기법 없이도 가치가 커 보임. 문제는 운영 연구가 전반적으로 접근성이 낮다는 데 있음. 잘 지원되는 해결기 대부분은 수학적 패러다임으로 문제를 정의하게 하는데, “보통 사람”은 보자마자 압도됨. 흔한 일정 문제용 기성 솔루션도 있지만 처음부터 쓰지 않았다면 각 사업장마다 고유한 변형이 있어서 완전 도입이 어렵다. 그 변형을 지원하지 않거나, 도구 안에 어떻게 끼워 넣어야 할지 알 수 없음. 일정을 더 잘 풀어보려는 의지가 있어도 찾게 되는 강의는 보통 상당한 프로그래밍 또는 수학 사전 지식을 가정함. Excel로는 부족하지만 운영 연구 전문가를 고용할 수 없는 “보통 사람”도 쓸 수 있는 노코드 모델링 환경을 일정 문제용으로 만들 수 있어야 한다고 봄
    • 이건 정말 중요한 문제이고, 많은 소프트웨어가 이미 다루고 있음
      거의 모든 대형 HR/인력 관리 시스템에 관련 옵션이 들어 있음. 예를 들어 https://www.workday.com/en-us/products/workforce-management/...와 https://www.oracle.com/human-capital-management/workforce-ma...가 있고, 전용 업체도 많음. 다만 다른 사람이 말했듯 이런 시스템은 논란도 있었음. 일부는 정상적인 인간적 필요를 고려하지 않는 방식으로 쓰이기 때문임. 예를 들어 연속 근무를 배정하거나, 짧은 통보로 일정을 바꾸거나, 인간 매니저라면 반영할 수 있는 육아 같은 현실 사정을 고려하지 못하는 경우가 있음
    • 같은 운영 연구 그룹에 식당용 일정 예제가 있음: https://developers.google.com/optimization/service/schedulin...
    • 조합 최적화 배경이 조금 있어서 이 분야나 학교 시간표 계획 같은 소프트웨어를 써볼까 생각한 적이 있음
      하지만 각 사업장마다 제약이 다르다는 게 문제임. 한 근무조에 응급 처치 가능자가 최소 1명 있어야 한다든지, Alice와 Bob은 사이가 안 좋다든지, 토요일을 2주 연속 일하면 안 된다든지, 근무조가 2주마다 바뀐다든지, 근무 사이에 최소 12시간이 있어야 한다든지 하는 식임. 상당수 조직이 쓸 만큼 유연한 도구는 결국 너무 복잡해서 쓰기 어려워질 것 같음

  • 이런 선박의 적재 계획이 아직 궁금함
    각 컨테이너의 경로 계획 다음 단계에서 근사적으로 풀어야 하는 문제일 것 같음. 적재 계획은 나중에 나오고, 전역 시스템 수준의 관점보다 훨씬 상황 의존적인 제약을 가짐. 대략 낙관적으로 봐도 안벽 크레인은 시간당 30~50회 이동하고, 선박당 2대나 4대, 많으면 6대가 붙으며, 껍질처럼 층층이 풀어야 함. Ultra Large Container Vessel은 14,501 TEU 이상, New Panamax는 10,000~14,500 TEU, Post-Panamax는 5,101~10,000 TEU, Panamax는 3,001~5,100 TEU임. 24,000 TEU를 40피트 컨테이너 1.2만 개라고 하면, 4대 × 크레인당 시간당 50개 × 하루 24시간 = 하루 1,200개 컨테이너 정도임.
    https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
    선박 적재 계획에는 항구에서의 가용성 외에도 중량, 균형, 전력, 화물 가치 허용 기준이 있음. 글에서 항구 조기 출항을 언급해서 이런 오버헤드가 궁금해졌고, 대략적인 계산을 해봤음

    • Technical University of Denmark(DTU)의 연구자가 온라인에 올린 강연이 있는데, 적재 문제 입문으로 꽤 좋음: https://www.youtube.com/watch?v=9ltz4G-lPdg
      이 분야에 실제로 관여하는 입장에서 보면, 스스로 일을 쉽게 만드는 방법이 많음. 해치 커버별 블록 단위로 계획하고, 컨테이너를 목적지·크기·중량별로 묶어서 대체 가능하다고 다루는 건 기본임. 그런 다음 작업 시작 전에 선박에서 터미널로 계획을 보내면, 터미널도 야드 내 컨테이너 위치를 아니까 최적화와 재배치를 할 수 있음. 각 컨테이너의 세부 사항을 무시하고 그룹에만 집중하기로 하면 적재 계획은 훨씬 쉬워짐. 훨씬 적은 작업으로 결과는 매우 비슷하고, 터미널이 운영을 최적화할 유연성도 더 커짐
답변달기