Affordable Access

Access to the full text

A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem

Authors
  • Gülcü, Şaban1
  • Mahi, Mostafa2
  • Baykan, Ömer Kaan3
  • Kodaz, Halife3
  • 1 Necmettin Erbakan University, Department of Computer Engineering, Konya, Turkey , Konya (Turkey)
  • 2 Payame Noor University, Department of Computer Engineering and Information Technology, Tehran, Iran , Tehran (Iran)
  • 3 Selcuk University, Department of Computer Engineering, Faculty of Engineering, Konya, Turkey , Konya (Turkey)
Type
Published Article
Journal
Soft Computing
Publisher
Springer-Verlag
Publication Date
Nov 17, 2016
Volume
22
Issue
5
Pages
1669–1685
Identifiers
DOI: 10.1007/s00500-016-2432-3
Source
Springer Nature
Keywords
License
Yellow

Abstract

This article presented a parallel cooperative hybrid algorithm for solving traveling salesman problem. Although heuristic approaches and hybrid methods obtain good results in solving the TSP, they cannot successfully avoid getting stuck to local optima. Furthermore, their processing duration unluckily takes a long time. To overcome these deficiencies, we propose the parallel cooperative hybrid algorithm (PACO-3Opt) based on ant colony optimization. This method uses the 3-Opt algorithm to avoid local minima. PACO-3Opt has multiple colonies and a master–slave paradigm. Each colony runs ACO to generate the solutions. After a predefined number of iterations, each colony primarily runs 3-Opt to improve the solutions and then shares the best tour with other colonies. This process continues until the termination criterion meets. Thus, it can reach the global optimum. PACO-3Opt was compared with previous algorithms in the literature. The experimental results show that PACO-3Opt is more efficient and reliable than the other algorithms.

Report this publication

Statistics

Seen <100 times