Optional Computational Project (CO 353, Winter 2016)
Goal: Finding a shortest-possible USA 48-States Tour
This is an optional project that can replace the final exam for CO 353. Completing the project will require a large amount of time, so I can only recommend it if you are very interested in the implementation details of the topics we have discussed in class.
|
| American Statesman, May 23, 2010 |
Generalized TSP
In the generalized traveling salesman problem (GTSP), the nodes V are partitioned into k clusters V1, V2,..., Vk and you are asked to find a minimum cost circuit that includes exactly one node in each cluster. There are many papers describing work on the GTSP. For example, the following paper describes a genetic algorithm to find a GTSP tour.
The generalized traveling salesman problem: A new genetic algorithm approach John Silberholz and Bruce L. Golden, Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, edited by E. Baker, A. Joesph, A. Mehrotra, M. Trick, Springer, 2007.
The above paper reports on test instances with up to 1,000 nodes, but with a large number of small clusters of approximately 5 nodes each. The project is to adopt heurstic methods from the literature (or develop your own ideas) to find a good solution to an example having many more nodes (over 100,000), but with fewer clusters.
USA Data
The data set for the project contains 115,475 cities in the United States. Here is a list giving the (scaled) latitude and longitude of each city, grouped by states. Information on how the 115,475 cities were selected can be found on the page Are there really 115,475 Cities in the United States? Your algorithm must select one city from this list in each of the 48 states and compute a tour through the 48 points. The goal is to make the tour as short as possible.
For the project, use the Euclidean distance (rounded to the nearest integer) as the travel distance between pairs of cities; this is the EUC_2D norm adopted in the TSPLIB, the standard library for the TSP.
Your Work
All of your algorithmic work should be your own, that is, you cannot adopt TSP or generalized TSP codes or packages written by others. You can, however, use exisiting tools for visualizing the data or other analysis. Please contact me if you have questions on whether it is permitted to use some particular optimization tool or package.
Project Report
To obtain credit for the project (replacing the final exam), your material must be turned in by Tuesday, March 29. The material should consist of a written report of 5 to 10 pages, describing the methodology used in your computations and the results of your computational tests. The written report can be a pdf file or a printed document.
You must also turn in a text file giving a list of the 48 cities in your best tour, in the order visited by the tour. Each line in your tour file should consist of one line from the 115,475-city data file (latitude-longitude, city name, county name, state).
Finally, you must turn in files giving the source code (written by yourself) that was used to obtain the computational results, together with instructions on how to build and run the code, so that your results can be reproduced.