Models and algorithm for the orienteering problem in a fuzzy environment

The orienteering problem is a classical decision-making problem that can model many applications in logistics, tourism, and several other fields. In the orienteering problem, a graph is given, in which each vertex is associated with a score and the travel time along each edge is provided. The goal of this problem is to find a path that maximizes the sum of the collected scores, such that the total travel time along the path is below a given time limit. In the real world, the scores and the travel time may be uncertain, especially when the historical data are not sufficient. In this paper, we study the orienteering problem in a fuzzy environment and represent the scores and the travel time as fuzzy variables. Based on credibility theory, three fuzzy programming models under different decision criteria are proposed. For cases where the fuzzy variables are of some specific types, crisp equivalents of the models are constructed. In order to solve the proposed models, we design a hybrid intelligent algorithm integrating fuzzy simulation with genetic algorithm. A series of numerical experiments are performed to show the effectiveness and robustness of our hybrid intelligent algorithm.

Recommended citation: Ni, Y., Chen, Y., Ke, H., & Ralescu, D. A. (2018). "Models and algorithm for the orienteering problem in a fuzzy environment." International Journal of Fuzzy Systems. 20(3):861-876.
Download Paper