# Travelling salesman variation in python

Discussion in 'Python' started by Erlend Andreas Garberg, Apr 1, 2004.

1. ### Erlend Andreas GarbergGuest

Hi!

I'm trying to code a implementation of a variation of the travelling
salesman problem.

The problem is the following.

I have X nodes.
Each node has a number assosiated with each of the other nodes.

The problem is then:
Construct a ring of the nodes so that the sum of the numbers is the
highest possible.

Example:
Nodes:
A with numbers B->1200, C->2000
B with numbers A->3000, C->4000
C with numbers A->9000, B->5000

The optimal ring is in this case can f.ex. be:
A->1200->B->4000->C->9000->A with sum 14200.

I have implemented this in python in the following way:

hash is a dictionary with node-name as key and node-object as value.
Each node-object has a dictionary speeds with node-name as key and a
number as value. this dict stores the numbers associated with the other
nodes.

-------------------------------------------------------------------
# method xcombinations
def xcombinations(items, n):
if n==0: yield []
else:
for i in xrange(len(items)):
for cc in xcombinations(items[:i]+items[i+1:],n-1):
yield [items]+cc

# help function
func = lambda x,y: int(hash[x].speeds[y])

# code starts here:
bestcomb = []
bestspeed = 0

for comb in xcombinations(hash.keys(),len(hash)):
speed = sum(map(func,comb,comb[1:] + comb[:1]))
if speed > bestspeed:
bestcomb = comb
bestspeed = speed

-----------------------------------------------------------------

My implementation generate all combinations, and check which gives the
highest result.

My problem is that when the number of nodes is higher than 8, the
algorithm slows to a crawl (because of O(n!) complexity). I wonder if
there is some way I can optimize my algorithm to make it run faster?
Currently it takes 20 seconds to compute the best combination with 9
nodes on my hardware.

I would appreciate some comments on this

--
Regards
Erlend Garberg

Erlend Andreas Garberg, Apr 1, 2004

2. ### Josiah CarlsonGuest

> I would appreciate some comments on this

Look at current TSP algorithms, and exchange their minimization rutines
for a maximization rutine. TSP is an NP-hard problem, which means that
there is no currently known algorithm for solving it in polynomial time.
You can approximate it or do a search on the solution space, but
solving it requires searching basically all of the solution space.

- Josiah

Josiah Carlson, Apr 1, 2004

3. ### Erlend Andreas GarbergGuest

In article <c4ho3l\$4he\$>, Josiah Carlson wrote:
> Look at current TSP algorithms, and exchange their minimization rutines
> for a maximization rutine. TSP is an NP-hard problem, which means that
> there is no currently known algorithm for solving it in polynomial time.
> You can approximate it or do a search on the solution space, but
> solving it requires searching basically all of the solution space.
>
> - Josiah

An approximate solution would be good enough, do you have any
suggestions about how do do that?

--
mvh
Erlend Garberg

Erlend Andreas Garberg, Apr 1, 2004
4. ### Paul RubinGuest

Erlend Andreas Garberg <> writes:
> An approximate solution would be good enough, do you have any
> suggestions about how do do that?

Is it just an arbitrary graph? Most TSP approximation algorithms
depend e.g. on the triangle inequality, i.e. d(A,C) <= d(A,B) + d(B,C).

Papadimitriou and Stieglitz, "Combinatorial Optimization" was a
standard textbook on this stuff, though is pretty old by now.

Paul Rubin, Apr 1, 2004
5. ### Erlend Andreas GarbergGuest

In article <>, Paul Rubin wrote:
> Erlend Andreas Garberg <> writes:
>> An approximate solution would be good enough, do you have any
>> suggestions about how do do that?

>
> Is it just an arbitrary graph? Most TSP approximation algorithms
> depend e.g. on the triangle inequality, i.e. d(A,C) <= d(A,B) + d(B,C).
>
> Papadimitriou and Stieglitz, "Combinatorial Optimization" was a
> standard textbook on this stuff, though is pretty old by now.

The graph is arbitrary, yes..

--

mvh
Erlend Garberg

Erlend Andreas Garberg, Apr 1, 2004
6. ### Günter JantzenGuest

Hello Erlend,

