{"id":3819,"date":"2018-09-17T12:00:29","date_gmt":"2018-09-17T17:00:29","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=3819"},"modified":"2018-09-16T17:39:38","modified_gmt":"2018-09-16T22:39:38","slug":"usa-traveling-salesman-tour","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2018\/09\/17\/usa-traveling-salesman-tour\/","title":{"rendered":"USA Traveling Salesman Tour"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Find the optimum traveling salesman tour through the capitals of the 48 contiguous states in the USA.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#453cc309-c8a4-403c-8e5f-49bdf5aa0903\">State Capitals<\/a><\/li><li><a href=\"#68a33b0b-0c47-4e26-8724-0ee2c07ff139\">Travel<\/a><\/li><li><a href=\"#551ad710-19c6-4e34-a371-2b6507b8bd88\">Traveler<\/a><\/li><li><a href=\"#1c6966ee-a2cf-4ae1-8a58-e7bda636eab2\">Distance Matrix<\/a><\/li><li><a href=\"#95984fcc-9063-47e7-9695-edc5a7b1e3d7\">Extrema<\/a><\/li><li><a href=\"#3e4bcd66-cd80-4fed-b75f-635632d20f6d\">Road Trip<\/a><\/li><li><a href=\"#0542486e-3f41-4954-aa82-d2fb977bbf36\">Highlight<\/a><\/li><li><a href=\"#dc923a21-8c79-4651-80ab-1fd42101ee5d\">Final Order<\/a><\/li><li><a href=\"#72ad05a3-536c-4e2a-b783-9abc60ee7a18\">Last Step<\/a><\/li><li><a href=\"#db9bce03-683c-4505-9639-2f82b0e59f55\">Optimum<\/a><\/li><li><a href=\"#15563bbb-ed8c-41d2-b37a-96da7e868449\">Animation<\/a><\/li><li><a href=\"#07277ea0-8ba3-469c-88ce-ef3337d31937\">Traveler_game<\/a><\/li><li><a href=\"#e35b50e7-6ae6-42f3-88cb-67cb83f1d1d2\">Codes<\/a><\/li><\/ul><\/div><h4>State Capitals<a name=\"453cc309-c8a4-403c-8e5f-49bdf5aa0903\"><\/a><\/h4><p>I am continuing with the workspace from <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2018\/09\/03\/graph-object-of-48-usa-states\">my previous blog post<\/a>.<\/p><p>John Burkardt provides a second data set, <a href=\"https:\/\/people.sc.fsu.edu\/~jburkardt\/datasets\/states\/state_capitals_ll.txt\">state_capitals_ll.txt<\/a>, giving the longitudes and latitudes of capitals of the 48 contiguous states. (Ignore AK, DC, HI, PR and US.)<\/p><pre class=\"codeinput\">    [lon,lat] = get_capital_coordinates;\r\n<\/pre><p>When I use these coordinates for the graph I created in my previous post, we get a more accurate picture of the USA.<\/p><pre class=\"codeinput\">    G = graph(A,cellstr(names));\r\n    plot(G,<span class=\"string\">'xdata'<\/span>,lon,<span class=\"string\">'ydata'<\/span>,lat);\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_2b_01.png\" alt=\"\"> <h4>Travel<a name=\"68a33b0b-0c47-4e26-8724-0ee2c07ff139\"><\/a><\/h4><p>The <a href=\"https:\/\/en.wikipedia.org\/wiki\/Travelling_salesman_problem\">travelling salesman problem<\/a>, the TSP, was mathematically formulated in the 19th century.  The problem is to find the closed circuit of a list of cities that travels the shortest total distance.<\/p><p>For 25 years MATLAB releases have included a simple demo program named <tt>travel<\/tt> that finds an approximate solution to the TSP through a few dozen randomly chosen points.  The background of the plot, an outline the USA, is just for artistic effect.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/travel.png\" alt=\"\"> <\/p><h4>Traveler<a name=\"551ad710-19c6-4e34-a371-2b6507b8bd88\"><\/a><\/h4><p>I've made the <tt>travel<\/tt> demo into a function named <tt>traveler<\/tt> whose input is the distance matrix <tt>D<\/tt>, the pairwise distances between the cities. The output is a path length <tt>miles<\/tt> and permutation vector <tt>p<\/tt> so that <tt>miles<\/tt> is the length of the route produced by <tt>lon(p)<\/tt> and <tt>lat(p)<\/tt>.<\/p><p>Each time it is called, <tt>travel<\/tt> starts with a random permutation of the cities.  Then, for several thousand iterations, it tries to reduce the length of the trip by revising the permutation in each of two simple ways. One scheme is to move one city to another position in the ordering. This example starts with the order <tt>[1:7]<\/tt>.  It then moves city <tt>4<\/tt> to follow city <tt>5<\/tt>, so the order becomes <tt>[1 2 3 5 4 6 7]<\/tt>. This reduces the length from <tt>9.71<\/tt> to <tt>7.24<\/tt>.<\/p><pre class=\"codeinput\">   half_fig\r\n   traveler_scheme1\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_2b_02.png\" alt=\"\"> <p>The second scheme is based on the observation that any time a route crosses itself, the length can be reduced by reversing the crossed segment. We don't actually look for crossings, we just try reversing random chunks of the ordering. This example reverses the <tt>[3 4 5]<\/tt> in <tt>[1:7]<\/tt> to get <tt>[1 2 5 4 3 6 7]<\/tt>, thereby reducing the length from <tt>9.47<\/tt> to <tt>7.65<\/tt>.<\/p><pre class=\"codeinput\">   traveler_scheme2\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_2b_03.png\" alt=\"\"> <p>These two heuristics are not powerful to guarantee that <tt>traveler<\/tt> will find the global shortest path.  It's easy to get stuck in local minima.  And the random path approach means that <tt>traveler<\/tt> is inefficient for more than a few dozen cities.<\/p><p>But nobody knows how to find a guaranteed shortest path for the TSP and the code for <tt>traveler<\/tt> is only 58 lines.  I will include the code at the end of this post and in <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a> on the MATLAB Central File Exchange.<\/p><pre class=\"codeinput\">    close\r\n<\/pre><h4>Distance Matrix<a name=\"1c6966ee-a2cf-4ae1-8a58-e7bda636eab2\"><\/a><\/h4><p>The input to <tt>traveler<\/tt> is the distance matrix.<\/p><pre class=\"codeinput\">    D = distances(lon,lat);\r\n<\/pre><p>The inputs to the function <tt>distances<\/tt> are the vectors <tt>lon<\/tt> and <tt>lat<\/tt>, the longitude and latitude of the cities. The output is the 48-by-48 matrix <tt>D<\/tt>, the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Great-circle_distance\">great circle distance<\/a> between pairs of cities. With some spherical trigonometry, <tt>lon<\/tt> and <tt>lat<\/tt>, which are essentially angles measured in degrees, are converted to miles, the lengths of \"as the crow flies\" geodesics on the surface of the earth. The radius of the earth is a scale factor. Here is the core of the function.<\/p><pre class=\"codeinput\">    dbtype <span class=\"string\">11:20<\/span> <span class=\"string\">distances.m<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\n11        R = 3959; % radius of the earth (mi.)\r\n12        n = length(lon);\r\n13        D = zeros(n,n);\r\n14        for k = 1:n\r\n15            for j = 1:k-1\r\n16                D(k,j) = R*acos(sind(lat(k))*sind(lat(j)) + ...\r\n17                    cosd(lat(k))*cosd(lat(j))*cosd(lon(k)-lon(j)));\r\n18                D(j,k) = D(k,j);\r\n19            end\r\n20        end\r\n<\/pre><h4>Extrema<a name=\"95984fcc-9063-47e7-9695-edc5a7b1e3d7\"><\/a><\/h4><p>Which two capitals are nearest each other?<\/p><pre class=\"codeinput\">    Dmin = min(min(D(D&gt;0)))\r\n    [k,j] = find(D == Dmin)\r\n    cities = names(k)\r\n<\/pre><pre class=\"codeoutput\">Dmin =\r\n   34.9187\r\nk =\r\n    37\r\n    19\r\nj =\r\n    19\r\n    37\r\ncities = \r\n  2&times;1 string array\r\n    \"RI\"\r\n    \"MA\"\r\n<\/pre><p>Providence, Rhode Island and Boston, Massachusetts (\"our fair city\") are less than 35 miles apart.<\/p><p>What about the other extreme?<\/p><pre class=\"codeinput\">    Dmax = max(max(D))\r\n    [k,j] = find(D == Dmax)\r\n    cities = names(k)\r\n<\/pre><pre class=\"codeoutput\">Dmax =\r\n   2.6629e+03\r\nk =\r\n    17\r\n     4\r\nj =\r\n     4\r\n    17\r\ncities = \r\n  2&times;1 string array\r\n    \"ME\"\r\n    \"CA\"\r\n<\/pre><p>As we might have expected, the capitals of Maine and California are the farthest apart, 2663 miles.  That would require one prodigious crow.<\/p><h4>Road Trip<a name=\"3e4bcd66-cd80-4fed-b75f-635632d20f6d\"><\/a><\/h4><p>Based on some experience that I will describe shortly, I am going to set the random number seed to <tt>347<\/tt> before we take our road trip with <tt>traveler<\/tt>.<\/p><pre class=\"codeinput\">    rng(347)\r\n    [miles,p] = traveler(D);\r\n    miles = round(miles)\r\n<\/pre><pre class=\"codeoutput\">miles =\r\n       10818\r\n<\/pre><p>That's an average of<\/p><pre class=\"codeinput\">    avg = miles\/48\r\n<\/pre><pre class=\"codeoutput\">avg =\r\n  225.3750\r\n<\/pre><p>miles per leg.<\/p><h4>Highlight<a name=\"0542486e-3f41-4954-aa82-d2fb977bbf36\"><\/a><\/h4><p>Let's highlight our graph of neighboring states with our traveling salesman path linking capital cities.<\/p><pre class=\"codeinput\">    Gp = plot(G,<span class=\"string\">'xdata'<\/span>,lon,<span class=\"string\">'ydata'<\/span>,lat,<span class=\"string\">'edgecolor'<\/span>,turquoise);\r\n    highlight(Gp,p,<span class=\"string\">'edgecolor'<\/span>,darkred,<span class=\"string\">'linewidth'<\/span>,2)\r\n    title(miles)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_2b_04.png\" alt=\"\"> <p>There are four missing links.  The path goes from UT to MT, but those states are not neighbors.  We must go through ID.  And the leg from FL to SC goes through GA.  There are two more in the northeast. Fill in those missing links with dashed lines.<\/p><pre class=\"codeinput\">    missing_links(A,lon,lat,p,darkred)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_2b_05.png\" alt=\"\"> <p>Zoom in on the northeast.<\/p><pre class=\"codeinput\">    axis([-84 -68 33 46])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_2b_06.png\" alt=\"\"> <h4>Final Order<a name=\"dc923a21-8c79-4651-80ab-1fd42101ee5d\"><\/a><\/h4><p>Here the state abbreviations, ordered by this path.<\/p><pre class=\"codeinput\">    fprintf(fmt,names(p))\r\n<\/pre><pre class=\"codeoutput\">LA TX OK NM AZ NV CA OR WA ID MT UT CO WY SD ND \r\nMN WI MI OH WV PA NY VT ME NH MA RI CT NJ DE MD \r\nVA NC SC FL AL GA TN KY IN IL IA NE KS MO AR MS \r\nLA <\/pre><h4>Last Step<a name=\"72ad05a3-536c-4e2a-b783-9abc60ee7a18\"><\/a><\/h4><p>It is interesting to look at the last step.  After 3298 iterations, <tt>travel<\/tt> arrives at this situation with a path length of 10952.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/penultimate_b.png\" alt=\"\"> <\/p><p>The link connecting WV to VA crosses the link connecting NC to PA. It takes <tt>travel<\/tt> 222 more iterations, but eventually a permutation that reverses the path from VA and PA is tried.  This connects WV to PA and NC to VA to produce the path shown in the previous plot. The total path length is decreased by 134 miles to 10818.<\/p><h4>Optimum<a name=\"db9bce03-683c-4505-9639-2f82b0e59f55\"><\/a><\/h4><p>I am confident that we have found the shortest path, but I don't have a proof.<\/p><p>I ran 1000 different initializations of <tt>rng<\/tt>. Eight runs produced the path with length 10818 that we found with <tt>rng(347)<\/tt>. None of the runs found a shorter path. Sixteen more runs found a quite different path with length 10821, only three miles longer.  Here is this next best path.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/nextbest_b.png\" alt=\"\"> <\/p><h4>Animation<a name=\"15563bbb-ed8c-41d2-b37a-96da7e868449\"><\/a><\/h4><p>I must include an animated gif here.  This initially shows every sixth step. It switches to every step when the path length is less than 12000.  Few legs in random paths match edges in the neighbor graph so initially most lines are dashed. As we near the minimum, more solid lines appear.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/travels.gif\" alt=\"\"> <\/p><h4>Traveler_game<a name=\"07277ea0-8ba3-469c-88ce-ef3337d31937\"><\/a><\/h4><p>Chances that, without help, <tt>traveler<\/tt> will find the shortest route through the 48 capital cities are less than 1 in 100.  Here is your opportunity to help guide the search.  The <tt>traveler_game<\/tt> is a modification of <tt>travel<\/tt> that plots every successful step and that provides controls so that you to back up a few steps and try the random strategy again.<\/p><p>I will include the <tt>traveler_game<\/tt> in the next update, version 3.70, of <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a> on the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">MATLAB Central File Excange<\/a>.  That may take a few days.<\/p><p>There are five push buttons.<\/p><div><ul><li>&gt;   Take one minimization step.<\/li><li>&gt;&gt;  Take repeated steps, until a local minimum is reached.<\/li><li>&lt;   Reverse one step.<\/li><li>&lt;&lt;  Reverse many steps.<\/li><li>^   Start over in a new figure window.<\/li><\/ul><\/div><p>Here are four typical runs.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/four.png\" alt=\"\"> <\/p><h4>Codes<a name=\"e35b50e7-6ae6-42f3-88cb-67cb83f1d1d2\"><\/a><\/h4><p>Here are the codes for <tt>traveler<\/tt>, <tt>distances<\/tt>, and <tt>path_length<\/tt>.<\/p><pre class=\"codeinput\">    type <span class=\"string\">traveler<\/span>\r\n    type <span class=\"string\">distances<\/span>\r\n    type <span class=\"string\">path_length<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction [len,p] = traveler(D)\r\n%TRAVELER  Functional form of old MATLAB demo, \"travel\".\r\n%   A pretty good, but certainly not the best, solution of the\r\n%   Traveling Salesman problem.  Form a closed circuit of a\r\n%   number of cities that travels the shortest total distance.\r\n%\r\n%   [len,p] = traveler(D).\r\n%   Input: D = distances between cities with coordinates x and y.\r\n%   Output: p a permutation, x(p) and y(p) is a path with length len.\r\n\r\n%   Copyright 1984-2018 The MathWorks, Inc.\r\n\r\n    n = size(D,1);\r\n    p = randperm(n);\r\n    len = path_length(p,D);\r\n\r\n    for iter = 1:10000\r\n\r\n        % Try to reverse a portion.\r\n\r\n        pt1 = floor(n*rand)+1;\r\n        pt2 = floor(n*rand)+1;\r\n\r\n        lo = min(pt1,pt2);\r\n        hi = max(pt1,pt2);\r\n\r\n        q = 1:n;\r\n        q(lo:hi) = q(hi:-1:lo);\r\n        pnew = p(q);\r\n\r\n        lennew = path_length(pnew,D);\r\n        if lennew &lt; len\r\n            p = pnew;\r\n            len = lennew;\r\n            iterp = iter;\r\n        end\r\n\r\n        % Try a single point insertion\r\n\r\n        pt1 = floor(n*rand)+1;\r\n        pt2 = floor((n-1)*rand)+1;\r\n\r\n        q = 1:n;\r\n        q(pt1) = [];\r\n        q = [q(1:pt2) pt1 q((pt2+1):(n-1))];\r\n        pnew = p(q);\r\n\r\n        lennew = path_length(pnew,D);\r\n        if lennew &lt; len\r\n            p = pnew;\r\n            len = lennew;\r\n            iterp = iter;\r\n        end\r\n    end\r\n\r\n    % Close the permutation.\r\n    p(end+1) = p(1);\r\nend\r\n\r\nfunction D = distances(lon,lat)\r\n%   D = distances(lon,lay)\r\n%   Input: vectors lon and lat, the longitude and latitude of the cities.\r\n%   Output: D(k,j) is the distance (in miles) between cities k and j.\r\n\r\n%   Copyright 1984-2018 The MathWorks, Inc.\r\n     \r\n    % Great circle distance matrix between pairs of cities.\r\n    % https:\/\/en.wikipedia.org\/wiki\/Great-circle_distance.\r\n    \r\n    R = 3959; % radius of the earth (mi.)\r\n    n = length(lon);\r\n    D = zeros(n,n);\r\n    for k = 1:n\r\n        for j = 1:k-1\r\n            D(k,j) = R*acos(sind(lat(k))*sind(lat(j)) + ...\r\n                cosd(lat(k))*cosd(lat(j))*cosd(lon(k)-lon(j)));\r\n            D(j,k) = D(k,j);\r\n        end\r\n    end\r\nend\r\n\r\nfunction len = path_length(p,D)\r\n% len = path_length(p,D)\r\n\r\n    % Calculate current path length for traveling salesman problem.\r\n    % This function calculates the total length of the current path\r\n    % p in the traveling salesman problem.\r\n    %\r\n    % This is a vectorized distance calculation.\r\n    %\r\n    % Create two vectors: p and q = p([n 1:(n-1)]).\r\n    % The first is the list of first cities in any leg, and the second\r\n    % is the list of destination cities for that same leg.\r\n    % (the second vector is an element-shift-right version of the first)\r\n    %\r\n    % Use column indexing into D to create a vector of\r\n    % lengths of each leg which can then be summed.\r\n    \r\n    n = length(p);\r\n    q = p([n 1:(n-1)]);\r\n    len = sum(D(q + (p-1)*n));\r\n    \r\nend\r\n<\/pre><script language=\"JavaScript\"> <!-- \r\n    function grabCode_ea53d69dfa3f427a8715b9c56614d99c() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='ea53d69dfa3f427a8715b9c56614d99c ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' ea53d69dfa3f427a8715b9c56614d99c';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2018 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_ea53d69dfa3f427a8715b9c56614d99c()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2018a<br><\/p><\/div><!--\r\nea53d69dfa3f427a8715b9c56614d99c ##### SOURCE BEGIN #####\r\n%% USA Traveling Salesman Tour\r\n% Find the optimum traveling salesman tour\r\n% through the capitals of the 48 contiguous states in the USA.\r\n\r\n%% State Capitals\r\n% I am continuing with the workspace from\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2018\/09\/03\/graph-object-of-48-usa-states\r\n% my previous blog post>.\r\n\r\n%%\r\n% John Burkardt provides a second data set,\r\n% <https:\/\/people.sc.fsu.edu\/~jburkardt\/datasets\/states\/state_capitals_ll.txt\r\n% state_capitals_ll.txt>,\r\n% giving the longitudes and latitudes of capitals of the 48 contiguous\r\n% states.\r\n% (Ignore AK, DC, HI, PR and US.)\r\n\r\n    [lon,lat] = get_capital_coordinates;\r\n    \r\n%%\r\n% When I use these coordinates for the graph I created in my\r\n% previous post, we get a more accurate picture of the USA.\r\n\r\n    G = graph(A,cellstr(names));\r\n    plot(G,'xdata',lon,'ydata',lat);\r\n\r\n%% Travel\r\n% The <https:\/\/en.wikipedia.org\/wiki\/Travelling_salesman_problem\r\n% travelling salesman problem>, the TSP, was mathematically formulated\r\n% in the 19th century.  The problem is to find the closed circuit of\r\n% a list of cities that travels the shortest total distance.\r\n%\r\n% For 25 years MATLAB releases have included a simple demo program named\r\n% |travel| that finds an approximate solution to the TSP through a\r\n% few dozen randomly chosen points.  The background of the plot,\r\n% an outline the USA, is just for artistic effect.\r\n%\r\n% <<travel.png>>\r\n\r\n%% Traveler\r\n% I've made the |travel| demo into a function named |traveler| whose \r\n% input is the distance matrix |D|, the pairwise distances between\r\n% the cities.\r\n% The output is a path length |miles| and permutation vector |p| so that \r\n% |miles| is the length of the route produced by |lon(p)| and |lat(p)|.\r\n%\r\n% Each time it is called,\r\n% |travel| starts with a random permutation of the cities.  Then,\r\n% for several thousand iterations, it tries to reduce the length\r\n% of the trip by revising the permutation in each of two simple ways.\r\n% One scheme is to move one city to another position in the ordering.\r\n% This example starts with the order |[1:7]|.  It then moves city |4|\r\n% to follow city |5|, so the order becomes |[1 2 3 5 4 6 7]|.\r\n% This reduces the length from |9.71| to |7.24|.\r\n\r\n   half_fig\r\n   traveler_scheme1\r\n   \r\n%%\r\n% The second scheme is based on the observation that any time\r\n% a route crosses itself, the length can be reduced by reversing\r\n% the crossed segment. We don't actually look for crossings,\r\n% we just try reversing random chunks of the ordering.\r\n% This example reverses the |[3 4 5]| in |[1:7]| to get |[1 2 5 4 3 6 7]|,\r\n% thereby reducing the length from |9.47| to |7.65|.\r\n\r\n   traveler_scheme2\r\n   \r\n%%\r\n% These two heuristics are not powerful to guarantee that |traveler|\r\n% will find the global shortest path.  It's easy to get stuck in\r\n% local minima.  And the random path approach means that |traveler|\r\n% is inefficient for more than a few dozen cities.\r\n\r\n%%\r\n% But nobody knows how to find a guaranteed shortest path for the TSP\r\n% and the code for |traveler| is only 58 lines.  I will include the code\r\n% at the end of this post and in\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% Cleve's Laboratory> on the MATLAB Central File Exchange.\r\n%%\r\n    close\r\n\r\n%% Distance Matrix\r\n% The input to |traveler| is the distance matrix.\r\n\r\n    D = distances(lon,lat);\r\n\r\n%%\r\n% The inputs to the function |distances| are the vectors\r\n% |lon| and |lat|, the longitude and latitude of the cities.\r\n% The output is the 48-by-48 matrix |D|, the\r\n% <https:\/\/en.wikipedia.org\/wiki\/Great-circle_distance\r\n% great circle distance> between pairs of cities.\r\n% With some spherical trigonometry, |lon| and |lat|,\r\n% which are essentially angles measured in degrees, are converted \r\n% to miles, the lengths of \"as the crow flies\" geodesics on the\r\n% surface of the earth. \r\n% The radius of the earth is a scale factor.\r\n% Here is the core of the function.\r\n\r\n    dbtype 11:20 distances.m    \r\n\r\n%% Extrema\r\n% Which two capitals are nearest each other?\r\n\r\n    Dmin = min(min(D(D>0)))\r\n    [k,j] = find(D == Dmin)\r\n    cities = names(k)\r\n    \r\n%%\r\n% Providence, Rhode Island and Boston, Massachusetts (\"our fair city\")\r\n% are less than 35 miles apart.\r\n%\r\n% What about the other extreme?\r\n    \r\n    Dmax = max(max(D))\r\n    [k,j] = find(D == Dmax)\r\n    cities = names(k)\r\n    \r\n%%\r\n% As we might have expected, the capitals of Maine and California\r\n% are the farthest apart, 2663 miles.  That would require\r\n% one prodigious crow.\r\n\r\n%% Road Trip\r\n% Based on some experience that I will describe shortly,\r\n% I am going to set the random number seed to |347| before\r\n% we take our road trip with |traveler|.\r\n\r\n    rng(347)\r\n    [miles,p] = traveler(D);\r\n    miles = round(miles)\r\n\r\n%%\r\n% That's an average of\r\n\r\n    avg = miles\/48\r\n    \r\n%%\r\n% miles per leg.\r\n\r\n%% Highlight\r\n% Let's highlight our graph of neighboring states with our traveling\r\n% salesman path linking capital cities.\r\n\r\n    Gp = plot(G,'xdata',lon,'ydata',lat,'edgecolor',turquoise);    \r\n    highlight(Gp,p,'edgecolor',darkred,'linewidth',2)\r\n    title(miles)\r\n\r\n%%\r\n% There are four missing links.  The path goes from UT to MT, but those\r\n% states are not neighbors.  We must go through ID.  And the leg from\r\n% FL to SC goes through GA.  There are two more in the northeast.\r\n% Fill in those missing links with dashed lines.\r\n\r\n    missing_links(A,lon,lat,p,darkred)\r\n    \r\n%%\r\n% Zoom in on the northeast.\r\n \r\n    axis([-84 -68 33 46])\r\n\r\n%% Final Order\r\n% Here the state abbreviations, ordered by this path.\r\n\r\n    fprintf(fmt,names(p))\r\n    \r\n%% Last Step\r\n% It is interesting to look at the last step.  After 3298 iterations,\r\n% |travel| arrives at this situation with a path length of 10952.\r\n%\r\n% <<penultimate_b.png>>\r\n%\r\n% The link connecting WV to VA crosses the link connecting NC to PA.\r\n% It takes |travel| 222 more iterations, but eventually a permutation\r\n% that reverses the path from VA and PA is tried.  This connects\r\n% WV to PA and NC to VA to produce the path shown in the previous plot.\r\n% The total path length is decreased by 134 miles to 10818.\r\n\r\n%% Optimum\r\n% I am confident that we have found the shortest path, but I don't\r\n% have a proof.\r\n%\r\n% I ran 1000 different initializations of |rng|. Eight runs produced\r\n% the path with length 10818 that we found with |rng(347)|.\r\n% None of the runs found a shorter path.\r\n% Sixteen more runs found a quite different path with length 10821,\r\n% only three miles longer.  Here is this next best path.\r\n%\r\n% <<nextbest_b.png>>\r\n%\r\n\r\n%% Animation\r\n% I must include an animated gif here.  This initially shows every\r\n% sixth step. It switches to every step when the path length is\r\n% less than 12000.  Few legs in random paths match edges\r\n% in the neighbor graph so initially most lines are dashed.\r\n% As we near the minimum, more solid lines appear.\r\n%\r\n% <<travels.gif>>\r\n%\r\n\r\n%% Traveler_game \r\n% Chances that, without help, |traveler| will find the shortest route\r\n% through the 48 capital cities are less than 1 in 100.  Here is your\r\n% opportunity to help guide the search.  The |traveler_game| is a \r\n% modification of |travel| that plots every successful step and that\r\n% provides controls so that you to back up a few steps and try the random\r\n% strategy again.\r\n\r\n%%\r\n% I will include the |traveler_game| in the next update, version 3.70, of\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% Cleve's Laboratory> on the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% MATLAB Central File Excange>.  That may take a few days.\r\n\r\n%%\r\n% There are five push buttons.\r\n%\r\n% * >   Take one minimization step.\r\n% * >>  Take repeated steps, until a local minimum is reached.\r\n% * <   Reverse one step.\r\n% * <<  Reverse many steps.\r\n% * ^   Start over in a new figure window.\r\n\r\n%%\r\n% Here are four typical runs.\r\n%\r\n% <<four.png>>\r\n\r\n%% Codes\r\n% Here are the codes for |traveler|, |distances|, and |path_length|.\r\n\r\n    type traveler\r\n    type distances\r\n    type path_length\r\n##### SOURCE END ##### ea53d69dfa3f427a8715b9c56614d99c\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/traveler_thumb.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p>Find the optimum traveling salesman tour through the capitals of the 48 contiguous states in the USA.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2018\/09\/17\/usa-traveling-salesman-tour\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":3871,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[11,5,4,26],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3819"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=3819"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3819\/revisions"}],"predecessor-version":[{"id":3867,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3819\/revisions\/3867"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/3871"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=3819"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=3819"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=3819"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}