NVIDIA cuOpt는 복잡한 라우팅 문제를 해결하기 위해 가속화된 최적화 엔진입니다. 또한 휴식 시간, 대기 시간, 차량의 여러 비용 및 시간 매트릭스, 다양한 목표, 주문-차량 매칭, 차량 시작 및 종료 위치, 차량 시작 및 종료 시간 등과 같은 다양한 측면의 문제를 효율적으로 해결합니다.
구체적으로, cuOpt는 두 가지 문제 CVRPTW(Capacitated Vehicle Routing Problem with Time Windows) 및 PDPTW(Pickup and Delivery Problem with Time Windows)의 여러 변형을 해결합니다. 이러한 문제의 목표는 각 주문에서 차량 수와 총 이동 거리를 최소화하면서 고객의 요청을 처리하는 것입니다.
SINTEF에서 검증한 바와 같이 cuOpt는 최대 라우팅 벤치마크에서 지난 3년 동안 세운 23개의 세계 기록을 경신했습니다.
본 게시물에서는 최적화 알고리즘의 핵심 요소와 그 정의, 그리고 NVIDIA cuOpt를 업계 최고의 솔루션과 벤치마킹하는 프로세스를 살펴보고 이러한 비교의 중요성에 대해 설명할 예정입니다. 게시물 전반에서는 CVRPTW의 주문과 PDPTW 문제의 픽업-배송 주문 쌍에 ‘요청(request)’이라는 용어를 사용합니다.
이 영역에는 다양한 제약 조건과 문제 차원이 있지만 본 게시물에서 다루는 범위는 용량 및 시간대 제약 조건으로 제한됩니다. 용량 제약은 차량에 있는 총 상품이 언제든 차량의 용량을 초과할 수 없도록 시행합니다. 시간대 제약은 주문이 시간대의 시작보다 이르지 않고, 시간대의 끝보다 늦지 않은 시간에 서비스되도록 시행합니다.
조합 최적화
조합 최적화 문제는 검색 공간에서 가능한 상태의 수를 계승적으로 증가시키는, 세상에서 가장 계산 비용이 많이 드는(NP-hard) 문제 중 하나입니다. 대규모 문제에는 정확한 알고리즘을 사용할 수 없으므로 최적 지점을 향해 솔루션을 근사화하는 휴리스틱이 사용됩니다. 휴리스틱은 2차 또는 더 높은 연산 복잡도로 연산 비용이 많이 드는 다양한 알고리즘을 사용하여 검색 공간을 탐색합니다.
높은 복잡성과 문제의 특성으로 인해 대규모 병렬 GPU를 사용하여 이러한 알고리즘을 가속화할 수 있습니다. GPU 가속화로 최적에 가까운 솔루션을 합리적인 시간 안에 얻을 수 있습니다.
발전적인 경로 최적화 알고리즘 구축
일반적인 라우팅 솔버는 초기 솔루션 생성과 솔루션 개선이라는 두 단계로 구성됩니다. 이 섹션에서는 초기 솔루션을 생성하고 개선하는 절차를 설명합니다.
초기 솔루션 생성 알고리즘
모든 제약 조건을 충족하는 제한된 플릿으로 실현 가능한 초기 솔루션을 생성하는 것은 NP-hard 문제 그 자체입니다. 우리 팀은 요청을 경로에 배치하기 위해 GES(Guided Ejection Search) 알고리즘을 개선하고 병렬화했습니다.
GES의 주요 아이디어는 간단합니다. 먼저 요청을 경로에 삽입하려고 시도합니다. 해당 요청을 삽입할 수 없는 경우에는 경로에서 하나 이상의 삽입하기 쉬운 요청을 제거하고 해당 요청을 완화된 경로에 삽입합니다. 각 요청에 대한 페널티 점수(p-점수)는 해당 요청을 경로에 삽입하기의 어려움을 나타냅니다. 알고리즘은 제거된 요청의 p-점수 합계가 고려되는 요청보다 작은 경우에만 요청을 삽입합니다.
요청을 경로에 삽입할 수 없을 때마다, 설령 요청을 제거하더라도 해당 요청의 p-점수를 증가시키고 다시 시도합니다. 처리되지 않은 요청은 모두 이젝션 풀에 보관하고 알고리즘은 이젝션 풀이 비워질 때까지 실행됩니다. 다시 말해, 모든 요청이 처리될 때까지 알고리즘이 실행됩니다.
이 알고리즘의 주요 단점은 순환(솔루션의 이전 노드 집합으로 돌아감), 배출된 노드 수가 많을 때 배출 조합을 찾는 속도가 느리고, 약하고 무작위로 교란된 솔루션만 고려한다는 점입니다. 이러한 단점을 제거하여 현재 최신 방법보다 훨씬 적은 수의 경로로 솔루션을 생성할 수 있게 되었습니다.
제거 알고리즘을 더 자세히 살펴보기 전에 타당성 검사와 솔루션 평가가 시간 왜곡 방법을 사용하여 일정한 시간에 수행된다는 점을 이해하는 것이 중요합니다. 이 접근 방식은 계산 시간을 크게 줄여주지만 임의의 수의 제거를 검색하는 사전 순서를 따라야 하기 때문에 병렬 처리가 더 어려워집니다.
제거할 요청과 고려된 요청을 실행 가능하도록 삽입할 위치를 찾는 것은 계산 비용이 많이 드는 문제입니다. 제거된 요청 수와 관련하여 기하급수적으로 증가하는 모든 경로의 모든 삽입 위치를 확인해야 합니다. 실험 결과에 따르면 소수의 제거는 알고리즘의 순환을 일으킵니다.
따라서 NVIDIA는 광범위한 검색이 수행될 때 최대 10개의 요청(휴리스틱)과 5개의 요청을 병렬로 제거할 수 있는 방법을 제안합니다. 우리는 각 경로에서 조각을 꺼내고 스레드 블록에서 이러한 임시 경로를 처리하여 제거 알고리즘을 병렬화합니다. 그런 다음, 고려된 요청을 가능한 모든 위치에 병렬로 삽입하려고 시도합니다.
심층 검색 알고리즘은 경로에 있는 모든 요청의 제거에 가능한 모든 순열을 시도합니다. 각 요청 삽입 위치에 서로 다른 스레드 블록을 사용하고 사전 순서를 독립적인 하위 순열로 분할하여 사전 검색을 병렬로 수행합니다.
GES 알고리즘은 제한 시간이 소진되거나 요청 풀이 비워질 때까지 반복됩니다. 반복할 때마다 솔루션을 교란하여 솔루션 상태를 개선하고 솔루션에 빈틈을 주어 실행 가능한 삽입을 찾을 수 있도록 합니다. 섭동은 경로 사이 및 경로 내에서 노드를 무작위로 재배치하고 교체하는 무작위 지역 탐색입니다.
요청을 충족하는 최적의 차량 수를 찾은 후에는 목표를 최소화하는 개선 단계로 전환합니다. 기본적으로 이는 총 이동 거리이지만 cuOpt에서 다른 목표를 구성할 수도 있습니다.
발전적 프로세스 및 지역 탐색 알고리즘
개선 단계는 여러 솔루션에서 작동하며 발전적 전략을 사용하여 개선합니다. 생성된 솔루션은 모집단에 배치됩니다. 충분히 다양한 초기 솔루션에 도달하기 위해 생성 프로세스에서 무작위화를 사용합니다. GPU 아키텍처를 활용하여 여러 다양한 솔루션을 병렬로 생성합니다. 다양한 모집단이 솔루션 최상의 특성을 새로운 세대에 유지하면서, 발전적인 개선 프로세스를 거칩니다.
발전적인 프로세스의 단일 단계에서는 두 개의 무작위 솔루션을 선택하고 교차 연산자를 적용합니다. 그러면 상위 집단 모두에서 좋은 속성을 상속하는 하위 솔루션이 생성됩니다. 솔루션에 다양한 교차 연산자를 적용할 수 있으며, 그중 일부는 하위 집단을 불완전한 상태로 만듭니다. 중복 노드를 제거하거나, 라우팅되지 않은 노드를 삽입하거나, 지역 탐색을 수행하여 실행 불가능성을 수정하여 솔루션을 복구합니다.
예를 들어 순서 기반 교차 연산자는 다른 상위 솔루션에 나타나는 순서를 기준으로 한 상위 솔루션의 하나 이상의 경로에서 노드를 재정렬합니다. 결과로 생성되는 하위 집단은 한 상위 솔루션의 그룹화 속성과 다른 솔루션의 정렬 속성을 보존합니다. 이 특정 연산자의 결과는 시간 및 용량 제약과 관련하여 실행 불가능하고 완전한 솔루션입니다. cuOpt에는 솔루션에서 무작위로 실행되는 여러 교차 연산자가 포함되어 있습니다.
교차 후 지역 탐색 단계는 실행 불가능성을 줄이거나 없애거나 총 목표(이 경우 이동한 거리)를 개선하는 데 중요한 역할을 합니다. 지역 탐색의 목표 가중치는 최적화에 무엇이 중요한지에 따라 결정됩니다. 실현 가능성에 대한 가중치가 높을수록 솔루션을 실현 가능한 영역으로 반환하는 데 도움이 되며, 이는 일반적으로 대부분의 문제에 해당합니다.
지역 탐색은 하위 솔루션에 대한 로컬 최솟값을 찾은 다음, 추가 발전 단계에 참여합니다. 시간 예산 내에 얼마나 많은 개선 반복을 수행할 수 있는지에 대한 주요 요인이므로 빠른 지역 탐색이 중요합니다. 우리는 빠르고 대략적인 대규모 이웃 검색 알고리즘을 사용하여 성능을 유지하면서 우수한 지역 최솟값을 찾습니다. 기존의 접근 방식처럼 고정된 크기의 이웃 지역 탐색을 하는 대신 쉬운 개선 사항을 빠르게 포착하는 ‘네트’와 정체 상태에 도달했을 때 매우 심층적인 연산자를 설계했습니다.
빠른 연산자는 작은 이웃을 빠르게 탐색하며, 근사 연산자는 적용할 때마다 다른 움직임을 평가할 수 있습니다. 교차 연산자가 일부 경로를 그대로 유지하는 경우가 많기 때문에 이는 특히 중요합니다. 대규모 이웃 연산자는 그래프에서 음의 하위 집합 분리 주기를 찾기 위한 GPU 병렬 알고리즘에 설명된 대로 경로 간 이동 사이클로 표현되는 일련의 이동으로 요청을 이동합니다.
순환 연산자는 단순한 연산자로는 탐색할 수 없는 매우 큰 영역을 탐색합니다. 이는 제약 조건으로 인해 단순한 연산자가 검색 공간의 일부 언덕을 통과하는 것이 제한되기 때문입니다. 이 워크플로우를 통해 빠른 연산자를 자주 사용하고 계산 비용이 높은 심층 연산자를 덜 자주 사용할 수 있습니다.
GPU 병렬화는 각 가상 경로를 스레드 블록에 매핑하여 수행됩니다. 이를 통해 공유 메모리를 사용하여 이동을 검색하는 동안 일시적인 경로 관련 데이터를 저장할 수 있습니다. 임시 경로는 원래 경로의 복사본이거나 하나 이상의 요청이 제거되는 버전입니다. 스레드 블록의 스레드는 다른 경로에서 임시 경로의 모든 위치로 가능한 모든 요청을 삽입하려고 시도합니다.
모든 움직임을 찾고 기록하면 각각의 삽입/제거 비용 델타를 합산하여 경로 쌍당 최상의 움직임을 찾을 수 있습니다. 비용 델타는 목표 가중치에 의해 계산되며, 여기에는 실현불가능성 페널티 가중치도 포함됩니다. 그러한 움직임이 수정되는 경로의 관점에서 서로 배타적인 경우 그러한 움직임을 여러 번 실행합니다.
cuOpt 벤치마킹
NVIDIA는 cuOpt의 성능과 품질을 지속적으로 개선해 왔습니다. 품질을 측정하기 위해 CVRPTW에 대한 Gehring & Homberger 및 PDPTW에 대한 Li & Lim 등 가장 많이 연구된 벤치마크에서 가장 잘 알려진 솔루션과 솔버를 벤치마킹했습니다. 실제로 솔버가 원하는 솔루션에 얼마나 빨리 도달할 수 있는지가 기업에 중요한 문제입니다.
평가 기준 및 목표
- 정확도는 목표 측면에서 발견된 솔루션과 가장 잘 알려진 솔루션(Best Known Solutions, BKS) 간의 비율 차이로 정의됩니다. 문제 사양은 첫 번째 목표를 차량 수로, 두 번째 목표를 주행 거리로 명시합니다.
- 솔루션 시간 측정은 BKS 또는 원하는 목표 결과에 대한 특정 격차에 도달하는 데 필요한 시간을 나타냅니다. 솔루션 구현 시간은 실제 사용 사례에서 아주 중요한 기준 중 하나입니다. 제한된 시간 내에 정확도가 높은 솔루션에 도달하는 것이 중요합니다. 조합 최적화 알고리즘은 상당한 시간이 걸립니다.
그림 3 및 4는 대규모 벤치마크 인스턴스의 하위 세트에 대한 솔버의 수렴 동작을 보여줍니다.
각 범주(C1_10_1, C2_10_1, R1_10_1, R2_10_1, RC1_10_1, RC2_10_1)에서 인스턴스 하나를 선택하여 (클러스터, 무작위) 및 (긴 경로, 짧은 경로) 인스턴스에 따른 솔버의 전반적인 동작을 표시합니다. 1분마다 샘플링되는 집계된 합계는 집계된 BKS와 비교됩니다.
처음에는 급격한 수렴으로 인해 시간이 경과함에 따라 총 BKS에 천천히 접근하게 됩니다. 이러한 인스턴스 집합의 경우 BKS의 총 차량 수를 일치시킬 수 있었습니다. cuOpt 솔버는 거의 모든 Gehring & Homberger 인스턴스에서 BKS 차량 수를 찾을 수 있습니다. 그러나 실제 성능은 개선 단계와 비교하여 초기 솔루션 생성에 소요된 시간에 따라 달라집니다.
솔버는 더 큰 인스턴스에서 빠르게 수렴되지만 더 작은 인스턴스에서는 훨씬 빠르게 수렴됩니다. 다음 표에서는 다양한 문제 크기에서 BKS에 도달하는 동시에 모든 문제에 대해 BKS와 동일한 차량 수를 달성하는 데 걸리는 시간을 보여줍니다.
23개의 세계 신기록을 세운 cuOpt
cuOpt는 GPU 가속화 휴리스틱의 새로운 접근 방식과 최첨단 진화 전략을 통해 Gehring & Homberger 벤치마크의 인스턴스 15개와 Li & Lim 벤치마크의 인스턴스 8개에 대한 기록을 경신했습니다.
NVIDIA는 이제 지난 3년간의 CVRPTW 및 PDPTW 범주에 대한 모든 기록을 보유하고 있습니다.
그림 5에서 각 엣지는 한 작업에서 다른 작업으로 이동하는 경로를 나타냅니다. 녹색 선은 이전 레코드에 공통적인 엣지를 나타냅니다. 파란색과 빨간색 가장자리는 두 솔루션 간에 다릅니다. 혁신적인 전략 덕분에 cuOpt 솔루션은 가능한 솔루션의 검색 공간에서 완전히 다른 위치에 있으며, 이는 다양한 엣지가 있음을 의미합니다.
Gehring & Homberger의 BKS에 대한 전반적인 평균 격차는 거리 격차 -0.07%, 차량 수 격차 0.29%입니다. Li & Lim의 BKS에 대한 전반적인 평균 격차는 거리 격차 1.22%, 차량 수 격차 0.36%입니다. 벤치마크는 단일 NVIDIA H100 GPU에서 200분 동안 실행되었습니다.
결론
NVIDIA cuOpt는 GPU 가속화 및 RAPIDS와 같은 NVIDIA 기술을 통해 몇 초 만에 고품질 솔루션을 달성합니다. CPU 기반 구현에 비해 지역 탐색 작업의 속도가 100배 빨라졌습니다. CPU 기반 솔버는 유사한 솔루션에 도달하는 데 몇 시간이 걸립니다.
NVIDIA cuOpt과 함께 시작해 보세요. NVIDIA API 카탈로그 및 NVIDIA LaunchPad를 통해 모델을 살펴볼 수도 있습니다. cuOpt가 조직의 시간과 비용 절감에 어떻게 도움이 되는지 알아보세요.
NVIDIA GTC 2024 세션 최적화 AI의 발전에 참여하여 NVIDIA 최적화 AI 엔지니어링 매니저 Alex Fender의 이야기를 들어보세요. 또한 NVIDIA Deep Learning Institute의 경로 최적화 마이크로 서비스를 사용하여 효율성 및 비용 절감을 촉진하는 방법 알아보기를 수강할 수 있습니다.
관련 리소스
- GTC 세션: 경로 최적화 클라우드 서비스를 사용하여 효율성 및 비용 절감을 촉진하는 방법 알아보기
- GTC 세션: 최적화 AI의 발전
- GTC 세션: 강력한 개발자 도구로 CUDA 디버깅 및 성능 이해하기
- NGC 컨테이너: cuOpt
- SDK: cuOpt
- 웨비나: NVIDIA Jetson에서 NITROS와 함께 자체 CUDA ROS 노드 사용하기
