TSP 경로 최적화
모든 위치를 방문하고 출발지로 돌아오는 최단 경로 탐색. 휴리스틱 알고리즘(최근접 이웃, Clarke-Wright 절약법)을 사용하여 외판원 문제를 풉니다. 위치 좌표를 입력하여 최적화된 경로를 찾으세요.
휴리스틱 알고리즘(최근접 이웃, Clarke-Wright 절약법)을 사용하여 외판원 문제를 풉니다. 위치 좌표를 입력하여 최적화된 경로를 찾으세요.
외판원 문제(TSP)란 무엇인가?
외판원 문제(TSP)는 다음과 같이 묻습니다: 일련의 위치와 그 사이의 거리가 주어졌을 때, 각 위치를 정확히 한 번 방문하고 출발점으로 돌아오는 가능한 가장 짧은 경로는 무엇인가? 이것은 조합 최적화에서 가장 많이 연구된 문제 중 하나입니다.
TSP는 NP-난해이므로, 대규모 인스턴스를 다항 시간에 최적으로 풀 수 있는 알려진 알고리즘이 없습니다. n개 위치에 대해 (n-1)!/2개의 가능한 경로가 있습니다 — 10개 정류장은 181,440개, 20개 정류장은 10^16개의 경로를 생성합니다. 실용적인 해법은 휴리스틱에 의존합니다: 최근접 이웃(빠르지만 최적보다 ~25% 높음), Clarke-Wright 절약법(더 나은 품질), 2-opt, 시뮬레이티드 어닐링, 유전 알고리즘 등의 메타 휴리스틱.
TSP는 라스트마일 배송 라우팅, 현장 서비스 스케줄링, PCB 드릴링, 창고 피킹 경로 최적화에 직접 적용됩니다. 10-15%의 경로 개선도 차량 운영에 상당한 연료 및 시간 절감으로 이어집니다.
Formula: 목표: Σ d(route[i], route[i+1])을 최소화 (i = 0..n) 최근접 이웃: 가장 가까운 미방문 위치를 탐욕적으로 방문 절약법: s(i,j) = d(depot,i) + d(depot,j) − d(i,j) 가장 큰 절약부터 경로 병합
계산 예시
출발지 (0,0), 4개 정류장 (3,4), (6,1), (8,5), (2,7). 최근접 이웃: (3,4) d=5.0 방문, (2,7) d=3.2, (8,5) d=6.3, (6,1) d=4.5, 복귀 d=6.1. 총 = 25.1. Clarke-Wright는 가장 유리한 쌍을 먼저 병합하여 23.4의 더 짧은 경로를 찾을 수 있습니다.
이 계산기를 사용해야 할 때
- 배송 디스패처가 10-30개 고객 위치를 방문하는 단일 운전자의 일일 경로를 계획할 때
- 현장 서비스 관리자가 서비스 콜 간 이동 시간을 최소화하는 기술자 경로를 최적화할 때
- 창고 엔지니어가 여러 통로 위치를 통한 최적 피킹 경로를 설계할 때
- 영업 담당자가 최소 운전 거리로 고객을 방문하는 다중 도시 출장을 계획할 때
피해야 할 일반적인 실수
- 최근접 이웃 솔루션이 최적이라고 가정 — 탐욕적 휴리스틱이며 최적 경로보다 20-25% 더 길 수 있습니다; 항상 여러 알고리즘을 시도하고 비교하세요
- 도로 기반 라우팅에 직선(유클리드) 거리 사용 — 실제 운전 거리는 도로망으로 인해 20-40% 더 길 수 있습니다; 도로 라우팅에는 가능하면 실제 거리를 사용하세요
- 출발지로의 복귀 여행 포함 잊음 — TSP는 출발점으로 돌아올 것을 요구합니다; 복귀를 생략하면 총 경로 거리가 과소 추정됩니다
- 실제로 VRP인 문제에 TSP 적용 — 용량 제약, 시간 창, 또는 다중 차량이 있으면 더 나은 결과를 위해 VRP 도구를 사용하세요
결과 해석 방법
- Nearest Neighbor와 Clarke-Wright 결과를 비교: 차이가 크면 더 고급 방법으로 추가 최적화 여지가 있습니다
- 밀리초 단위의 계산 시간은 문제 규모에 대해 실시간 재라우팅이 가능한지 평가하는 데 도움됩니다
- 경로 맵 시각화는 교차 경로나 불필요한 역주행 같은 명백한 비효율을 식별하는 데 도움됩니다
관련 표준 및 참고자료
- Nearest Neighbor 및 Clarke-Wright savings (1964) — 본 도구에서 벤치마크하는 구성 휴리스틱
- Lin-Kernighan 국소 탐색 — 고품질 TSP 경로를 위한 사실상의 표준 휴리스틱
- TSPLIB — TSP 솔버 품질 비교에 사용되는 표준 공개 벤치마크 라이브러리
자주 묻는 질문
내 라우팅 문제에 어떤 알고리즘을 사용해야 하나요?
15개 미만의 정류장에는 최근접 이웃이 최적의 20-25% 이내에서 빠른 결과를 제공합니다. 15-50개 정류장에는 Clarke-Wright 절약법 후 2-opt 개선이 최적의 5-10% 이내를 달성합니다. 50개 이상 정류장에는 메타 휴리스틱(유전 알고리즘, 시뮬레이티드 어닐링) 또는 Google OR-Tools와 같은 상용 솔버를 사용하세요.
TSP는 실제 배송 라우팅과 어떻게 다른가요?
실제 라우팅에는 시간 창, 차량 용량, 운전자 근무 시간, 교통, 일방통행, 다중 차량(VRP)이 추가됩니다. TSP는 기초이지만, 실용적인 라우팅 소프트웨어는 이러한 제약을 추가합니다. 그래도 TSP 솔루션은 벤치마킹을 위한 거리 하한을 제공합니다.