[파이썬] OSRM과 2-opt 알고리즘으로 TSP(경로 최적화) 연산 속도 극대화해봤습니다

안녕하세요! 외판원 순환문제라는 것을 발견하고 흥미가 생겨서 실제 도로망 기반의 경로 최적화(TSP) 알고리즘을 구현해보면서 연산 속도를 극대화한 소소한 프로젝트를 공유해봅니다.

1. 왜 만들었나요?

지점 수가 조금만 늘어나도 완전 탐색($O(N!)$) 방식은 연산 시간이 폭발적으로 증가해 실제 서비스에 적용하기 어렵습니다.

이를 해결하기 위해 OSRM Distance Matrix API와 Nearest Neighbor + 2-opt 국소 탐색 알고리즘을 결합해 수 밀리초(ms) 내에 최적 동선을 산출하도록 만들었습니다.

2. 핵심 특징

- 실제 도로망 연동: 단순 직선거리가 아닌 OSRM 실제 도로 네트워크 Distance Matrix 활용

- 속도 극대화: 탐욕 알고리즘으로 1차 동선을 생성하고 2-opt로 꼬인 경로를 교차 제거해 빠른 연산 보장

3. 성능 비교 (Benchmark)

- 10개 지점: 원래 컴퓨터 탐색 (~3.6초) vs 본 엔진 (< 10ms)

- 15개 지점: 원래 컴퓨터 탐색 (~35시간+, Timeout) vs 본 엔진 (< 20ms)

- 20개 이상: 원래 컴퓨터 탐색 (연산 불가) vs 본 엔진 (< 50ms)

---

🔗 GitHub 저장소: https://github.com/swiri0921-bit/TSP-Route-Optimizer

아직 중3이라 부족한점이 있을수 있습니다….피드백이나 개선 아이디어 있으시면 편하게 댓글 남겨주세요! 감사합니다.