Selamoğlu, BI and Salhi, A and Sulaiman, M (2018) Strip Algorithms as an Efficient Way to Initialise Population-Based Metaheuristics. In: Recent Developments in Metaheuristics. Operations Research/Computer Science Interfaces (ORCS), 62 . Springer, pp. 319-331. ISBN 978-3-319-58253-5. Official URL: https://doi.org/10.1007/978-3-319-58253-5_18
Selamoğlu, BI and Salhi, A and Sulaiman, M (2018) Strip Algorithms as an Efficient Way to Initialise Population-Based Metaheuristics. In: Recent Developments in Metaheuristics. Operations Research/Computer Science Interfaces (ORCS), 62 . Springer, pp. 319-331. ISBN 978-3-319-58253-5. Official URL: https://doi.org/10.1007/978-3-319-58253-5_18
Selamoğlu, BI and Salhi, A and Sulaiman, M (2018) Strip Algorithms as an Efficient Way to Initialise Population-Based Metaheuristics. In: Recent Developments in Metaheuristics. Operations Research/Computer Science Interfaces (ORCS), 62 . Springer, pp. 319-331. ISBN 978-3-319-58253-5. Official URL: https://doi.org/10.1007/978-3-319-58253-5_18
Abstract
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 Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 17 Nov 2017 16:28 |
Last Modified: | 16 May 2024 19:08 |
URI: | http://repository.essex.ac.uk/id/eprint/20688 |