Trouble finding shortest possible distance between all points
13 views (last 30 days)
Show older comments
Hi,
I'm trying to find the shortest possible distance between these points, with the red dot being the start and finishing point.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1026305/image.png)
I have two 14x1 arrays with each point's x and y position, and I already have a function to tell me how long a path of the points ordered in a certain way is, but I'm wondering if there's any way to automatically find the shortest possible distance?
Here's my code for context:
[location_data, location_names] = xlsread('exposure_sites.xlsx') ;
latitude_dms = location_data(:, 1:3);
longitude_dms = location_data(:, 4:6);
latitude_degrees = dms2degrees(latitude_dms) ;
longitude_degrees = dms2degrees(longitude_dms) ;
exposure_origin = [mean(latitude_degrees), mean(longitude_degrees)] ;
origin_x = exposure_origin(1,2) ;
origin_y = exposure_origin(1,1) ;
km_per_degree_latitude = 2 .* pi .* 6373.6 / 360 ;
km_per_degree_longitude = km_per_degree_latitude * cos((-27.4743) .* (pi/180)) ;
exposure_x = longitude_degrees * km_per_degree_longitude ;
exposure_y = latitude_degrees * km_per_degree_latitude ;
figure
plot(exposure_x, exposure_y, '.', MarkerSize = 15)
grid on
axis equal
xlabel('x-coordinates'), ylabel('y-coordinates'), title('Coronavirus Variant Exposure Sites')
text(exposure_x, exposure_y, location_names, 'VerticalAlignment', 'bottom')
box off
c = convhull(exposure_x, exposure_y)' ;
first_trip = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 1] ;
computeTripDistance([exposure_x exposure_y], first_trip) ;
axis([1.5095*10^4, 1.512*10^4, -3066, -3045])
trip_3 = ([1 4 8 10 5 3 7 2 13 11 9 14 12 6 1]) ;
computeTripDistance([exposure_x exposure_y], trip_3) ;
axis([1.5095*10^4, 1.512*10^4, -3066, -3045])
As you can see, I've gotten one that works pretty well but I'm wondering if anyone can get it lower? Sorry if this turned out to be more of a maths thing than a coding thing, I just wanted to give as much context as possible.
2 Comments
jessupj
on 9 Jun 2022
"I'm wondering if there's any way to automatically find the shortest possible distance."
This is a well known problem that's worth reading up on. https://en.wikipedia.org/wiki/Travelling_salesman_problem
Mathieu NOE
on 9 Jun 2022
Edited: Mathieu NOE
on 9 Jun 2022
yeap
there is already matlab ressources for the Travelling Salesman Problem (TSP)
and probably many more if you spend some time on the FileExchange section
Answers (0)
See Also
Categories
Find more on Traveling Salesman (TSP) in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!