가장 일반적인 최적화 작업 중 하나는 차량 라우팅으로, 일련의 위치를 방문하는 여러 차량에 대한 최적의 경로를 찾는 것입니다. 일반적으로 '최적'은 총 거리 또는 비용이 가장 적은 경로를 의미합니다. 다음은 라우팅 문제의 몇 가지 예입니다.
- 택배 배송 회사에서 배송 기사에게 배송 경로를 지정하려고 합니다.
- 케이블 TV 회사에서 기술자가 가정에서 서비스 호출을 할 수 있는 경로를 할당하려고 합니다.
- 차량 공유 회사에서 운전자가 승객을 태우고 내릴 경로를 할당하려고 합니다.
가장 유명한 경로 문제는 여행 영업사원 문제 (TSP)입니다. 여러 위치에 있는 고객을 만나고 출발지로 돌아가야 하는 영업사원이 가장 짧은 경로를 찾는 것입니다. TSP는 그래프로 표시할 수 있습니다. 그래프에서는 노드가 위치에 해당하고 에지 (또는 원호)는 위치 간의 직접 이동을 나타냅니다. 예를 들어 아래 그래프는 A, B, C, D로 표시된 네 개의 위치만 있는 TSP를 보여줍니다. 두 위치 사이의 거리는 두 위치를 연결하는 가장자리 옆에 있는 숫자로 계산됩니다.
가능한 모든 경로의 거리를 계산하면 최단 경로가 ACDBA이며 총 거리는 35 + 30 + 15 + 10 = 90임을 알 수 있습니다.
위치가 많으면 문제가 더 어려워집니다. 위의 예에는 경로가 6개뿐입니다. 그러나 위치가 10개 (시작점을 포함하지 않는 경우)가 있는 경우 경로 수는 362880입니다. 20개 위치의 경우 숫자가 2432902008176640000으로 이동합니다. 가능한 모든 경로를 철저히 검색하면 최단 거리를 찾을 수 있지만 이는 일부 위치를 제외한 모든 위치에서 계산하기가 쉽지 않습니다. 더 큰 문제의 경우 솔루션 공간을 지능적으로 검색하고 최적의 (또는 최적에 가까운) 솔루션을 찾기 위한 최적화 기술이 필요합니다.
보다 일반적인 버전의 TSP는 여러 차량이 있는 차량 경로 문제 (VRP)입니다. 대부분의 경우 VRP에는 제약이 있습니다. 예를 들어 차량에 운반할 수 있는 최대 중량 또는 물량의 용량이 있을 수 있으며, 고객이 요청한 지정된 기간 동안 운전자가 위치를 방문해야 할 수도 있습니다.
OR-도구로 다음을 비롯하여 다양한 유형의 VRP를 해결할 수 있습니다.
- 이동 영업 담당자 문제는 차량이 한 대뿐인 클래식한 라우팅 문제입니다.
- 차량 라우팅 문제: 여러 차량으로 구성된 TSP의 일반화입니다.
- 용량 제약이 있는 VRP: 차량에 운반할 수 있는 최대 용량이 차량에 적용됩니다.
- 기간이 있는 VRP: 차량이 지정된 시간 간격으로 위치를 방문해야 합니다.
- 리소스 제약조건이 있는 VRP: 창고 (경로의 시작점)에서 차량을 적재하거나 하역하는 공간 또는 직원과 같은 요소
- 방문이 중단된 VRP: 차량이 모든 위치를 방문할 필요는 없지만 방문이 중단될 때마다 위약금을 지불해야 합니다.
차량 경로 문제 해결 시 제한사항
차량 경로 문제는 본질적으로 다루기가 어렵습니다. 문제를 해결하는 데 걸리는 시간은 문제의 규모에 따라 기하급수적으로 증가합니다. 충분히 큰 문제의 경우 최적의 솔루션을 찾는 데 OR-Tools (또는 다른 라우팅 소프트웨어)가 몇 년이 걸릴 수 있습니다. 따라서 OR-Tools는 유용하지만 최적의 솔루션을 반환하는 경우가 있습니다. 더 나은 해법을 찾으려면 솔버의 검색 옵션을 변경하세요. 관련 예는 검색 전략 변경을 참조하세요.