Comparing traveling salesman problem algorithms to chart delivery routes in a city

Delivery and logistics companies such as Swiggy, Uber Eats, and Zomato strive to deliver to customers as fast as possible by traveling the shortest, most optimal routes to reduce travel time. The travelling salesman problem (TSP) is a combinatorial optimization problem that attempts to minimize tour lengths when traversing edges in a mathematical graph. Given that the TSP is a computationally heavy problem, modern computers lack the processing power needed to find an exact, optimal solution, which requires large amounts of recursion and backtracking. In a city, nodes represent households or neighborhoods, while edges represent the roads traveled by delivery vans. Therefore, the TSP offers a solution to reduce travel time in cities by minimizing the distances traveled on roads. Our study compared different TSP algorithms and heuristics used to estimate solutions. We implemented multiple approximation algorithms and determined the accuracy and efficiency of these models using real-world datasets. Further, we hypothesized that increasing the number of delivery destinations will result in higher total travel times, and that the choice of logistics algorithm will significantly influence both the estimated travel distance and the algorithmic compute time when charting optimal travel routes. Our results indicated that with more delivery destinations, longer routes produced greater travel times. Additionally, we saw that simpler TSP algorithms estimated longer tour lengths, but also took shorter runtimes to compute the solution than more complex TSP algorithms. Finally, our findings gave us insights into the potential of utilizing the TSP to chart delivery routes in a city.