Theme Park Route Planner

테마파크에서 실시간 대기시간과 방문객 제약조건을 고려하여 최적의 어트랙션 순회 경로를 찾는 시스템

---

0. 팀 구성원

• 2023112414 김태이
• 2019113634 조준혁
• 2023112540 최희수

---

1. 문제 개요

• 입력

  • 테마파크 지도 (노드: 어트랙션/편의시설, 간선: 이동 경로)
  • 실시간 대기시간 정보 (queue-times.com API)
  • 방문객 정보 (나이, 키)
  • 방문 희망 어트랙션 리스트

• 출력

  • 방문객 제약조건을 만족하는 최적 순회 경로
  • 이동시간 + 대기시간 가중치 기반 비용 최소화

• 목표

  • 다양한 경로 탐색 알고리즘 구현 및 성능 비교
  • 비용, 실행시간, 메모리 사용량 분석

---

2. 그래프 모델

노드

• 타입: entrance, attraction, restaurant, show
• 속성: id, name, wait_time, 제약조건 (키/나이 제한)
• 필터링: 방문객 조건 불만족 시 제외

간선

• 무방향 그래프: 양방향 이동 가능
• 속성: move_time (이동 시간, 분)
• 고정 구조: 노드/간선은 시간에 따라 변하지 않음

---

3. 가중치 수식

cost(u → v) = α * move_time(u, v) + β * wait_time(v)
total_cost(P) = Σ cost(vi → v{i+1})

• α = 2, β = 1: 현재 가중치 계수 (이동시간이 대기시간보다 체감 부담이 크므로 2배 가중)
• 모든 알고리즘은 입구로 돌아오는 순환 경로로 평가 (마지막 노드 → 입구 비용 포함)
• 실시간 대기시간은 API로 갱신

---

4. 알고리즘

공통: 최단 경로 사전 계산

모든 알고리즘은 노드 간 이동 비용을 빠르게 계산하기 위해 사전 계산된 최단 경로를 사용한다.

• 방법: Dijkstra 알고리즘을 모든 노드에 대해 실행
• 결과: travel_cost[i][j] - 노드 i에서 j까지의 최소 이동 시간
• 사용: 상위 알고리즘에서 leg_cost(i, j) = α * travel_cost[i][j] + β * wait_time[j]로 계산
• 시간 복잡도: O(V * (V+E) log V)

4.1 Greedy Nearest-Next

가장 단순한 탐욕 알고리즘으로, 매 단계마다 현재 위치에서 가장 비용이 낮은 미방문 노드를 선택한다.

동작 과정:

1. 시작 노드 (입구)에서 출발
2. 아직 방문하지 않은 노드들 중 leg_cost(current, candidate)가 최소인 노드 선택
3. 해당 노드로 이동하고 방문 처리
4. 모든 노드를 방문할 때까지 2-3 반복

특징:

• 빠른 실행 속도
• 지역 최적해에 빠질 가능성 높음
• 시간 복잡도: O(K²) (K = 방문할 노드 수)

4.2 Greedy + Lookahead

Greedy에 미래 예측 기능을 추가하여, 현재 선택의 즉각적인 비용뿐만 아니라 그 다음 단계의 예상 비용까지 고려하는 알고리즘이다.

동작 과정:

1. 시작 노드 (입구)에서 출발
2. 각 후보 노드에 대해 lookahead 점수 계산:
   • 즉각 비용: leg_cost(current, candidate)
   • 예상 비용: candidate에서 남은 노드들까지의 평균 비용
   • 총 점수 = 즉각 비용 + 예상 비용 × lookahead_weight
3. 총 점수가 최소인 노드 선택
4. 모든 노드를 방문할 때까지 2-3 반복

특징:

• 단순 Greedy보다 전체 경로를 고려한 선택
• lookahead_depth로 예측 깊이 조절 가능
• 먼 미래일수록 가중치 감소 (0.5^depth)
• 시간 복잡도: O(K³) (K = 방문할 노드 수)