in my opinion its not a TSP. In TSP problems a minimum is searched, you
search the maximum
And TSP is usually formulated for undirected graphs. So (for me) its not so
clear if the problem is NP

Did you think about trying a greedy algorithm. Start at some point and go
always the way with the highest value and eliminate the previous note

If you want better results, try it with more combinations. For example
choose the three highest values from every node and follow this ways if
possible

Use backtracking with recursive calls
(explained in many textbooks about discrete mathematics. Typical example -
the 8 queens problem)

Of course I have no idea if this approch will be helpful

Günter

"Erlend Andreas Garberg" <> schrieb im Newsbeitrag
news:...
> Hi!
>
> I'm trying to code a implementation of a variation of the travelling
> salesman problem.
>
> The problem is the following.
>
> I have X nodes.
> Each node has a number assosiated with each of the other nodes.
>
> The problem is then:
> Construct a ring of the nodes so that the sum of the numbers is the
> highest possible.
>
> Example:
> Nodes:
> A with numbers B->1200, C->2000
> B with numbers A->3000, C->4000
> C with numbers A->9000, B->5000
>
> The optimal ring is in this case can f.ex. be:
> A->1200->B->4000->C->9000->A with sum 14200.
>
> I have implemented this in python in the following way:
>
> hash is a dictionary with node-name as key and node-object as value.
> Each node-object has a dictionary speeds with node-name as key and a
> number as value. this dict stores the numbers associated with the other
> nodes.
>
> -------------------------------------------------------------------
> # method xcombinations
> def xcombinations(items, n):
> if n==0: yield []
> else:
> for i in xrange(len(items)):
> for cc in xcombinations(items[:i]+items[i+1:],n-1):
> yield [items]+cc
>
> # help function
> func = lambda x,y: int(hash[x].speeds[y])
>
>
> # code starts here:
> bestcomb = []
> bestspeed = 0
>
> for comb in xcombinations(hash.keys(),len(hash)):
> speed = sum(map(func,comb,comb[1:] + comb[:1]))
> if speed > bestspeed:
> bestcomb = comb
> bestspeed = speed
>
> -----------------------------------------------------------------
>
> My implementation generate all combinations, and check which gives the
> highest result.
>
> My problem is that when the number of nodes is higher than 8, the
> algorithm slows to a crawl (because of O(n!) complexity). I wonder if
> there is some way I can optimize my algorithm to make it run faster?
> Currently it takes 20 seconds to compute the best combination with 9
> nodes on my hardware.
>
>
> I would appreciate some comments on this
>
> --
> Regards
> Erlend Garberg
>

Günter Jantzen, Apr 1, 2004
7. ### Jeff EplerGuest

Can't TSP be converted to your problem?

If you have TSP with distance(Xi, Xj)=Dij, then convert it to your
problem by letting distance(X'i, X'j)=distance(X'j, X'i)=-Dij.
or if only positive weights are allowed then use max(D)-Dij.

Jeff

Jeff Epler, Apr 1, 2004
8. ### Josiah CarlsonGuest

> An approximate solution would be good enough, do you have any
> suggestions about how do do that?

One approximate solution to the TSP is the bitonic TSP. That is, start
at the leftmost point, find a path to the rightmost point, then find a
return path to the leftmost point.

Search for 'optimal bitonic tsp' in google, the second entry will have
pseudocode for the algorithm. I've personally converted it to Python
for other uses, but I'll leave it as an exercise for you.

You can convert it into your 'maximum' by changing the line:
if q < b[j - 1, j] then
to:
if q > b[j - 1, j] then

- Josiah

Josiah Carlson, Apr 2, 2004
9. ### Nick Craig-WoodGuest

Erlend Andreas Garberg <> wrote:
> My problem is that when the number of nodes is higher than 8, the
> algorithm slows to a crawl (because of O(n!) complexity). I wonder if
> there is some way I can optimize my algorithm to make it run faster?
> Currently it takes 20 seconds to compute the best combination with 9
> nodes on my hardware.

I had to solve exactly this problem when I was at University (many
moons ago now ;-)

I used Simulated Annealing - have a search for the term and you'll see
plenty of references. Its good at finding a (local) minimum.

Just be glad you don't have to write it in Fortran like I did!

--
Nick Craig-Wood

Nick Craig-Wood, Apr 2, 2004
10. ### Erlend Andreas GarbergGuest

