A Taboo Search approach for solving Multi Constrained Team Orienteering Problem for application in touristic trip planning

K. Sylejmani, J. Dorn, N. Musliu:
"A Taboo Search approach for solving Multi Constrained Team Orienteering Problem for application in touristic trip planning";
in:"12th International Conference on HybridIntelligent Systems", herausgegeben von: IEEE; IEEE Computer Society, 2012, ISBN: 978-1-4673-5114-0, S. 300 - 305.

[ Publication Database ]

Abstract:


The touristic trip planning problem can be
considered as a Multi Constrained Team Orienteering
Problem with Time Windows (MCTOPTW). The MCTOPTW
is characterized with a set of points of interest (POI), each
having a score, a time window and some attributes such as the
type or entry fee. The maximum number of POIs of certain
types that can be included into the itinerary is limited. A
tourist can visit the POIs during their respective time windows.
The objective is to visit the points that have the highest scores
during specified periods of time. This paper proposes a Tabu
Search approach for solving the MCTOPTW problem. To
explore the neighborhood the moves Insert, Replace and Swap
are applied. Additionally, the algorithm employs a tabu list, a
perturbation and a diversification mechanism. The algorithm
is evaluated on benchmark instances from the literature and its
performance is compared to the state of the art results.