Recommendations & Route Optimization in Travel Application

I built a travel itinerary maker, TravelBug, a rails app, which helps a user create itineraries by selecting different cities. The app provided lot of interesting opportunities to improve user functionality using data structures. Below are some of the user features I implemented using data structures and algorithms:

A. Destination Recommendation

My app provides recommendations to users based on destinations that they’ve already selected. The idea behind the recommendation system is to provide users information based on past data of other users on our travel app.

For example, let’s consider we have the following trips created by users on our travel app in the past:

A -> B -> C

A -> D -> E

B -> F -> G

A -> B -> F

X -> Y -> Z

I created a graph system that iteratively creates new nodes/paths when each new route is added. Each graph node is also added into a hash to enable search in O(1) time as opposed to implementing search algorithms with O(V+E) time complexity. When a user creates a new trip with a destination B, we provide recommendations of B’s children in the graph i.e. , F & C.

Graph System Representing all Trip Paths

Code integrated in Ruby, integrated with Rails models:

Challenge (Implementation in Rails):

The graph is deleted every time the server is killed and creating the graph every time scales in time complexity with the number of destination nodes O(n). A simple fix was to create a GraphNode model in the database with 2 columns each for the node value and the adjacency matrix.

The graph_nodes table in our database is as shown:

B. Route Optimization

Let’s consider the following scenario where a user wants to embark upon a journey across the United States from London. He wants to visit the following cities — Seattle, Austin, New York City, San Francisco and Orlando.

My itinerary will also tell the user the most optimal route that he needs to take for his trip i.e., London -> New York City -> Orlando -> Austin -> San Francisco -> Seattle

Shortest Possible Trip Distance

This is a classic spanning tree problem where we have to cover all the vertices.

This problem can be solved using the Prim’s Minimum Spanning Tree algorithm for the shortest path in a graph. The Prim’s algorithm is a greedy algorithm where we have a mapped and unmapped set of vertices. The mapped vertices initially set to a single random vertex and gradually expanded to cover all vertices. We keep choosing the closest vertex to our already mapped vertices collection, at every step.

Algorithm

1. Choose a random starting vertex to begin from
2. Find the closest edge to the selected vertices and add the added edge vertices to a priority queue
3. Repeat 2 until you cover all nodes

I created a “complete” graph of the user inputs and obtained the distances between each pair of cities using the Google API. The resulting graph looks like this :

Implementation of my code in Python:

Test Run

Assumptions:

1. More popularly known as the Travelling Salesperson problem, this is an unsolved algorithm and the Minimum Spanning Tree solution only offers an upper bound solution.

2. I assume that the user can only take flights from and/or to the cities in his itinerary

3. Took the road travel routes to calculate distances in creating the graph which may not be an accurate depiction of flight travel routes