The Probabilistic Orienteering Problem is an optimization problem where a set of customers, each with an associated prize and probability of requiring a service, a time budget and travel times between customers are given. The objective is to select the subset of customers that maximize the expected total prize collected in the given time (taking into account of the total travel time spent visiting them).Random Restart Local Search is a heuristic method widely used to solve combinatorial optimization problems. In particular, it is used in conjunction with local search procedures to escape from local optima. The method works by restarting the optimization search once no further improvement is possible by the embedded local search component. Each restart is associated with a new initial solution for the optimization, and selecting such restart initial solutions play an important role in the success of the overall algorithm. In this work we propose a method to effectively selecting such solutions, and we present an empirical study to validate our ideas.

Re-Initialising Solutions in a Random Restart Local Search for the Probabilistic Orienteering Problem / Chou, Xc; Mele, Uj; Gambardella, Lm; Montemanni, R. - ICIEA 2021-Europe: 2021 The 8th International Conference on Industrial Engineering and Applications:(2021), pp. 153-158. ((Intervento presentato al convegno ICIEA 2021-Europe: 2021 The 8th International Conference on Industrial Engineering and Applications(Europe) tenutosi a Barcelona, Spain nel January 8 - 11, 2021 [10.1145/3463858.3463895].

Re-Initialising Solutions in a Random Restart Local Search for the Probabilistic Orienteering Problem

Montemanni, R
2021-01-01

Abstract

The Probabilistic Orienteering Problem is an optimization problem where a set of customers, each with an associated prize and probability of requiring a service, a time budget and travel times between customers are given. The objective is to select the subset of customers that maximize the expected total prize collected in the given time (taking into account of the total travel time spent visiting them).Random Restart Local Search is a heuristic method widely used to solve combinatorial optimization problems. In particular, it is used in conjunction with local search procedures to escape from local optima. The method works by restarting the optimization search once no further improvement is possible by the embedded local search component. Each restart is associated with a new initial solution for the optimization, and selecting such restart initial solutions play an important role in the success of the overall algorithm. In this work we propose a method to effectively selecting such solutions, and we present an empirical study to validate our ideas.
ICIEA 2021-Europe: 2021 The 8th International Conference on Industrial Engineering and Applications(Europe)
Barcelona, Spain
January 8 - 11, 2021
ICIEA 2021-Europe: 2021 The 8th International Conference on Industrial Engineering and Applications
153
158
Chou, Xc; Mele, Uj; Gambardella, Lm; Montemanni, R
Re-Initialising Solutions in a Random Restart Local Search for the Probabilistic Orienteering Problem / Chou, Xc; Mele, Uj; Gambardella, Lm; Montemanni, R. - ICIEA 2021-Europe: 2021 The 8th International Conference on Industrial Engineering and Applications:(2021), pp. 153-158. ((Intervento presentato al convegno ICIEA 2021-Europe: 2021 The 8th International Conference on Industrial Engineering and Applications(Europe) tenutosi a Barcelona, Spain nel January 8 - 11, 2021 [10.1145/3463858.3463895].
File in questo prodotto:
File Dimensione Formato  
3463858.3463895.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 675.48 kB
Formato Adobe PDF
675.48 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

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