# Trip Planner Feature - Technical Design Document **Version**: 1.0 **Date**: 2025-12-15 **Status**: Draft --- ## 📋 Overview Tính năng Trip Planner cho phép user lên kế hoạch chuyến đi bằng cách: 1. Chat với AI để tìm địa điểm 2. Thêm địa điểm vào Plan Box 3. Tối ưu lộ trình bằng thuật toán TSP 4. Chỉnh sửa/thay thế địa điểm --- ## 🎯 User Flow ```mermaid flowchart TD A[User Chat] --> B{AI Response} B --> C[Place Cards với 'Add to Plan'] C --> |Click Add| D[Plan Box] D --> E{User Actions} E --> |Optimize| F[TSP Algorithm] E --> |Drag & Drop| G[Reorder Places] E --> |Replace| H[AI hỏi criteria mới] H --> I[Suggest Alternatives] I --> D F --> D ``` --- ## 🏗️ Architecture ### Backend Components ``` app/ ├── planner/ │ ├── __init__.py │ ├── models.py # Plan, PlanItem schemas │ ├── router.py # API endpoints │ ├── service.py # Business logic │ └── tsp.py # TSP optimization algorithm └── mcp/tools/ └── graph_tool.py # Neo4j + OSM (có sẵn) ``` ### API Endpoints | Method | Endpoint | Description | |--------|----------|-------------| | POST | `/planner/create` | Tạo plan mới | | GET | `/planner/{plan_id}` | Lấy plan | | POST | `/planner/{plan_id}/add` | Thêm place vào plan | | DELETE | `/planner/{plan_id}/remove/{item_id}` | Xóa place | | PUT | `/planner/{plan_id}/reorder` | Sắp xếp lại thứ tự | | POST | `/planner/{plan_id}/optimize` | Chạy TSP | | POST | `/planner/{plan_id}/replace/{item_id}` | Thay thế place | --- ## 📦 Data Models ### Plan ```python @dataclass class Plan: plan_id: str user_id: str name: str items: list[PlanItem] created_at: datetime updated_at: datetime total_distance_km: float | None estimated_duration_min: int | None ``` ### PlanItem ```python @dataclass class PlanItem: item_id: str place_id: str name: str category: str lat: float lng: float order: int # Thứ tự trong plan added_at: datetime notes: str | None ``` --- ## 🧮 TSP Algorithm ### Approach: Nearest Neighbor + 2-opt Optimization ```python # app/planner/tsp.py from math import radians, sin, cos, sqrt, atan2 def haversine(lat1, lng1, lat2, lng2) -> float: """Calculate distance between 2 points in km.""" R = 6371 # Earth's radius in km dlat = radians(lat2 - lat1) dlng = radians(lng2 - lng1) a = sin(dlat/2)**2 + cos(radians(lat1)) * cos(radians(lat2)) * sin(dlng/2)**2 return 2 * R * atan2(sqrt(a), sqrt(1-a)) def calculate_distance_matrix(places: list[dict]) -> list[list[float]]: """Build NxN distance matrix.""" n = len(places) matrix = [[0.0] * n for _ in range(n)] for i in range(n): for j in range(n): if i != j: matrix[i][j] = haversine( places[i]['lat'], places[i]['lng'], places[j]['lat'], places[j]['lng'] ) return matrix def nearest_neighbor(matrix: list[list[float]], start: int = 0) -> list[int]: """Greedy nearest neighbor heuristic.""" n = len(matrix) visited = [False] * n tour = [start] visited[start] = True for _ in range(n - 1): current = tour[-1] nearest = -1 min_dist = float('inf') for j in range(n): if not visited[j] and matrix[current][j] < min_dist: min_dist = matrix[current][j] nearest = j tour.append(nearest) visited[nearest] = True return tour def two_opt(tour: list[int], matrix: list[list[float]]) -> list[int]: """2-opt local search improvement.""" improved = True while improved: improved = False for i in range(1, len(tour) - 1): for j in range(i + 1, len(tour)): # Calculate improvement d1 = matrix[tour[i-1]][tour[i]] + matrix[tour[j-1]][tour[j]] d2 = matrix[tour[i-1]][tour[j-1]] + matrix[tour[i]][tour[j]] if d2 < d1: # Reverse segment tour[i:j] = tour[i:j][::-1] improved = True return tour def optimize_route(places: list[dict], start_index: int = 0) -> tuple[list[int], float]: """ Main TSP optimization function. Args: places: List of places with 'lat', 'lng' keys start_index: Index of starting place Returns: (optimized_order, total_distance_km) """ if len(places) <= 2: return list(range(len(places))), 0.0 matrix = calculate_distance_matrix(places) tour = nearest_neighbor(matrix, start_index) tour = two_opt(tour, matrix) # Calculate total distance total = sum(matrix[tour[i]][tour[i+1]] for i in range(len(tour)-1)) return tour, total ``` ### Complexity - **Nearest Neighbor**: O(n²) - **2-opt**: O(n²) per iteration, ~O(n³) worst case - **Suitable for**: Up to ~50 places (typical trip size) --- ## 🔄 Replace Flow ### Workflow ```mermaid sequenceDiagram participant U as User participant F as Frontend participant B as Backend participant AI as LLM Agent U->>F: Click Replace on Place X F->>B: POST /chat {"message": "replace_context", "place_id": X} B->>AI: "User muốn thay thế [Place X]. Hỏi họ muốn tìm địa điểm như nào?" AI->>B: "Bạn muốn tìm địa điểm thay thế như thế nào? (VD: gần hơn, rẻ hơn, khác loại...)" B->>F: Response F->>U: Display AI question U->>F: "Tìm quán cafe yên tĩnh hơn" F->>B: POST /chat with context B->>AI: Search for alternatives AI->>B: Return alternatives as Place Cards B->>F: Place Cards U->>F: Select replacement F->>B: PUT /planner/{plan_id}/replace/{item_id} B->>F: Updated Plan ``` ### API Request ```json // POST /planner/{plan_id}/replace/{item_id} { "new_place_id": "cafe_xyz_123", "new_place": { "name": "Cafe XYZ", "lat": 16.0544, "lng": 108.2480, "category": "Coffee shop" } } ``` --- ## 🎨 Frontend Integration ### Chat Response Format ```json { "response": "Đây là một số quán cafe gần Cầu Rồng:", "places": [ { "place_id": "sound_cafe", "name": "Sound Cafe", "category": "Coffee shop", "lat": 16.0611, "lng": 108.2272, "rating": 4.7, "description": "Quán cafe âm nhạc acoustic...", "distance_km": 1.75, "actions": ["add_to_plan", "view_details"] } ], "plan_context": { "plan_id": "plan_abc123", "item_count": 3 } } ``` ### Plan Box State ```typescript interface PlanState { planId: string; items: PlanItem[]; isOptimized: boolean; totalDistanceKm: number; estimatedDurationMin: number; } interface PlanItem { itemId: string; placeId: string; name: string; category: string; lat: number; lng: number; order: number; } ``` --- ## 📐 Implementation Plan ### Phase 1: Core API (Week 1) - [ ] Create `app/planner/` module - [ ] Implement `models.py` with Pydantic schemas - [ ] Implement `tsp.py` with optimization algorithm - [ ] Create `router.py` with basic CRUD endpoints - [ ] Add session-based plan storage ### Phase 2: Chat Integration (Week 2) - [ ] Modify chat response format to include `places` array - [ ] Add `add_to_plan` action handling in agent - [ ] Implement replace flow with context tracking - [ ] Store plan context per user session ### Phase 3: TSP & Optimization (Week 3) - [ ] Implement `/optimize` endpoint - [ ] Add distance matrix calculation using graph_tool - [ ] Integrate with Neo4j for real distances (optional: OSRM for road distances) - [ ] Return optimized order with total distance ### Phase 4: Frontend (Week 4) - [ ] Create Place Card component with actions - [ ] Implement Plan Box with drag-drop (react-beautiful-dnd) - [ ] Add Optimize button with loading state - [ ] Implement Replace flow UI --- ## 🔧 Technical Considerations ### Storage Options | Option | Pros | Cons | |--------|------|------| | In-memory (Redis) | Fast, simple | Lost on restart | | Supabase | Persistent, user-linked | Requires auth | | Session-based | No auth needed | Client-side storage | **Recommendation**: Start with session-based (in-memory per user_id), migrate to Supabase later. ### Distance Calculation | Method | Accuracy | Speed | |--------|----------|-------| | Haversine | ~95% | Very fast | | OSRM API | ~99% (road) | Slower | | Graph (Neo4j) | ~95% | Fast | **Recommendation**: Use Haversine for MVP, add OSRM for production. ### Rate Limits - OpenStreetMap Nominatim: 1 req/sec - OSRM: Self-hosted or 10 req/min (demo server) --- ## 📝 Example Usage ### 1. User Chat ``` User: "Tìm quán cafe và nhà hàng hải sản gần Mỹ Khê" ``` ### 2. AI Response with Place Cards ``` AI: "Đây là một số gợi ý cho bạn: ☕ **Cafe** - [Nia Coffee] - 4.3★ - 1.2km [Add to Plan] - [Sound Cafe] - 4.7★ - 1.8km [Add to Plan] 🦐 **Hải sản** - [My Hanh Seafood] - 4.8★ - 0.5km [Add to Plan] - [Bé Ni 2] - 4.8★ - 0.6km [Add to Plan] " ``` ### 3. Plan Box ``` 📍 Your Plan (4 places) ┌──────────────────────────────┐ │ 1. Nia Coffee [✏️] [🔄] │ │ 2. Sound Cafe [✏️] [🔄] │ │ 3. My Hanh Seafood [✏️] [🔄] │ │ 4. Bé Ni 2 [✏️] [🔄] │ └──────────────────────────────┘ Total: 8.2km | ~45min [🔀 Optimize Route] [📤 Export] ``` ### 4. After Optimization ``` 📍 Your Plan (Optimized ✓) ┌──────────────────────────────┐ │ 1. My Hanh Seafood (start) │ │ 2. Bé Ni 2 (+0.3km) │ │ 3. Sound Cafe (+1.2km) │ │ 4. Nia Coffee (+0.8km) │ └──────────────────────────────┘ Total: 2.3km | ~15min (Saved 5.9km!) ``` --- ## 🔗 Related Files - [`app/mcp/tools/graph_tool.py`](file:///Volumes/WorkSpace/Project/LocalMate/localmate-danang-backend-v2/app/mcp/tools/graph_tool.py) - Existing geocoding/spatial search - [`app/shared/chat_history.py`](file:///Volumes/WorkSpace/Project/LocalMate/localmate-danang-backend-v2/app/shared/chat_history.py) - Session management - [`app/agent/mmca_agent.py`](file:///Volumes/WorkSpace/Project/LocalMate/localmate-danang-backend-v2/app/agent/mmca_agent.py) - Chat agent --- ## ✅ Success Metrics - User can add 5+ places to plan in < 2 minutes - TSP optimization runs in < 500ms for 20 places - Replace flow completes in < 3 exchanges with AI