Introducing Complexity Curtailing Techniques for the Tour Construction Heuristics for the Travelling Salesperson Problem
Joint Authors
Ursani, Ziauddin
Corne, David W.
Source
Issue
Vol. 2016, Issue 2016 (31 Dec. 2016), pp.1-15, 15 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2016-08-23
Country of Publication
Egypt
No. of Pages
15
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Ursani, Ziauddin& Corne, David W.. 2016. Introducing Complexity Curtailing Techniques for the Tour Construction Heuristics for the Travelling Salesperson Problem. Journal of Optimization،Vol. 2016, no. 2016, pp.1-15.
https://search.emarefa.net/detail/BIM-1110148
Modern Language Association (MLA)
Ursani, Ziauddin& Corne, David W.. Introducing Complexity Curtailing Techniques for the Tour Construction Heuristics for the Travelling Salesperson Problem. Journal of Optimization No. 2016 (2016), pp.1-15.
https://search.emarefa.net/detail/BIM-1110148
American Medical Association (AMA)
Ursani, Ziauddin& Corne, David W.. Introducing Complexity Curtailing Techniques for the Tour Construction Heuristics for the Travelling Salesperson Problem. Journal of Optimization. 2016. Vol. 2016, no. 2016, pp.1-15.
https://search.emarefa.net/detail/BIM-1110148
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1110148