4.3 Greedy + 2-Opt Local Search

Greedy로 생성한 초기 경로를 2-opt 지역 탐색으로 개선하는 알고리즘이다.

동작 과정:

1. Greedy Nearest-Next로 초기 경로 생성
2. 경로 상의 두 구간 (i, i+1), (j, j+1) 선택
3. 두 구간 사이의 순서를 뒤집었을 때 (2-opt swap) 비용 감소 확인
4. 비용이 줄어들면 교환 적용
5. 더 이상 개선되지 않을 때까지 2-4 반복

특징:

• Greedy보다 높은 품질의 경로 생성
• 지역 최적해 탈출 가능
• 대기시간 비대칭성 고려한 정확한 비용 재계산
• 시간 복잡도: O(K² + I*K³) (I = 개선 반복 횟수)

4.4 Cheapest Insertion Heuristic

경로에 노드를 하나씩 삽입할 때, 비용 증가가 최소인 위치를 찾아 삽입하는 알고리즘이다.

동작 과정:

1. 시작 노드로 초기 경로 구성
2. 아직 포함되지 않은 노드 중 하나 선택
3. 현재 경로의 모든 가능한 위치에 해당 노드를 삽입했을 때의 비용 증가량 계산
4. 비용 증가가 최소인 위치에 노드 삽입
5. 모든 노드가 포함될 때까지 2-4 반복

특징:

• 전역적 관점에서 경로 구성
• Greedy보다 균형 잡힌 경로
• 삽입 위치 탐색에 시간 소요
• 시간 복잡도: O(K³)

4.5 Random Baseline

성능 비교를 위한 기준선으로, 무작위로 노드 순서를 결정한다.

동작 과정:

1. 방문할 노드 리스트를 무작위로 섞음 (shuffle)
2. 섞인 순서대로 경로 생성

특징:

• 가장 빠른 실행 속도
• 다른 알고리즘의 성능을 평가하는 하한선 역할
• 시간 복잡도: O(K)

4.6 MILP 최적화

Mixed Integer Linear Programming을 사용하여 TSP를 정확하게 푸는 알고리즘이다. 이론적으로 최적해를 보장하지만, 노드 수가 많을 경우 시간이 오래 걸릴 수 있다.

동작 과정:

1. 변수 정의:
   • x[i][j]: 간선 (i, j)를 사용하면 1, 아니면 0 (이진 변수)
   • u[i]: 노드 i의 방문 순서 (정수 변수, subtour elimination용)
2. 목적 함수: minimize Σ cost[i][j] × x[i][j]
3. 제약조건:
   • 각 노드에서 정확히 하나의 간선이 나감
   • 각 노드로 정확히 하나의 간선이 들어옴
   • Subtour elimination (MTZ formulation): u[i] - u[j] + n × x[i][j] ≤ n - 1
4. MILP 솔버로 최적해 탐색

특징:

• 이론적 최적해 보장 (시간 제한 내)
• 노드 수가 적을 때 효과적
• 시간 제한 초과 시 feasible solution 반환
• 시간 복잡도: 지수적 (NP-hard)
• 필요 라이브러리: pulp

---

5. 평가 지표

측정 항목

• total_cost: 이동시간 + 대기시간 가중치 합
• total_move_time: 총 이동시간
• total_wait_time: 총 대기시간
• 실행시간: 알고리즘 수행 시간
• 메모리 사용량: tracemalloc 측정

알고리즘 순위 결정 기준

1. total_cost
2. 동일 시 total_move_time
3. 동일 시 execution_time
4. 동일 시 memory_used

---

6. 코드 구조

