Ant Colony Optimization With Local Search for Dynamic Traveling Salesman Problems

For a dynamic traveling salesman problem (DTSP), the weights (or traveling times) between two cities (or nodes) may be subject to changes. Ant colony optimization (ACO) algorithms have proved to be powerful methods to tackle such problems due to their adaptation capabilities. It has been shown that...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2017-07, Vol.47 (7), p.1743-1756
Main Authors: Mavrovouniotis, Michalis, Muller, Felipe M., Shengxiang Yang
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Ant colony optimization
Ant colony optimization (ACO)
Benchmark testing
dynamic traveling salesman problem (DTSP)
Generators
Heuristic algorithms
Inserts
local search
memetic algorithm
Memetics
Performance enhancement
Searching
State of the art
Travel time
Traveling salesman problem
Traveling salesman problems
Urban areas
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a dynamic traveling salesman problem (DTSP), the weights (or traveling times) between two cities (or nodes) may be subject to changes. Ant colony optimization (ACO) algorithms have proved to be powerful methods to tackle such problems due to their adaptation capabilities. It has been shown that the integration of local search operators can significantly improve the performance of ACO. In this paper, a memetic ACO algorithm, where a local search operator (called unstring and string) is integrated into ACO, is proposed to address DTSPs. The best solution from ACO is passed to the local search operator, which removes and inserts cities in such a way that improves the solution quality. The proposed memetic ACO algorithm is designed to address both symmetric and asymmetric DTSPs. The experimental results show the efficiency of the proposed memetic algorithm for addressing DTSPs in comparison with other state-of-the-art algorithms.
ISSN:2168-2267
2168-2275
DOI:10.1109/TCYB.2016.2556742