The TravelingStudent Problem

Inspiration

Our inspiration stemmed from the need to optimize travel and navigation for students, especially those new to a city or country. The complexity of finding the most efficient route in a new environment prompted us to explore how we could use geolocation and data optimization techniques to make everyday errands easier and faster.

What it does

Our tool provides an optimized route planner designed to help users navigate multiple stops efficiently. By using geolocation data, it calculates the best possible route, minimizing travel time and distance. The tool integrates Google Street View for each stop, offering users a clear view of their destination. It is ideal for people unfamiliar with their surroundings, offering simplicity and practicality.

How we built it

We started by exploring and using multiple Melissa Data APIs to get geolocation data (latitude and longitude). We used the Haversine formula for accurate distance calculations between stops based on latitude and longitude. The backend was built using Python and Folium, while the frontend was developed with HTML, CSS, and JavaScript. To solve the Traveling Salesman Problem (TSP), we initially tested a greedy algorithm before switching to brute-force TSP for accuracy. The optimization ensures minimal travel distance across all stops.

Challenges we ran into

API Rate Limits: We faced limitations on the number of API calls, causing us to adjust our approach and utilize alternative methods. Device Blocking: Some devices were blocked due to too many API hits, requiring us to work with different setups. Algorithm Complexity: Initially using a greedy algorithm for TSP to make it more efficient but led to inaccuracies, requiring us to switch to a brute-force method for optimal results.

Accomplishments that we're proud of

Optimized Route Planner: We successfully created an optimized route for 353 stops, minimizing the total distance to 9.5 km. Real-World Application: The tool is user-friendly, integrating essential features like Google Street View for each stop and clear route visualization, making it practical for everyday use.

What we learned

Data Handling: Real-world data is messy, and cleaning and verifying data is essential to ensure accuracy. Optimization: Switching from the greedy algorithm to brute-force TSP helped us strike the right balance between efficiency and accuracy. User-Centric Design: We prioritized simplicity and accessibility in our interface, ensuring it’s easy to use for non-technical users. Resilience: We learned the value of persistence — by trying different approaches, we eventually overcame obstacles and found the right solutions. Collaboration: Effective communication and task delegation within our team enabled us to leverage each other’s strengths and stay on track. Adaptability: Adapting quickly to new challenges and shifting approaches helped us navigate technical and logistical hurdles. Problem-Solving: We honed our ability to think creatively to address issues, ultimately leading to an optimized solution.

What's next for The TravelingStudent Problem

Enhanced Street Navigation: We plan to integrate detailed street-level data, including buildings, walkways, and pedestrian routes, to provide more accurate and practical directions, simulating real-world navigation. Dynamic Re-routing: Real-time traffic updates will allow the tool to adjust routes based on live conditions, improving travel efficiency and reducing delays. Real-Time Location Tracking: Users will have the ability to track their location and dynamically reroute based on their position, offering a personalized navigation experience. Platform Integration: We envision extending this tool to work seamlessly with popular navigation platforms like Google Maps, allowing everyday users to leverage the optimized routing for various scenarios. Expanded Use Cases: Beyond students, the tool will serve tourists, professionals, and anyone navigating complex urban environments, offering a smarter, more efficient way to move around the city.