Set TSP problem

<h2 id="illustration-from-the-cutting-stock-problem">Illustration from the cutting stock problem</h2>
<p>The one-dimensional <a href="/facts/Cutting_stock_problem/aGw6fSEd">cutting stock problem</a> as applied in the paper / plastic film industries, involves cutting jumbo rolls into smaller ones. This is done by generating cutting patterns typically to minimise waste. Once such a solution has been produced, one may seek to minimise the knife changes, by re-sequencing the patterns (up and down in the figure), or moving rolls left or right within each pattern. These moves do not affect the waste of the solution.
</p><p>In the above figure, patterns (width no more than 198) are rows; knife changes are indicated by the small white circles; for example, patterns 2-3-4 have a roll of size 42.5 on the left - the corresponding knife does not have to move. Each pattern represents a TSP set, one of whose permutations must be visited. For instance, for the last pattern, which contains two repeated sizes (twice each), there are 5! / (2! × 2!) = 30 permutations. The number of possible solutions to the above instance is 12! × (5!)6 × (6!)4 × (7!)2 / ((2!)9 × (3!)2) ≈ 5.3 × 1035. The above solution contains 39 knife changes, and has been obtained by a heuristic; it is not known whether this is optimal. Transformations into the regular TSP, as described in <a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> would involve a TSP with 5,520 nodes.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Fagnano%2527s_problem/0FbUQebt">Fagnano's problem</a> of finding the shortest tour that visits all three sides of a triangle</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>C.E. Noon, "The Generalized Traveling Salesman Problem", PhD dissertation, 1988. <a href="https://hdl.handle.net/2027.42/161841" target="_blank">https://hdl.handle.net/2027.42/161841</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Noon, Charles E.; Bean, James C. (February 1993). "An efficient transformation of the generalized traveling salesman problem". INFOR: Information Systems and Operational Research. 31 (1): 39–44. doi:10.1080/03155986.1993.11732212. hdl:2027.42/6833. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Satyanarayana G. Manyam, Sivakumar Rathinam, Swaroop Darbha, David Casbeer, Yongcan Cao, Phil Chandler (2016). "GPS Denied UAV Routing with Communication Constraints". Journal of Intelligent & Robotic Systems. 84 (1–4): 691–703. doi:10.1007/s10846-016-0343-2. S2CID 33884807.{{cite journal}}:  CS1 maint: multiple names: authors list (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Satyanarayana G. Manyam, Sivakumar Rathinam (2016). "On Tightly Bounding the Dubins Traveling Salesman's Optimum". Journal of Dynamic Systems, Measurement, and Control. 140 (7): 071013. arXiv:1506.08752. doi:10.1115/1.4039099. S2CID 16191780. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Satyanarayana G. Manyam, Sivakumar Rathinam, David Casbeer, Eloy Garcia (2017). "Tightly Bounding the Shortest Dubins Paths Through a Sequence of Points". Journal of Intelligent & Robotic Systems. 88 (2–4): 495–511. doi:10.1007/s10846-016-0459-4. S2CID 30943273.{{cite journal}}:  CS1 maint: multiple names: authors list (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Noon, Charles E.; Bean, James C. (February 1993). "An efficient transformation of the generalized traveling salesman problem". INFOR: Information Systems and Operational Research. 31 (1): 39–44. doi:10.1080/03155986.1993.11732212. hdl:2027.42/6833. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Set TSP problem open-in-new

Set TSP problem