In this paper we propose a new metaheuristic approach based on sampling for the Orienteering Problem with Stochastic Travel Times (OPSTS). As in many Stochastic Combinatorial Optimization Problems, the computational bottleneck of OPSTS is in the objective function evaluation. For this reason, this study is mainly devoted to the development and integration of on-purpose, sampling-based fast objective function evaluations into metaheuristic methods. In details, we show how a Variable Neighbourhood Search Metaheuristic can be enhanced by adopting such evaluators. Experimental results show that the new sampling-based method is faster than conventional methods for the given problem, and the improvement is particularly relevant for large-scale instances.
A sampling-based metaheuristic for the Orienteering Problem with Stochastic Travel Times / Papapanagiotou, Vassilis; Montemanni, Roberto; Gambardella Luca, Maria. - (2016), pp. 97-109. (Intervento presentato al convegno International Conference on Theory and Practice of Natural Computing tenutosi a Sendai, Japan nel December 2016) [10.1007/978-3-319-49001-4_8].
A sampling-based metaheuristic for the Orienteering Problem with Stochastic Travel Times
Montemanni Roberto;
2016
Abstract
In this paper we propose a new metaheuristic approach based on sampling for the Orienteering Problem with Stochastic Travel Times (OPSTS). As in many Stochastic Combinatorial Optimization Problems, the computational bottleneck of OPSTS is in the objective function evaluation. For this reason, this study is mainly devoted to the development and integration of on-purpose, sampling-based fast objective function evaluations into metaheuristic methods. In details, we show how a Variable Neighbourhood Search Metaheuristic can be enhanced by adopting such evaluators. Experimental results show that the new sampling-based method is faster than conventional methods for the given problem, and the improvement is particularly relevant for large-scale instances.
Pubblicazioni consigliate
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
