TSP 라우팅 (외판원 최적 경로)
지점 좌표를 입력하거나 지도 클릭으로 추가하면 Nearest Neighbor + 2-opt 휴리스틱으로 최단 경로·총 거리·개선율을 자동 산출합니다.
자주 묻는 질문 (FAQ)
TSP가 뭔가요?
Travelling Salesman Problem 외판원 문제. 출발지에서 모든 지점을 한 번씩 방문하고 돌아오는 최단 경로. NP-hard 고전 문제. 배송·영업 라우팅·관광 코스 등 광범위 응용.
왜 휴리스틱?
25지점 = 25!/2 ≈ 7.7×10²³ 경로. 정확한 최적해는 ≤15지점에서만 실용적. 본 도구는 Nearest Neighbor (가장 가까운 다음) → 2-opt (반복 개선) 휴리스틱. 실제 최적과 5-10% 이내.
2-opt가 뭔가요?
경로의 두 간선을 골라 reverse 했을 때 짧아지면 교환. 모든 쌍을 반복해 개선 안 될 때까지. Lin·Kernighan 알고리즘의 기반. 본 도구는 50회 반복 한도.
실무 활용?
택배·영업 일일 라우팅, 정비 순회, 다지점 출장. 실제 도로망은 직선 거리와 다르나 좌표 기반 1차 분석 충분. 정밀 라우팅은 OR-Tools, OptimoRoute, Routific 등 SaaS 활용.