A distance matrix based algorithm for solving the traveling salesman problem

Shengbin Wang (), Weizhen Rao () and Yuan Hong ()
Additional contact information
Shengbin Wang: North Carolina A&T State University
Weizhen Rao: Shandong University of Science and Technology
Yuan Hong: Illinois Institute of Technology

Operational Research, 2020, vol. 20, issue 3, No 13, 1505-1542

Abstract: Abstract This paper presents a new algorithm for solving the well-known traveling salesman problem (TSP). This algorithm applies the Distance Matrix Method to the Greedy heuristic that is widely used in the TSP literature. In particular, it is shown that there exists a significant negative correlation between the variance of distance matrix and the performance of the Greedy heuristic, that is, the less the variance of distance matrix among the customer nodes is, the better solution the Greedy heuristic can provide. Thus the Distance Matrix Method can be used to improve the Greedy heuristic’s performance. Based on this observation, a method called Minimizing the Variance of Distance Matrix (MVODM) is proposed. This method can effectively improve the Greedy heuristic when applied. In order to further improve the efficiency, a heuristic that can quickly provide approximate solutions of the MVODM is developed. Finally, an algorithm combining this approximate MVODM method and Greedy heuristic is developed. Extensive computational experiments on a well-established test suite consisting of 82 benchmark instances with city numbers ranging from 1000 to 10,000,000 demonstrate that this algorithm not only improves the average tour quality by 40.1%, but also reduces the running time by 21.7%, comparing with the Greedy algorithm. More importantly, the performance of the proposed approach can beat the Savings heuristic, the best known construction heuristic in the TSP literature.

Keywords: Traveling salesman problem; Distance matrix method; Greedy heuristic; Savings heuristic; Construction heuristics (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-018-0386-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:20:y:2020:i:3:d:10.1007_s12351-018-0386-1

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-018-0386-1

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().