A survey on algorithmic approaches for solving tourist trip design problems

被引:211
作者
Gavalas, Damianos [1 ,2 ,3 ]
Konstantopoulos, Charalampos [2 ,3 ,4 ]
Mastakas, Konstantinos [2 ,3 ,5 ]
Pantziou, Grammati [2 ,3 ,6 ]
机构
[1] Univ Aegean, Dept Cultural Technol & Commun, Mitilini, Greece
[2] Comp Technol Inst, GR-26110 Patras, Greece
[3] Press Diophantus CTI, Patras, Greece
[4] Univ Piraeus, Dept Informat, Piraeus, Greece
[5] Univ Athens, Dept Math, Athens, Greece
[6] Technol Educ Inst Athens, Dept Informat, Athens, Greece
关键词
Tourist trip design problem; Electronic tourist guide; Tour planning; Orienteering problem; Time windows; TEAM ORIENTEERING PROBLEM; TRAVELING SALESMAN PROBLEM; MAXIMUM COLLECTION PROBLEM; VEHICLE-ROUTING PROBLEM; DISCOUNTED-REWARD TSP; MULTIPLE TIME WINDOWS; ITERATED LOCAL SEARCH; APPROXIMATION ALGORITHMS; K-MST; PROFITS;
D O I
10.1007/s10732-014-9242-5
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The tourist trip design problem (TTDP) refers to a route-planning problem for tourists interested in visiting multiple points of interest (POIs). TTDP solvers derive daily tourist tours, i.e., ordered visits to POIs, which respect tourist constraints and POIs attributes. The main objective of the problem discussed is to select POIs that match tourist preferences, thereby maximizing tourist satisfaction, while taking into account a multitude of parameters and constraints (e. g., distances among POIs, visiting time required for each POI, POIs visiting days/hours, entrance fees, weather conditions) and respecting the time available for sightseeing on a daily basis. The aim of this work is to survey models, algorithmic approaches and methodologies concerning tourist trip design problems. Recent approaches are examined, focusing on problem models that best capture a multitude of realistic POIs attributes and user constraints; further, several interesting TTDP variants are investigated. Open issues and promising prospects in tourist trip planning research are also discussed.
引用
收藏
页码:291 / 328
页数:38
相关论文
共 140 条
[81]   Electronic mobile guides: a survey [J].
Kenteris, Michael ;
Gavalas, Damianos ;
Economou, Daphne .
PERSONAL AND UBIQUITOUS COMPUTING, 2011, 15 (01) :97-111
[82]   An innovative mobile electronic tourist guide application [J].
Kenteris, Michael ;
Gavalas, Damianos ;
Economou, Daphne .
PERSONAL AND UBIQUITOUS COMPUTING, 2009, 13 (02) :103-118
[83]  
Korula N. J., 2010, THESIS U ILLINOIS UR
[84]  
Labadi N, 2010, LECT NOTES COMPUT SC, V6239, P219, DOI 10.1007/978-3-642-15871-1_23
[85]   The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search [J].
Labadie, Nacima ;
Mansini, Renata ;
Melechovsky, Jan ;
Calvo, Roberto Wolfler .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 220 (01) :15-27
[86]   Hybridized evolutionary local search algorithm for the team orienteering problem with time windows [J].
Labadie, Nacima ;
Melechovsky, Jan ;
Calvo, Roberto Wolfler .
JOURNAL OF HEURISTICS, 2011, 17 (06) :729-753
[87]   2 EXACT ALGORITHMS FOR THE DISTANCE-CONSTRAINED VEHICLE-ROUTING PROBLEM [J].
LAPORTE, G ;
DESROCHERS, M ;
NOBERT, Y .
NETWORKS, 1984, 14 (01) :161-172
[88]   THE SELECTIVE TRAVELING SALESMAN PROBLEM [J].
LAPORTE, G ;
MARTELLO, S .
DISCRETE APPLIED MATHEMATICS, 1990, 26 (2-3) :193-207
[89]   ON THE DISTANCE CONSTRAINED VEHICLE-ROUTING PROBLEM [J].
LI, CL ;
SIMCHILEVI, D ;
DESROCHERS, M .
OPERATIONS RESEARCH, 1992, 40 (04) :790-799
[90]  
Li J, 2010, P IEEE INFOCOM, P3, DOI DOI 10.1109/ICIECS.2010.5678245