Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem (Q1659213)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem
scientific article

    Statements

    Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem (English)
    0 references
    0 references
    0 references
    15 August 2018
    0 references
    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.
    0 references
    max difference
    0 references
    complexity curtailing technique
    0 references

    Identifiers