Research Repository

Strip Algorithms as an Efficient Way to Initialise Population-Based Metaheuristics

Selamoğlu, BI and Salhi, A and Sulaiman, M (2018) 'Strip Algorithms as an Efficient Way to Initialise Population-Based Metaheuristics.' In: Amodeo, L and Talbi, EG and Yalaoui, F, (eds.) Recent Developments in Metaheuristics. Operations Research/Computer Science Interfaces (ORCS) . Springer, 319 - 331. ISBN 978-3-319-58253-5

Full text not available from this repository.


The Strip Algorithm (SA) is a constructive heuristic which has been tried on the Euclidean Travelling Salesman Problem (TSP) and other planar network problems with some success. Its attraction is its efficiency. In its simplest form, it can find tours of length Ω (n−−√) in O (n log n) operations where n is the number of nodes. Here, we set out to investigate new variants such as the 2-Part Strip Algorithm (2-PSA), the Spiral Strip Algorithm (SSA) and the Adaptive Strip Algorithm (ASA). The latter is particularly suited for Euclidean TSPs with non-uniform distribution of cities across the grid; i.e problems with clustered cities. These cases present an overall low density, but high localised densities. ASA takes this into account in that smaller strips are generated where the density is high. All three algorithms are analysed, implemented and computationally tested against each other and the Classical Strip Algorithm. Computational results are included.

Item Type: Book Section
Uncontrolled Keywords: Strip Algorithm, Travelling Salesman, Heuristics, Optimisation
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Elements
Date Deposited: 17 Nov 2017 16:28
Last Modified: 17 Nov 2017 17:15

Actions (login required)

View Item View Item