CIS 554 Clojure Assignment 3: Traveling Salesman
Fall 2013, David Matuszek

Purposes of this assignment

General idea of the assignment

You probably know the Traveling Salesman problem. A salesman wants to visit each of N cities exactly once, then return to his starting point, and to cover the minimum possible distance while doing so. Your assignment is to write a program to find an approximate solution to this problem, using STM.

There are more efficient ways to tackle this problem. Don't worry about that; just program the algorithm described below.

Detailed specification

Set up the problem

Here is a file containing the latitudes and longitudes of the capitol cities of each of the 50 US states. You can read this in from a file, or build it directly into your Clojure program.

Below is some Java code for computing the distance between two points on Earth, which you should convert to Clojure.

    /**
     * Computes the distance between two locations on Earth.
     * 
     * @param lat1degrees Latitude, in degrees, of the first location.
     * @param long1degrees Longitude, in degrees, of the first location.
     * @param lat2degrees Latitude, in degrees, of the second location.
     * @param long2degrees Longitude, in degrees, of the second location.
     * @return The distance, in miles, between the two locations.
     */
    private static double distance(double lat1degrees, double long1degrees,
            double lat2degrees, double long2degrees) {
        final double earthRadius = 3956; // miles
        double lat1 = toRadians(lat1degrees);
        double long1 = toRadians(long1degrees);
        double lat2 = toRadians(lat2degrees);
        double long2 = toRadians(long2degrees);
        double dLat = lat2 - lat1;
        double dLong = long2 - long1;
        double sinHalfLat = sin(dLat / 2);
        double sinHalfLong = sin(dLong / 2);
        double a = square(sinHalfLat) + cos(lat1) * cos(lat2) * square(sinHalfLong);
        double c = 2 * atan2(sqrt(a), sqrt(1 - a));
        return earthRadius * c;
    }

    private static double square(double x) {
        return x * x;
    }

The initial path will be the sequence of capitol cities, in order. Determine the cost of this path. Use this path and its cost as the current best solution.

Whenever an improvement to this path is found, save the new path, the cost of the path, and the id of the agent that found it. Print the agent number and the new cost, for example Agent 3 found a path with cost 213097.8626953470357.

Find better paths

Create 100 agents, numbered 1 to 100, giving each agent a copy of the current best solution.

Each agent should:

Stop the program when 1000 improvements have been made. Print the final path.

Due date

Your program is due before 6am Wednesday, October 9, via Canvas.