The Orienteering Problem with Stochastic Travel and Service Times New approaches to sampling-based objective function evaluation

DOI: 10.5176/2251-1911_CMCGS15.24

Authors: Vassilis Papapanagiotou, Roberto Montemanni, Luca Maria Gambardella

Abstract:  In recent years, the interest on Stochastic Combinatorial Optimization Problems has increased a lot, since through them it is possible to model the reality more accurately than with their deterministic counterparts. However, for many problems the added stochastic element introduces intricacies that make the objective function either difficult to solve or very time-consuming. In this paper, we propose alternative sampling-based techniques for approximating the objective function of the Orienteering Problem with Stochastic Travel and Service Times, a combinatorial optimization problem arising in logistic applications. The sampling-based techniques are finally compared from an experimental point of view.

Keywords: orienteering problem; stochastic optimization; objective function evaluation; Monte Carlo sampling