Trouble finding shortest possible distance between all points

15 views (last 30 days)
Hi,
I'm trying to find the shortest possible distance between these points, with the red dot being the start and finishing point.
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
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

Sign in to comment.

Answers (0)

Products


Release

R2021b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!