Travelling salesman variation in python

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

  1. 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
    #1
    1. Advertising

  2. > 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
    #2
    1. Advertising

  3. 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
    #3
  4. Erlend Andreas Garberg

    Paul Rubin Guest

    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
    #4
  5. 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
    #5
  6. 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
    #6
  7. Erlend Andreas Garberg

    Jeff Epler Guest

    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
    #7
  8. > 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
    #8
  9. 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
    #9
  10. 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
    #10
  11. Erlend Andreas Garberg

    Peter Maas Guest

    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
    #11
  12. 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
    #12
  13. Erlend Andreas Garberg

    Peter Hansen Guest

    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
    #13
  14. Erlend Andreas Garberg

    Duncan Smith Guest

    "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
    #14
  15. Erlend Andreas Garberg

    Mitja Guest

    "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
    #15
  16. "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
    #16
  17. 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
    #17
  18. Erlend Andreas Garberg

    Terry Reedy Guest

    "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
    #18
  19. 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
    #19
  20. > 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
    #20
    1. Advertising

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.
Similar Threads
  1. Luc The Perverse
    Replies:
    12
    Views:
    1,341
    Roedy Green
    May 5, 2006
  2. KantKwitDansin1

    Traveling Salesman Problem

    KantKwitDansin1, Dec 11, 2004, in forum: C++
    Replies:
    9
    Views:
    5,571
    Surendra Singhi
    Dec 12, 2004
  3. Vinay Adella

    complexity of Traveling Salesman Problem?

    Vinay Adella, Sep 3, 2003, in forum: C Programming
    Replies:
    4
    Views:
    1,804
    Jack Klein
    Sep 4, 2003
  4. Travelling salesman problem in C

    , Sep 10, 2006, in forum: C Programming
    Replies:
    26
    Views:
    14,400
  5. Replies:
    5
    Views:
    999
    Jim Langston
    Sep 11, 2006
Loading...

Share This Page