Finding Shortest Path through whole points without revisiting

Hi all,

I have a problem and I need urgent help. I have more than 30 points (2D cartesian coordinate) with known x and y coordinates. All points can be distributed randomly or on a regular basis such as star shape or cross shape. I would like to asing a one way path which connects all points without circling or revisiting them. How can I implement this question? I would like to visit each point only once and complete the whole journey as quick as possible.

Thanks in advance.

Answer 1

[Bruno Luong]

You can look at TMW tuto on Traveling Salesman Prroblem

https://uk.mathworks.com/help/optim/ug/travelling-salesman-problem.html

or file exchanges of this author

https://uk.mathworks.com/matlabcentral/fileexchange/?q=profileid:397959

[Walter Roberson]

Note that the request is for a Hamiltonian Path not Travelling Salesman. Travelling Salesman can revisit a point.

[Bruno Luong]

They are equivalent https://en.wikipedia.org/wiki/Travelling_salesman_problem Related problems

"An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight."

Answer 2

[Walter Roberson]

this problem is known as the Hamiltonian Path

https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph-source-destination

[Ömer Yaman]

Thank you but I am new at that kind of structures. I could not understand well.

Let's say my points as (x,y)

(1,-1), (0,3), (-1,2), (0,2), (1,1), (1,0), (1,3), (1,5), (2,1), (3,1), (-2,1), (0,0), (-1,0), (3,4), (2,3), (4,1), (2,-1)

I need to find the shortest path covers all those points. It should not visit same point twice (like circles or backlines). It may start from any of them (which is optimum)

I have found something known as Minimal Nearest-Neighbor Closed Contour but in this contour it creates loops on some points. I hope I explained my question clearly.

Answer 3

[Ömer Yaman]

Thank you for your helps. I have found this code and helped me to solve my issue.

https://www.mathworks.com/matlabcentral/fileexchange/13680-traveling-salesman-problem-genetic-algorithm