 A linearithmic heuristic for the travelling salesman problemÉric D. Taillard European Journal of Operational Research, 2022, vol. 297, issue 2, 442-450 Abstract: A linearithmic (nlogn) randomized method based on POPMUSIC (Partial Optimization Metaheuristic Under Special Intensification Conditions) is proposed for generating reasonably good solutions to the travelling salesman problem. The method improves a previous work with empirical algorithmic complexity in n1.6. The method has been tested on instances with billions of cities. For a lot of problem instances of the literature, a few dozens of runs are able to generate a very high proportion of the edges of the best solutions known. This characteristic is exploited in a new release of the Helsgaun’s implementation of the Lin-Kernighan heuristic (LKH) that is also able to produce rapidly extremely good solutions for non-Euclidean instances. The practical limits of the proposed method are discussed on a new type of problem instances arising in a manufacturing process, especially in 3D extrusion printing. Keywords: Travelling salesman; Local search; POPMUSIC; Large-scale optimization; Metaheuristics; 3D printing (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:297:y:2022:i:2:p:442-450 DOI: 10.1016/j.ejor.2021.05.034 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.