TSP (Travelling Salesman Problem)

Red Alert

I'm trying to solve the Travelling Salesman program at the moment. Aside from using the 'nearest neighbour' algorithm - has anybody come across any other methods which lend themselves well to either matrix methods or to computer programming constructs. (I'm currently trying to deal with it using MATLAB and I don't think the nearest-neighbour is going to give a good solution unless the points are relatively large in number or well spaced out.)

Cheers,
R.A.

breadmonkey

Since I haven't heard of a lot of the stuff in your previous post, I don't think I'm in a position to help but just out of curiosity, what is the problem?

Capt'n Midnight

traveling sales man has to visit several cities one after the other.
the trick is to figure out the shortest route.

only thing is the number of possible combinations grows exponentially with each new city so you can't search exhaustively .

Red Alert

I found this solution - insert the node whose minimal distance to a tour node (one already on the route) is maximal. Start off with a triangular tour.

It's proving difficult to code... very difficult!

Delphi91

Red Alert wrote:

I found this solution - insert the node whose minimal distance to a tour node (one already on the route) is maximal. Start off with a triangular tour.

It's proving difficult to code... very difficult!

Hmm, correct me if I'm wrong, but isn't the TSP insoluble????

Mike

Capt'n Midnight

Delphi91 wrote:

Hmm, correct me if I'm wrong, but isn't the TSP insoluble????

No it's not. Just takes a lot of time to work out all possible combinations.

Bit like the steiner tree you need to generate local minimums without risking missing a bigger one - IIRC one result of the steiner tree was that generating extra nodes to shorten the routes only resulted in a 13% saving.

Is there anything like this in the travelling salesman problem ?
where the time taken to compute the next incremental saving in travelling time would take longer than the time saved - and how do you recognise you've reached that point ?

ecksor

Delphi91 wrote:

Hmm, correct me if I'm wrong, but isn't the TSP insoluble????

Depends on what you mean. It's a problem in NP, so there's no known algorithm that is always efficient (which is what is meant when people mention the TSP as being insoluble), but there are algorithms that are efficient in certain situations and inefficient in others. A judgement must be made as to what is most suitable and that appears to be what Red Alert is trying to do here.

Delphi91

ecksor wrote:

Depends on what you mean. It's a problem in NP, so there's no known algorithm that is always efficient (which is what is meant when people mention the TSP as being insoluble), but there are algorithms that are efficient in certain situations and inefficient in others...

Ah right.

Actually I did write a program a few years back to come up with a solution based on a matrix idea where the matrix consisted of the distance of every town from every other town. Every time I ran the program it gave different answers! (Obviously not very efficient!)

Mike

sirpsycho

u could always try a neural network to figure out a solution

Billabong

I worked briefly with the TSP algorithm last year in order to speed up an automated PCB drilling plot which I had to design as a project last year. I was getting optimisation of up to 70% improvement over the original tour order which the ECAD was outputting in the NC drill files. I coded it originally in C which was a pain in the *** but i'm sure you should have no problem with Matlab.

Simulated Annealing
chose a start tour
chose a start temperature (T), set x
repeat{
repeat{
make a change to the old tour
delta=new tour length – old tour length
if delta < T
then old tour = new tour
}until no positive changes were done in x attempts
reduce T
}until T has reached a predefined value}
end

The two parameteres are the temperature T and x. These are key to the efficiency in speed of calculation and in output tour length. Set x to 100,000 or more if you have a faster computer. I found it is best when the temperature is related to the average distance between points on the tour.
Your welcome to the mess of c code i used to acheive the 70 % reduction if you want it.
Good luck pulling your hair out with your project.

ps for yet another useless piece of bull**** information its called simulated annealing as the temperature is gradually reduced or cooled over time i.e annealing>metallurgy.

silverside

haven't studied this problem in any depth but when i was taught it donkey's years ago, the algorithm was:
generate any feasible route
search for '2-opt' or '3-opt' swaps which would decrease the total length
these are generated by taking 2 points or 3 points and moving them around in the route order so that the total length decreases.
no doubt you could also use simulated annealing here.

there should be loads of papers on this on ssrn.com or whatever the equivalent is for computer science.