In this paper we present a new memetic approach to solve the orienteering problem. The key method of our proposal is the procedure ReduceExtend which, starting from a permutation of all the vertices in the orienteering problem, produces a feasible path with a locally optimal score. This procedure is coupled with an evolutionary algorithm which navigate the search space of permutations. In our experiments we have considered the following algorithms: the algebraic differential evolution algorithm, and the three continuous algorithms CMA-ES, DE and PSO equipped with the random key technique. The experimental results show that the proposed approach is competitive with the state of the art results of some selected benchmark instances.

A Memetic Approach for the Orienteering Problem

Santucci, Valentino
;
2020

Abstract

In this paper we present a new memetic approach to solve the orienteering problem. The key method of our proposal is the procedure ReduceExtend which, starting from a permutation of all the vertices in the orienteering problem, produces a feasible path with a locally optimal score. This procedure is coupled with an evolutionary algorithm which navigate the search space of permutations. In our experiments we have considered the following algorithms: the algebraic differential evolution algorithm, and the three continuous algorithms CMA-ES, DE and PSO equipped with the random key technique. The experimental results show that the proposed approach is competitive with the state of the art results of some selected benchmark instances.
978-3-030-45015-1
978-3-030-45016-8
File in questo prodotto:
File Dimensione Formato  
_WIVACE2019____PostProceedings.pdf

accesso aperto

Descrizione: Preprint
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 244.01 kB
Formato Adobe PDF
244.01 kB Adobe PDF Visualizza/Apri
wivace2019_p49-p59.pdf

non disponibili

Descrizione: Versione editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 308.34 kB
Formato Adobe PDF
308.34 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/20.500.12071/20745
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact