A sophisticated trail recommendation system that uses advanced algorithms to find the perfect hiking trails for groups with diverse preferences. The system implements both Greedy MinMax Regret and Pareto Weighted Scoring algorithms to balance individual satisfaction with group consensus.
- Greedy MinMax Regret: Minimizes maximum regret across all group members
- Pareto Weighted Scoring: Uses Pareto frontier + weighted scoring for optimal balance
- Complete Methodology: Individual utility functions with 5-criteria evaluation
- Group Satisfaction Model: Combines average satisfaction, fairness, and consensus metrics
- Social Choice Theory: Grounded in multi-attribute decision-making principles
- Individual Utility Function: 5-criteria utility based on difficulty, distance, time, elevation, and preferences
- Gaussian Preference Function: Sophisticated distance preference modeling
- Group Satisfaction Model: Combines average satisfaction, fairness, consensus, and controversy metrics
- Diversity Enhancement: Ensures varied trail selections for better group experience
- Family Groups: Diverse ages and fitness levels (parents, children, grandparents)
- Friends Groups: Similar interests with compromise capabilities
- Expert Groups: Experienced hikers with specialized preferences
- React Frontend: Interactive group setup and preference collection
- Real-time Recommendations: Instant trail suggestions with detailed metrics
- Responsive Design: Works on desktop devices
- Orange Gradient Theme: Beautiful and modern UI
./start.sh# Backend
cd backend
npm install
npm start
# Frontend (new terminal)
cd frontend
npm install
npm startAccess the application:
- Frontend: http://localhost:3000
- Backend API: http://localhost:3001
Optimal_TrailSelection_for_Groups/
├── 📁 frontend/ # React frontend
│ ├── 📁 src/
│ │ ├── InteractiveTrailSelector.js # Main component
│ │ ├── index.js # App entry
│ │ └── index.css # Styles
│ └── package.json
│
├── 📁 backend/ # Node.js backend
│ ├── 📁 csv/ # Trail data
│ │ ├── van_wa_200_sorted.csv # 200+ Pacific Northwest trails
│ │ └── README.md
│ ├── 📁 utils/
│ │ ├── groupSatisfaction.js # Core methodology
│ │ └── normalize.js # Data normalization
│ ├── server.js # Express server with API endpoints
│ ├── greedyMinMaxRegret.js # Simplified Greedy algorithm
│ ├── paretoWeightedScoring.js # Pareto algorithm
│ ├── test_greedy.js # Greedy testing
│ ├── test_comparison.js # Algorithm comparison
│ └── package.json
│
├── start.sh # One-click start
└── README.md # This file
Greedy MinMax Regret Refinement:
- Simplified Core Logic: Removed diversity considerations to focus purely on regret minimization
- Clean Return Structure: Returns both trails array and detailed metrics object
- Enhanced Performance: Streamlined implementation for better efficiency
- Core Metric Focus: Emphasizes maximum regret as the primary optimization target
Key Changes:
- Removed
calculateDiversityandcalculateTrailSimilarityfunctions - Simplified
greedyMinMaxRegretto focus on pure regret minimization - Added
returnOnlyTrailsoption for backward compatibility - Enhanced return object with algorithm metadata
Best for: Diverse preferences, fairness-focused groups
Core Principle: Minimizes the maximum regret across all group members by iteratively selecting trails that reduce the worst-case dissatisfaction.
Algorithm Steps:
- Individual Utility Calculation: Each member's satisfaction based on 5 criteria
- Regret Computation: Calculate potential regret for each candidate trail
- Greedy Selection: Choose trail that minimizes maximum group regret
- Iterative Process: Repeat until k trails are selected
Key Features:
- Pure Regret Minimization: Focuses solely on minimizing maximum regret
- Simple and Efficient: Clean implementation without complexity overhead
- Scalable: O(k × m x n² × logn) time complexity
- Fairness Guarantee: Ensures no member is severely dissatisfied
Best for: Similar preferences, consensus-building groups
Core Principle: Uses Pareto frontier to identify non-dominated solutions, then applies weighted scoring for final selection.
Algorithm Steps:
- Pareto Frontier: Identify non-dominated solutions using multi-objective optimization
- Objective Vector: 6-dimensional evaluation (satisfaction, fairness, accessibility, distance, time, consensus)
- Dominance Check: Solution A dominates B if A ≥ B on all objectives and A > B on at least one
- Weighted Scoring: Apply methodology weights to Pareto set
- Final Selection: Choose top-k trails from weighted Pareto set
Key Features:
- Multi-Objective: Balances multiple conflicting objectives
- Pareto Optimal: Guarantees no dominated solutions
- Consensus Focus: Optimizes for group agreement
- Methodology Aligned: Uses same weights as satisfaction model
Individual Utility Function (0-100 scale):
utility = difficulty_score + distance_score + time_score +
elevation_score + preference_scoreGroup Satisfaction Model:
group_score = 0.4 * avg_satisfaction +
0.3 * fairness_score +
0.3 * consensus_degreePareto Objective Vector (6-dimensional):
objectives = [
avg_satisfaction, // Average group satisfaction
fairness_score, // Minimum member satisfaction
accessibility, // Difficulty-based accessibility
distance_score, // Normalized distance preference
time_score, // Normalized time preference
consensus_degree // Group agreement level
]Algorithm Comparison:
| Aspect | Greedy MinMax Regret | Pareto Weighted Scoring |
|---|---|---|
| Focus | Fairness & Regret Minimization | Consensus & Multi-objective |
| Complexity | O(k × m x n² × logn) | O(n² × m) |
Greedy MinMax Regret Usage:
const { greedyMinMaxRegret } = require('./greedyMinMaxRegret');
// Simple usage - returns selected trails
const trails = greedyMinMaxRegret(trails, groupMembers, 5, { returnOnlyTrails: true });
// Full usage - returns detailed results
const result = greedyMinMaxRegret(trails, groupMembers, 5);
console.log(result.selectedTrails); // Selected trails
console.log(result.maxRegret); // Maximum regret value
console.log(result.algorithm); // Algorithm name
console.log(result.objective); // Objective descriptionPareto Weighted Scoring Usage:
const { selectParetoK } = require('./paretoWeightedScoring');
const weights = {
avg: 0.4, // Average satisfaction weight
min: 0.3, // Fairness score weight
cons: 0.3 // Consensus degree weight
};
const recommendations = selectParetoK(trails, groupMembers, 5, weights);- Average Rating: Trail quality assessment (1-5 stars)
- Average Distance: Physical accessibility (km)
- Average Satisfaction: Overall group happiness (0-100%)
- Fairness Score: Minimum member satisfaction (0-100%)
- Consensus Degree: Group agreement level (0-100%)
- Max Regret: Maximum group dissatisfaction (core Greedy metric)
- Diversity Score: Trail variety percentage (0-100%)
- Family: Safety, accessibility, fairness across ages
- Friends: Compromise, shared experiences, group dynamics
- Expert: Technical difficulty, specialized interests, challenge level
cd backend
# Test Greedy algorithm
node test_greedy.js
# Test Pareto algorithm
node test_pareto.js
# Compare both algorithms
node test_comparison.js- Family Group: Diverse ages and fitness levels
- Friends Group: Similar interests with compromise
- Expert Group: Experienced hikers with specialized preferences
- Greedy MinMax Regret: O(k × n × m)
- Pareto Weighted Scoring: O(n² + k × n × m)
- Where: k = trails to select, n = total trails, m = group size
- Greedy MinMax Regret:
- ✅ Higher average satisfaction
- ✅ Better fairness scores
- ✅ Lower maximum regret
- ✅ Ideal for diverse groups
- Pareto Weighted Scoring:
- ✅ Better consensus building
- ✅ Multi-objective optimization
- ✅ Ideal for similar preferences
- Trail Dataset: 200+ Pacific Northwest trails
- Group Size: 2-10+ members
- Real-time Processing: < 1 second response time
GET /api/trails- Get all trailsGET /api/trails/filter- Get filtered trailsPOST /api/trails/recommend- Get group recommendationsGET /api/scenery-types- Get all scenery typesGET /api/trails/stats- Get trail statisticsGET /api/health- Server health check
- Difficulty: Easy, Moderate, Hard
- Distance: 0-50km range
- Time: 0-12 hours
- Elevation: 0-3000m
- Scenery: Ocean, Mountain, Forest, Lake, etc.
- Member Management: Add/remove group members
- Preference Collection: Individual preference forms
- Constraint Setting: Physical and time limitations
- Trail Cards: Detailed trail information
- Metrics Dashboard: Algorithm performance metrics
- Group Satisfaction: Individual and collective scores
- Real-time Updates: Instant recommendation updates
- Machine Learning Integration: ML-based preference prediction
- Real-time Updates: WebSocket support for live updates
- Advanced Filtering: More sophisticated filtering options
- User Feedback: Incorporate user ratings and feedback
- Mobile App: Native mobile application
- Social Features: Share recommendations and group planning
- Caching: Redis integration for faster responses
- Database: PostgreSQL for persistent data
- Authentication: User accounts and saved preferences
- API Documentation: Swagger/OpenAPI documentation
- Testing: Comprehensive unit and integration tests
This project implements advanced concepts from:
- Social Choice Theory: Group decision-making principles
- Multi-Attribute Decision Making (MADM): Multi-criteria evaluation
- Gaussian Preference Functions: Sophisticated preference modeling
- Pareto Optimality: Multi-objective optimization
- Regret Minimization: Worst-case scenario optimization
MIT License - see LICENSE file for details
- Pacific Northwest Trail Data: Real hiking trail information
- React Community: Frontend framework and ecosystem
- Node.js Community: Backend runtime and packages
- Academic Research: Social choice theory and group decision-making