A Skewed VNS for solving a nonlinear optimization case: The Generalized Team Orienteering Problem
Adolfo Urrutia  1@  , Gregorio Tirado  2@  , Alfonso Mateos Caballero  1@  
1 : Universidad Politécnica de Madrid  (UPM)  -  Website
Edif. A.- Calle Ramiro de Maeztu, 7, Madrid -  Spain
2 : Universidad Complutense de Madrid

This work approaches the Team Orienteering Problem (TOP), from a nonlinear optimization perspective. The Generalized Team Orienteering Problem (GTOP) extends the TOP, but keeps some features of the latter. In the GTOP, as in the TOP, a set of nodes which could potentially be visited is given, and the travel time between any pair of nodes, time budget, and the number of tours with starting and ending points, are known. The problem consists in finding a closed tour maximizing the scores of the visited nodes while not exceeding the time limit. The difference with the TOP is that each of the nodes is now associated with two or more scores, there is a vector of preferences that indicates the importance of each score in the final value, and the objective function that aggregates the values is nonlinear.

To solve this optimization problem, we propose a skewed variable neighborhood search with a reduced number of local search operators. The metaheuristic evaluation is performed on 10 benchmarks, some of them already in the literature such as Tsiligirides' and Chaos'. In these cases, a linear objective function was used to enable the comparison with other techniques, and the results were encouraging. For that reason, we proceeded, from a nonlinear perspective, with new datasets based on real data from Spanish tourist cities. The results in this case are an interesting first approximation for the GTOP and future applications of the VNS to similar problems like the Tourist Trip Design Problem.



  • Poster
Online user: 1 RSS Feed