## Inspiration

Earlier this month, our group of friends decided to travel around Europe for three weeks at the end of the school year. Since we’re college students and naturally want to save money, we spent hours comparing different flights from so many different websites, trying to find the best deals on the right days to book plane tickets at each airport. Even after hours of comparing different options, we still didn’t manage to agree a good travel plan for the 6 cities that we planned to visit. There were simply too many combinations to try, and having to compare flights across several different airlines’ websites quickly became messy and hard to keep track of.

## What it does

We then learned about the Amadeus API and realized that we could leverage its flight low-fare search to help us find the cheapest viable path through all the cities we wanted to visit. We modeled this problem as a dynamic variant of the travelling salesman problem, where we treat each city to visit as a node on our graph, each connecting flight as an edge, and seek to minimize the total cost of visiting all cities subject to the constraint of spending a minimum amount of time at each city. It is a dynamic variant of the problem because we want to spend a certain amount of time in each city, meaning that the flight prices (and therefore edge weights) change every time we visit a new city.

Doing this allowed us to computationally determine the cheapest route through Europe without having to sacrifice leaving a city early in the hopes of saving more money.

In order to make this process even easier, we chose to let users use our service by answering a few questions on our website or by simply chatting with our Facebook Messenger chat bot. Using Messenger allowed us to add additional functionality such as providing suggestions for vacation spots and reminding the user of their flight the day of departure. Since people often lose their cell service and SMS ability when travelling overseas, we thought that using Messenger (which only requires Internet) for text reminders would be very valuable.

## How we built it

The first thing we did was build a small library over the Amadeus API which allowed us to build our graph. We then split the project into two parts - building the chatbot and building the website. Both parts used the same javascript library that we wrote for computing the minimum prices. The website was built with Ruby on Rails, and the chatbot was built with Node.JS. The graph algorithm and handling the Amadeus data were done in Javascript.

## Challenges we ran into

The travelling salesman problem is NP-Complete, meaning that there does not exist a polynomial time algorithm for computing it. Therefore, with many cities, and therefore many calls to the Amadeus API, computing the true optimal path becomes nearly intractable given practical constraints. Therefore, we implemented a randomized greedy approach. We couldn't just use the standard travelling salesman algorithms, since the graph changed depending on how long the visitor stayed at each node. There are definitely still kinks that we are working out, but it was a great way to practice creating new approaches to problems in a real world setting.

We also spent a long time wrangling with Facebook messenger, and while we learned a lot in the process, we weren't able to make it very generalizable.

## Accomplishments that we're proud of

We were able to find a great path through Europe that we hadn't considered before that saved us a substantial amount of money compared to what we had considered before. If nothing else, we learned a ton and will be happy to know that at least it made a difference in our lives and our friends lives for the summer.

We also have it hosted on a public website, so other people who want to use the service can free of charge. Also, the Facebook messenger bot will be published so other people can interact with it.

## What we learned

API integration, practical nitty-gritty, how to reason about algorithms in the real world given new, unique constraints. We learned that it is actually possible solve problems in the real world, and create things that actually can make an impact on other people's lives.

## What's next for RoundTrip

Ideally we will fix some kinks in the graph algorithm, and polish the facebook messenger bot. We'd like to get it into a state where it is standalone usable by the general public.