TSP 라우팅 (외판원 최적 경로)

Travelling Salesman Problem 외판원 문제. 출발지에서 모든 지점을 한 번씩 방문하고 돌아오는 최단 경로. NP-hard 고전 문제. 배송·영업 라우팅·관광 코스 등 광범위 응용.

25지점 = 25!/2 ≈ 7.7×10²³ 경로. 정확한 최적해는 ≤15지점에서만 실용적. 본 도구는 Nearest Neighbor (가장 가까운 다음) → 2-opt (반복 개선) 휴리스틱. 실제 최적과 5-10% 이내.

경로의 두 간선을 골라 reverse 했을 때 짧아지면 교환. 모든 쌍을 반복해 개선 안 될 때까지. Lin·Kernighan 알고리즘의 기반. 본 도구는 50회 반복 한도.

택배·영업 일일 라우팅, 정비 순회, 다지점 출장. 실제 도로망은 직선 거리와 다르나 좌표 기반 1차 분석 충분. 정밀 라우팅은 OR-Tools, OptimoRoute, Routific 등 SaaS 활용.

Nearest Neighbor는 매 순간 가장 가까운 지점만 선택하는 탐욕 방식이라 초반에는 효율적이지만 마지막에 멀리 남은 지점 때문에 경로가 크게 우회하는 문제가 생깁니다. 평균적으로 최적해 대비 20~25% 긴 경로가 나오며, 2-opt 개선을 거치면 이 격차가 5% 내외로 줄어듭니다. 그래서 두 단계를 결합하는 것이 표준입니다.

차량 여러 대 배차는 VRP(Vehicle Routing Problem), 방문 시간대 제약이 붙으면 VRPTW로 확장되며 TSP보다 훨씬 복잡합니다. 용량·근무시간·시간창 제약을 다루려면 Google OR-Tools 같은 전용 솔버가 필요합니다. 본 도구는 차량 1대·제약 없는 순수 TSP 기준이므로 단일 라우트 1차 검토용으로 활용하세요.