Travelling salesman problem

The Travelling Salesman Problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. The seller visits N cities  and returns finally to his original city. Each city is to be visited once and the route is made as short as possible. The computation time for an exact solution as exp(const*N).



Here(C++)  is Code Implementation for the Traveling
Salesman Problem using the Metropolis algorithm, illustrates
the main aspects of the simulated annealing technique for combinatorial optimization problems. Detail here.

void order(VecDoub_I &x, VecDoub_I &y, VecInt_IO &iorder)
This routine calculates the shortest round-trip path to ncity cities whose coordinates are in the arrays x[0..ncity-1],y[0..ncity-1].
The array iorder[0..ncity-1] is the order in which the cities are visited. On input, the elements of iorder may be set to any
permutation of the numbers 0 to ncity-1. This routine will return the best alternative path it can find.


Bool metrop(const Doub de, const Doub t)
Metropolis algorithm, obtaining a sequence of random samples from a probability distribution. Control temperature t initially is set as 0.5,10% decrease in each step.  If de<0, metrop is true, while if de>0, metrop is only true with probability exp(-de/t) (Boltzmann probability distribution), where t is a temperature determined by the annealing schedule.  Used in function order.

inline Doub alen(const Doub a, const Doub b, const Doub c, const Doub d)
Calculated distance between (a,b) to (c,d)

Doub trncst(VecDoub_I &x, VecDoub_I &y, VecInt_I &iorder, VecInt_IO &n)
This routine returns the value of the cost function for a proposed path segment transport. ncity is the number of cities, and arrays x[0..ncity-1] and y[0..ncity-1] give the city
coordinates. iorder[0..ncity-1] is an array giving the present itinerary.

The first three elements of array n give the starting and ending cities of the path to be transported, and the point among the
remaining cities after which it is to be inserted.

n[3]=(n[2]+1) % ncity;   Find the city following n[2]..
n[4]=(n[0]+ncity-1) % ncity;    the city preceding n[0]..
n[5]=(n[1]+1) % ncity;   the city following n[1].

Calculate the cost of disconnecting the path segment from n[0] to
n[1], opening a space between n[2] and n[3], connecting the
segment in the space, and connecting n[4] to n[5]

Here is a way to use the Numerical Recipes, Version 3, Anneal object on something like a "traveling salesman's" problem:

1. Create vectors of doubles, x and y, for the coordinates of the cities. There will be one x and one y entry for each city visited. Populate the vectors with coordinates of the cities.

2. Create a vector of ints, iorder, for the sequence in which the cities will be visited. This will be changed by the order() function so that its values will be the indices of x,y for the path. Unless you have some particular reason to give a specific initial path, just initialize this vector with 0, 1, 2, ...


3. Create an object of type Anneal.

4. Call that object's order() function with arguments x, y and iorder.

Here's an example that generates random coordinates for ten cities and uses the order() function of an Anneal object:

code:

// Driver for routine anneal

#include "../code/nr3.h"
#include "../code/ran.h"
#include "../code/anneal.h"

//
// Print path and distances
//
void printall(VecDoub x, VecDoub y, VecInt iorder, Int n);

int main()
{
    Ran myRan(12345678);  // For debugging, use the same seed every time
    //Ran myRan(time(0)); // For exploration, use different seeds

    Int       ncity = 10;
    VecInt    iorder(ncity);
    VecDoub   x(ncity), y(ncity);

    for (Int i = 0; i < ncity; i++) {
        x[i] = myRan.doub();
        y[i] = myRan.doub();
        iorder[i] = i;
    }

    cout << endl << "Initial ";
    printall(x, y, iorder, ncity);

    Anneal a;

    a.order(x, y, iorder);

    cout << endl << "Final ";
    printall(x, y, iorder, ncity);

    return 0;
}
void printall(VecDoub x, VecDoub y, VecInt iorder, Int n)
{
    Int i, ii, iii, iiip;
    Doub sum = 0;
    Doub dist;
    cout << "Path:" << endl;
    cout << setw(5) << "City" << setw(8) << "x" << setw(11) << "y" << endl;
    cout << fixed << setprecision(4);
    for (i = 0; i < n; i++) {
        ii = iorder[i];
        cout << setw(4) << ii << setw(11) << x[ii];
        cout << setw(11) << y[ii] << endl;
    }
    // Print out distances for each step
    cout << endl;
    cout << setw(5) << "Leg"
        << setw(11) << "Distance" << setw(9) << "Total" << endl;
    for (i = 0; i < n - 1; i++) {
        iii = iorder[i];
        iiip = iorder[i + 1];
        dist = sqrt(SQR(x[iiip] - x[iii]) + SQR(y[iiip] - y[iii]));
        sum += dist;
        cout << setw(3) << iii << "-" << iiip
            << setw(10) << dist << setw(11) << sum << endl;

    }
    cout << endl << endl;
}

pseudo code for annealing schedule

 

s ← s0; e ← E(s)                                // Initial state, energy.
sbest ← s; ebest ← e                            // Initial "best" solution
k ← 0                                           // Energy evaluation count.
while k < kmax and e > emax                     // While time left & not good enough:
  snew ← neighbour(s)                           // Pick some neighbour.
  enew ← E(snew)                                // Compute its energy.
  if enew < ebest then                          // Is this a new best?
    sbest ← snew; ebest ← enew                  // Save 'new neighbour' to 'best found'.
  if P(e, enew, temp(k/kmax)) > random() then   // Should we move to it?
    s ← snew; e ← enew                          // Yes, change state.
  k ← k + 1                                     // One more evaluation done
return sbest                                    // Return the best solution found.

In Matlab: FindShortestTour
A problem in graph theory requiring the most efficient (i.e., least total distance) Hamiltonian cycle a salesman can take through each of cities. No general method of solution is known, and the problem is NP-hard. Solution to the traveling salesman problem is implemented as TravelingSalesman[g] in the Mathematica package Combinatorica` and FindShortestTour[v1, v2, ...].

Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver either seemingly or probably good solutions, but which could not be proved to be optimal.