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

> Clean Markdown view of GeekNews topic #15210. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=15210](https://news.hada.io/topic?id=15210)
- GeekNews Markdown: [https://news.hada.io/topic/15210.md](https://news.hada.io/topic/15210.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-06-07T08:38:50+09:00
- Updated: 2024-06-07T08:38:50+09:00
- Original source: [research.google](https://research.google/blog/heuristics-on-the-high-seas-mathematical-optimization-for-cargo-ships/)
- Points: 1
- Comments: 1

## Topic Body

### 화물선의 수송 네트워크 최적화: 수학적 최적화 기법

#### 개요
- 구글 연구팀이 새로운 Shipping Network Design API를 발표함.
- 이 API는 화물선의 네트워크 설계 및 일정 문제를 해결하는 데 도움을 줌.
- 이 솔루션은 기존 방법보다 더 빠르고 효율적이며, 수익을 두 배로 늘리고, 더 적은 선박으로 더 많은 컨테이너를 운송할 수 있게 함.

#### 배경
- LSNDSP(선박 네트워크 설계 및 일정 문제)는 네트워크 설계, 네트워크 일정, 컨테이너 경로 설정의 세 가지 요소로 구성됨.
- 기존에는 이 문제들을 개별적으로 해결했으나, 동시에 해결하면 더 나은 솔루션을 찾을 수 있음.

#### 방법론
- 최적화 문제는 변수, 제약 조건, 목표 함수로 구성됨.
- 구글은 'Double Column Generation'과 'CP-SAT' 두 가지 접근 방식을 사용해 문제를 해결함.
- 이 방법들은 중소 규모 문제에 대해서는 최적의 솔루션을 제공하지만, 대규모 문제에는 적합하지 않음.
- 대규모 문제 해결을 위해 'Large Neighborhood Search'와 'Variable Neighborhood Search'를 사용함.
- 이 방법들은 검색 공간을 줄이고, 병렬 처리를 통해 효율성을 높임.

#### 결과
- LINERLIB 벤치마크를 사용해 성능을 평가함.
- 구글의 솔루션은 더 적은 선박으로 더 많은 컨테이너를 운송할 수 있게 함.
- 각 시나리오에서 효율성을 높이고, 수익을 크게 증가시킴.

#### 결론
- 구글의 최적화 기법은 대규모 선박 네트워크 설계 및 일정 문제를 해결할 수 있는 최초의 방법임.
- 이 연구가 글로벌 공급망의 효율성을 높이는 데 기여할 것으로 기대됨.

### GN⁺의 의견
- **기술적 배경**: LSNDSP는 복잡한 최적화 문제로, 네트워크 설계, 일정 관리, 경로 설정을 동시에 해결해야 함.
- **산업적 중요성**: 글로벌 무역의 90%가 해상 운송에 의존하고 있어, 이 문제의 해결은 경제적 영향이 큼.
- **기술적 도전**: 대규모 문제를 해결하기 위해 병렬 처리와 검색 공간 축소 등의 고급 기법이 필요함.
- **경쟁 제품**: 비슷한 기능을 제공하는 다른 최적화 솔루션으로는 IBM의 CPLEX, Gurobi 등이 있음.
- **고려 사항**: 새로운 기술 도입 시 초기 설정 비용과 학습 곡선이 있을 수 있음. 하지만 장기적으로는 효율성과 수익성을 크게 향상시킬 수 있음.

## Comments



### Comment 25990

- Author: neo
- Created: 2024-06-07T08:38:50+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40580142) 
- **터미널 측면에서의 의견**: 터미널 최적화는 매우 복잡하고, 각 터미널마다 방식이 달라서 확장하기 어려움.
- **책 "The Box" 추천**: 컨테이너화의 초기 역사에 대한 책으로, 엔지니어링, 디자인, 비즈니스, 역사를 혼합한 흥미로운 읽을거리임.
- **컨테이너 최적화 문제**: 대형 선단에 대한 컨테이너 최적화 문제는 해결되지 않았음.
- **Google OR의 개선**: Google OR이 기존 솔루션을 10%-20% 개선함.
- **API 사용 여부**: demurrage(체선료)가 고려되지 않은 상황에서 시도해볼 가치가 있는지 의문임.
- **API 엔드포인트 사용 호기심**: Google에서 제공하는 API 엔드포인트를 실제로 사용할지 궁금함.
- **Omega Tau Podcast 추천**: 컨테이너 선적 및 최적화에 대한 훌륭한 에피소드가 있음.
- **도커 컨테이너 실행**: 도커 컨테이너에서 실행될 때만 작동함.
- **알고리즘 사용 제안**: 파트타임 직원의 일정 계획을 알고리즘으로 해결할 수 있지 않을까 생각함.
- **OR-tools 서비스 제공**: OR-tools를 서비스로 제공하기 시작한 것 같음. 더 나은 API가 제공된다면 GCP 컴퓨팅 비용을 지불할 의향이 있음.
- **적재 계획에 대한 의문**: 적재 계획은 경로 계획 다음 단계로 해결해야 할 문제임. 크레인 작업 속도와 적재/하역 과정에 대한 대략적인 계산을 제시함.
- **적재 계획의 복잡성**: 적재 계획에는 무게, 균형, 전력, 가치 수용성 등의 기준이 포함됨. 이러한 복잡성 때문에 간단한 계산을 시도해봄.