src/
  graph.py                 # 그래프 자료구조 및 노드 정의
  weights.py               # 가중치 계산 함수
  user.py                  # 사용자 프로필 및 제약조건
  park_loader.py           # 테마파크 데이터 로더 및 실시간 API
  evaluation.py            # 성능 평가 및 메트릭
  visualize.py             # 그래프 시각화
  main.py                  # 메인 실행 파일
  routing/
    shortest_path.py       # Dijkstra 최단 경로
    greedy_nearest.py      # Greedy Nearest-Next
    greedy_lookahead.py    # Greedy + Lookahead
    greedy_2opt.py         # Greedy + 2-Opt
    cheapest_insertion.py  # Cheapest Insertion
    random_baseline.py     # Random Baseline
    milp_optimizer.py      # MILP 최적화

data/everland/
  nodes.json               # 노드 데이터
  edges.json               # 간선 데이터
  coords.json              # 노드 좌표

asset/icons/
  입구.png, 어트랙션.png, 식당.png, 공연.png

output/everland/
  graph.png                # 전체 그래프
  filtered_graph.png       # 제약조건 적용 그래프
  path_*.png               # 알고리즘별 경로

---

7. 데이터 구조

nodes.json

{
  "id": 157,
  "name": "T 익스프레스",
  "type": "attraction",
  "min_height": 140,
  "min_age": 12
}

edges.json

{
  "u": 157,
  "v": 158,
  "move_time": 2.5
}

실시간 API

• 엔드포인트: https://queue-times.com/parks/125/queue_times.json
• 처리: 운영 중단 시 999분, API 실패 시 기본값 사용

---

8. 시각화

시각화 출력

1. 전체 그래프: 노드 타입별 컬러 아이콘, 간선 연결
2. 제약조건 그래프: 사용 가능/불가능 노드 구분, 이름 표시
3. 1등 알고리즘 경로 지도: 최적 경로 시각화
4. 2등 알고리즘 경로 지도: 차선 경로 시각화 (비교용)

시각화 특징

• 다크모드: 검은 배경, 흰색 텍스트/경로
• 아이콘 기반: PNG 아이콘 색상 변환 (입구, 어트랙션, 식당, 공연)
• 자동 레이아웃: 좌표 범위 정규화, aspect ratio 유지
• FHD 최적화: 최대 1920x1080, 300 DPI 출력

---

9. 설치 및 실행

의존성 설치

# 방법 1: 직접 설치
pip install requests matplotlib numpy Pillow pulp

# 방법 2: requirements.txt 사용
pip install -r requirements.txt

실행

cd src
python main.py

입력

• 이름 (Name)
• 나이 (Age): 0-150세
• 키 (Height): 50-250cm

출력

1. 실시간 대기시간 API 호출
2. 사용자 제약조건 필터링
3. 6가지 알고리즘 실행 및 비교
4. 성능 메트릭 테이블 (다단계 정렬 기준 적용)
5. 최적 경로 상세 정보 (이동/대기/식사/공연 시간 분류)
6. 4가지 그래프 시각화 이미지 (전체, 제약조건, 1등 경로, 2등 경로)

---

10. 구현 특징

사용자 경험

• 입력 검증 및 재입력 처리
• 필터링 단계별 상세 피드백
• 한글 전각문자 고려 텍스트 정렬
• 시간 분류별 출력 (대기/식사/공연)

성능 및 평가

• Dijkstra 기반 최단 경로 사전 계산
• 메모리 추적 (tracemalloc)
• 실행 시간 정밀 측정 (time.perf_counter)
• 모든 알고리즘이 입구로 복귀하는 순환 경로로 평가
• total_cost → move_time → exec_time → memory 순으로 비교

에러 처리

• API 실패 시 기본 대기시간 사용 (타임아웃 3초)
• 그래프 연결성 보강 (add_missing_connections): 간선 부족 구간 자동 보완

---

11. 실행 환경

• 언어: Python 3.7+
• 라이브러리: requests, matplotlib, numpy, Pillow
• OS: Windows
• CPU: Intel Core i5 13600KF
• Memory: G.Skill DDR4-3200 CL14 32GB
• SSD: 삼성전자 PM9A1 M.2 NVMe 512GB