Efficient Cluster-Based Heuristics for the Team Orienteering Problem with Time Windows

Damianos Gavalas (), Charalampos Konstantopoulos, Konstantinos Mastakas () and Grammati Pantziou ()
Additional contact information
Damianos Gavalas: Department of Product & Systems Design Engineering, University of the Aegean, Syros, 84100, Greece and Computer Technology Institute and Press, “Diophantus” (CTI), Patras, Greece
Charalampos Konstantopoulos: Department of Informatics, University of Piraeus, Karaoli & Dimitriou 80 Piraeus, 18534, Greece and Computer Technology Institute and Press, “Diophantus” (CTI), Patras, Greece
Konstantinos Mastakas: School of Applied Mathematical and Physical Sciences, National Technical University of Athens, Heroon Polytechniou 9 Zografou, 15780, Greece and Computer Technology Institute and Press, “Diophantus” (CTI), Patras, Greece
Grammati Pantziou: Department of Informatics and Computer Engineering, University of West Attica, Agiou Spyridonos Aigaleo, 12243, Greece and Computer Technology Institute and Press, “Diophantus” (CTI), Patras, Greece

Asia-Pacific Journal of Operational Research (APJOR), 2019, vol. 36, issue 01, 1-44

Abstract: In the Team Orienteering Problem with Time Windows (TOPTW), a variant of the Vehicle Routing Problem with Profits, a set of locations is given, each associated with a profit, a visiting time and a time window. The aim is to maximize the overall profit collected by a number of routes, while the duration of each route must not exceed a given time budget. TOPTW is NP-hard and is typically used to model the Tourist Trip Design Problem. The latter deals with deriving near optimal multiple-day tours for tourists visiting a destination with several points of interest (POIs). The most efficient known heuristic approach to TOPTW which yields the best solution quality versus execution time, is based on Iterated Local Search (ILS). However, the ILS algorithm treats each node separately, hence it tends to overlook highly profitable areas of nodes situated far from the current solution, considering them too time-expensive to visit. We propose two cluster-based extensions to ILS addressing the aforementioned weakness by grouping nodes on separate clusters (based on geographical criteria), thereby making visits to such nodes more attractive. Our approaches improve ILS with respect to solutions quality and execution time as evidenced by experimental tests exercised on both existing and new TTDP-oriented benchmark instances.

Keywords: Team orienteering problem with time windows; iterated local search; clustering; tourist trip design problem; point of interest (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595919500015
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:36:y:2019:i:01:n:s0217595919500015

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595919500015

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().