0

Has anybody ever come across a solution for the ' multiple visit asymetric traveling sales man problem'?

The normal travelling salesman problem see (http://en.wikipedia.org/wiki/Travelling_salesman_problem) that the cost of getting from A->B is the same as getting from B-A, an asymetric version handles the case when the cost of from from A->B is different from B->A, but I have a problem where the best case of travel requires a trip via a repeated node.

Assuming a network of four nodes A,B,C,D, this can be expressed as a distance matrix of

{{0,7,99999,2},{4,0,2,3},{99999,2,0,,2},{1,3,2,0}}

The cost if going from A-B is 7 the cost of going from B->A is 4

The best solution would be 5 internet node jumps A->D D->C C->D ->D->B B-A The normal asymetric version would not make a return trip from C back to D

Any suggestions

Dave

Dave
  • 577
  • 6
  • 25
  • have you looked around in Programmers.stackexchange.com? Might be more suitable there. – jcollum Aug 06 '13 at 22:14
  • Might be a better match for math.stackexchange.com, I'm thinking. – Aaron Miller Aug 06 '13 at 22:21
  • possible duplicate of [Variation of TSP which visits multiple cities](http://stackoverflow.com/questions/1458048/variation-of-tsp-which-visits-multiple-cities) – Joel Aug 07 '13 at 18:49

1 Answers1

2

My guess is that you could use the asymmetric solution, but just keep the weights the same. By duplicating the nodes, you should be able to back up once. Of course that's no longer a Hamiltonian Cycle, which is why it's excluded from the common solutions.

Joel
  • 5,618
  • 1
  • 20
  • 19
  • Hi Joel, Are you suggesting that converting the problem to an asymmetric solution would work eg the wiki answer http://en.wikipedia.org/wiki/Travelling_salesman_problem#Solving_by_conversion_to_symmetric_TSP would resolve all issues? – Dave Aug 07 '13 at 06:30
  • If you fill out the other corners appropriately, you would have two trips around, and should be able to trim that to get a shorter cycle. – Joel Aug 07 '13 at 18:43
  • 1
    ALso, there's this: http://stackoverflow.com/questions/1458048/variation-of-tsp-which-visits-multiple-cities – Joel Aug 07 '13 at 18:47