/usa-travel-planner

Maximize the number of places you can visit in the USA

Primary LanguagePythonMIT LicenseMIT

usa-travel-planner

Project Status: Inactive – The project has reached a stable, usable state but is no longer being actively developed; support/maintenance will be provided as time allows. Project License Latest Commit Repo Size GitHub Followers

"Homepage"

Link: https://nameless-island-45745.herokuapp.com/travelplanner/

Getting Started

Objective: To help users maximise the number of places they can visit in the USA, within a limited amout of time.

If this problem sounds familiar, you've probably heard of the Travelling Salesman Problem. In this NP-Hard problem, if we were to consider calculating the length of all possible routes, we'd end up with a time complexity of O(n!). In other words, it's going to take an extremely long time before we find the answer!

One way to overcome this issue is to use Heuristics, which are approximation algorithms that provide answers close to the optimal solution. Here, I've implemented the Greedy heuristic, otherwise known as the shortest links heuristic. This works by constructing a graph based on the establishing shortest links between nodes without creating cycles prior to completion of the algorithm. The time complexity of this heuristic is O(n2log2(n)) which is significantly lower than O(n!).

Application Details

This web application relies on Flask as the web framework. The user interface has been designed using Dash by Plotly, and the list of Cities are stored in DynamoDB.

Step One

Step One Select the destination and the attractions you'd like to visit, as well as the place you will be staying and the length of your stay. Click Proceed.

  • In the backend, the application uses Google Places API to identify all selected attractions in your accomodation vicinity.
    • It then performs K-means clustering using sklearn, where 'K' represents the duration of your stay, to group attractions based on their coordinates.
    • A scatterplot of the clustered locations will be displayed.

Step Two

Step Two For each day of your stay, select the attractions you'd like to see by clicking the checkbox of the attraction. Once done, click Select.

  • The application then performs the Greedy TSP heuristic.
  • Routes for each day is captured in a networkx graph plot.

Step Three

Step Three For ease of reference, click on Download to download an Excel file containing the routes in a user-friendly format.

  • Excel files are stored in an Amazon S3 bucket which is accessed using Boto3.

Installation and Deployment

1) Pre-conditions

You'll need to create an AWS account to interact with DynamoDB and S3. Take note of your AWS credentials - we'll need it later.

Next, you'll need credentials for the Google Places API which can be obtained here.

2) Setting up the Environment

Once you SSH into your server, clone this repository.

git clone https://github.com/Jordan396/usa-travel-planner.git

cd usa-travel-planner/

Create a virtualenv and install dependencies:

python3 -m virtualenv venv
source venv/bin/activate
pip install -r requirements.txt

Create a new file called config.py.

vim config.py

Insert your credentials (from step 1) accordingly:

AWS_SECRET_ACCESS_KEY = [YOUR AWS_SECRET_ACCESS_KEY]
AWS_ACCESS_KEY_ID = [YOUR AWS_ACCESS_KEY_ID]
GOOGLE_MAPS_API_KEY = [YOUR GOOGLE_MAPS_API_KEY]
AWS_REGION_NAME = [YOUR AWS_REGION_NAME]

3) Run Application

python index.py

There you have it! You can access your web application at localhost:5000/travelplanner.