The orienteering problem with stochastic profits

Taylan Ilhan, Seyed MR Iravani, Mark S. Daskin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

54 Scopus citations

Abstract

Given a graph G = (N, E), N representing the set of nodes associated with Normally distributed random profits and E representing the set of edges with associated travel times, we define the Orienteering Problem with Stochastic Profits (OPSP) as the problem of finding a tour that visits a subset of N within a prespecified time limit and maximizes the probability of collecting more than a prespecified target profit level. We develop an exact solution scheme based on a parametric formulation of the problem and present a bi-objective genetic algorithm. We also analyze the characteristics of the problem and test the algorithms computationally. The experimental results identify conditions under which the OPSP results in significant improvements in reaching the target profit when compared with the solution from the deterministic variant of the problem.

Original languageEnglish (US)
Pages (from-to)406-421
Number of pages16
JournalIIE Transactions (Institute of Industrial Engineers)
Volume40
Issue number4
DOIs
StatePublished - Apr 1 2008

Keywords

  • Bi-objective optimization
  • Genetic algorithm
  • Stochastic routing

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'The orienteering problem with stochastic profits'. Together they form a unique fingerprint.

Cite this