In article <c4ialj\$mcq\$>, Josiah Carlson wrote:
> One approximate solution to the TSP is the bitonic TSP. That is, start
> at the leftmost point, find a path to the rightmost point, then find a
> return path to the leftmost point.

The problem is that all nodes are connected to all the other nodes, and
the weights are in essence random.. So it won't be possible to find
leftmost/rightmost point.

--
mvh
Erlend Garberg

Erlend Andreas Garberg, Apr 2, 2004
11. ### Peter MaasGuest

Nick Craig-Wood wrote:
> I used Simulated Annealing - have a search for the term and you'll see
> plenty of references. Its good at finding a (local) minimum.

I used to think that Simulated Annealing avoids local traps and
is good at finding a global minimum, at least with a certain
probability that depends on some temperature function. Am I wrong?

Mit freundlichen Gruessen,

Peter Maas

--
-------------------------------------------------------------------
Peter Maas, M+R Infosysteme, D-52070 Aachen, Hubert-Wienen-Str. 24
Tel +49-241-93878-0 Fax +49-241-93878-20 eMail
-------------------------------------------------------------------

Peter Maas, Apr 2, 2004
12. ### Diez B. RoggischGuest

You could go for local search. First, create a randow tour. Then select a
neighborhood. Find the local minimum for that neighborhood. Do this as
often as you like.

A typical neighborhood for tsps are four nodes where two of them are
adjacent in your tour. Then exchange the nodes so that they still form a
tours. If that has less costs, keep it that way.

--n1--n2--
--n3--n4--

becomes

--n1\/n2--
--n3/\n4--

--
Regards,

Diez B. Roggisch

Diez B. Roggisch, Apr 2, 2004
13. ### Peter HansenGuest

Erlend Andreas Garberg wrote:

> In article <c4ho3l\$4he\$>, Josiah Carlson wrote:
>
>>Look at current TSP algorithms, and exchange their minimization rutines
>>for a maximization rutine. TSP is an NP-hard problem, which means that
>>there is no currently known algorithm for solving it in polynomial time.
>> You can approximate it or do a search on the solution space, but
>>solving it requires searching basically all of the solution space.

>
> An approximate solution would be good enough, do you have any
> suggestions about how do do that?

I haven't tried it for such a case, but have you considered a
genetic algorithm approach? Since you say an approximate solution
is good enough, I would think a GA could vastly shrink the search
space that has to be covered to get "close", assuming that data is
not such that hidden somewhere in it is a single link which has
an associated number that is vastly higher than the others. (That
would tend to make the GA search even worse than a brute force
approach.)

-Peter

Peter Hansen, Apr 2, 2004
14. ### Duncan SmithGuest

"Peter Maas" <> wrote in message
news:c4jikc\$eq4\$...
> Nick Craig-Wood wrote:
> > I used Simulated Annealing - have a search for the term and you'll see
> > plenty of references. Its good at finding a (local) minimum.

>
> I used to think that Simulated Annealing avoids local traps and
> is good at finding a global minimum, at least with a certain
> probability that depends on some temperature function. Am I wrong?
>
> Mit freundlichen Gruessen,
>
> Peter Maas

No, you're not. I think simulated annealing is a decent candidate for this
problem. The difficulty (in my experience) is in finding decent parameters
for the cooling schedule, so you can find good solutions in reasonable time.

Duncan

Duncan Smith, Apr 2, 2004
15. ### MitjaGuest

"Diez B. Roggisch" <> wrote in message
news:c4jk1t\$2k9keu\$-berlin.de...
> You could go for local search. First, create a randow tour. Then select a
> neighborhood. Find the local minimum for that neighborhood. Do this as
> often as you like.
>
> A typical neighborhood for tsps are four nodes where two of them are
> adjacent in your tour. Then exchange the nodes so that they still form a
> tours. If that has less costs, keep it that way.
>
> --n1--n2--
> --n3--n4--
>
> becomes
>
> --n1\/n2--
> --n3/\n4--
>

This is more or less just one of the things you'd do with simulated
annealing. And with such a "randomized" problem, this is certainly the one
and only way to go. If there are no rules defining the structure of the
graph, you can't write an optimized code which takes these rules into
account. Anyway, SA is what you want. Google for it, use it.

