Introducing Complexity Curtailing Techniques for the Tour Construction Heuristics for the Travelling Salesperson Problem

Ziauddin Ursani and David W. Corne

Journal of Optimization, 2016, vol. 2016, 1-15

Abstract:

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 to 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 . 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.

Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/7179/2016/4786268.pdf (application/pdf)
http://downloads.hindawi.com/journals/7179/2016/4786268.xml (text/xml)

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:hin:jjopti:4786268

DOI: 10.1155/2016/4786268

Access Statistics for this article

More articles in Journal of Optimization from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().