32 - Traveler Hacks

The cheapest flight which adds Hong Kong and Shanghai which reduces the cost by $394.9 (34.2% savings!) when compared to a single RT ticket.
This image is currently processing. Please be patient...
This image is currently processing. Please be patient...
Adding Sydney and Melbourne to your flight costs only $95.6 more!

Inspiration

When I got married, I always had the dream of going on an extended honeymoon. So, when I saw that a round-trip from SFO to NRT was over $1,800, my dreams were crushed. However, being unreasonable, I wanted to check how much it would cost to add South Korea in the route as another destination. To my surprise, the cost of the flight went down.

After continuing further, I booked 8 flights from San Francisco to Tokyo, Taiwan, Singapore, Thailand; Beijing, Seoul, San Francisco for $1,694 per person (tax included) with all direct flights and no mileage points. In comparison, rent in San Francisco would have costed us nearly $4,000. When we got back, we ended up moving to Seattle.

What it does

It can save consumers money on long trips and lets them visit more cities with only direct flights. For example, if you want to head to Tokyo (NRT) and would like to stop in a few cities with about 21 days of vacation, it would recommend that you stop in ICN to save $247.6 (21.4%). Or, if you choose to visit three destinations, you can visit Tokyo, Bangkok, and Shanghai for $196.54 (17%) less than a round-trip ticket to Tokyo.

How we built it

Our algorithm was initially inspired by a knapsack routing algorithm we developed to pick the best dates which slowly morphed as we ran it on test data. To figure out the routes, we created a non-stop route map of the most popular airports in the world, sorted each airport by region in the world, and leveraged stop-overs for route inspiration to find the best route.

Our backend is built primarily Node.JS / Sails, leverages the suggestions & resolutions Expedia API for city lookup and disambiguation, and flight search data from Google.

Challenges we ran into

The largest issue we ran was sorting through 1M+ different flight combinations (SFO -> NRT -> BKK -> ICN -> SFO) – which yields 1M+ combinations with just about 100 airports. If you include date ranges, it quickly becomes over 100M+ possible flight routes.

Leveraging iterative search, dynamic programming to build up routes, greedy to optimize flight dates w/ a modified knapsack, and building caches of the route maps around the world – we were able to reduce 1M+ possibilities to nearly ~300 flight combinations and relatively attractive routes that are very difficult to find on traditional travel sites.

Accomplishments that we're proud of

Our product can help the price-conscious honeymoon traveler visit their dream cities for a fraction of the cost. We used it on Saturday night (1/30) to help one of my former groomsmen plan their honeymoon. They'll be traveling to HKG and Bangkok in late February.