Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows

Algorithms

Damianos Gavalas¹  Charalampos Konstantopoulos²  Konstantinos Mastakas²  Grammati Pantziou²  Nikolaos Vathis² 

[1]Department of Cultural Technology and Communication, University of the Aegean, University Hill, GR 81 100 Mytilini, Lesvos, Greece

[2]Computer Technology Institute & Press Diophantus, “D. Maritsas” Building, Nikou Kazantzaki St., University Campus of Patras 265 04 Rion, P.O. Box 1382, Greece

关键词: Iterated Local Search;    Simulated Annealing;    Team Orienteering Problem;    Arc Orienteering Problem;   

DOI  :  10.3390/a9010006

来源: mdpi

【 摘 要 】

Given a graph whose nodes and edges are associated with a profit, a visiting (or traversing) time and an admittance time window, the Mixed Team Orienteering Problem with Time Windows (MTOPTW) seeks for a specific number of walks spanning a subset of nodes and edges of the graph so as to maximize the overall collected profit. The visit of the included nodes and edges should take place within their respective time window and the overall duration of each walk should be below a certain threshold. In this paper we introduce the MTOPTW, which can be used for modeling a realistic variant of the Tourist Trip Design Problem where the objective is the derivation of near-optimal multiple-day itineraries for tourists visiting a destination which features several points of interest (POIs) and scenic routes. Since the MTOPTW is a NP-hard problem, we propose the first metaheuristic approaches to tackle it. The effectiveness of our algorithms is validated through a number of experiments on POI and scenic route sets compiled from the city of Athens (Greece).

【 授权许可】

CC BY   
© 2016 by the authors; licensee MDPI, Basel, Switzerland.