Difference between revisions of "Double - ended nearest and loneliest neighbour – a nearest neighbour heuristic variation for the travelling salesman problem"
(Created page with "by: Fernando Guilherme Silvano Lobo Pimentel '''Abstract''' This paper presents a new tour construction heuristic for the travelling salesman problem that introduces the concep...") |
|||
| Line 11: | Line 11: | ||
Link to material: https://repositorioaberto.uab.pt/bitstream/10400.2/2110/4/RCC.pdf | Link to material: https://repositorioaberto.uab.pt/bitstream/10400.2/2110/4/RCC.pdf | ||
| + | |||
| + | <addhtml><html> | ||
| + | <head> | ||
| + | </head> | ||
| + | <body> | ||
| + | <script type="text/javascript">(function(d, t, e, m){ | ||
| + | // Async Rating-Widget initialization. | ||
| + | window.RW_Async_Init = function(){ | ||
| + | RW.init({ | ||
| + | huid: "141148", | ||
| + | uid: "6db8b62d52afa816e07e3917b2d0ce28", | ||
| + | source: "website", | ||
| + | options: { | ||
| + | "advanced": { | ||
| + | "layout": { | ||
| + | "lineHeight": "22px" | ||
| + | } | ||
| + | }, | ||
| + | "size": "medium", | ||
| + | "style": "oxygen" | ||
| + | } | ||
| + | }); | ||
| + | RW.render(); | ||
| + | }; | ||
| + | |||
| + | // Append Rating-Widget JavaScript library. | ||
| + | var rw, s = d.getElementsByTagName(e)[0], id = "rw-js", | ||
| + | p = d.location.protocol, a = ("https:" == p ? "secure." + | ||
| + | m + "js/" : "js." + m), ck = "Y" + t.getFullYear() + "M" + | ||
| + | t.getMonth() + "D" + t.getDate(); | ||
| + | if (d.getElementById(id)) return; | ||
| + | rw = d.createElement(e); | ||
| + | rw.id = id; rw.async = true; rw.type = "text/javascript"; | ||
| + | rw.src = p + "//" + a + "external.min.js?ck=" + ck; | ||
| + | s.parentNode.insertBefore(rw, s); | ||
| + | }(document, new Date(), "script", "rating-widget.com/"));</script> | ||
| + | <div class="rw-ui-container rw-urid-504"></div> | ||
| + | </body> | ||
| + | </html></addhtml> | ||
[[Category:General Articles]] | [[Category:General Articles]] | ||
Revision as of 23:03, 8 June 2018
by: Fernando Guilherme Silvano Lobo Pimentel
Abstract
This paper presents a new tour construction heuristic for the travelling salesman problem that introduces the concept of loneliness of a city computed from the average distance of that city to all others and combines it with ideas from other nearest neighbour heuristics. Having the same time complexity of the faster nearest neighbour heuristics, the new method clearly leads to better tours, outperforming them as well as several other tour construction heuristics reported in the literature. A promising feature of the proposed heuristic is that it gives some priority to more isolated locations in travel route definitions. The earlier distribution of goods and services to loneliest sites might be considered a positive social externality that is appealing to the application of heuristics by public or private institutions that are engaged in acts of social responsibility.
Keywords: Travelling Salesman, Heuristics, Nearest Neighbour
Link to material: https://repositorioaberto.uab.pt/bitstream/10400.2/2110/4/RCC.pdf
<addhtml>
</addhtml>