Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.2/2110
Título: Double-ended nearest and loneliest neighbour : a nearest neighbour heuristic variation for the travelling salesman problem
Autor: Pimentel, Fernando Guilherme Silvano Lobo
Palavras-chave: Caixeiro viajante
Heurísticas
Vizinho mais próximo
Travelling salesman
Heuristics
Nearest neighbour
REA
Data: 2011
Editora: Universidade Aberta
Citação: Pimentel, Fernando Guilherme Silvano Lobo - Double-ended nearest and loneliest neighbour : a nearest neighbour heuristic variation for the travelling salesman problem. "Revista de Ciências da Computação" [Em linha]. ISSN 1646-6330. Vol. 6, nº 6 (2011), p. 17-30
Resumo: Este artigo apresenta uma nova heurística para o problema do caixeiro viajante que introduz o conceito de solidão de uma cidade - calculada como a distância média dessa cidade a todas as outras - e o combina com ideias de outras variações de heurísticas do vizinho mais próximo. Tendo a mesma complexidade das heurísticas de vizinho mais próximo mais rápidas, o novo método conduz a melhores resultados que estas heurísticas, ultrapassando igualmente várias outras heurísticas reportadas na literatura. Uma característica interessante da heurística proposta é que dá prioridade a localizações mais isoladas na definição de rotas. A antecipação da distribuição de bens e serviços a localizações mais periféricas pode ser considerada uma externalidade social positiva, tornando a heurística passível de adopção por determinadas entidades por razões não meramente económicas mas também sociais.
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.
Peer review: yes
URI: http://hdl.handle.net/10400.2/2110
ISSN: 1646-6330
Aparece nas colecções:REA - Revista de Ciências da Computação
Revista de Ciências da Computação

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
RCC.pdf342,94 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.