Optimal Route Planner

1. 앱 화면 — 경로 그래프

출발지·경유지·도착지를 지도 위의 노드로 두고, 최적화된 방문 순서를 엣지(경로선)로 이어 그린다. 아래는 6개 지점을 잇는 최적 경로로, 출발(녹색 ▶)·경유(파란 번호 1–4)·도착(빨강 ■) 마커가 보라색 폴리라인으로 연결된다.

지도 아래 RouteSummary는 각 구간의 예상 소요시간과 이동거리, 그리고 전체 합계를 보여준다. 순서는 드래그 앤 드롭으로 직접 바꿀 수 있고, 바뀌면 즉시 다시 계산한다.

2. 문제 — 왜 어려운가

N개 장소의 최적 방문 순서를 찾는 건 전형적인 외판원 문제(TSP)다. 순열을 전부 시도하는 완전탐색은 O(n!)이고, 각 순열마다 실제 도로 이동시간을 길찾기 API에 물어봐야 하므로 비용이 폭발한다.

경유지 8개(10 지점) → 순열 8! = 40,320 가지
각 순열마다 Directions API 1회 호출 = 40,320 회 호출

현실에서는 장소가 5–15개 사이인 경우가 대부분이라, 정확도를 유지하면서 API 호출을 획기적으로 줄이는 것이 이 앱의 핵심 과제였다.

3. 시스템 설계

• 프론트: Next.js 정적 내보내기(static export) + React 18. 컴포넌트·커스텀 훅 분리 구조.
• 지도 SDK: Kakao Maps로 지도 렌더링·마커·폴리라인·장소 검색을 처리.
• 길찾기: Kakao Mobility Directions API로 실제 도로 기반 이동시간·거리 산출. 방향성 거리(A→B ≠ B→A) 반환.
• 백엔드: Firebase Functions에 API 프록시를 두어 클라이언트 키 노출 없이 CORS·키를 처리.
• 데이터 흐름: 장소 추가 → 비대칭 거리 행렬(n(n-1)쌍) → Branch and Bound → 최적 순서로 지도 갱신.

4. 알고리즘 — 비대칭 TSP Branch and Bound

핵심은 비대칭 거리 행렬 + Branch and Bound 하나다. 이전 버전은 경유지 수에 따라 완전탐색·TSP DP·2-opt·휴리스틱을 섞는다고 README·포트폴리오에서 주장했지만, 실제 코드는 그중 하나만 동작했다. v3.0에서 비대칭 TSP의 정확한 최적해를 보장하는 단일 알고리즘으로 단순화하고 dead code를 모두 제거했다 (issue #2, PR #3).

4.1 비대칭 거리 행렬 — 왜 절반만 부르면 안 되는가

카카오 모빌리티 Directions는 방향성 거리다. 일방통행·회전 제한 때문에 A→B와 B→A의 totalTime이 다르다. 거리 행렬을 i<j만 부르고 matrix[j][i] = matrix[i][j]로 대칭을 강제하면 실제 도로의 방향성을 무시해 잘못된 최적해를 선택할 수 있다. 이 앱은 모든 방향을 부른다.

// 비대칭 거리 행렬: i≠j 모든 방향 호출
API 호출 = n(n-1)  // 대칭 가정(절반만 부름) 대비 정확도 보존

4.2 Branch and Bound — 비대칭 TSP에서 valid한 하한

행렬 위에서 in-memory로 모든 순열을 평가하되, 가지치기로 탐색 공간을 줄인다. 가지치기의 핵심은 남은 비용의 하한(LB)이 실제 남은 비용 이하임이 보장되어야 한다는 점이다.

// 비대칭 TSP에서 valid한 LB
LB = firstStepMin + Σ outgoingSum[u]
firstStepMin        = min over v in unvisited of d[currentPos][v]   // 다음 1회 이동의 하한
outgoingSum[u]      = min(within-unvisited, d[u][endIndex])  // u의 leaving edge 하한
가지치기            : currentCost + LB ≥ bestCost → 컷

valid 증명: 각 unvisited 노드 u는 Hamiltonian path에서 정확히 한 번 빠져나가고, 도착점은 (다른 unvisited 노드 또는 endIndex)다. 따라서 실제 비용 ≥ min(within-unvisited, to-end). currentPos의 다음 이동 도착점도 unvisited 안의 노드이므로 firstStepMin의 후보에서 endIndex를 제외해야 한다 (이걸 빠뜨리면 LB가 실제 남은 비용을 초과해 최적해를 잘못 가지치기한다).

회귀 검증은 routeOptimizer.test.js에 있다. 사용자 제공 counterexample을 포함해 무작위·adversarial 비대칭 행렬에 대해 brute force와 cost 일치, 그리고 모든 expanded 노드에서 LB ≤ 실제 남은 비용 invariant를 instrumented check로 확인한다.

4.3 분기 — 두 경로

4.4 API 호출 수 — 비대칭화로 2배, B&B로 압축

비순열·비-TSP-DP·비-2-opt가 되어 n!을 직접 부르지 않으니, 호출 수는 n(n-1) + 1로 압축된다. 비대칭 강제 복사를 쓰던 이전 구현의 n(n-1)/2 + 1과 비교하면 2배 늘었지만, 그 2배가 대칭 가정으로 잘못된 최적해를 고르던 정확도 손실을 막는다.

// 11 지점(9 경유) — 비대칭 B&B
완전탐색 (가정)         : 9! = 362,880 회 HTTP 호출
비대칭 B&B (실제)       : 11·10 + 1 = 111 회 HTTP 호출

5. 결과

방향성 거리까지 반영한 정확한 최적해. 거리 행렬을 비대칭으로 채우고 그 위에서 Branch and Bound를 돌려, 어떤 경유지 수든 100% 최적해를 보장한다. 절감의 의미는 "솔루션 품질"이 아니라 "API 호출 수" — 11 지점 기준 naive 362,880 호출을 111 호출로 줄여 응답 지연과 비용을 크게 낮춘다. 13 지점 이상은 UI 추가 차단 + 엔진 가드(TOO_MANY_LOCATIONS)로 거부한다.

6. 한계와 정직

이 작품은 두 차례 정직성 수정의 대상이었다.

1. README·포트폴리오의 4단계 알고리즘 주장 vs 코드 3단계 + dead code — issue #2. 비대칭 거리 가정 오류와 LB 결함까지 함께 발견되어 PR #3에서 비대칭 B&B 단일 알고리즘으로 단순화하고 회귀 테스트를 추가했다.
2. 현재 페이지의 "1–8 경유는 완전탐색" 같은 구버전 묘사 — 이번 수정으로 비대칭 B&B 단일 알고리즘에 맞춰 다시 썼다.

코드와 문서가 다른 작품에 비해 자주 어긋났던 만큼, 이 페이지는 README.md와 코드 양쪽을 다시 읽고 정합하게 다시 썼다.

7. 레포지토리

Next.js 앱 + Firebase Functions 프록시로 구성된 단일 레포.