Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem
type: Item
instance of: scholarly article
title: Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem
DOI: 10.1155/2016/4786268
author: Ziauddin Ursani
author: David Corne
published in: Journal of Optimization
publication date: 2018-08-15T00:00:00Z
review text: Summary: In this paper, complexity curtailing techniques are introduced to create faster version of insertion heuristics, that is, cheapest insertion heuristic (CIH) and largest insertion heuristic (LIH), effectively reducing their complexities from \(O(n^3)\) to \(O(n^2)\) with no significant effect on quality of solution. This paper also examines relatively not very known heuristic concept of max difference and shows that it can be culminated into a full-fledged max difference insertion heuristic (MDIH) by defining its missing steps. Further to this the paper extends the complexity curtailing techniques to MDIH to create its faster version. The resultant heuristic, that is, fast max difference insertion heuristic (FMDIH), outperforms the ``farthest insertion'' heuristic (FIH) across a wide spectrum of popular datasets with statistical significance, even though both the heuristics have the same worst case complexity of \(O(n^2)\). It should be noted that FIH is considered best among lowest order complexity heuristics. The complexity curtailing techniques presented here open up the new area of research for their possible extension to other heuristics.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90B06
zbMATH DE Number: 6918394
zbMATH Keywords: max difference
zbMATH Keywords: complexity curtailing technique
Wikidata QID: Q59129519
describes a project that uses: TSPLIB
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2016/4786268
OpenAlex ID: W2513360157
cites work: Some Simple Applications of the Travelling Salesman Problem
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem
cites work: On the Significance of the Initial Solution in Travelling Salesman Heuristics
cites work: An Analysis of Several Heuristics for the Traveling Salesman Problem
cites work: Q4461911
cites work: Fast Algorithms for Geometric Traveling Salesman Problems
cites work: Q4365133
cites work: A Sequential Method for Discrete Optimization Problems and its Application to the Assignment, Travelling Salesman, and Three Machine Scheduling Problems
cites work: The traveling salesman. Computational solutions for RSP applications
description: scientific article; zbMATH DE number 6918394