Journal article
A polynomial-time deterministic approach to the travelling salesperson problem
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS, v 35(4), pp 454-460
03 Jul 2020
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We propose a new polynomial-time deterministic algorithm that produces an approximated solution for the travelling salesperson problem. The proposed algorithm ranks cities based on their priorities calculated using a power function of means and standard deviations of their distances from other cities and then connects the cities to their neighbours in the order of their priorities. When connecting a city, a neighbour is selected based on their neighbours' priorities calculated as another power function that additionally includes their distance from the focal city to be connected. This repeats until all the cities are connected into a single loop. The time complexity of the proposed algorithm is O(n(2)), where n is the number of cities. Numerical evaluation shows that, despite its simplicity, the proposed algorithm produces shorter tours with less time complexity than other conventional tour construction heuristics. The proposed algorithm can be used by itself or as an initial tour generator for other more complex heuristic optimisation algorithms.
Metrics
Details
- Title
- A polynomial-time deterministic approach to the travelling salesperson problem
- Publication Details
- INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS, v 35(4), pp 454-460
- Publisher
- TAYLOR & FRANCIS LTD; ABINGDON
- Number of pages
- 0
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Drexel University
- Web of Science ID
- WOS:000546909600004
- Scopus ID
- 2-s2.0-85087424084
- Other Identifier
- 991021860676704721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods