테마파크에서 실시간 대기시간과 방문객 제약조건을 고려하여 최적의 어트랙션 순회 경로를 찾는 시스템
- 2023112414 김태이
- 2019113634 조준혁
- 2023112540 최희수
-
입력
- 테마파크 지도 (노드: 어트랙션/편의시설, 간선: 이동 경로)
- 실시간 대기시간 정보 (queue-times.com API)
- 방문객 정보 (나이, 키)
- 방문 희망 어트랙션 리스트
-
출력
- 방문객 제약조건을 만족하는 최적 순회 경로
- 이동시간 + 대기시간 가중치 기반 비용 최소화
-
목표
- 다양한 경로 탐색 알고리즘 구현 및 성능 비교
- 비용, 실행시간, 메모리 사용량 분석
- 타입: entrance, attraction, restaurant, show
- 속성: id, name, wait_time, 제약조건 (키/나이 제한)
- 필터링: 방문객 조건 불만족 시 제외
- 무방향 그래프: 양방향 이동 가능
- 속성: move_time (이동 시간, 분)
- 고정 구조: 노드/간선은 시간에 따라 변하지 않음
cost(u → v) = α * move_time(u, v) + β * wait_time(v)
total_cost(P) = Σ cost(vi → v{i+1})
α = 2, β = 1: 현재 가중치 계수 (이동시간이 대기시간보다 체감 부담이 크므로 2배 가중)- 모든 알고리즘은 입구로 돌아오는 순환 경로로 평가 (마지막 노드 → 입구 비용 포함)
- 실시간 대기시간은 API로 갱신
모든 알고리즘은 노드 간 이동 비용을 빠르게 계산하기 위해 사전 계산된 최단 경로를 사용한다.
- 방법: Dijkstra 알고리즘을 모든 노드에 대해 실행
- 결과:
travel_cost[i][j]- 노드 i에서 j까지의 최소 이동 시간 - 사용: 상위 알고리즘에서
leg_cost(i, j) = α * travel_cost[i][j] + β * wait_time[j]로 계산 - 시간 복잡도: O(V * (V+E) log V)
가장 단순한 탐욕 알고리즘으로, 매 단계마다 현재 위치에서 가장 비용이 낮은 미방문 노드를 선택한다.
동작 과정:
- 시작 노드 (입구)에서 출발
- 아직 방문하지 않은 노드들 중
leg_cost(current, candidate)가 최소인 노드 선택 - 해당 노드로 이동하고 방문 처리
- 모든 노드를 방문할 때까지 2-3 반복
특징:
- 빠른 실행 속도
- 지역 최적해에 빠질 가능성 높음
- 시간 복잡도: O(K²) (K = 방문할 노드 수)
Greedy에 미래 예측 기능을 추가하여, 현재 선택의 즉각적인 비용뿐만 아니라 그 다음 단계의 예상 비용까지 고려하는 알고리즘이다.
동작 과정:
- 시작 노드 (입구)에서 출발
- 각 후보 노드에 대해 lookahead 점수 계산:
- 즉각 비용:
leg_cost(current, candidate) - 예상 비용: candidate에서 남은 노드들까지의 평균 비용
- 총 점수 = 즉각 비용 + 예상 비용 × lookahead_weight
- 즉각 비용:
- 총 점수가 최소인 노드 선택
- 모든 노드를 방문할 때까지 2-3 반복
특징:
- 단순 Greedy보다 전체 경로를 고려한 선택
- lookahead_depth로 예측 깊이 조절 가능
- 먼 미래일수록 가중치 감소 (0.5^depth)
- 시간 복잡도: O(K³) (K = 방문할 노드 수)
Greedy로 생성한 초기 경로를 2-opt 지역 탐색으로 개선하는 알고리즘이다.
동작 과정:
- Greedy Nearest-Next로 초기 경로 생성
- 경로 상의 두 구간
(i, i+1),(j, j+1)선택 - 두 구간 사이의 순서를 뒤집었을 때 (2-opt swap) 비용 감소 확인
- 비용이 줄어들면 교환 적용
- 더 이상 개선되지 않을 때까지 2-4 반복
특징:
- Greedy보다 높은 품질의 경로 생성
- 지역 최적해 탈출 가능
- 대기시간 비대칭성 고려한 정확한 비용 재계산
- 시간 복잡도: O(K² + I*K³) (I = 개선 반복 횟수)
경로에 노드를 하나씩 삽입할 때, 비용 증가가 최소인 위치를 찾아 삽입하는 알고리즘이다.
동작 과정:
- 시작 노드로 초기 경로 구성
- 아직 포함되지 않은 노드 중 하나 선택
- 현재 경로의 모든 가능한 위치에 해당 노드를 삽입했을 때의 비용 증가량 계산
- 비용 증가가 최소인 위치에 노드 삽입
- 모든 노드가 포함될 때까지 2-4 반복
특징:
- 전역적 관점에서 경로 구성
- Greedy보다 균형 잡힌 경로
- 삽입 위치 탐색에 시간 소요
- 시간 복잡도: O(K³)
성능 비교를 위한 기준선으로, 무작위로 노드 순서를 결정한다.
동작 과정:
- 방문할 노드 리스트를 무작위로 섞음 (shuffle)
- 섞인 순서대로 경로 생성
특징:
- 가장 빠른 실행 속도
- 다른 알고리즘의 성능을 평가하는 하한선 역할
- 시간 복잡도: O(K)
Mixed Integer Linear Programming을 사용하여 TSP를 정확하게 푸는 알고리즘이다. 이론적으로 최적해를 보장하지만, 노드 수가 많을 경우 시간이 오래 걸릴 수 있다.
동작 과정:
- 변수 정의:
x[i][j]: 간선 (i, j)를 사용하면 1, 아니면 0 (이진 변수)u[i]: 노드 i의 방문 순서 (정수 변수, subtour elimination용)
- 목적 함수:
minimize Σ cost[i][j] × x[i][j] - 제약조건:
- 각 노드에서 정확히 하나의 간선이 나감
- 각 노드로 정확히 하나의 간선이 들어옴
- Subtour elimination (MTZ formulation):
u[i] - u[j] + n × x[i][j] ≤ n - 1
- MILP 솔버로 최적해 탐색
특징:
- 이론적 최적해 보장 (시간 제한 내)
- 노드 수가 적을 때 효과적
- 시간 제한 초과 시 feasible solution 반환
- 시간 복잡도: 지수적 (NP-hard)
- 필요 라이브러리: pulp
- total_cost: 이동시간 + 대기시간 가중치 합
- total_move_time: 총 이동시간
- total_wait_time: 총 대기시간
- 실행시간: 알고리즘 수행 시간
- 메모리 사용량: tracemalloc 측정
- total_cost
- 동일 시 total_move_time
- 동일 시 execution_time
- 동일 시 memory_used
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 # 알고리즘별 경로
{
"id": 157,
"name": "T 익스프레스",
"type": "attraction",
"min_height": 140,
"min_age": 12
}{
"u": 157,
"v": 158,
"move_time": 2.5
}- 엔드포인트:
https://queue-times.com/parks/125/queue_times.json - 처리: 운영 중단 시 999분, API 실패 시 기본값 사용
- 전체 그래프: 노드 타입별 컬러 아이콘, 간선 연결
- 제약조건 그래프: 사용 가능/불가능 노드 구분, 이름 표시
- 1등 알고리즘 경로 지도: 최적 경로 시각화
- 2등 알고리즘 경로 지도: 차선 경로 시각화 (비교용)
- 다크모드: 검은 배경, 흰색 텍스트/경로
- 아이콘 기반: PNG 아이콘 색상 변환 (입구, 어트랙션, 식당, 공연)
- 자동 레이아웃: 좌표 범위 정규화, aspect ratio 유지
- FHD 최적화: 최대 1920x1080, 300 DPI 출력
# 방법 1: 직접 설치
pip install requests matplotlib numpy Pillow pulp
# 방법 2: requirements.txt 사용
pip install -r requirements.txtcd src
python main.py- 이름 (Name)
- 나이 (Age): 0-150세
- 키 (Height): 50-250cm
- 실시간 대기시간 API 호출
- 사용자 제약조건 필터링
- 6가지 알고리즘 실행 및 비교
- 성능 메트릭 테이블 (다단계 정렬 기준 적용)
- 최적 경로 상세 정보 (이동/대기/식사/공연 시간 분류)
- 4가지 그래프 시각화 이미지 (전체, 제약조건, 1등 경로, 2등 경로)
- 입력 검증 및 재입력 처리
- 필터링 단계별 상세 피드백
- 한글 전각문자 고려 텍스트 정렬
- 시간 분류별 출력 (대기/식사/공연)
- Dijkstra 기반 최단 경로 사전 계산
- 메모리 추적 (tracemalloc)
- 실행 시간 정밀 측정 (time.perf_counter)
- 모든 알고리즘이 입구로 복귀하는 순환 경로로 평가
- total_cost → move_time → exec_time → memory 순으로 비교
- API 실패 시 기본 대기시간 사용 (타임아웃 3초)
- 그래프 연결성 보강 (add_missing_connections): 간선 부족 구간 자동 보완
- 언어: 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