The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are fulfilled, and the objective is to find a feasible solution with minimum cost. A particle swarm optimization approach hybridized with a local search procedure is discussed in this paper. The method is shown to be very effective in guiding a sophisticated local search previously introduced in the literature towards high quality regions of the search space. Differently from standard particle swarm algorithms, the proposed hybrid method tends to fast convergence to local optima. A mechanism to self-adapt a parameter and to avoid stagnation is therefore introduced. Extensive experimental results, where the new method is compared with the state-of-the-art algorithms, show the effectiveness of the new approach.

A Hybrid Particle Swarm Optimization approach for the Sequential Ordering Problem

ANGHINOLFI, DAVIDE;PAOLUCCI, MASSIMO;
2011-01-01

Abstract

The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are fulfilled, and the objective is to find a feasible solution with minimum cost. A particle swarm optimization approach hybridized with a local search procedure is discussed in this paper. The method is shown to be very effective in guiding a sophisticated local search previously introduced in the literature towards high quality regions of the search space. Differently from standard particle swarm algorithms, the proposed hybrid method tends to fast convergence to local optima. A mechanism to self-adapt a parameter and to avoid stagnation is therefore introduced. Extensive experimental results, where the new method is compared with the state-of-the-art algorithms, show the effectiveness of the new approach.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11567/282438
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 35
  • ???jsp.display-item.citation.isi??? 30
social impact