The Traveling Salesman Problem (TSP) is one of the most studied problems in optimization. Since it is an NP-Hard problem, there exist several heuristics that find locally optimal solutions, as opposed to the globally optimal solution. We are interested in developing a new algorithm using a connection between Minimum Cost Flow Problems (MCF) and TSP.

MCF, which is a fundamental network flows problem, can be solved efficiently. A popular strategy, known as cycle-cancelling, can solve the MCF in strongly-polynomial time. In this project we study the advantages and disadvantages of cycle-cancelling algorithms in the context of the TSP. We identify scenarios in which a cycle-cancelling algorithm performs well or poorly on the TSP. Specifically, we study the properties that cycles must satisfy to retain a tour when cancelled and how to best deal with subtours that may arise through the cancellation of a general cycle. Practical implementations will lead to new heuristics for the TSP.