TY - JOUR

T1 - A hybrid particle swarm optimization - simulated annealing algorithm for the probabilistic travelling salesman problem

AU - Guillermo Cabrera, G.

AU - Silvana Roncagliolo, D.

AU - Riquelme, Juan P.

AU - Cubillos, Claudio

AU - Soto, Ricardo

PY - 2012/3

Y1 - 2012/3

N2 - The Probabilistic Traveling Salesman Problem (PTSP) is a variation of the well known Traveling Salesman Problem (TSP). This problem arises when the information about customers demand is not available at the moment of the tour generation and/or the tour re-calculating cost is too elevated. In this article, a Hybrid Algorithm combining Particle Swarm Optimization (PSO) and Simulated Annealing (SA) is proposed, in order to solve the PTSP. The PSO heuristic offers a simple structured algorithm which supplies a high level of exploration and fast convergence, compared with other evolutionary algorithms. The SA algorithm is used to improve the particle diversity and to avoid the algorithm being trapped into local optimum. Two well-known benchmarks of the literature are used and the proposed PSO-SA algorithm obtains acceptable results. In fact, the hybrid algorithm improves the performance of simple PSO algorithm for all instances.

AB - The Probabilistic Traveling Salesman Problem (PTSP) is a variation of the well known Traveling Salesman Problem (TSP). This problem arises when the information about customers demand is not available at the moment of the tour generation and/or the tour re-calculating cost is too elevated. In this article, a Hybrid Algorithm combining Particle Swarm Optimization (PSO) and Simulated Annealing (SA) is proposed, in order to solve the PTSP. The PSO heuristic offers a simple structured algorithm which supplies a high level of exploration and fast convergence, compared with other evolutionary algorithms. The SA algorithm is used to improve the particle diversity and to avoid the algorithm being trapped into local optimum. Two well-known benchmarks of the literature are used and the proposed PSO-SA algorithm obtains acceptable results. In fact, the hybrid algorithm improves the performance of simple PSO algorithm for all instances.

KW - Hybrid algorithm

KW - Metaheuristics

KW - Routing problems

KW - Stochastic optimization

KW - Swarm intelligence

UR - http://www.scopus.com/inward/record.url?scp=84866602766&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84866602766

VL - 21

SP - 49

EP - 58

JO - Studies in Informatics and Control

JF - Studies in Informatics and Control

SN - 1220-1766

IS - 1

ER -