Travelling Landscaper Cloud Project

For my CS351 Cloud Computing course, we were assigned an open-ended course project, allowing essentially anything related to the Cloud. People wrote research papers, built personal Cloud-gaming services, and almost anything imaginable. I wanted to use Google Maps APIs to implement the famous Travelling Salesman Problem and apply it to my previous summer job: designing an optimized landscaping route.

There were four stages of the software pipeline to turn a list of 40 addresses into two lists of correctly ordered routes:

  • Convert the Addresses to Lat/Long Coordinates using Google Cloud Platform's (GCP's) Geocoding API.
  • K Means Clustering algorithm to generate the geometric center, which is then used to form two clusters that contain half of the addresses.
  • Generate 2 separate distance matrices using GCP's Distance Matrix API.
  • Solving the Travelling Salesman Problem for both of the two distance matrices with a Dynanmic Programming Algorithm that runs in exponential time. The algorithm will output the most efficient route.

    • Here is an example of one of the routes that was generated (Source: MapQuest)

    This project, including the PowerPoint that I presented in class, are available on GitHub: https://github.com/Bmeshanko/Travelling-Landscaper