CIS Logo SVC Logo

   Computing & Information Systems
   Department

 

Schoology Facebook        Search CIS Site      Tutorials

Traveling Salesperson Problem: Software and Lab


The following are simple C++ implementations of various algorithms for solving small traveling salesperson problems exactly. All have a plain text-based interface. Only the source code is provided under the following links.

  • tsp1.cpp carries out the basic brute-force TSP (traveling salesperson problem) algorithm to enumerate all the tours of the cities in order to find an optimal tour.
  • tsp2.cpp uses the capability of backtracking to avoid recomputing the cost of a partial tour that has already been found. This reduces somewhat the number of additions used in finding the costs of the tours.
  • tsp3.cpp also adds a simple branch and bound technique. Whenever a partial tour has a cost that is greater or equal to the lowest cost tour found thus far, the entire branch of the search tree that begins with this partial tour is eliminated.
  • tspcombined.cpp carries out all three of the above TSP algorithms.
  • Data files for use with the above programs.
  • TSPLab.docx is a lab for students to time how long the above algorithms take to solve TSP problems with different numbers of cities, and to graph and analyze the results.

All of the above materials are made available under the following license:

Creative Commons License
TSP educational software and lab by David Carlson with Paul Scarrone and Daniel Kissel is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Maintained by: Br. David Carlson
Last updated: July 04, 2017
Disclaimer