https://optimization.cbe.cornell.edu/index.php?title=Traveling_salesman_problem&feed=atom&action=historyTraveling salesman problem - Revision history2024-03-29T09:07:52ZRevision history for this page on the wikiMediaWiki 1.40.1https://optimization.cbe.cornell.edu/index.php?title=Traveling_salesman_problem&diff=88&oldid=prevYoufengqi at 02:47, 26 September 20202020-09-26T02:47:11Z<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:47, 25 September 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l86">Line 86:</td>
<td colspan="2" class="diff-lineno">Line 86:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>; Go-to constraints</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>; Go-to constraints</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: After visiting a city <math>i</math>, the salesman must visit only one city next:</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: After visiting a city <math>i</math>, the salesman must visit only one city next:</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>: <math>\sum_j y_{ij} = 1, ~~ i = 0, 1, ..., n-1</math></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>\sum_j y_{ij} = 1, ~~<ins style="font-weight: bold; text-decoration: none;">\forall </ins>i = 0, 1, ..., n-1</math></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>; Come-from constraints</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>; Come-from constraints</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: When visiting a city, the salesman must have come from only one city:</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: When visiting a city, the salesman must have come from only one city:</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>: <math>\sum_i y_{ij} = 1, ~~ j = 0, 1, ..., n-1</math></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>\sum_i y_{ij} = 1, ~~ <ins style="font-weight: bold; text-decoration: none;">\forall </ins>j = 0, 1, ..., n-1</math></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>; Subtour elimination </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>; Subtour elimination </div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: Ensure that a tour is fully connected, i.e. no subtours</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: Ensure that a tour is fully connected, i.e. no subtours</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>: <math>\sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 2 \le |S| \le n - 2</math></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>\sum_i \sum_j y_{ij} \le |S| - 1<ins style="font-weight: bold; text-decoration: none;">, </ins>~~ <ins style="font-weight: bold; text-decoration: none;">\forall </ins>S \subset V, 2 \le |S| \le n - 2</math></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: where <math>S</math> is the set of all tours of <math>G</math></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: where <math>S</math> is the set of all tours of <math>G</math></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
</table>Youfengqihttps://optimization.cbe.cornell.edu/index.php?title=Traveling_salesman_problem&diff=84&oldid=prevYoufengqi at 01:27, 26 September 20202020-09-26T01:27:23Z<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:27, 25 September 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l107">Line 107:</td>
<td colspan="2" class="diff-lineno">Line 107:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>& ~~ \sum_i y_{ij} = 1, ~~ j = 0, 1, ..., n-1 \\ </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>& ~~ \sum_i y_{ij} = 1, ~~ j = 0, 1, ..., n-1 \\ </div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>& ~~ \sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 2 \le |S| \le n - 2 \\</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>& ~~ \sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 2 \le |S| \le n - 2 \\</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>& ~~ y_{ij} \in \{0,1\} ~ \forall i,j \in E \\</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>& ~~ y_{ij} \in \{0,1\}<ins style="font-weight: bold; text-decoration: none;">, </ins>~ \forall i,j \in E \\</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\end{align}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\end{align}</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></math></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></math></div></td></tr>
</table>Youfengqihttps://optimization.cbe.cornell.edu/index.php?title=Traveling_salesman_problem&diff=83&oldid=prev68.175.150.241: /* Example */2020-09-26T01:00:24Z<p><span dir="auto"><span class="autocomment">Example</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:00, 25 September 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l413">Line 413:</td>
<td colspan="2" class="diff-lineno">Line 413:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2" class="diff-side-added"></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"><math>\max xx^2</del></div></td><td colspan="2" class="diff-side-added"></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">s.t. dy/dx = {\partial^2\over\partial x_1\partial x_2}y</math></del></div></td><td colspan="2" class="diff-side-added"></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== References ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== References ==</div></td></tr>
</table>68.175.150.241https://optimization.cbe.cornell.edu/index.php?title=Traveling_salesman_problem&diff=82&oldid=prev68.175.150.241 at 00:58, 26 September 20202020-09-26T00:58:42Z<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:58, 25 September 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l413">Line 413:</td>
<td colspan="2" class="diff-lineno">Line 413:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>\max xx^2</ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">s.t. dy/dx = {\partial^2\over\partial x_1\partial x_2}y</math></ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== References ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== References ==</div></td></tr>
</table>68.175.150.241https://optimization.cbe.cornell.edu/index.php?title=Traveling_salesman_problem&diff=69&oldid=prevWc593: Created page with "This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems Author: Jessica Yu (ChE 345 Spring 2014) Steward: Dajun..."2020-09-08T20:24:16Z<p>Created page with "This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems Author: Jessica Yu (ChE 345 Spring 2014) Steward: Dajun..."</p>
<p><b>New page</b></p><div>This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems<br />
<br />
Author: Jessica Yu (ChE 345 Spring 2014)<br />
<br />
Steward: Dajun Yue, Fengqi You<br />
<br />
The traveling salesman problem (TSP) is a widely studied combinatorial optimization problem, which, given a set of cities and a cost to travel from one city to another, seeks to identify the tour that will allow a salesman to visit each city only once, starting and ending in the same city, at the minimum cost.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1</span><br />
<br />
== History ==<br />
<br />
[[File:48StatesTSP.png|frame|Solution to 48 States Traveling Salesman Problem]]<br />
<br />
The origins of the traveling salesman problem are obscure; it is mentioned in an 1832 manual for traveling salesman, which included example tours of 45 German cities but gave no mathematical consideration.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> W. R. Hamilton and Thomas Kirkman devised mathematical formulations of the problem in the 1800s.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span><br />
<br />
It is believed that the general form was first studied by Karl Menger in Vienna and Harvard in the 1930s.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2,3</span><br />
<br />
Hassler Whitney, who was working on his Ph.D. research at Harvard when Menger was a visiting lecturer, is believed to have posed the problem of finding the shortest route between the 48 states of the United States during either his 1931-1932 or 1934 seminar talks.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> There is also uncertainty surrounding the individual who coined the name “traveling salesman problem” for Whitney’s problem.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span><br />
<br />
The problem became increasingly popular in the 1950s and 1960s. Notably, George Dantzig, Delber R. Fulkerson, and Selmer M. Johnson at the RAND Corporation in Santa Monica, California solved the 48 state problem by formulating it as a linear programming problem.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> The methods described in the paper set the foundation for future work in combinatorial optimization, especially highlighting the importance of cutting planes.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2,4</span><br />
<br />
In the early 1970s, the concept of P vs. NP problems created buzz in the theoretical computer science community. In 1972, Richard Karp demonstrated that the Hamiltonian cycle problem was NP-complete, implying that the traveling salesman problem was NP-hard.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">4</span><br />
<br />
Increasingly sophisticated codes led to rapid increases in the sizes of the traveling salesman problems solved. Dantzig, Fulkerson, and Johnson had solved a 48 city instance of the problem in 1954.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5</span> Martin Grötechel more than doubled this 23 years later, solving a 120 city instance in 1977.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5</span> Enoch Crowder and Manfred W. Padberg again more than doubled this in just 3 years, with a 318 city solution.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5</span> <br />
<br />
In 1987, rapid improvements were made, culminating in a 2,392 city solution by Padberg and Giovanni Rinaldi. In the following two decades, David L. Appelgate, Robert E. Bixby, Vasek Chvátal, & William J. Cook led the cutting edge, solving a 7,397 city instance in 1994 up to the current largest solved problem of 24,978 cities in 2004.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5</span><br />
<br />
== Description ==<br />
<br />
=== Graph Theory ===<br />
<br />
Let <math>G = (V, E)</math> be a directed or undirected graph with set of vertices <math>V</math> and set of edges <math>E = \{(x,y) | x, y \in V\}</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3,6</span> Each edge <math>e \in E</math> is assigned a cost <math>c_e</math>. Let <math>\mathbb{H}</math> be the set of all Hamiltonian cycles, a cycle that visits each vertex exactly once, in <math>G</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> The traveling salesman problem is to find the tour <math>h \in \mathbb{H}</math> such that the sum of the costs <math>c_e</math> in the tour is minimized.<br />
<br />
Suppose graph <math>G</math> is a complete graph, where every pair of distinct vertices is connected by a unique edge.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> Let the set of vertices be <math>V = \{v_1, v_2, ..., v_n\}</math>. The cost matrix is given by <math> C = (c_{ij})_{n \times n}</math> where the cost of the edge joining node <math>v_i</math> to node <math>v_j</math>, denoted <math>c_{ij}</math>, is given in entry <math>(i,j)</math>.<br />
<br />
In the context of the traveling salesman problem, the verticies correspond to cities and the edges correspond to the path between those cities. When modeled as a complete graph, paths that do not exist between cities can be modeled as edges of very large cost without loss of generality.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> Minimizing the sum of the costs for Hamiltonian cycle is equivalent to identifying the shortest path in which each city is visiting only once.<br />
<br />
=== Classifications of the TSP ===<br />
<br />
The TRP can be divided into two classes depending on the nature of the cost matrix.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3,6</span> <br />
<br />
* Symmetric traveling salesman problem (sTSP) - <math>C</math> is symmetric (<math>\forall ~ i, j: c_{ij} = c_{ji} </math>)<br />
** <math>G</math> is undirected <br />
** Applies when the distance between cities is the same in both directions<br />
* Asymmetric traveling salesman problem (aTSP) - <math>C</math> is asymmetric (<math>\exists ~ i, j: c_{ij} \neq c_{ji} </math>)<br />
** <math>G</math> is directed<br />
** Applies when there are differences in distances (e.g. one-way streets)<br />
<br />
An ATSP can be formulated as an STSP by doubling the number of nodes.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span><br />
<br />
=== Variations of the TSP ===<br />
<br />
; MAX TSP<br />
: Rather than minimizing the tour cost, the MAX TSP seeks to identify a tour in which the total cost of edges is maximimum.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> The MAX TSP can be refomulated as a TSP by replacing each edge cost with its addivitive inverse.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span><br />
; Bottleneck TSP<br />
: Objective is to locate a tour with the minimum cost for the edge with the largest cost, which can be reformulated as a TSP with exponentially large edge costs.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span><br />
; TSP with mutiple visits (TSPM)<br />
: A relaxation of the TSP problem, the TSPM attempts to route a salesman such that each node is visited at least once and the total travel distance is minimized.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> Reformulations into a TSP involves replacing edge costs with the shortest path distance.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span><br />
; Messenger problem<br />
: Also known as the wandering salesman problem, this problem seeeks to find the Hamiltonian path of least cost from specified node <math>u</math> to node <math>v</math> in <math>G</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> The TSP reformulations incorporates a large negative cost for the edge <math>(v, u)</math>. <br />
; Clustered TSP<br />
: The set of vertices <math>V</math> in <math>G</math> are parititioned into clusters <math>V_1, V_2, ..., V_k</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> The objective is to identify the least cost tour such that cities within the same cluster must all be visited before moving to the next cluster.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> This can be reformualted by adding a large cost to each edge between clusters.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span><br />
; Generalized TSP (GTSP)<br />
: Given a set of clusters <math>V_1, V_2, ..., V_k</math>, the GTSP seeks to find the shortest cycle that passes through exactly one node in each cluster <math>V_i</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> The GTSP reduces to a TSP if <math>|V_i| = 1 ~\forall~ i</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span> The GTSP can be solved as a TSP by modifying the cost matrix.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span><br />
; <math>m</math>-salesmen TSP<br />
: Given <math>m</math> salesmen located at a node <math>1</math>, minimize the total distance traveled by each salesman <math>i</math> where each visits every node in a subset <math>V_i</math> of <math>G</math> exactly once before returning to node <math>1</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">6</span><br />
<br />
== Formulation ==<br />
<br />
Given a set of <math>n</math> cities enumerated <math>0, 1, ..., n-1</math> to be visited with the distance between each pair of cities <math>i</math> and <math>j</math> is given by <math>c_{ij}</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1</span> Introduce decision variables <math>y_{ij}</math> for each <math>(i,j)</math> such that<br />
<br />
<math><br />
y_{ij} = \begin{cases}<br />
1 ~~\text{if city }j\text{ is visited immediately after city }i\\ <br />
0 ~~\text{otherwise}<br />
\end{cases}<br />
</math><br />
<br />
The objective function is then given by<br />
<br />
<math><br />
\text{min} \sum_i \sum_j c_{ij}y_{ij}<br />
</math><br />
<br />
To ensure that the result is a valid tour, several contraints must be added.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1,3</span><br />
<br />
; Go-to constraints<br />
: After visiting a city <math>i</math>, the salesman must visit only one city next:<br />
: <math>\sum_j y_{ij} = 1, ~~ i = 0, 1, ..., n-1</math><br />
; Come-from constraints<br />
: When visiting a city, the salesman must have come from only one city:<br />
: <math>\sum_i y_{ij} = 1, ~~ j = 0, 1, ..., n-1</math><br />
; Subtour elimination <br />
: Ensure that a tour is fully connected, i.e. no subtours<br />
: <math>\sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 2 \le |S| \le n - 2</math><br />
: where <math>S</math> is the set of all tours of <math>G</math><br />
<br />
There are several other formulations for the subtour elimnation contraint, including circuit packing contraints, MTZ constraints, and network flow constraints. <br />
<br />
=== aTSP ILP Formulation ===<br />
<br />
The integer linear programming formulation for an aTSP is given by<br />
<br />
<math><br />
\begin{align}<br />
\text{min} & ~~ \sum_i \sum_j c_{ij}y_{ij}\\<br />
\text{s.t} & ~~ \sum_j y_{ij} = 1, ~~ i = 0, 1, ..., n-1 \\<br />
& ~~ \sum_i y_{ij} = 1, ~~ j = 0, 1, ..., n-1 \\ <br />
& ~~ \sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 2 \le |S| \le n - 2 \\<br />
& ~~ y_{ij} \in \{0,1\} ~ \forall i,j \in E \\<br />
\end{align}<br />
</math><br />
<br />
=== sTSP ILP Formulation ===<br />
<br />
The symmetric case is a special case of the asymmetric case and the above formulation is valid.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3, 6</span> The integer linear programming formulation for an sTSP is given by<br />
<br />
<math><br />
\begin{align}<br />
\text{min} & ~~ \sum_i \sum_j c_{ij}y_{ij}\\<br />
\text{s.t} & ~~ \sum_{i < k} y_{ik} + \sum_{j > k} y_{kj} = 2, ~~ k \in V \\<br />
& ~~ \sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 3 \le |S| \le n - 3 \\<br />
& ~~ y_{ij} \in \{0,1\} ~ \forall i,j \in E \\<br />
\end{align}<br />
</math><br />
<br />
== Solutions ==<br />
<br />
=== Exact algorithms ===<br />
<br />
The most direct solution algorithm is a complete enumeration of all possible path to determine the path of least cost. However, for <math>n</math> cities, the problem is <math>O(n!)</math> time, and this method is practical only for extremely small values of <math>n</math>.<br />
<br />
Branch-and-bound algorithms are commonly used to find solutions for TSPs.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span> The ILP is first relaxed and solved as an LP using the Simplex method, then feasibility is regained by enumeration of the integer variables.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span><br />
<br />
Other exact solution methods include the cutting plane method and branch-and-cut.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">8</span> <br />
<br />
=== Heuristic algorithms ===<br />
<br />
Given that the TSP is an NP-hard problem, heuristic algorithms are commonly used to give a approximate solutions that are good, though not necessarily optimal. The algorithms do not guarantee an optimal solution, but gives near-optimal solutions in reasonable computational time.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> The Held-Karp lower bound can be calculated and used to judge the performance of a heuristic algorithm.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span><br />
<br />
There are two general heuristic classifications<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span>:<br />
* ''Tour construction procedures'' where a solution is gradually built by adding a new vertex at each step<br />
* ''Tour improvement procedures'' where a feasbile solution is improved upon by performing various exchanges<br />
<br />
The best methods tend to be ''composite algorithms'' that combine these features.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span><br />
<br />
==== Tour construction procedures ====<br />
<br />
; Nearest neighbor<br />
: The nearest neighbor algorithm follows a simple greedy procedure where the next city on a tour is simply the nearest city that has not yet been visited.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">8</span> This approach generally gives a tour within 25% of the Held-Karp lower bound.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span><br />
; Greedy<br />
: A tour is constructed by repeatedly selecting the shortest edge that does not create a subtour, resulting in tours within 15-20% of the Held-Harp lower bound.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span><br />
; Insertion<br />
: Insertion algorithms start with an arbitrary subset of cities and then select a new city <math>k</math> that is not yet on the tour.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3, 8</span> This city is inserted into the tour between two consecutive cities <math>i</math> and <math>j</math> such that the increase to the length of the tour (insertion cost) given by <math>d(i,k) + d(k,j) = d(i,j)</math> is minimized.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">8</span><br />
<br />
==== Tour improvement procedures ====<br />
<br />
; 2-opt and 3-opt<br />
: Either two (2-opt) or three (3-opt) edges are randomly removed from a tour and reconnected in such a way that the tour is still feasible.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> This continues until no further improvements can be made. The 2-opt and 3-opt moves usually result in tours that are about 5% and 3% above the Held-Karp bound, respectively.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span><br />
; k-opt<br />
: The k-opt move is the generalized case of the 2-opt and 3-opt methods that requires more computatinal time.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> A local optimum called the k-optimal is found by moving a tour to its best neighbor until no further improvements can be made, where a neighbor of a tour <math>t</math> is one that can be obtained by deleting <math>k</math> edges in <math>t</math> and replacing them with another set of feasible edges.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">8</span><br />
; Tabu search<br />
: A 2-opt exchange mechanism that keeps a tabu list in order to prevent cycling and getting stuck in local minima.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3,7</span> <br />
; Simulated annealing<br />
: Analogous to material annealing, where at high temperature many possible states are reached by the system but as the system cools, the number of possibilities decreases.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span> In the beginning, a high value of <math>T</math> allows for a large number of moves. The number of moves decreasess with <math>T</math> until a local minima is reached. <br />
<br />
== Applications ==<br />
<br />
The importance of the traveling salesman problem is two fold. First its ubiquity as a platform for the study of general methods than can then be applied to a variety of other discrete optimization problems.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5</span> Second is its diverse range of applications, in fields including mathematics, computer science, genetics, and engineering.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5,6</span> <br />
<br />
; Drilling of printed circuit boards<br />
: Consider a printed circuit board, where holes must be drilled in order to connect a conductor on one layer to that on another layer.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> These holes may be different sizes and, in order to drill two holes of different sizes consecutively, the head of the machine must perform a time-consuming drill equipment change.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> The process is then select a diameter, drill all the holes of that diameter, change to a different diameter, and repeat until complete.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> This problem can be seen as a series of TSPs, one for each diameter, where the nodes are the locations of the holes, the edges are the time required to move the drill head from one hole to the next, and the objective is to minimize machine head travel time.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span><br />
; Job sequencing<br />
: Consider <math>n</math> jobs that must be completed in order on a single machine and a setup time for executing job <math>j</math> immediately after job <math>i</math>.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span> This problem can be formulated as a TSP where the nodes are jobs, the edges are the setup times, and the objective is to minimize the time required to complete all the jobs.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span> <br />
; Computer wiring<br />
: Consider a computer board on which a set of pins must be connected such that no more than two wires are attached to each pin.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> This simplifies to solving the TSP with the pins as nodes, the distance between the pins as edges, and the minimum length of wire as the objective.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span><br />
; Crystallography<br />
: Consider an experiment in which a large number of X-ray crystallography measurements must be taken, where each requires the sample to be mounted and the detector to be positioned approprirately.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span> Describing the time it takes to move the detector to a certain position as the cost, solving a TSP with the positions as nodes can identify the order to measurements needed to complete the experiment in the shortest time.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">7</span><br />
<br />
== Example ==<br />
<br />
[[File:NU_TSP.png|frame|Distances between buildings]]<br />
<br />
Suppose a Northwestern student, who lives in '''Foster-Walker''', has to accomplish the following tasks:<br />
<br />
* Drop off a homework set at '''Tech'''<br />
* Work out a '''SPAC'''<br />
* Complete a group project at '''Annenberg'''<br />
<br />
Distances between buildings can be found using Google Maps. Note that there is particularly strong western wind and walking east takes 1.5 times as long. <br />
<br />
It is the middle of winter and the student wants to spend the least possible time walking. Determine the path the student should take in order to minimize walking time, starting and ending at Foster-Walker.<br />
<br />
Start with the cost matrix (with altered distances taken into account):<br />
<br />
{| class="wikitable"<br />
!<br />
! colspan="4" | ''Ending Building''<br />
|-<br />
! ''Starting Building''<br />
! style="width: 100px;" | Tech<br />
! style="width: 100px;" | SPAC<br />
! style="width: 100px;" | Annenberg<br />
! style="width: 100px;" | Foster-Walker<br />
|-<br />
! Tech<br />
| style="text-align: center;" | 0<br />
| style="text-align: center;" | 3831<br />
| style="text-align: center;" | 2079<br />
| style="text-align: center;" | 2644<br />
|-<br />
! SPAC<br />
| style="text-align: center;" | 2554<br />
| style="text-align: center;" | 0<br />
| style="text-align: center;" | 2028<br />
| style="text-align: center;" | 4418<br />
|-<br />
! Annenberg<br />
| style="text-align: center;" | 1384<br />
| style="text-align: center;" | 3042<br />
| style="text-align: center;" | 0<br />
| style="text-align: center;" | 2519<br />
|-<br />
! Foster-Walker<br />
| style="text-align: center;" | 3966<br />
| style="text-align: center;" | 6627<br />
| style="text-align: center;" | 3778.5<br />
| style="text-align: center;" | 0<br />
|}<br />
<br />
<br />
''' <font size="3">Method 1: Complete Enumeration</font> '''<br />
<br />
All possible paths are considered and the path of least cost is the optimal solution. Note that this method is only feasible given the small size of the problem.<br />
<br />
{| class="wikitable"<br />
! style="width: 30px;" | Path<br />
! style="width: 100px;" | Start<br />
! style="width: 100px;" | Building 1<br />
! style="width: 100px;" | Building 2<br />
! style="width: 100px;" | Building 3<br />
! style="width: 100px;" | End<br />
! style="background-color:#888;" |''Cost''<br />
|-<br />
| style="text-align: center;" | 1<br />
| style="text-align: center;" | Foster-Walker<br />
| style="text-align: center;" | Tech<br />
| style="text-align: center;" | Annenberg<br />
| style="text-align: center;" | SPAC<br />
| style="text-align: center;" | Foster-Walker<br />
| style="background-color:#ccc;" | 13502 ft (2.56 mi)<br />
|-<br />
| style="text-align: center;" | 2<br />
| style="text-align: center;" | Foster-Walker<br />
| style="text-align: center;" | Tech<br />
| style="text-align: center;" | SPAC<br />
| style="text-align: center;" | Annenberg<br />
| style="text-align: center;" | Foster-Walker<br />
| style="background-color:#ccc;" | 12344 ft (2.34 mi)<br />
|-<br />
| style="text-align: center;" | 3<br />
| style="text-align: center;" | Foster-Walker<br />
| style="text-align: center;" | Annenberg<br />
| style="text-align: center;" | Tech<br />
| style="text-align: center;" | SPAC<br />
| style="text-align: center;" | Foster-Walker<br />
| style="background-color:#ccc;" | 13411.5 ft (2.54mi)<br />
|-<br />
| style="text-align: center;" | 4<br />
| style="text-align: center;" | Foster-Walker<br />
| style="text-align: center;" | Annenberg<br />
| style="text-align: center;" | SPAC<br />
| style="text-align: center;" | Tech<br />
| style="text-align: center;" | Foster-Walker<br />
| style="background-color:#ccc;" | 12018.5 ft (2.28 mi)<br />
|-<br />
| style="text-align: center;" | 5<br />
| style="text-align: center;" | Foster-Walker<br />
| style="text-align: center;" | SPAC<br />
| style="text-align: center;" | Annenberg<br />
| style="text-align: center;" | Tech<br />
| style="text-align: center;" | Foster-Walker<br />
| style="background-color:#ccc;" | 12683 ft (2.40 mi)<br />
|-<br />
| style="text-align: center;" | 6<br />
| style="text-align: center;" | Foster-Walker<br />
| style="text-align: center;" | SPAC<br />
| style="text-align: center;" | Tech<br />
| style="text-align: center;" | Annenberg<br />
| style="text-align: center;" | Foster-Walker<br />
| style="background-color:#ccc;" | 13776 ft (2.61 mi)<br />
|}<br />
<br />
From inspection, we see that Path 4 is the shortest. So, the student should walk 2.28 miles in the following order: '''Foster-Walker''' &rarr; '''Annenberg''' &rarr; '''SPAC''' &rarr; '''Tech''' &rarr; '''Foster-Walker'''<br />
<br />
<br />
''' <font size="3">Method 2: Nearest neighbor</font> '''<br />
<br />
{| class="wikitable" style="float:right; margin-left: 10px;"<br />
!<br />
! colspan="4" | ''Ending Building''<br />
|-<br />
! ''Starting Building''<br />
! style="width: 100px;" | Tech<br />
! style="width: 100px;" | SPAC<br />
! style="width: 100px;" | Annenberg<br />
! style="width: 100px;" | Foster-Walker<br />
|-<br />
! Tech<br />
| style="text-align: center;" | 0<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(5) 3831'''<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(3) 2079'''<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(4) 2644'''<br />
|-<br />
! SPAC<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(7) 2554'''<br />
| style="text-align: center;" | 0<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(6) 2028'''<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(8) 4418'''<br />
|-<br />
! Annenberg<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(2) 1384'''<br />
| style="text-align: center;" | 3042<br />
| style="text-align: center;" | 0<br />
| style="text-align: center;" | 2519<br />
|-<br />
! Foster-Walker<br />
| style="text-align: center;" | 3966<br />
| style="text-align: center;" | 6627<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(1) 3778.5'''<br />
| style="text-align: center;" | 0<br />
|}<br />
<br />
Starting from Foster-Walker, the next building is simply the closest building that has not yet been visited. With only four nodes, this can be done by inspection:<br />
<br />
# Smallest distance is from Foster-Walker is to Annenberg<br />
# Smallest distance from Annenberg is to Tech<br />
# Smallest distance from Tech is to Annenberg (''creates a subtour, therefore skip'')<br />
# Next smallest distance from Tech is to Foster-Walker (''creates a subtour, therefore skip'')<br />
# Next smallest distance from Tech is to SPAC <br />
# Smallest distance from SPAC is to Annenberg (''creates a subtour, therefore skip'')<br />
# Next smallest distance from SPAC is to Tech (''creates a subtour, therefore skip'')<br />
# Next smallest distance from SPAC is to Foster-Walker <br />
<br />
So, the student would walk 2.54 miles in the following order: '''Foster-Walker''' &rarr; '''Annenberg''' &rarr; '''Tech''' &rarr; '''SPAC''' &rarr; '''Foster-Walker'''<br />
<br />
<br />
''' <font size="3">Method 3: Greedy</font> '''<br />
<br />
{| class="wikitable" style="float:right;"<br />
!<br />
! colspan="4" | ''Ending Building''<br />
|-<br />
! ''Starting Building''<br />
! style="width: 100px;" | Tech<br />
! style="width: 100px;" | SPAC<br />
! style="width: 100px;" | Annenberg<br />
! style="width: 100px;" | Foster-Walker<br />
|-<br />
! Tech<br />
| style="text-align: center;" | 0<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(9) 3831'''<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(3) 2079'''<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(6) 2644'''<br />
|-<br />
! SPAC<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(5) 2554'''<br />
| style="text-align: center;" | 0<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(2) 2028'''<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(11) 4418'''<br />
|-<br />
! Annenberg<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(1) 1384'''<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(7) 3042'''<br />
| style="text-align: center;" | 0<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(4) 2519'''<br />
|-<br />
! Foster-Walker<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(10) 3966 '''<br />
| style="background-color: #B8B8E6; text-align: center;" | '''(12) 6627'''<br />
| style="background-color: #FFB8B8; text-align: center;" | '''(8) 3778.5'''<br />
| style="text-align: center;" | 0<br />
|}<br />
<br />
With this method, the shortest paths that do not create a subtour are selected until a complete tour is created.<br />
<br />
# Smallest distance is Annenberg &rarr; Tech<br />
# Next smallest is SPAC &rarr; Annenberg<br />
# Next smallest is Tech &rarr; Annenberg (''creates a subtour, therefore skip'')<br />
# Next smallest is Anneberg &rarr; Foster-Walker (''creates a subtour, therefore skip'')<br />
# Next smallest is SPAC &rarr; Tech (''creates a subtour, therefore skip'')<br />
# Next smallest is Tech &rarr; Foster-Walker<br />
# Next smallest is Annenberg &rarr; SPAC (''creates a subtour, therefore skip'')<br />
# Next smallest is Foster-Walker &rarr; Annenberg (''creates a subtour, therefore skip'')<br />
# Next smallest is Tech &rarr; SPAC (''creates a subtour, therefore skip'')<br />
# Next smallest is Foster-Walker &rarr; Tech (''creates a subtour, therefore skip'')<br />
# Next smallest is SPAC &rarr; Foster-Walker (''creates a subtour, therefore skip'')<br />
# Next smallest is Foster-Walker &rarr; SPAC<br />
<br />
So, the student would walk 2.40 miles in the following order: '''Foster-Walker''' &rarr; '''SPAC''' &rarr; '''Annenberg''' &rarr; '''Tech''' &rarr; '''Foster-Walker'''<br />
<br />
<br />
'''<font size="3">Results</font>'''<br />
<br />
[[File:TSPExampleSolutions.png|frame|TSP solution paths]]<br />
<br />
As we can see in the figure to the right, the heuristic methods did not give the optimal solution. That is not to say that heuristics can never give the optimal solution, just that it is not guaranteed. <br />
<br />
Both the optimal and the nearest neighbor algorithms suggest that Annenberg is the optimal first building to visit. However, the optimal solution then goes to SPAC, while both heuristic methods suggest Tech. This is in part due to the large cost of SPAC &rarr; Foster-Walker. The heuristic algorithms cannot take this future cost into account, and therefore fall into that local optimum.<br />
<br />
We note that the nearest neighbor and greedy algorithms give solutions that are 11.4% and 5.3%, respectively, above the optimal solution. In the scale of this problem, this corresponds to fractions of a mile. We also note that neither heuristic gave the worst case result, Foster-Walker &rarr; SPAC &rarr; Tech &rarr; Annenberg &rarr; Foster-Walker. <br />
<br />
Only tour building heuristics were used. Combined with a tour improvement algorithm (such as 2-opt or simulated annealing), we imagine that we may be able to locate solutions that are closer to the optimum. <br />
<br />
The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.<br />
<br />
== References ==<br />
<br />
# Vanderbei, R. J. (2001). ''Linear programming: Foundations and extensions'' (2nd ed.). Boston: Kluwer Academic.<br />
# Schrijver, A. (n.d.). On the history of combinatorial optimization (till 1960).<br />
# Matai, R., Singh, S., & Lal, M. (2010). Traveling salesman problem: An overview of applications, formulations, and solution approaches. In D. Davendra (Ed.), ''Traveling Salesman Problem, Theory and Applications''. InTech.<br />
# Junger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., & Wolsey, L. (Eds.). (2009). ''50 years of integer programming, 1958-2008: The early years and state-of-the-art surveys''. Heidelberg: Springer.<br />
# Cook, W. (2007). History of the TSP. ''The Traveling Salesman Problem''. Retrieved from http://www.math.uwaterloo.ca/tsp/history/index.htm<br />
# Punnen, A. P. (2002). The traveling salesman problem: Applications, formulations and variations. In G. Gutin & A. P. Punnen (Eds.), ''The Traveling Salesman Problem and its Variations''. Netherlands: Kluwer Academic Publishers.<br />
# Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. ''European Journal of Operational Research, 59''(2), 231–247.<br />
# Goyal, S. (n.d.). A suvey on travlling salesman problem.</div>Wc593