Guillermo CABRERA G.¹, Silvana RONCAGLIOLO D.¹, Juan P. RIQUELME¹, Claudio CUBILLOS¹, Ricardo SOTO^1,2
1 Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso,
Av. Brasil 2241, Chile

² Universidad Autónoma de Chile,
Pedro de Valdivia 641, Santiago, Chile

Abstract: 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.

Keywords: Hybrid Algorithm, Metaheuristics, Routing Problems, Stochastic Optimization, Swarm Intelligence.

>>Full text
CITE THIS PAPER AS:
Guillermo G. CABRERA, Silvana D. RONCAGLIOLO, Juan P. RIQUELME, Claudio CUBILLOS, Ricardo SOTO, A Hybrid Particle Swarm Optimization – Simulated Annealing Algorithm for the Probabilistic Travelling Salesman Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 21 (1), pp. 49-58, 2012. https://doi.org/10.24846/v21i1y201206

1. Introduction and Literature Review

The Travelling Salesman Problem (TSP) has several different variations. One of them is the stochastic variant called Probabilistic Traveling Salesman Problem (PTSP), which can be classified as a Stochastic Combinatorial Optimization Problem (SCOP). PTSP was proposed by Jaillet [19] and several authors have solved this model using different approaches. In [19] the PTSP is described as follows: Consider a set of n points which must be visited with probability p. On any given instance of the problem only a subset consisting of k out of the n points (0<k<n) have to be visited. The k number is determined according to a known probability distribution (such as the binomial). An a priori tour through all n points has to be found. Each point must be included only once in the a priori tour. On any given instance of the problem, the present k points will then be visited in the same order as they appear in the a priori tour. The PTSP is usually tackled by an a priori optimization phase [4] which comprises two stages: First, as said above, an a priori solution is found. In the second stage, the a posteriori solution is derived from the a priori solution. For a posteriori solution, the edges are visited in the same order as in the a priori solution, but excluding the edges that do not require to be visited. Fig. 1 shows both different a priori and a posteriori tours. In the example only odd edges are visited in the a posteriori tour. The problem of finding such an a priori tour which is of minimum length in the expected value sense is defined as a PTSP.

Figure 1. a) A priori tour for 16 edges. (b) A posteriori tour after a realization.

The problem appears when the information about customers demand is not available at the moment of tour generation and/or the tour re-calculating cost is too elevated. In [19] the proposed model was solved by a well-known “hill climbing” algorithm. hereafter, several authors have used different stochastic approaches in order to solve this optimization problem, e.g., in [5, 6] the authors solved the homogeneous PTSP using an Ant Colony Optimization (ACO) approach. In there, a variation of traditional ACO algorithm, called probabilistic Ant Colony System (pACS), raised very good solution for the PTSP, being as one of the more efficient strategies for stochastic routing problems. The most important difference between pACS and ACS is the set of arcs on which the pheromone is globally increased. One of the main conclusions of these works is that the pACS algorithm is very competitive when the probabilities of the cities are far from 1. In this case (probabilities close to 1) the well-known ACS algorithm raised better solutions than pACS. In [26] the Expanding Neighborhood Search (ENS) is proposed for the resolution of the PTSP. The ENS is a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP) which obtained a very good solution for a theoretical dataset. In [25] the author proposed a set of initial solution generators under a genetic algorithm (GA) framework for solving the PTSP. These three initial solution generators allow the GA to reduce computational time without decreasing the quality of the best reached solution. In [2, 3], the authors present an Estimation-Based algorithm involving local search strategies. In both, the authors experiment with different metaheuristics applying an estimation-based customization strategy, to evaluate the solution cost of different PTSP instances, obtaining excellent results. In [27] an hybrid algorithm – nature inspired – based on PSO, GRASP and ENS strategy is proposed, for a solution of the PTSP. The GRASP and ENS strategies are used in order to improve the quality of initial solutions for the PSO algorithm, which have as main characteristic the use of multiple swarms, reducing considerably the required computational time.

Finally, in [1] the authors describe a variant of particle swarm, called hybrid swarms, that incorporates an explicit selection mechanism similar to that used in more traditional evolutionary computations. The main author’s conclusion is that the addition of selection supplies some advantage to particle swarm on certain functions.

The main contribution of this article is the application of an hybrid technique on a SCOP, using a simple but effective sort algorithm which improves considerably the solution reached by the hybrid algorithm in a reasonable computational time.

REFERENCES:

1. ANGELINE, P. J., Using Selection to Improve Particle Swarm Optimization. IEEE Int. Conf. on Computational Intelligence (ICEC’98), 1998, pp. 84-89.
2. BALAPRAKASH, P., M. BIRATTARI, T. Stützle, M. Dorigo, Estimation-based Metaheuristics for the Probabilistic Traveling Salesman Problem. Computers & Operations Research, vol. 37, no. 11, 2010, pp. 1939-1951.