Mitja

Mitja, Apr 2, 2004
16. ### Richard BrodieGuest

"Duncan Smith" <> wrote in message
news:c4jp26\$jko\$...

> No, you're not. I think simulated annealing is a decent candidate for this
> problem. The difficulty (in my experience) is in finding decent parameters
> for the cooling schedule, so you can find good solutions in reasonable time.

The book, "Numerical Recipes" contains a description of simulating annealing,
giving the travelling salesman problem as an example. Extracts available online.

Richard Brodie, Apr 2, 2004
17. ### Nick Craig-WoodGuest

Peter Maas <> wrote:
> Nick Craig-Wood wrote:
> > I used Simulated Annealing - have a search for the term and you'll see
> > plenty of references. Its good at finding a (local) minimum.

>
> I used to think that Simulated Annealing avoids local traps and
> is good at finding a global minimum, at least with a certain
> probability that depends on some temperature function. Am I wrong?

You aren't wrong... It does avoid local traps - that is what the
simulated annealing bit is for - but it isn't guaranteed to find the
global minimum otherwise you'd have solved an NP-complete problem in
polynomial time...

In practice it works extrememly well!

--
Nick Craig-Wood

Nick Craig-Wood, Apr 2, 2004
18. ### Terry ReedyGuest

"Erlend Andreas Garberg" <> wrote in message
news:...
> Example:
> Nodes:
> A with numbers B->1200, C->2000
> B with numbers A->3000, C->4000
> C with numbers A->9000, B->5000
>
> The optimal ring is in this case can f.ex. be:
> A->1200->B->4000->C->9000->A with sum 14200.
>
> I have implemented this in python in the following way:
>
> hash is a dictionary with node-name as key and node-object as value.
> Each node-object has a dictionary speeds with node-name as key and a
> number as value. this dict stores the numbers associated with the other
> nodes.

If you number (0 -- n-1) rather than name the nodes, then you just need a
nodes array and a speed array for each node. That should make your code a
bit simpler and easier to play with. It should also be a bit faster, but a
good approximation algorithm will be **far** more important. There is at
least one book on the TSP.

Terry J. Reedy

Terry Reedy, Apr 2, 2004
19. ### David M. CookeGuest

At some point, Nick Craig-Wood <> wrote:

> Peter Maas <> wrote:
>> Nick Craig-Wood wrote:
>> > I used Simulated Annealing - have a search for the term and you'll see
>> > plenty of references. Its good at finding a (local) minimum.

>>
>> I used to think that Simulated Annealing avoids local traps and
>> is good at finding a global minimum, at least with a certain
>> probability that depends on some temperature function. Am I wrong?

>
> You aren't wrong... It does avoid local traps - that is what the
> simulated annealing bit is for - but it isn't guaranteed to find the
> global minimum otherwise you'd have solved an NP-complete problem in
> polynomial time...

With the right cooling schedule simulated annealing *is* guaranteed to
find the global minimum.

Mind you, that cooling schedule is very slow: the temperature of the
n'th step is T_n = T0/log(n). To get to 1% of your initial
temperature, you'll need about 1e10 steps... polynomial time it ain't.

Most SA cooling schedules you'll see use a quench (T_n = T0*a**n for
some a) or a Cauchy distribution (T_n = T0/n) which are faster, but
aren't guaranteed to give you a global minimum.

--
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke
|cookedm(at)physics(dot)mcmaster(dot)ca

David M. Cooke, Apr 2, 2004
20. ### Josiah CarlsonGuest

> The problem is that all nodes are connected to all the other nodes, and
> the weights are in essence random.. So it won't be possible to find
> leftmost/rightmost point.

Give them arbitrary x,y positions in 2D space. Whenever you see
something like |p1p2|, that is asking the distance between those two
vertices, and you can make that a lookup into your weight table or a
call to your weight function.

If you look at the algorithm, the only thing that sorting the points in
ascending order based on their x location is doing, is breaking up the
problem into the left to right to left. You can use whatever weights
you want, and because of the way the problem is constructed, you're
going to be checking all possible left to right to left paths on your
way, so you'll find the 'optimal' in your case, bitonic TSP.

- Josiah

Josiah Carlson, Apr 2, 2004

## Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.