Drone Delivery

Project Overview

This command line program implements various graph algorithms. It first receives a list of (x,y) coordinates from standard input then produces a solution depending on the mode specified by the user:

MST: The program uses Prim's algorithm to construct a minimum spanning tree. It then outputs the total weight of the tree and a list of edges.

FASTTSP: The program uses an arbitrary approximation algorithm to create an upper-bound heuristic for the optimal traveling sales person route to use. I chose to implement a greedy nearest neighbor algorithm. The program outputs the total length of the tour followed by the nodes in the order they were visited.

OPTTSP: The program uses the "FASTTSP" algorithm to find and output the optimal tour using a branch and bound approach.

Date: Winter 2020

For more details read the original spec attached below

Project Role

As this was an individual assignment, I was reponsible for all implementation details, maintenance, version control, and functionality.

Relevant Technology

  • C++
  • Minimum spanning trees
  • Prim's algorithm
  • Tours
  • Traveling Salesman
  • Greedy nearest neighbor
  • Branch and bound
  • Graph algorithms

Relevant Skills

  • Time complexity efficiency
  • Independent development
  • Version control
  • Heuristics