Efficient metaheuristics for the mixed team orienteering problem with time windows
type: Item
instance of: scholarly article
title: Efficient metaheuristics for the mixed team orienteering problem with time windows
zbMATH Open document ID: 1461.90159
author: Damianos Gavalas
author: Charalampos Konstantopoulos
author: Konstantinos Mastakas
author: Nikolaos Vathis
author: Grammati Pantziou
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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).
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7042315
zbMATH Keywords: iterated local search
zbMATH Keywords: simulated annealing
zbMATH Keywords: team orienteering problem
zbMATH Keywords: arc orienteering problem
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a9010006
OpenAlex ID: W2225877659
cites work: The orienteering problem: a survey
cites work: A matheuristic for the team orienteering arc routing problem
cites work: The undirected capacitated arc routing problem with profits
cites work: Local search for the undirected capacitated arc routing problem with profits
cites work: The one-period bus touring problem: Solved by an effective heuristic for the orienteering tour problem and improvement algorithm
cites work: Approximation algorithms for the arc orienteering problem
cites work: Q5271458
cites work: Q5271451
cites work: Q5271453
cites work: Iterated local search for the team orienteering problem with time windows
cites work: Q4452900
cites work: Optimization by Simulated Annealing
DOI: 10.3390/A9010006
description: scientific article; zbMATH DE number 7042315