Particle Swarm Optimization Applied To Task Assignment Problem

Título: Particle Swarm Optimization Applied To Task Assignment Problem

Autores: Pierobom, Jean L.; Delgado, Myriam R.; Kaestner, Celso A. A.

Resumo: Particle Swarm Optimization (PSO) is a metaheuristic method that was inspired on the emerging social behavior found in nature. PSO has shown good results in some recent works of discrete optimization, even though it was originally designed for continuous optimization problems. This paper presents and solves an application of the combinatorial problem of allocation – consisting of cabs and customers – whose optimization goal is to minimize the distance traveled by the fleet. This problem can be categorized as a Task Assignment Problem, and it is optimized in this paper with two implementations of the discrete PSO: the first aprroach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach (permutation encoding) is superior than the first one (binary encoding) in terms of quality of the solutions and computational time, besides it is capable of achieving all the optimal values calculated by an exhaustive search.

Palavras-chave: Swarm Intelligence; Particle Swarm Optimization; Discrete Optimization; Task Assignment Problem

Páginas: 8

Código DOI: 10.21528/CBIC2011-16.4

Artigo em pdf: st_16.4.pdf

Arquivo BibTex: st_16.4.bib