I'm trying to solve the Travel Salesman problem for multigraph.

Namely, I have a fully-connected graph with 2 oriented edges between every pair of nodes. The weight of the edge from x to y corresponds to the distance from x to y, but dist(x, y) != dist(y, x).

The number of nodes is around 40. Every node should be visited.

To my best understanding, simulated annealing and its variations do not work with this type of graph.

I would like to find some ideas/methods how to approach my problem.

Thanks in advance :-)

  • $\begingroup$ I would try with linear programming, 40 nodes is not... excessive. $\endgroup$ Mar 16, 2022 at 13:45
  • $\begingroup$ Would you be better asking on a more programming-oriented site as this does not seem a very statistical problem? $\endgroup$
    – mdewey
    Mar 16, 2022 at 13:56
  • $\begingroup$ Agree that $40$ seems too large for simulation approach, too few of very many paths would be explored. $\endgroup$
    – BruceET
    Mar 16, 2022 at 14:07

1 Answer 1


I think this is the basic assymetric TSP. You can try the LKH-3 algorithm (http://webhotel4.ruc.dk/~keld/research/LKH-3/)

  • 2
    $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Mar 9, 2023 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.